Coding: A* Pathfinding
Here is the last part of Conformity's Change development. Sadly it wasn't implemented in the game because it took more time and was way harder to do than expected.
Since Conformity's Change is a story, not a game it's better to avoid any possible way for loosing the game. The algorithm in our case will be used in the Maze. If the player at some point get lost and would be able to press a key to show him the way out of the maze. I will show the work on the maze in separate project, not in the game one just to make the rendering faster and to give a clear view to what i am doing.
The black path show the way to get out of the maze.
Since i'm doing this post after i have finished the project the code will be shown in after-optimization level, but i will explain the changes i made.
First of all - setting up the scene,
After arranging the walls i had to create another layer mask and call it Unwalkable. All of the walls must be part of this layer.
Here is the time to explain how A* algorithm works. We create a grid of nodes. Each node has two values - hCost and gCost which are the distance from the starting point and the distance to the end point. The result (fCost) is the sum of these two. The algorithm checks the Node with the lowest value, until at some point reaches the end.
All of the scripts below should be attached to an object called something like A* in the hierarchy First thing to do is to create the nodes.
This class does not need to inherit MonoDevelop. The Heap class that Node.cs inherits is used for optimizing the pathfinding algorithm. We create the dimensions of the nodes in the constructor. And create the fCost function. Next thing i need to do is to create the grid.
In the beginning of the script i define variables and set the dimensions of the grid which are calculated this way: nodeDiameter = nodeRadius * 2;
gridSizeX = Mathf.RoundToInt(gridWorldSize.x / nodeDiameter);
gridSizeY = Mathf.RoundToInt(gridWorldSize.y / nodeDiameter);
CreateGrid();
All of this happens in the start function. I also define max size getter which is calculated as X * Y.
After that is the function for creating the grid. The Class Grid inherits Node
On these three screenshots i have displayed the functions CreateGrid(), GetNeighbours(), NodeFromWorldPoint and part of the Display function which allow us to see the path found. These
functions are obvious for what they are used for. It's mainly calculations inside them which returns cordinates.
And now i will explain what the heat does. First i will show a snippet from the pathfinding in the beginning and then one after optimizing.
The slowest part of the pathfinding before was this while here:
Each iteration the algorithm has to go trough the entire open set to find the Node with the lowest code. The way i will optimize this is quite similar to binary tree. The one simple rule is that every parent has fCost lower than the fCost of it's children. Each node will have an index. The great thing about heap is that if we want to add a new element to the list all we have to do is check if the value of the new element is bigger than it's parent and if yes - swap them. This repeats until the new value has gone in the right position. This whole While loop will be replaced with the two commented lines after the heap is done.
// Below i will put a pastebin link to the scrpit because taking screenshots of it it will take too much space and time.
HEAP:
http://pastebin.com/FuwUwDmK
This class contains the following functions:
Add(): Used to add elements to the heap
RemoveFirst(): Removes the first item of the heap
UpdateItem(): Update the "binary tree"
Count(): Returns the number of elements
Contains(): Returns boolean if the element is already in
SortDown(): Sorting Down
SortUp(): Sorting Up
Swap(): Swap two elements
and the template iHeapItem(): get & set for the index
Last and most important - Pathfinding.cs
// Below i will put a pastebin link to the scrpit because taking screenshots of it it will take too much space and time.
http://pastebin.com/yf81Em3k
The class contains the following functions:
Awake(): In the awake function we find the Grid component and make an instance of it
Update(): If button is pressed the algorithm is started
FindPath(): The most complicated part. First i take the positions of the two nodes i need and create a heap of nodes called OpenSet which will contains all of the unchecked nodes and one called ClosedSet which will contain nodes that have been tried already. First we add the starting node to get the loop iterating. Once i did that the loop start iterating while the nodes in the openSet are more than 0. If the current node is equal to the final one the loops exits. If not it starts looking at it's neighbours for their values and if they are walkable. Eventually it finds the exit point.
RetracePath(): This function is used to get back trough the path so it can be displayed.
GetDistance(): Calculating the distance between two points with mathematical formula.
And this is it. Eventually in implementation in the game this will spawn an object in front of the player and lead him to the exit of the maze.
