A* Pathfinding
Over the past years I’ve made many itterations of the A* pathfinding algorithm, Each time trying to optimize it even further. This is something I like to do because It gives you more freedom of how it should work compared to build in navmesh.
To learn how to make A* I first started with the Dijkstra method. After that worked and I fully understanded it I tackled A*. And I kept Upgrading it by going from 2D to 3D, adding multithreading and eventually looking into different ways to optimize the grid to make the pathfinding faster.
Grid Generation and walkable tiles
I start by generating a grid of nodes in the area that was assigned. when adding a grid it checks if there is collision on the given spot. The nodes are stored in a list for easy access.
When looking for the walkable tiles it will go through each node and check if a given amount of nodes above the node is not obstructed. When it is the node will be marked as markable so the pathfinding will only go through these nodes.
Calculation for final path
When calculating the path you need to give 2 positions with it, the starting position and the targeted position.
the code will find the closest walkable node for both points.
The code will make the starting node the current node. You will use the current node to get the next node that will be checked by finding the surrounding nodes. When it has a list of all the surrounding node the code will add it to the list as reachable points and give the node his costs. the costs are the amount of steps it took to get there(ArrivalCost) and the distance between the node and the targeted node(distanceCost).
The code will then look for the next current node. It will look for the node with the lowest total cost(arrivalCost + distanceCost) that is in the reachable points. The new current node will be added to a separate list of final nodes so it won’t be checked again.
When the current node is is the same as the targeted node the loop will stop and it will calculate the final path
Getting the final path
When generating a final path the code will get the final nodes, the first in the list is the starting node and the last in the list is the targeted node. It will start at the targeted node and get all the nodes that are around it. It will take the node with the lowest arrival cost and take that as the current node and add it to the list of the final path.
When all the path nodes are added and it is at the starting node the code will inverse the node list so it won’t go backwards and return it.
Optimization I have tried
In other projects that I have made an A* pathfinding I made multiple types of optimizations.
The most basic optimization is to use multithreading to calculate the paths outside of the main gameplay thread.
Besides that the biggest and most effecient optimization is to change the grid in order to make it easier to go through the tiles.
For a 3D fps game I made A* and generated the grid the same way as above but in order to make it smaller I went through each cluster of tiles to check if i could combine then in order to for example combine 9 tiles in to 1. That way instead of a 200 tile grid it could become a 90 tile grid. Making it easier to find the destination
For a different game I used a different technique. The game didn’t have any overlapping ground or stairs. With that in mind I changed the A* into 2 overlapping pathfindings. Between each path I made key points. those key points would become it’s own grid in which I could calculate what paths it needed to pass through. Between each key point I generated a diffrent grid path. So in short I had a different grid on each path between each key point. By first calculating through the keypoints I could only use the grids that were required skipping most of the tiles that weren’t required.
(These optimization were made for different games outside of this snippet)
