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]) def add_x(house_map, row, col): 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() visited.add(node.state) 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
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
FringeGraphclasses probably live in a separate module/file. Also, could you include an example of what
map1.txtlooks like? \$\endgroup\$