Python Depth First Search stop when found

Question

I'm having issues with this. When the grid status of the above coordinates of the searched area == 5, it is meant to stop and move to that position. For some reason it carries on and I have been trying to work out why. I'm assuming it is going to be something obvious with someone else's eyes looking at it!

def depthfirstsearch(visited,graph,vertex):
    # Do a depth-first search of all neighbours if found stop.
    moveto(vertex,3)
    visited.append(vertex)
    if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
        x = vertex[0] - 1
        y = vertex[1]
        moveto((x, y), 0)
        return
    else:
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                depthfirstsearch(visited, graph, neighbour)

Answer 1

Your function returns when it finds the target.

if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
    # ..
    return

However, it returns None and the recursive call doesn't do anything with the fact that it returned:

if neighbour not in visited:
    depthfirstsearch(visited, graph, neighbour)

If this call to depthfirstsearch() finds the target, you'd want the function to return as well, with a positive result. If the call doesn't find it, you'd want it to continue searching.

So instead, you need:

if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
    # ..
    return True

And:

if neighbour not in visited:
    if depthfirstsearch(visited, graph, neighbour):
        return True

And finally, you can rely on the function just returning None when it finishes without explicitly returning, but that's a bit ugly. None evaluates to False as a bool, but you can also just return False at the end for clarity and type-safeness.

So, the result:

def depthfirstsearch(visited,graph,vertex):
    # Do a depth-first search of all neighbours if found stop.
    moveto(vertex,3)
    visited.append(vertex)
    if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
        x = vertex[0] - 1
        y = vertex[1]
        moveto((x, y), 0)
        # found it, report success
        return True
    else:
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                if depthfirstsearch(visited, graph, neighbour):
                    # found in recursion, report success
                    return True
    # if this point is reached, this call didn't find it anywhere
    return False