Game AI Pro 2

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 ...