Python grid world inncorrect depth first search algorithm implementation

Question

I'm trying to write a depth-first search algorithm that will find a path form where the agent (black cube is) to the exit at the bottom of the right-hand path. But the algorithm I have written loops back on itself as part of the path found. How do I implement a DFS algorithm that doesn't do this?

Any ideas on what I am doing wrong?

Any help much appreciated, please.

Thanks What the world looks like:

The result of the depth first search path planning:

My code for the agent class:

class Agent(turtle.Turtle):
    def __init__(self, location, endPoint, world): 
        turtle.Turtle.__init__(self)
        self.shape("square")
        self.color("black")
        self.penup()
        self.speed(0)
    
        # Variables
        self._bump = 0
        self._location = location
        self._endPoint = endPoint
        self._world = world
        self._map = dict()
    
    def dfs_paths(self, start, goal, path=None):
        if path is None:
            path = [start]
        if start == goal:
            yield path
        for next in self._map[tuple(start)] - set(path):
            yield from dfs_paths(next, goal, path + [next])
    
    def _planPath(self, node, visited=None):
        if visited is None:
            visited = [node]
        self._map[tuple(node)] = self._world.testDirections(node)
        if node not in visited:
            visited.append(tuple((node)))
            print("Visited = " + str(visited))
            for neighbour in self._map[tuple((node))]:
                print("Neighbour = " + str(neighbour))
                if neighbour == self._endPoint:
                    visited.append(neighbour)
                    print("Here 1...")
                    return [node, neighbour]
                else:     
                    path = self._planPath(neighbour,visited)
                    if path:
                        print("Here 2...")
                        return [node] + path

Answer 1

You are building the path from the visited information. But that does not represent the path. It just represents the nodes you have visited, which includes unsuccessful paths from which you have already backtracked.

When you find the target node, you should instead create a (partial) path with just the end node in it, and return that to the caller. The caller can detect from the return value of the recursive call that the target was found and can then prepend its own node to that partial path, and return that to its own caller.

That way the backtracking phase (after success) will be used to build the path.

So, to get you started, replace this:

self._planPath(neighbour, visited)

with:

path = self._planPath(neighbour, visited)
if path:  # success!
    return [node] + path

Or do an append which is more efficient, but then you must reverse the path at the very end.

And replace this:

self._world.showPath(visited)

with:

return [node, neighbor]

The main caller of self._planPath would probably do something like this:

path = self._planPath(startnode, [])
if path:
    self._world.showPath(path)

Note that for visited you should really be using a set, not a list.