In class we were introduced to a simple form of A* pathfinding through waypoints. For my midterm I worked to make a better pathfinding system for projects in the future. For a few days I worked on implementing A* and found it to be terribly slow. I scoured the internet looking for better solutions and found Jump Point. I found papers explaining the science behind it, but few resources for implementation. I worked on it for the next two weeks and eventually ended up with this in time to turn in!
Jump point works almost exactly the same as A* and the structure is the same. Instead of grabbing every neighbour around the parent node and doing all the calculations to every single node, you instead move along a direction recursively until you find a point of importance or hit an obstacle/off the map. A node of importance is one where there is a possible path around an object, for example a corner where the top node is unwalkable, but the diagonal node in the direction of movement is clear. It cuts all the node calculations down monumentally, prunes symmetrical paths, and eliminates a lot of overhead memory.
A* ran through that maze in 40ms. That doesn't seem so bad until you realize that's just for one unit. When adding multiple units with
their own unique destination, you can get crazy amounts of computing time for pathing.
Jump Point cuts down the time dramatically, cutting the computing time to a fraction of A*. Through many different tests this holds true
in every situation, especially cases where the target is unreachable. While jump point excels in open environments, it is still extremely
fast in confined spaces with hard to reach places.
One of the hardest things to understand was just getting the algorithm to make sense. After a couple attempted tries it still didn't make any sense. After understanding it, there were still many problems with each iteration. Debugging became a massive hassle and I learned an enormous amount about debugging and how important it is to set up custom tools. I restarted the project around 10 times, even with the 2 week deadline.
This is not the most optimal iteration. There's a lot more than can be added to this to make it even faster. I had plans to change the structure and store the grid as sets of bits so that I could bit-shift rapidly instead of recursively calling a function to find neighbours.
Sources: A* algorithm explained Jump Point algorithm Jump Point explained Another Jump Point explination