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