The problem set I had to solve is available in this PDF as Problem Set 8-2 Video Game Design.

In short the problem is that there is a Game with Rooms and Corridors connecting those rooms. Each Room will have either a monster or a life potion. Encountering the monster decreases life and drinking life potion increases life. The objective of the algorithm was to find the minimum life points required to start the Game.

I used Floyd and Warshall Algorithm as the base to solve the problem and modified it to get the output. I had the following assumptions in place;

- Maximum life points a player can have is 100. If a maze requires more than 100 at the start of the maze to finish the maze that maze is not r-admissible.
- The mazes will only have a maximum of 100 rooms or less. This is because the player will be frustrated to finish the maze if it is longer than that.
- From start room there is at least two paths to the destination.

Following are the two part flow chart diagrams of the algorithm.

Implementation of the algorithm is seen below;

The Maze is a Adjacency Matrix implementation with Two Dimensional Double array. I used the following maze designs to test the algorithm.

Many couldn't finish this task in my batch and I was awarded highest marks (91) for the coursework.

Implementation of the algorithm is seen below;

```
public double RAdmissible() {
```

if (maze != null) {

// Variable to store the result

double r = 0d;

// Constant to store No of vertices in the Maze

final int MAZE_LENGTH = maze.getSize();

// Variable to store Adjacency Matrix of the Maze

double matrix[][] = maze.getAdjacencyMatrix();

// Variable to store Predecessor of the Longest path

double pred[][] = new double[MAZE_LENGTH][MAZE_LENGTH];

/*

*

* If there is a positive cycle

* then with minimum of r = 1 maze is navigable

* Else have to find the least costly path from start to end of the maze

*

*

*/

// Variable to store whether this maze contains a positive cycle

boolean positiveCycle = false;

/*

* Modified version of Floyd-Warshall Algorithm. Runs at O(N^3).

* This is used to find the least cost path from start to finish

* and to find whether there are positive cycles in the maze.

*/

for (int k = 0; k < MAZE_LENGTH && !positiveCycle; k++) {

for (int i = 0; i < MAZE_LENGTH && !positiveCycle; i++) {

for (int j = 0; j < MAZE_LENGTH && !positiveCycle; j++) { if (matrix[k][j] != Double.NEGATIVE_INFINITY && matrix[i][k] + matrix[k][j] > matrix[i][j]) {

// Assigning the new least cost path

matrix[i][j] = matrix[i][k] + matrix[k][j];

// Assigning the new predecessor

pred[i][j] = k;

/*

* If i == j then it is a cycle.

* But we have to determine whether it is a positive cycle.

* For that we check whether the new path is not Negative Infinity and it is positive.

*/

if (i == j && matrix[i][j] != Double.NEGATIVE_INFINITY && matrix[i][j] > 0) {

positiveCycle = true;

}

}

}

}

// Minimum r is the cost to go from start to finish

double minimumR = matrix[0][MAZE_LENGTH - 1];

// If Minimum r is Negative Infinity then cost from start to next to finish is taken

minimumR = minimumR == Double.NEGATIVE_INFINITY ? matrix[0][MAZE_LENGTH - 2] : minimumR;

/*

* If a positive cycle is available then Minimum r is 1

* This is because life points necessary to safely navigate

* the maze can be gained by going through the positive cycle.

*

* If no positive cycle is found then

* If Minimum r is Negative or Zero the Minimum r should be

* one greater than the absolute value of Minimum r.

*

* If Minimum r is Positive then

* Minimum r is 1 this is because there is safe path

* from start to end where the player's lifepoints will

* never become 0 or less.

*

*/

minimumR = positiveCycle ? 1.0 : minimumR <= 0 ? abs(minimumR) + 1.0 : 1.0; /*

* If Minimum r is greater than 100 then * r is 0 which means there is no safe path in the maze. *

* Note : This is based on the assumption that a player can have a maximum of * 100 life points.

*/

r = minimumR > 100 ? 0 : minimumR;

}

// Return the Minimum r

return r;

} else {

throw new IllegalStateException("Maze is invalid");

}

}

The Maze is a Adjacency Matrix implementation with Two Dimensional Double array. I used the following maze designs to test the algorithm.

Many couldn't finish this task in my batch and I was awarded highest marks (91) for the coursework.

## 1 comment:

Post a Comment