GDC:
| Session Name | JPS+: Over 100x Faster than A* |
| Speaker(s) | Steve Rabin |
| Company Name(s) | DigiPen Institute of Technology |
| Track / Format | AI Summit |
| Overview | It has been said that "pathfinding is a solved problem." Just because something is "solved" doesn't mean it can't be improved especially with regards to execution time. Normally, a speed gain of 10x or 100x over a traditional algorithm is unheard of. Recently, a method has been devised that is capable of doing just that to A*. In 2011, Harabor and Grastien introduced Jump Point Search (JPS) that achieves up to a 10x speed improvement over A* on uniform cost grids. In the last year, an additional 10x speed improvement to JPS, called JPS+ was independently developed by Steve Rabin as well as Harabor and Grastien. This improved algorithm is over 100x faster than A* on maps with open areas and over 2x faster than A* on worst-case maps. This incredible speed-up is due to pre-computation, eliminating the recursion in JPS and focusing only on touching select relevant nodes during the search. |
Recommended
