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 world_generator.py -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 :

$ python world_generator.py -x 45
[*] Command-line invoker engaged
[*] Handling command line arguments
[*] Logger received
[*] Building walls
[*] Generating map template
...

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.

Show [m]ap
[C]heck level paths (not done)
[R]egenerate
[S]ave (world_gen_output.py)
[Q]uit
Selection > c

[*] Testing the path from (32, 24, 0) to (6, 22, 0)
[*] Testing the path from (6, 22, 1) to (40, 24, 1)
[*] Testing the path from (40, 24, 2) to (9, 12, 2)
[*] Testing the path from (9, 12, 3) to (13, 24, 3)

Show [m]ap
[C]heck level paths (done!)
[R]egenerate
[S]ave (world_gen_output.py)
[Q]uit
Selection > m

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.

floor1_with_path

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 :

class Pathfinder:

    """ Performs basic pathfinding operations """

    a_star = 0      # A* algorithm (default)
    b_first = 1     # Breadth first
    gb_first = 2    # Greedy best-first

    def __init__(self,alg=0):
        self.early_exit = True
        self.impediments = []
        self.alg = alg
        self.g = None
        self.start = None
        self.dest = None

    def execute(self):

        assert self.g is not None, 'Graph (Pathfinder.g) not initialized!'
        assert self.start is not None, 'Start point not specified!'
        assert self.dest is not None, 'End point not specified!'

        if self.alg==Pathfinder.a_star:
            results = self.a_star(self.g,self.start,self.dest)
        elif self.alg==Pathfinder.b_first:
            results = self.bf_search(self.g,self.start,self.dest)
        elif self.alg==Pathfinder.gb_first:
            results = self.gbf_search(self.g,self.start,self.dest)
        else:
            results = False

        return results

    def gbf_search(self,graph,start,goal):
        """ Greedy Best-First search """
        frontier = PriorityQueue()
        frontier.put(start,0)
        came_from = {}
        came_from[start] = None

        while not frontier.empty():
            current = frontier.get()

            if current == goal and self.early_exit:
                break

            for next in graph.neighbor(current):
                if next not in came_from:
                    priority = self.heuristic(goal,next)
                    frontier.put(next,priority)
                    came_from[next] = current

        return came_from

    def heuristic(self,a,b):
        (x1,y1) = a
        (x2,y2) = b
        return abs(x1-x2) + abs(y1-y2)

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.

File List:
https://raw.githubusercontent.com/wnormandin/pokeycode/master/pokeygame.py
https://raw.githubusercontent.com/wnormandin/pokeycode/master/resources/games/pathfinder.py
https://raw.githubusercontent.com/wnormandin/pokeycode/master/resources/games/world_generator.py

 

 

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.