# How to create a maze solve search with BFS provide navigation movements

How should I structure this code to create a maze, solve it with breath-first-search (BFS) and to provide basic navigation movements by 1 step within maze with number of moves required to navigate? Use move along the path, Up, Left, Right, Down.

Below is some code that I mangled together on how to think / approach and figure how to structure python for this BFS algorithm code.

Is anyone open to mentoring on this BFS algorithm navigation maze python structure or provide another more suitable approach to BFS algorithm maze navigation?

import sys

def parse_map(filename):
with open(filename, "r") as f:
return [[char for char in line] for line in f.read().rstrip("\n").split("\n")][3:]

def count_x(house_map):
return sum([ row.count('p') for row in house_map ] )

def printable_house_map(house_map):
return "\n".join(["".join(row) for row in house_map])

return house_map[0:row] + [house_map[row][0:col] + ['p',] + house_map[row][col+1:]] + house_map[row+1:]

def successors(house_map):
return [ add_x(house_map, r, c) for r in range(0, len(house_map)) for c in range(0,len(house_map)) if house_map[r][c] == '.' ]

def is_goal(house_map, k):
return count_x(house_map) == k

def bfs_graph_search(house_map):
fringe = [initial_house_map]
if house_map.goal_test(node.state):
return fringe
fringe = deque([house_map])
visited = set()
while fringe:
fringe = fringe.popleft()
for child in node.expand(problem):
if child.state not in fringe and child not in visited:
if house_map.goal_test(child.state):
return child
fringe.append(child)
return None

def solve(initial_house_map,k):
fringe = [initial_house_map]
while len(fringe) > 0:
for new_house_map in successors( fringe.pop() ):
if is_goal(new_house_map,k):
return(new_house_map,True)
fringe.append(new_house_map)

if __name__ == "__main__":

house_map=parse_map('map1.txt')
k = 2
print ("Initial ]house map:\n" + printable_house_map(house_map) + "\n\nSearching for solution...\n")
solution = solve(house_map,k)
print ("Found:")
print (printable_house_map(solution) if solution else "False")

class Agent:

def __init__(self, initial, goal=None):
self.initial = initial
self.goal = goal

def actions(self, state):
raise NotImplementedError

def result(self, state, action):
raise NotImplementedError

def goal_test(self, state):
if isinstance(self.goal, list):
return is_in(state, self.goal)
else:
return state == self.goal

def path_cost(self, c, state1, action, state2):
return c + 1

def value(self, state):
raise NotImplementedError

class FringeGraph:

def __init__(self, state, parent=None, action=None, path_cost=0):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
self.depth = 0
if parent:
self.depth = parent.depth + 1

def path(self):
node, path_back = self, []
while node:
path_back.append(node)
node = node.parent
return list(reversed(path_back))

def solution(self):
return [node.action for node in self.path()[1:]]

def expand(self, agent):
return [self.child_node(agent, action)
for action in agent.actions(self.state)]

def child_node(self, agent, action):
next_state = agent.result(self.state, action)
next_node = Node(next_state, self, action, problem.path_cost(self.path_cost, self.state, action, next_state))
return next_node

• Class Agent is showed twice (did you mean to subclass Sep 8, 2021 at 16:48
• sorry bad copy / paste, yes just one Agent() class Sep 8, 2021 at 19:42
• Does this code work? I'm seeing what should be a NameError in bfs_graph_search with node. It's not defined anywhere. I also don't see your classes explicitly used anywhere. Are you importing them or renaming them? It seems like your Agent and FringeGraph classes probably live in a separate module/file. Also, could you include an example of what map1.txt looks like? Sep 11, 2021 at 21:29