Pathfinding is an essential part of many games. Once implemented properly your game gets huge benefits from it.
Your enemies will get the ability to avoid walls and follow you.
I guess one reason for the massive amount of zombie games out there is that a zombie does not need pathfinding to seem realistic. Zombies are dumb by nature.
But we want smarter enemies!
So that is why i have written this tutorial for you.
I will show you how to implement the A* algorithm in Java and how to use it in your game.
You can find the full source code related to this post here.
The Theory of A*
Let me show you the concept behind the algorithm first so it’s easier for you to understand the code.
A* is an informed search sometimes called best-first algorithm. That means it searches all possible paths from a start to an end node and delivers always the cheapest (best) one.
Speaking of games that means that enemies which are equiped with the power of an A* algorithm can find the shortest way around walls following the player character.
The algorithm holds 2 lists of nodes. The closed and the open list. The closed list contains nodes which has been already expanded (visited, added to the path).
The open list contains nodes which are known but haven’t been expanded (visited) yet.
In the following i will use three different terms for costs. There is the move cost (G) which is basically the costs from the start node to the current evaluated node. Then we have the heuristic costs (H) which is basically the estimated costs (distance) from the current node to the goal. And there is the total costs (F) the sum of both.
Let’s see now step by step how A* works.
1. The pathfinding begins at a specific start node which is actually the first step (node) of the path.
2. It adds the node to the closed list, as it has been already evaluated.
2. It checks all the neighbors of the node.
3. If the current neighbor is already contained in the closedList ignore it.
4. It calculates the move costs of the path (G) from start to the current neighbor.
5. If the current neighbor isn’t already contained in the open list it gets added.
6. If the costs calculated in step 4 is bigger than the the move cost (G) of the neighbor already calculated before ignore it. (That means there is a path from which this neighbor can be reached cheaper).
7. Set the neighbors parent to the current step and recalculate all costs (G,H and F).
8. Get and then remove the best node (lowest F cost) from the open list and use it as the next step.
9. Continue doing steps 2-8 until the open list is empty or the destination node is reached.
10. Build the path reversely by starting at the destination and iterating through the parent nodes until the start node is reached.
A* is using heuristics to estimate the costs (distance) from each node to the goal. The quality of the resulting path is dependent on the heuristics.
To make A* always find the best path the following 2 conditions must be true.
1. The function used as A* heuristic should be always optimistic which means the estimated costs should always be lower than the real cost from a node to the goal.
2. In addition the heuristic should be monotonic that means that every successor node’s heuristic costs plus the actual costs to move from there from it’s parent must be bigger or equal than the heuristic costs of the parent.
h(k) <= step(k,k') + h(k')
If the used heuristic is not monotonic the shortest path is not guaranteed to be found.
The heuristic is a useful tool for game development since you can control behavior of the algorithm with it.
- The lower the heuristic costs are estimated the more nodes will be expanded by the algorithm which can have a bad impact on performance.
- If the estimation is very precise and almost always equal to the real costs of moving from a node to the goal it will be very fast because it won't expand other nodes except the ones contained in the shortest path.
- Choosing a heurstic which is not always optimistic (estimations are sometimes bigger than real costs) it's not always finding the shortest path. This can be used to give the enemies's movement some variation.
That should be enough of the boring theoretical part let's dive into some code now!
The tile class: A node on the path
Before we start coding the actual algorithm we must implement a class for the nodes.
This A* implementation is suited for a tile based game. So a tile represents a node of our map which will be used by the algorithm. The tile class itself includes attributes for the position, move costs and heuristic costs aswell as constants for the size and the origin and two lists for the surrounding neighbor tiles.
Lets take a look on the important part of the tile class namely the cost calculations.
calcCostH calculates the heuristic costs. Heuristic means basically that the costs needed to reach the goal are estimated by the heuristic function provided to the algorithm. In our case we use a basic manhattan distance calculation because we don't want our algorithm to check diagonal neighbors. The name manhattan distance originates of the street layout of new york city which has also almost no diagonal streets.
moveCost calculates the costs actually needed to walk up to this tile. So it is basically the full cost from the start to the current tile. Because we want to avoid walls in our example we multiply the costs of this step by the factor 10 to make it really unattractive for the algorithm to choose this tile as a component of the path.
calcCostF does nothing more than sum up both costs the heuristic costs and the actual move costs.
I only show the cost calculations in this post because i don't want to annoy you with all the getters and setters. To see the full source code click on the link at the end of this post. I created a little github repository which can be cloned and runs a little demo out of the box.
The A* algorithm in Java
It's finally time to really go to the bone of A* as we will now take a look at the pathfinding algorithm itself.
The constructor: Business as usual
Nothing fancy awaits us in the constructor.
Just 3 important things to mention at this point.
allTiles contains every single tile of our map.
closed the algorithm will add the tiles already evaluated to this list.
open the algorithm will add tiles to list which he discovers and have not been expanded.
Method for receiving the best tile from openlist
Our algorithm needs to get the best tile from the open list to add it to the path. The following method does exactly that: It returns the tile with the lowest F value.
The core method of the A* algorithm
getPath brings it all together. It has 2 parameters: The start tile and the destination tile. It computes the best path between them both and returns it as an ArrayList of tiles.
Let's have a look at the quite lengthy method now!
I think the code comments already explain the method pretty good.
Get the full source code including a demo
It includes a little demo. The demo shows a simple randomly generated game world with 2 different tiles, floor and wall tiles. By clicking a tile and then click another the demo calculates the path between both and displays it.
How to use A* for enemy pathfinding in your own game
Once you have integrated the A* code into your project it is quite simple to make enemies moving along a path.
1. Give each enemy a path field which is basically an
as well as a field for the current tile and one for the next step on the path.
2. Implement a method which checks if the enemy has taken a step. Do that by checking if the center of the enemy polygon is inside of the current tile or in one of its neighbors. If the latter is true set the current tile to that tile and pull the next step out of the path.
3. Calculate the move direction by building a vector from step to the current tile. Normalize this vector.
4. Multiply this vector by the delta time of the current frame and by the velocity of the enemy.
5. Translate the enemy polygon by the resulting vector.
You can make your game calculating a new path for each enemy once the goal is reached. That would be suitable for strategy games for example.
Action games where the enemies should follow the player require the path to be recalculated periodically. It is a good idea to randomize this period to make calculations spread across frames for performance reasons.
Now you know how to implement A* in Java. You can start now and create smart enemies that follow the player character even around walls.
Or what about a navigation system app what is something A* is also usable for? 😀
You can freely use the code and implement it into your own projects. 😉
If you have any questions just leave me a comment i will help you as soon as possible.