GDC Vault is part of the Informa Tech Division of Informa PLC
This is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.
|Session Name:||JPS+: Over 100x Faster than A*|
|Company Name(s):||DigiPen Institute of Technology|
|Track / Format:||AI Summit|
Did you know free users get access to 30% of content from the last 2 years?
|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.|