< index
< 12. Field of view toolkit

=====================================
13. Path finding
=====================================

> 14. BSP toolkit
This toolkit allows to easily calculate the optimal path between two points in your dungeon by using either the A* algorithm or Dijkstra's algorithm.

Please note that the paths generated with the two algorithms may differ slightly. Due to how they're implemented, A* will usually prefer diagonal moves over orthogonal, while Dijkstra will have the opposite preference. In other words, paths from point X to point Y will look like this:
A*:         Dijkstra:
..........  ..........
.X........  .X****....
..*.......  ......*...
...*......  .......*..
....****Y.  ........Y.
..........  ..........
13.1 Creating a path
13.2 Computing the path
13.3 Reading path information
13.4 Destroying a path