The A* Pathfinding Algorithm

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:

grid1Right away one may think this is easy enough; however, how do we tell the computer to get from the coordinates (0,0) to (6,6)?

In this example, we use the simple slope formula:Slope_formula_2 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:

grid2_wall

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 Formula

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.

grid1_with_numbers

 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.

Scoring

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.

grid3_circle

The program will give each cell 3 sets of values that will represent and assign the F, G, and H variables a numeric value.

grid4_fgh

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:

grid5_h

 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.

grid6_g

 The next step will add the G and H values, and assign it to the F (total cost) variable:

grid7_f

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.

grid8

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.)

grid9

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.

grid10

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.

grid11

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.

grid12

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.

 

grid13

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.

grid14

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.

grid15

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.

Astar_progress_animation

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.

Satellite Hunt:
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.

Survival Shooter:
A game that can be found on Unity Tutorial.  Here you notice how the NPCs will follow you around, avoiding obstacles along the way.

And the Winner Is…

“Success is not about winning but it’s about learning after the game. Life doesn’t end if you win but a start for a new challenge of a harder fight.” 

In every game there is a challenge…and Egg Defender faced another competition head on! For those who have followed our story, the first competition took place during Georgia Game Jam in 2013 where the Egg Defender team was one of five finalists and progressed on to compete at SiegeCon where we were first runner-up!

This past year, we were invited to compete in another CDC partner event, GameOn! Challenge, where we competed with twelve other competition teams.

The goal of the Game On! Challenge is to support the development of an original and innovative game app for smartphones.  The game app will educate young people about HIV and STD prevention. The target population for this game is adolescents aged 13 to 17 years or young adults aged 18 to 24 years.  

Although we did not place with first or second, we were one of the THREE Honorable Mentions and appreciate how much this competition brought our group together as we faced the next challenge of marketing and producing the game for the mobile application and desktop markets.

We are glad each of you is along with us in this journey and we encourage you to follow the latest updates on the Egg Defender Facebook Page  and here on the ZapMil blog.

See you in the WINNERS CIRCLE…

Unweaving the Web: How to Dissect the World of Web Design

My website is driving me WACKY!

We understand. In a world of web based design and technology, your website is the doorstep into your organization, your brand, and your identity. Unfortunately for many, you may be wearing out your World Wide Web welcome mat.

What are some of the biggest WEB WOES?

  • Busy or complicated layout

Instead of being a busy bee, your web is displaying the whole hive.  While this may serve and share all your solutions, your visitors become more overwhelmed and confused and unfortunately will click OFF your page instead of clicking through.  Streamline and Simplify.  Let our team of experts give you a winning design which attracts more clients to the honey of your business.

  • Pop-ups, flash, and ads – oh my!

We’ve all experienced the annoying buzz of the ever present pop-up, distracting flash, or misplaced ad when visiting a website.  Eliminate the Vegas flash and opt instead for influential advertising. Instead of driving your clients away, learn techniques from our team to help draw in and bring your client to the source of your business, your website.

  • Small print that’s hard to read

When you bring your client to your webpage you don’t want their first thought to be an immediate scheduling of a trip to the optometrist.  Your content should be accessible, readable, and BOLD. Don’t fit massive text in a smaller space, your client may miss important influential keys to your business and organization’s accomplishments.  Our web designers will guide you with content placement and display.  No need for new glasses to view your site!

  • Standard web design

We all don’t want to be THAT web page.  The one where people think you literally changed the content from the original template.  Instead of tackling it on your own, let our team customize your page so it is unique and special – not a cookie cutter!

While these are just a few of the biggest web woes, we know there are many more.  Our web design team is ready to consult with you and make sure you are upgraded, updated, and uncomplicated!