< 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