Skip to Main Content
Game AI Pro 2
book

Game AI Pro 2

by Steven Rabin
April 2015
Beginner content levelBeginner
577 pages
17h 58m
English
A K Peters/CRC Press
Content preview from 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 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Game AI Pro 3

Game AI Pro 3

Steve Rabin
Game AI Pro

Game AI Pro

Steven Rabin

Publisher Resources

ISBN: 9781482254792