Game AI Pro 360: Guide to Movement and Pathfinding

Steve Rabin

• Publisher: CRC Press
• Year: 2019
• ISBN:
  9780429619670
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Science General
• Index: Computer Science

Steve Rabin's Game AI Pro 360: Guide to Movement and Pathfinding gathers all the cutting-edge information from his previous three Game AI Pro volumes into a convenient single source anthology covering movement and pathfinding in game AI. This volume is complete with articles by leading game AI programmers that explore better ways to smooth paths, avoid obstacles, and navigate 3D space with cutting-edge techniques.

Key Features

• Provides real-life case studies of game AI in published commercial games

• 
  
  

• Material by top developers and researchers in Game AI

• 
  
  

• Downloadable demos and/or source code available online

• 
  
  

1

Pathfinding Architecture Optimizations

Steve Rabin and Nathan R. Sturtevant

1.1Introduction

1.2Orders of Magnitude Difference in Performance

1.3Optimization #1: Build High-Quality Heuristics

1.4Optimization #2: Using an Optimal Search Space Representation

1.5Optimization #3: Preallocate All Necessary Memory

1.6Optimization #4: Overestimating the Heuristic

1.7Optimization #5: Better Heuristics

1.8Optimization #6: Open List Sorting

1.9Optimization #7: Don’t Backtrack during the Search

1.10Optimization #8: Caching Successors

1.11Bad Ideas for Pathfinding

1.12Conclusion

1.1 Introduction

Agent path requests are notorious for devouring huge proportions of the AI’s CPU cycles in many genres of games, such as real-time strategy games and first-person shooters. Therefore, there is a large need for AI programmers to all be on the same page when it comes to optimizing pathfinding architectures. This chapter will cover in a priority order the most significant steps you can take to get the fastest pathfinding engine possible.

All game developers understand that A* is the pathfinding search algorithm of choice, but surprisingly, or not so surprisingly, it is not a panacea. There is a huge realm of knowledge that is crucial to crafting the fastest engine. In fact, even if a large number of pathfinding design choices have already been made, there is still much you can do.

1.2 Orders of Magnitude Difference in Performance

What is the difference between the fastest and slowest A* implementations?

At the DigiPen Institute of Technology video game university, the introductory AI course has students program a simple A* implementation on fixed regular grid as one of the first assignments. As extra credit for the assignment, there is a contest held to see who can write the fastest A* implementation. So if you were to guess the difference between the fastest and slowest solutions, what would you guess? Would you guess that the best solution is several times faster than the slowest?

The true answer is quite surprising. Given hundreds of students who have taken the course over the years, the fastest implementations are 2 orders of magnitude faster than the slowest implementations (a 100× difference). The fastest implementations are also 1 order of magnitude faster than the average implementation (a 10× difference). To put concrete numbers behind this example, on a given map, the fastest implementation finds a path in ~200 us, the average takes ~2500 us, and the slowest implementations take upwards of 20,000 us. Given that these are junior, senior, and master’s students, how do you think you would rank if given the same task? It’s a strange question, since as a professional game programmer you would never be put in such a position. Wherever you might rank, it is a scary thought that you might be 1 to 2 orders of magnitude slower than the best solution.

Although with fewer students, the second author has had similar experiences with his students in both regular assignments and competitions. The insights of both authors have been distilled here. Thus, you might want to scour this chapter for the nuggets of wisdom that will keep you within spitting distance of the best implementations.

1.3 Optimization #1: Build High-Quality Heuristics

This first optimization is the epitome of the classic programming trade-off between memory and speed. There are many ways that heuristics can be built; we will go through several useful approaches here.

1.3.1 Precompute Every Single Path (Roy–Floyd–Warshall)

While at first glance it seems ridiculous, it is possible to precompute every single path in a search space and store it in a look-up table. The memory implications are severe, but there are ways to temper the memory requirements and make it work for games.

The algorithm is known in English-speaking circles as the Floyd–Warshall algorithm, while in Europe it is better known as Roy–Floyd. Since the algorithm was independently discovered by three different mathematicians, we’ll give credit to each and refer to it as the Roy–Floyd–Warshall algorithm [Millington 09].

While we won’t explain the algorithm in enough detail to implement it, you should be aware of its basic advantages and properties so that you can make an informed choice whether to pursue implementing it for your game. Here are the facts:

• Roy–Floyd–Warshall is the absolute fastest way to generate a path at runtime. It should routinely be an order of magnitude faster than the best A* implementation.
• The look-up table is calculated offline before the game ships.
• The look-up table requires O(n²) entries, where n is the number of nodes. For example, for a 100 by 100 grid search space, there are 10,000 nodes. Therefore, the memory required for the look-up table would be 100,000,000 entries (with 2 bytes per entry, this would be ~200 MB).
• Path generation is as simple as looking up the answer. The time complexity is O(p), where p is the number of nodes in the final path.

Figure 1.1 shows a search space graph and the resulting tables generated by the Roy–Floyd–Warshall algorithm. A full path is found by consecutively looking up the next step in the path (left table in Figure 1.1). For example, if you want to find a final path from B to A, you would first look up the entry for (B, A), which is node D. You would travel to node D, then look up the next step of the path (D, A), which would be node E. By repeating this all the way to node A, you will travel the optimal path with an absolute minimum amount of CPU work. If there are dynamic obstacles in the map which must be avoided, this approach can be used as a very accurate heuristic estimate, provided that distances are stored in the look-up table instead of the next node to travel to (right table in Figure 1.1).

As we mentioned earlier, in games you can make the memory requirement more reasonable by creating minimum node networks that are connected to each other [Waveren 01, van der Sterren 04]. For example if you have 1000 total nodes in your level, this would normally require 1000² = 1,000,000 entries in a table. But if you can create 50 node zones of 20 nodes each, then the total number of entries required is 50 × 20² = 20,000 (which is 50 times fewer entries).

Figure 1.1

A search space with its corresponding Roy–Floyd–Warshall path look-up table on the left and a very accurate heuristic cost look-up table on the right.

1.3.2 Lossless Compression of Roy–Floyd–Warshall

Another approach to reducing the memory requirement is to compress the Roy–Floyd–Warshall data. Published work [Botea 11] has shown the effectiveness of compressing the data, and this approach fared very well in the 2012 Grid-Based Path Planning competition (http://www.movingai.com/GPPC/), when sufficient memory was available.

An alternate way to compress the Roy–Floyd–Warshall data is to take advantage of the structure of the environment. In many maps, but not all maps, there are relatively few optimal paths of significant length through the state space, and most of these paths overlap. Thus, it is possible to find a sparse number of “transit nodes” through which optimal paths cross [Bast et al. 07]. If, for every state in the state space, we store the path to all transit nodes for that state, as well as the optimal paths between all transit nodes, we can easily reconstruct the shortest path information between any two states, using much less space than when storing the shortest path between all pairs of states. This is one of several methods which have been shown to be highly effective on highway road maps [Abraham et al. 10].

1.3.3 Lossy Compression of Roy–Floyd–Warshall

The full Roy–Floyd–Warshall data results in very fast pathfinding queries, at the cost of memory overhead. In many cases you might want to use less memory and more CPU, which suggests building strong, but not perfect heuristics.

Imagine if we store just a few rows/columns of the Roy–Floyd–Warshall data. This corresponds to keeping the shortest paths from a few select nodes. Fortunately, improved distance estimates between all nodes can be inferred from this data. If d(x, y) is the distance between node x and y, and we know d(p, z) for all z, then the estimated distance between x and y is h(x, y) = | d(p, x) – d(p, y) |, where p is a pivot node that corresponds to a single row/column in the Roy–Floyd–Warshall data. With multiple pivot nodes, we can perform multiple heuristic lookups and take the maximum. The improved estimates will reduce the cost of A* search.

This approach has been developed in many contexts and been given many different names [Ng and Zhang 01, Goldberg and Harrelson 05, Goldenberg et al. 11, Rayner et al. 11]. We prefer the name Euclidean embedding, which we will justify shortly. First, we summarize the facts about this approach:

• Euclidean embeddings can be far more accurate than the default heuristics for a map, and in some maps are nearly as fast as Roy-Floyd-Warshall.
• The look-up table can be calculated before the game ships or at runtime, depending on the size and dynamic nature of the maps.
• The heuristic requires O(kn) entries, where n is the number of nodes and k is the number of pivots.
• Euclidean embeddings provide a heuristic for guiding A* search. Given multiple heuristics, A* should usually take the maximum of all available heuristics.

Why do we call this a Euclidean embedding? Consider a map that is wrapped into a spiral, such as in Figure 1.2. Points A and B are quite close in the coordinates of the map, but quite far when considering the minimal travel distance between A and B. If we could just unroll the map into a straight line, the distance estimates would be more accurate. Thus, the central problem is that the coordinates used for aesthetic and gameplay purposes are not the best for A* search purposes. That is, they do not provide accurate heuristic estimates. If we could provide a different set of coordinates optimized for A* search, we could use these coordinates to estimate distances between nodes and have a higher quality heuristic. This process of transforming a map into a new state...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• About the Editor
• About the Contributors
• Introduction
• 1 Pathfinding Architecture Optimizations
• 2 Choosing a Search Space Representation
• 3 Creating High-Order Navigation Meshes through Iterative Wavefront Edge Expansions
• 4 Precomputed Pathfinding for Large and Detailed Worlds on MMO Servers
• 5 Techniques for Formation Movement Using Steering Circles
• 6 Collision Avoidance for Preplanned Locomotion
• 7 Crowd Pathfinding and Steering Using Flow Field Tiles
• 8 Efficient Crowd Simulation for Mobile Games
• 9 Animation-Driven Locomotion with Locomotion Planning
• 10 JPS+: An Extreme A* Speed Optimization for Static Uniform Cost Grids
• 11 Subgoal Graphs for Fast Optimal Pathfinding
• 12 Theta* for Any-Angle Pathfinding
• 13 Advanced Techniques for Robust, Efficient Crowds
• 14 Context Steering: Behavior-Driven Steering at the Macro Scale
• 15 Guide to Anticipatory Collision Avoidance
• 16 Hierarchical Architecture for Group Navigation Behaviors
• 17 Dynamic Obstacle Navigation in Fuse
• 18 Steering against Complex Vehicles in Assassin’s Creed Syndicate
• 19 Predictive Animation Control Using Simulations and Fitted Models
• 20 Fast Cars, Big City: The AI of Driver San Francisco
• 21 A Unified Theory of Locomotion
• 22 RVO and ORCA: How They Really Work
• 23 Optimization for Smooth Paths
• 24 3D Flight Navigation Using Sparse Voxel Octrees
• 25 Faster A* with Goal Bounding
• 26 Faster Dijkstra Search on Uniform Cost Grids