Pathfinding

This is a demonstration of pathfinding, where I have created a 30 X 30 grid on which I perform pathfinding through A* algorithm. There are many other ways like Dijkstra’s algorithm, but A* is very optimal. I select a starting node, an ending node and then the algorithm finds the shortest path. You can also draw walls on the map, which are blocked and then the algorithm adjusts accordingly to find the path. I have made this is Unity 5, you can find the code here at GitHub.

Demo:

 

To give an brief idea how this works: I have made two lists: OpenList and ClosedList. The openlist works like a shoping cart. The open list has the nodes you find along the path, which may or may not be on the path. The nodes that are on the path get added to the closed list, which adds nodes with their ‘parent’ nodes which eventually helps us trace a path.

So the next question must be: which nodes are supposed to be added to the list? To determine this we follow the formula:

F = G+H

where G = movement cost from starting point to given node on the grid

             H = estimated cost to move from that node to ending node

We calculate H using the famous Manhattan method here, which almost always gives us the shortest path.

Here I calculate the FGH values.

capture1capture2

Here I calculate the start and end node.

capture3

This is where I get all the neighbours of a given node, and add them to a list depending on if diagonal neighbours are to be included or not.

capture6

Here I calculate the cost so far for a node, which depends on the g value of all its parents summed up. In the BackTrace Function I calculate the shortest path through the closed list, back tacking through parents of parents till the start node.

capture5

The update function.

capture4capture

 

Advertisements

Blog at WordPress.com.

Up ↑

%d bloggers like this: