Creating your first 2D game with A* Algorithm

Moving from point A to point B is the prime requirement for many games—whether it is a strategic tactic-based RPG (role-playing game) like Warcraft III or one that’s as simple as Snakes and Ladders. The source-to-destination navigation sometimes requires more intelligence from your character than you believe,it needs to find the path with ease. You can’t have your characters walking through a wall or bumping into a car while playing, can you?

This is where pathfinding algorithms are used. Pathfinding is the basic building block for most games. Players have to reach a destination by moving around blocks, cars, rivers, and prisons. The algorithm ensures that the character not only avoids the obstacles but also gets to the destination by using the shortest path.

Games like Warcraft III use the A* pathfinding algorithm, where the protagonist is not only expected to reach his destination by the shortest path. But also move around the castles, not get in through the huts, dungeon, or walk through a dragon on its way.

A* algorithm (Pronounced A-star algorithm)

The A* algorithm is the fastest graph search algorithm that finds the path that costs the least from source node to goal node. (A node can be hexagon, square or circle, etc.)

In the gaming world, a node graph is a map of your gaming world, and the path that costs the least is the shortest path; A* traverses a node graph and finds the path that costs the least

A* algorithm has properties of both Dijkstra and Best-first search. Unlike DFS and BFS, the A* algorithm selects the node which looks most promising instead of guessing the next node.

The cost function

The cost of node F is calculated as:

F=G+H

  • G is the cost that is required to reach a particular node from the source node.
  • H often termed the Heuristic Value (a heuristic, informally, is like an algorithm, which helps us determine the answer but not in a definite series of steps).It is the estimated cost from one square on the grid to the other square, which is the goal on the grid. H being heuristic,can never be perfect and is usually based on assumptions.

Here we implemented the Euclidean distance for the cost function. The Manhattan and the Chebyshev functions are also shown in case required.

Let’s look at the following example:

Traversing A* algorithm

Assume that the graph or table above is a game grid where our protagonist needs to move from the source node of the grid to the goal node.

We have implemented the node as coordinates depending on the type of object that is passed. The attributes that it will have are the position, distance, priority and the possible directions that the node object can move. These attributes are managed through the updatePriority and nextMove methods. The implementation is shown below. You might notice that the cost function shown above is the estimate method of the node object.

Let’s consider that every block to the left, right, top, and bottom of the selected (parent) node is at a distance of 1 unit. That means that each block is at a diagonal distance of √2, which is equal to 1.4.

To make things easier, multiply each value by 10, thereby converting the distance to 10 and 14 for adjacent and diagonal nodes, respectively.

Let’s make 2 lists of open and closed nodes. Any node that is selected for the path is moved to the closed node list. Any node that is not selected is considered to be an open node.

How to traverse in A* algorithm

Assume that our protagonist is at the location source. Every block surrounding the location source has a certain F cost, which is the obtained by summing G (which is the distance from the source node) and H (which is the distance from the goal node).

For example, a block that is diagonally opposite to the source and marked in red would have a G value of 14 (1.4 * 10), an H value of 10 (2*1.4*10 +10), and an F value of 52. You can compute the values for all other blocks similarly.

After we have the cost of all the blocks, select the block which has the lowest cost. In this case, F=52 and mark it as closed.

Repeat the entire process with all the open nodes (nodes which are not selected), and select the block with the lowest F value as you head towards your goal.

Once you reach the goal, the path traversed is the lowest possible path for a given matrix. This process has been represented in red and purple for the problem above.

However, in a game, the path is not so simple. It is usually filled with hurdles and areas that the character is not supposed to walk in.

How A* algorithm works

Assume that, in a game, the section in black is the area which cannot be traversed by the player. We will use the same approach that we used in the previous example while keeping in mind that there is now a black node that the player cannot traverse.

Select the Source node and calculate the F cost of all its surrounding nodes (F=G+H). Now select the node with the smallest value, which in this case is 48. Once you select the node with the smallest value, find the F values of all its surrounding nodes. The process of selecting the smallest node continues.

But what if two nodes have the same values, like F=48, in the table above?

In such cases, you must select any one of the nodes with a similar F value and proceed with finding F values of its surrounding nodes.

Select the node with the smallest F value and carry on along the path. You will soon reach the goal node by the shortest path possible.

Summary of A * Algorithm

  1. Select the starting point and put it in the open list.
  2. Find the F cost to the current node.
  3. Mark it in the closed list.
  4. For each of the 8 nodes adjacent to the current node, do the following:
    • If the node is in the closed list or cannot be walked through, then ignore it.
    • If it is not open, then put it on the open list and find the G, H, and F values for it.
    • If it is in the open list, then check if the path has a better cost and make it the parent node.
  5. Stop when your target node is marked as closed, or there are no more nodes to be marked as open.

At this point, you should have a decent conceptual understanding of how the A* pathfinding algorithm can be adapted to a platform. This article is not a definitive work on the subject, rather it is a beginner’s guide of sorts.

Remember that A* only finds the most optimal path. The graph search is only one piece of the puzzle. A* does not handle things like object movement, map changes, etc.

Why don't you create your own 2D game with movement and hone your skills as your game evolves with better algorithms? 

If you enjoy algorithms as much as I do, read my other article on the Elo rating algorithm.

PS: For code enthusiasts, here is the python code to the A* algorithm.

About the Author

Arpit Mishra
Avid book reading advocate. Hardcore travel nerd. Technology freak. Follow me on LinkedIn to get more Insights on Tech Recruitment.
Share