ABSTRACT

The choice of a path planning architecture for a game will help determine what features the game can support easily, and what features will require significant effort to implement. There are good articles describing different types of path planning architectures, and there have been debates in different forums about the correct choice for a path planning architecture. In addition to representing space for path planning, the representation can often be used for more generic queries to facilitate artificial intelligence behavior. This chapter focuses on the primary representations: grids, waypoint graphs, and navigation meshes. Waypoint graphs are most useful when implementation time is limited, when fast path planning is needed, and when an accurate representation of the world is not necessary. Navigation meshes are best when there is adequate time for testing and implementation. They are the most flexible of the possible implementations when implemented well, but can be overkill for smaller projects.