1

I have a problem concerning a labyrinth pathfinder I'm making. I have got a depth first solution, but i want a breadth first solution. This is the depth first:

def find_path(pathList):
    if pathList[-1] == goal:
        return pathList

    for i in adjacent_passages(labyrinth, pathList[-1]):
        if i not in pathList:
            found_path = find_path(pathList + [i])
            if found_path:
                return found_path

And this is how "far" I've come on the breadth first problem:

def find_path_bf(pathL):
    num = 0

    for i in range(0, len(pathL)):
        frontier[i] = adjacent_passages(labyrinth, pathL[i][-1])

    for i in range(0, len(pathL)):    
        if pathL[i][-1] == goal:
            return pathL[i]

    for i in frontier:
        if i not in pathL:
            pathL[num].append(i)
            num = num + 1

    find_path_bf(pathL)

The labyrinth is a matrix of a labyrinth and adjacent_passages finds the adjacent squares :)

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
Mattias Bodén
  • 31
  • 3
  • 4
    take your working depth first solution and remove from frontier as a stack rather than a queue ... (I think at least ...) – Joran Beasley Nov 26 '12 at 18:52
  • @JoranBeasley That's true, but not easy, since he's using the call stack as his stack for the depth-first solution. :-) – Sam Mussmann Nov 26 '12 at 19:02

0 Answers0