1
\$\begingroup\$

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[0])) 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[0]) if solution[1] 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
\$\endgroup\$
3
  • \$\begingroup\$ Class Agent is showed twice (did you mean to subclass \$\endgroup\$ Sep 8 at 16:48
  • \$\begingroup\$ sorry bad copy / paste, yes just one Agent() class \$\endgroup\$
    – Matthew
    Sep 8 at 19:42
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – C.Nivs
    Sep 11 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.