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.
a. At the beginning, it is only 1, your starting position.
b. If your NPC can only move Vertically and Horizontally, this can simply be adding distance between X coordinates to the distance between Y coordinates.
Distance = Math.Abs(X1-X2)+Math.Abs(Y1-Y2)
c. If your NPC can move diagonally as well, then you’ll probably want to use a Pythagorean Distance Formula.
Opposite = (Y1-Y2) * (Y1-Y2)
Adjacent = (X1-X2) * (X1-X2)
Distance = Math.SqRt(Opposite + Adjacent)
d. If a few are the same distance, it doesn’t really matter which one you pick.
2) Remove the closest Tile from Possible Moves List.
a. Since we are about to consider this move, it will no longer by available to look at later
3) Add that Tile to the Attempted Moves List.
a. We will need to know which spaces we have considered.
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.
a. This increases our possible list of spaces. Below, these new spaces are marked as gray.
b. We can see that (D4), (E4), (F4), (F5) and (F6) are all Possible moves to make.
c. If the target tile ends up in our Possible Moves List, This loop is done.
5) The loop repeats until
a. It reaches the target
i. Then it moves on to Process Loop Part 2 because it found that the route is possible.
b. - OR - The target was never reached.
i. Then it cancels and alerts the game engine that the root is not possible.
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.
1) Making a path a little less straight.
a. This can relate to Making AI’s Dumber or Smarter.
b. It can also relate to making a group of random NPC’s not appear to be marching single file.
c. This is accomplished by messing with the distance equation. Add a random value to the distance. That way when you compare tile distance, you may end up with different tiles picked, which could mean the difference of right and left to go around a building.
2) Taking into account known dangers.
a. Some tiles may have enemies.
b. You can deal with that by accounting for any enemies with in X distance of the tile you are measuring. If an enemy is close by, add more to the value of how far away the target is. That way, it will be less likely to take that route. The closer the tile comes to the enemy, the more it should add.
3) Taking into account Valuable interests.
a. Suppose you have supplies that NPC’s can pick up that will help you. Like in StarCraft, how there are often supply drop offs, that if any of your characters walk over, you get the resources.
b. You can accomplish this, by looking at any pieces with bonus resources, and the closer you are to one, the more it will subtract from the estimated distance.
4) Terrain Speeds.
a. Some games have NPC’s move at different speeds depending on the terrain. For instance Sand vs. Road.
b. This can be accomplished by adding more to the distance, and consider it more a measurement of time. If the tile is on sand, Add 2 to the distance/time. If it is road, add 0. It would be better if you could add exact speed differences between the materials.
5) Block Path.
a. If a character’s path is blocked, Re-run the A* against their path.
b. If a large group of characters are travelling together, Have the blocked character try a tile to the side of the blocked tile, but still heading in the general direction. If it gets forced more than 1 or 2 spaces away from its route, have it rerun the A* to set a new route.
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.