You've been logged out of GDC Vault since the maximum users allowed for this account has been reached. To access Members Only content on GDC Vault, please log out of GDC Vault from the computer which last accessed this account.

Click here to find out about GDC Vault Membership options for more users.

close

The Number One Educational Resource for the Game Industry

Session Name: JPS+: Over 100x Faster than A*
Speaker(s): Steve Rabin
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?


Get your team full access to the most up to date GDC content

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.

GDC 2015

Steve Rabin

DigiPen Institute of Technology

free content

AI Summit

AI