O'Reilly logo

Game AI Pro 2 by Steven Rabin

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 14

JPS+

An Extreme A* Speed Optimization for Static Uniform Cost Grids

Steve Rabin and Fernando Silva

14.1 Introduction

Jump point search (JPS) is a recently devised optimal pathfinding algorithm that can speed up searches on uniform cost grid maps by up to an order of magnitude over traditional A* [Harabor 12]. However, by statically analyzing a map and burning in directions to walls and jump points, it is possible to dramatically speed up searches even further, up to two orders of magnitude over traditional A*. To illustrate the difference in speed on a particular 40 × 40 map, A* found an optimal solution in 180.05 ns, JPS in 15.04 ns, and JPS+ in 1.55 ns. In this example, JPS+ was 116x faster than traditional A*, while remaining perfectly ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required