Chapter 2. Navigation

In this chapter, we will cover the following recipes:

• Representing the world with grids
• Representing the world with Dirichlet domains
• Representing the world with points of visibility
• Representing the world with a self-made navigation mesh
• Finding your way out of a maze with DFS
• Finding the shortest path in a grid with BFS
• Finding the shortest path with Dijkstra
• Finding the best-promising path with A*
• Improving A* for memory: IDA*
• Planning navigation in several frames: time-sliced search
• Smoothing a path