You have to admit, technology is pretty awesome!
Recent advances in computer graphics and hardware are creating compelling and visually immersive game environments for today’s programmers and game developers. One favorite technique used to help captivate the player is Artificial Intelligence (AI). AI ranges from simple applications within a text-based game (scripted actions/reactions by the computer) to complex system programming, such as the A* pathfinding algorithm, showcasing the illusion of intelligence in a computer.
Before exploring how the A* Pathfinding works, let’s first delve into the basics of AI pathfinding through structure and example. While many articles may take a more technical and code example approach, this article is intended to break down and explain how the A* algorithm works in the code. As we delve into the algorithm, one thing to keep in mind is that a computer ALWAYS knows your location, and the locations of all Non-Player Characters (NPCs). The zombie which blindly walks past you hiding in a dark corner is how the programmer set it up, not clever intuitive personal gaming talent of picking a perfect hiding spot. Alternatively, perhaps you have found that perfect sniping spot, and all the soldiers in the distance can’t see you, making easy head shots in your scope. Sorry. Actually, the computer knows where you are at all times.
The programmer(s) are responsible for setting up rules and conditions for the NPCs. Called “states,” these regulations support the actions and plot driven sequences of the gaming environment. As a scenario example, the predator walks around aimlessly – or a “calm state.” When the player is close enough to the predator and either makes a sound, or creates any condition that will trigger a change, this “calm state” becomes a “chase state.” As the predator begins to give chase, the player will run seeking to gain enough distance for the predator to hasten its action, or give up. The “chase state” transitions to a “give up” state, directing the NPC to return to the area it was patrolling and revert to a “calm state.”
State of a Game
Once you understand the basic action structure or “state” of a game, the interaction of the player and predator is easier to comprehend. Simply, the a computer always knows the location of the player; therefore, it’s the program’s job to tell the predator to move its location to the player’s location. How does this work? Visualize looking down at an empty room. The player stands in one corner, and the predator (the computer) stands in the other corner. In the first diagram below, one can imagine the player (represented by an “P”) and the computer (represented by an “C”) trying to reach the player on a simple 2D 6×6 grid:
In this example, we use the simple slope formula: a programmer can use this formula to tell the program to “walk” along the coordinates of (0,0)(2,2)(3,3)(4,4)(5,5)(6,6) to reach the target, or the player. You may remember this formula from basic math using the “rise over run” method to find a slope. (Don’t worry, we won’t get into too much complex mathematics, remember the slope formula, and we’ll rely on more complicated math for the computer to solve.) A good example of a simple line can be read here on our Bresenham’s Line article.
Games of today are much more complex and entertaining. Many times the predator will not be chasing the player in an empty room like the example above. In most cases there will be a wall, a river, a mountain, or some kind of object in the way of allowing the predator a straight path to the player. In the next example, we can imagine there is a simple wall in the way:
In this situation, the slope formula will not be of much use, as there is an object blocking the path. This is where the A* pathfinding algorithm can be a useful tool for programmers and game developers.
The A* has a deceivingly simple math formula: F = G+H | F = Total Cost, G = Cost, H = Heuristic (or, “best guess”). From this formula, we can imagine that each cell (or block) has a cost/value. In the first example without obstacles, the total cost would be 6 due to the number of cells the predator would have to step through in order to reach the player.
In the second example with a wall in the way, the total cost will be much more complicated to figure out at a glance. Through steps and using the A* algorithm in the programming, the computer can process the formula at very fast speeds giving the computer a more intelligent-like behavior.
The first step will have the program search the surrounding cells, calculating values. Within the program, a code must be given so that it will start its search at the same cell every time is starts a search. In this example, the cell to the right will be the first cell searched. From there, the search will continue in a clockwise direction.
The program will give each cell 3 sets of values that will represent and assign the F, G, and H variables a numeric value.
From here, the program will give the movement of each cell a score of 10 for an adjacent cell (top, right, bottom, left,) a score of 14 for a cell located at a diagonal location, and assign those values to the H (best guess) value:
One can use any number for the values, but it has been found that multiplying numbers by 10 will help avoid any floating point numbers (EG – 1.400).
Next, the program will add up the cells required to move across in order to reach its’ target (by the rise over run method, multiply that value by 10, and assign that value to the G (cost) value.
The next step will add the G and H values, and assign it to the F (total cost) variable:
Now that the program has some values assigned to each cell, these values need to be put into 2 lists for record keeping and tracking: an “open list” and a “closed list.” By using opened and closed lists, the computer will be able to go through the process of pathfinding faster by eliminating cells that will be unnecessary to move through.
In the next image, the cell with the lowest value will be place in the opened list (marked in green) while the remaining cells are place in the closed list (marked in red). Since there is a wall blocking movement in the cells to the top right and right, the cell valued at 40 is also placed in the closed list because any other cell has either already been searched, or does not hold a lower value.
At this point, the F variable (total cost) needs to be updated by adding the previous values from before, using the same method we started with (giving 10 to straight directions, and 14 to diagonal directions.)
In the next example, all cells surrounding the previously searched cells will go through the same steps as before, adding their total costs, costs and heuristic values accordingly.
Through this search, the program finds 74 as the lowest total cost value, thus causing an update to the opened list (marked in yellow). Remember that our search started with the cell to the right. This causes the top cells with the same values as the bottom cells to remain in the closed list.
This time, the opened and closed lists are updated, and the search continues. The red represents closed lists, yellow represents old opened list now closed, green represents current open list.
This searching process continues until the target is reached. Once the path has been determined, the lowest values are traced backwards, telling the computer it is safe to move in that direction. In the next example, the yellow represents cells that were, at one point, placed into the opened list. The green represents the lowest total valued cell determined at each point of the search. The arrows show the path best suited for the computer to take.
Other Uses for A*
Through the use of A*, the programmer is not just limited to walls. This same method can be applied to the program when running into a dead end. Depending how smart the programmer wants to make the computer seem, the predator could be given protocols on whether or not to search any halls with dead ends, or to pursue and move into the hall with a dead end to see if the player can be found in there or not.
A programmer can also give “terrain costs” to each cell, prioritizing a path to be taken by the computer. For example, assume the wall was a river of acid that goes all the way across the room with a bridge at one end. Giving those cells a higher cost to go through could make the computer decide to choose a faster or safer path.
Perhaps there are items within the game that will assist the predator with its chase. A programmer could assign values to each cell, perhaps representing downhill terrain, or turbo boosts. In this example, a blue line represents a safe and fast route, where the red line is risky (at a higher cost) but much faster.
With the computing power of today, these calculations and movements are done at incredible speeds, much faster than the human eye and brain can comprehend. Even this animation example is very slow when comparing how fast the computer works out the mathematics in real-time.
This allows a game developer to create scenarios of their choosing. This also allows the player to keep moving around, while the computer constantly goes through the A* algorithm seeking a path to the player.
Level the Possibilities
The possibilities are endless how a game programmer can assign values and rules to their AI. For example, imagine you have an army out to destroy another player’s castle. You have tanks, bombers, soldiers, etc. Each character has their own assignments of priority when you send them out to attack. The tanks are assigned to prioritize any defenses, the bombers are assigned to blow up any walls, or obstacles in the way, soldiers are assigned to attack everything else. Through the use of the A* algorithm, the terrain values can be set, and changed within live gameplay. Your tanks are trying to get to a defensive object, so they move to the closest one, and start shooting a wall in the way. You send in a bomber to blow open a hole in the wall. This bomber blows open a hole that is a short distance away from the tanks location, so the tanks A* Pathfinding has now determined that the lower cost of the terrain value has been changed, thus the tanks change their direction. Although the direction the tanks original path may be shorter, through the change in terrain values, the A* algorithm has determined a better path to the objective.
Now, imagine this same example and some mystical “wall jumping spell” has been used over an area. Even if the tanks have a shorter path to their objective, the terrain value that has been placed for the wall jumping spell forces the tanks to take the lower cost path, rather than attacking a target that may be closer. So, the A* is great, but not perfect!
Perfection…Or Less Than Perfect
To highlight an example of when A* may be less than perfect, a programmer may have to give a terrain value a slightly higher value (like a step up on the floor) and the AI predator will determine it is not a crossable path to take. Perhaps there is a creek the player can run through, however, the AI calculates the creek as too high of a cost to cross and is forced to take a much longer route to find a bridge before reaching the player. Through play testing, it is possible to use A* in troubleshooting terrain flaws and alternate choices (such as the value of the before mentioned creek/floor.) In the end, it’s up to the programmers and game developers to decide when the A* algorithm is good use for AI intelligent behavior.
Would you like to see some examples and play a game?
Check out the following games found here on the ZapMil website.
Observe how the “Planet X’s” will follow you around if you get too close. This shows an example of the “states” mentioned at the beginning of this article. The Planet X’s start in a “stop” state, where they are not moving at all. One you get close enough to them, their state changes to “chase” and the A* algorithm is put into action with obstacle avoidance (by avoiding the walls) and choosing the shortest path available to reach you. Once you gain enough distance, the Planet X’s will return to a “stop” state in their current location.