pythonrecursive-backtracking

How do I output the quickest path of a maze via backtracking?


I'm trying to solve a backtracking problem in python. Not only should my code be able to identify and reach the goal, but also output the quickest path to it. The maze is looks like this:

xxxxxxx
xSx   x
x xx  x
x     x
xxxx  x
x     x
x xx xx
x E   x
xxxxxxx 

Start [1,1]
End   [7,2]

The backtrack function I wrote so far, looks as follows:

def find_escape(rN, cN, route=[]):
    route.append([rN, cN])
    if is_escape(rN, cN):
        return route
    else:
        escapeRoutes = []
        relCoordinates = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        for relN in relCoordinates:
            absN = [rN + relN[0], cN + relN[1]]
            if is_free(absN[0], absN[1]) and absN not in route:
                temp = find_escape(absN[0], absN[1], route)
                if len(temp) > 0:
                    escapeRoutes.append(temp)
        if len(escapeRoutes) > 0:
            min = escapeRoutes[0]
            for i in escapeRoutes:
                if len(i) < len(min):
                    min = i
            return min
        else:
            return []

My problem is, that the output shows no path but rather every single coordinate he "walked" through in chronological order:

Output:
[[2, 1], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 5], [5, 5], [5, 4], [6, 4], [7, 4], [7, 5], [7, 3], [7, 2], [5, 3], [5, 2], [5, 1], [6, 1], [7, 1], [4, 4], [2, 5], [2, 4], [1, 4], [1, 5], [1, 3], [1, 1]]

The assisting functions "is_escape" and "is_free" are simple. So no issue there.


Solution

  • try to always pass the copy of the route recursively. That works for me. Otherwise the function adds every field that the algorithm enters to the original route and the fields that do not belong to the best route are never removed from the route again. If you only pass a copy of the route you never change the original route but only the respective copy of the recusion pass. And there each copy contains a possible route independent of the other tried routes. Then the shortest route is returned without containing the other fields of the other routes.

    def find_escape(rN, cN, route=[]):
        route.append([rN, cN])
        if is_escape(rN, cN):
            return route
        else:
            escapeRoutes = []
            relCoordinates = [[0, 1], [1, 0], [0, -1], [-1, 0]]
            for relN in relCoordinates:
                absN = [rN + relN[0], cN + relN[1]]
                if is_free(absN[0], absN[1]) and absN not in route:
                    temp = find_escape(absN[0], absN[1], route.copy())
                    if len(temp) > 0:
                        escapeRoutes.append(temp)
            if len(escapeRoutes) > 0:
                min = escapeRoutes[0]
                for i in escapeRoutes:
                    if len(i) < len(min):
                        min = i
                return min
            else:
                return []