Pathfinding on a 2D Grid
The pathfinding algorithm is standard A* with some slight modifications / optimizations.
There are two optimizations that are worth mentioning, the first is that I create the nodes on the fly as that generally helps with speed and less memory overhead, especially so in the case of large open maps with few obstacles. The second optimization is that I use something called a HOT queue which is basically a variant of bucket queues. The HOT queue in my case make the lowermost bucket (since, we want to prioritize the lowest heuristic in A*) use a binary heap, and keep all the other buckets unsorted. I believe this optimization would play a bigger role if the movement cost from node to node was not uniform on the grid, but that is something I might add later on.
The project is available on GitHub here.
If you have any suggestions or comments please don’t hesitate to reach out!
Visualization of a found path
While trying out the algorithm on larger mazes I found it extremely useful to visualize what was happening so I wrote a small program that allowed me to easily modify a maze, run the pathfinding algorithm and output the result as a 24-bit BMP image.
Original Maze
The same program allowed me to convert a BMP image into a maze. It might be difficult to see but there are two pixels that determine the start position and the target position. They can be spotted in the top-left corner and the bottom-right corner.
I have not included the source code for the maze editing as there are plenty of more efficient and better written libraries out there that do the same thing. However, if requested I’d be more than willing to send it over.
Original maze
Original maze with path
Visualization of open and closed nodes
Visualization of nodes added as sorted and unsorted
Visualization of nodes added as sorted and unsorted and the ones that got sorted after being added
