A Star (A*) Path Finding AI

Artificial Intelligence comes in many forms, and for game developers, Path-Finding is an important ability for making an NPC (Non-Playable Character) maneuver through terrain.  A* is a particularly easy way to approach it.  I’ll start with the algorithm in general, and then give a few valuable upgrades and how to apply them.

Finding the first route (there are 2)

To begin with, let's take a look at a possible game map:

White indicates spaces we can travel in.  Blue represents Water, and that we cannot cross it.  Red represents our target (B6).  Finally, our starting place is at Green (E5).  I’m also going to say that the NPC can move horizontally, vertically and diagonally.

Next, we start with two Arrays/Lists to manage the creation of the path.  These lists will contain Grid Positions, which I will call “Tiles”:

1) Possible Moves List – This lists all the possible moves the character can make.  It is not filled with all the white spaces on the map at the beginning, but gets filled over time.

2) Attempted Moves List – This is a list of possible moves that we have considered.

Initialize your list by adding the starting Tile to the Possible Moves List.  

Process Loop Part 1 of 2:

1) Get the Tile from the Possible Moves List that is closest to the target.

Distance = Math.Abs(X1-X2)+Math.Abs(Y1-Y2)

Select all Open in new window

Opposite = (Y1-Y2) * (Y1-Y2)
                      Adjacent = (X1-X2) * (X1-X2)
                      Distance = Math.SqRt(Opposite + Adjacent)

Select all Open in new window

2) Remove the closest Tile from Possible Moves List.  
3) Add that Tile to the Attempted Moves List.
4) For every white tile around it, that is not in the possible moves or attempted moves lists, Add it to the possible moves list.

5) The loop repeats until       

Now, before we move on to the second loop, Lets walk through how this one works.  When we go back to step 1, we need to find the shortest distance. I’ll give you the two closest.  (D4) and (F6)  First, I’ll show you two different equations for getting the distances.  The first one shows that there are 3 steps to take either way.  The second, which uses diagonals, shows that the first route has 1 step, while the other has 3.
 
I’ll use the technique that counts diagonals so we get a clear start here.  What I’ll do next, is move the closer tile (D4) to the Attempted Moves List, which was step 2 and 3.  Next, I’ll add the spaces around it to the available moves list.  I will now use those red marks to mark the tiles in the Attempted Moves List.
We can see it's heading in the wrong direction.  It needs to go to the left, not the right.  While our brains tend to have very strong spatial understanding, the computer has to look at every detail and measure each one individually.  So now, I’m going to fast forward another loop and see where we are.  I’ll include a few more images after that continue this route.
With this next one, we can see that even though we have moved a Tile from Possible Moves to the Attempted Moves List, we have added no new Possible moves, because there are no available white spaces around it.  
So far, we have been following a path.  When faced with a similar issue in real life, if the first side didn’t work, we would try going around the other way.  But the algorithm does not understand potential paths the way our spatially thinking brains can.  They need to look at each tile.  So the computer looks at the next closest piece it can find, which is our new target.
Now, I’ll skip ahead a bit.  Let's start filling in the blocks with these equations, just prior to it spilling over.  We can see that it has looked at a huge portion of the map.  But, we can also see that it has looked at all the closest possible values first.  (I should have used a smaller map, this number of dots is bothersome to fill in :)
Out of all the gray spaces left, I’ll say that my algorithm looks at the one closest to completing our root.  Now the algorithm will start being more efficient.
[A few more…]
Now we are right in front of the target and the end goal is in our Possible Moves List.  Now, we begin the second loop.  It’s the EXACT same as the first loop, except that now, we don’t look at the whole map.  We ONLY look at the list of Attempted moves.  We also start at the end this time and make our way back to the beginning.  So this next map removes all the unused pieces.
Next, we begin repeating the first loop, but starting from the target tile.  The first few are pretty easy, since it’s a straight path.
The next couple of spaces are pretty obvious, the closest direction to the starting tile is directly left.  
Next, it will choose to deviate from the straight line because the tile above and to the left is closer to the target than the tile to the left.
So now, I’ll just finish this off, with the last of the path.
Now, let’s look at this route over the original map.
You now have the route completed.  All you need to do is store the list of moves on the NPC, and apply whatever movement code and events to move to the next tile.  

But the array is reversed?  Wouldn’t it work better to start with the end and move to the beginning?

I choose this one on purpose, because I can use a List<> object in the code, and removing an item from the end does not cause it to recreate the internal array.  If I were to remove the tile from the first item in the list, it would have to recreate the array with every tile, wasting memory and resources.

Of course I could also have just used an index and counted down from tile to tile.  Either way is your choice.


Improvements:
1) Making a path a little less straight.  
2) Taking into account known dangers.
3) Taking into account Valuable interests.
4) Terrain Speeds.
5) Block Path.
Most Artificial Intelligences simply come down to weighing the value of each option and picking the most valuable.  A* weighs the value of each tile on the route, but instead making only one decision, it makes a large list of decisions, as in all the Way-Points.  Consider what other characteristics your game might take into account on path finding and then think about how you can influence this equation to make them work better in your game.