A* Pathfinding

By: Anthon Fredriksson / February 27, 2014 /
Program: Programming
/ No Comments

Today I am going to talk about path finding, more specifically A* path finding which is just one of many methods of doing path finding.

What is path finding?
Essentially, path finding is a technique for finding a way trough a bunch of obstacles from point A to point B.
In general you apply path finding with AI, but there are other cases that path finding is used as well.
What is A*?
A* is a heuristic graph based algorithm.
A grid of nodes is used to find the fastest way trough point A to point B.
Why do we need path finding?
Since we are making a stealth based game with guards that will be able to detect the player, we need them to know where you are and how to get to you.
All of our guards has a chase state and when they are in that state, they will run/walk to you and start shooting.

At first, our guards just went straight to you, not taking any obstacles like walls and furnaces into account.
This is just silly because our guard should not be able to walk trough walls like a ghost.
That is the reason we need path finding. Now we are making AI.

So how did we implement this?
So our guard must have some intelligence, not very much but some.
He need to know this:

  1. Where he is. (point A)
  2. Where the player is. (point B)
  3. If there are any obstacles. (walls, furnaces etc.)
  4. Where the obstacles are located
  5. Where he can walk (point 3 and 4).
The first thing I did was to figure out all the regions where the guard can walk trough.
I started of by figuring out where the guard could walk.
Green: Walk-able. Red: Not walk-able
The map itself is really just a big bunch of nodes. Here is an image explaining how the nodes are defined in the grid.
Now our nodes are not that small, but 32×32 pixels.

Okay lets continue.

Every node has to know some things about itself.
It has to know if it is walk-able, the position of the node in the grid, how far away is it from the goal relative to the start.

Lets say our map is 100×100 nodes large, which is equal to 10.000 nodes!
All these nodes are stored in a list.
Every time we need to execute path finding, we will have to go trough these nodes, but not all of them!
You see, this method of path finding called A* is simple and yet very fast but there are others that are slower and faster.
I wont explain the difference about them but all I can say that most of the methods differs in how many nodes you are checking. By checking I mean telling if this specific node is better to walk trough than an other node.

———————————————————————————————————-
———————————————————————————————————-

Enough about this now. Lets look on how we can implement this in logic.
The guard has to find a way to point B.
Its path contains of nodes. So we need to find out what nodes the guard should walk upon/to.
The guard already know where he is, hence the first node in his path.

Now he need to check all of its neighbors. (check image)

So we need to tell which neighbor we should walk to.
This is done by giving each node a specific value called F.
The F value is a sum of two other values called G and H.
The G value is the movement cost from start to current node.
The H value is the movement cost from end to current node. (check the image below)
But the thing is, we does not know the H value yet, we will just estimate it.
The H value is calculated by using a method called Manhattan distance. Manhattan method just counts the number of horizontal and vertical nodes remaining to reach point B.
To optimize, we use a list called the open list and the closed list.
The open list is a list of nodes that needs to be checked for neighbors.
The closed list is a list of nodes containing nodes we already checked.
Finally the guard will find the shortest path by repeating these simple steps:
  1. Get the node with the lowest F value from the open list. Lets call this node C.
  2. If C is equal to point B, compute the path by these steps:
    1. Iterating trough each nodes parent starting of by the parent of C and walk your way backwards until you reach point A.
    2. Reverse the path(because we want to start with point A).
    3. Now you’ve got your path ready.
  3. Remove C from the open list and add it to the closed list
  4. And for each neighbor N adjacent to C:
    • If N is in the closed list or is not walk-able: Ignore it
    • If N is not in the closed list and is walk-able
      • Set N’s parent to C
      • Compute F score
      • Add N to the open list

Conclusion:
Since I have made pathfinding before I knew how to implement it and it really went fast. 
The only troubles I had was to figure out where the guard could walk. But it was solved. Since we use a semi-grid based map it was not that troublesome I expected it to be. But that actually took more time than creating the actual algorithm.
Resources:
I followed this article on the A* algorithm(http://theory.stanford.edu/~amitp/GameProgramming/)
And here is the result. http://pastebin.com/4Xhk7DgM

About Anthon Fredriksson

2013 Programming
Tags: 2013, 5SD022, 5SD023, 5SD033