Pathfinder explained

The Pathfinder class is used in the WorldGenerator functionality to ensure each level is passable, and I plan on integrating with the enemy AI for random level traversal and encounters.

Pathfinder is essentially a wrapper for several algorithms – A*, Breadth-First, and Greedy Best-First (heretofore GBF). Dijkstra’s will be added eventually, but I found solid early results using GBF so I am focusing on implementing this as the WorldGenerator post-run level checker.

Refer to the WorldGenerator update to PokeyGame for more information on how the world is generated.  There are four methods for accessing the post-run level check functionality – directly through the WorldGenerator.test_paths  method, setting the WorldGenerator post_check argument to True when initializing the class, the command-line menu, or using the -p|--path  command-line argument :

  • $ python -k
  • WorldGenerator(post_check=True)
  • WorldGenerator.test_paths()

For the purposes of this example, I will present the command-line option.  I’ll start by generating a world grid :

This creates a grid of size (x=45, y=25, z=3).  Here is floor 0 :floor1_no_path

Back at the main menu, enter “c” to check the paths.

This iterates through each floor (z dimension), locates the start and end points for that floor, and attempts to create a path connecting them using the GBF search algorithm.  The tiles passed are highlighted, and the map is displayed a second time.


Here you see the start point “S” connected to the descent point “D”.  I haven’t added locking doors and chests with items yet, but once those are present, the path testing method will be updated to follow a set of waypoints to ensure the logical layout of the floor passes as well.

The Pathfinder class generating this path is :

The returned  came_from will contain a dictionary with values reflecting the tile coordinates visited.  This is iterated over to update the WorldGenerator game grid.  Ideas for future versions include selection of different algorithms, and multiple path generation attempts with color-coded paths.

The Pathfinder, WorldGenerator, and PokeyGame classes are part of my general code repository available here.



Leave a Reply

Your email address will not be published. Required fields are marked *