April 2015
Beginner
577 pages
17h 58m
English
Chapter 16
Alex Nash and Sven Koenig
One of the central problems in game AI is finding short and realistic-looking paths. Pathfinding is typically divided into two steps: discretize and search. First, the discretize step simplifies a continuous environment into a graph. Second, the search step propagates information along this graph to find a path from a given start vertex to a given goal vertex. Video game developers (and roboticists) have developed several methods for discretizing continuous environments into graphs, such as 2D regular grids composed of squares (square grids), hexagons or triangles, 3D regular grids composed of cubes, visibility graphs, circle-based waypoint graphs, space-filling ...