Recursive pathfinding algorithm keeps returning None

Question

To find a path in a 2D map, I call get_building_path() on a Person instance, but it keeps returning None. I have no idea what is going wrong as I am pretty new to Python.

Below I have provided code needed to reproduce the issue. I have tried many things but I still don't understand why it keeps returning None:

from random import randint

width = 1400
height = 700
gridSize = 20
people = []
buildings = []
map = [['' for c in range(int(width/gridSize))] for r in range(int(height/gridSize))]

class Person():
    def __init__(self,row,col):
        self.row = row
        self.col = col
    def getMin(self,paths): # find shortest path
        if (len(paths) == 0): return [] # if nothing was found, return an empty list
        min = paths[0]
        for n in range(1,len(paths),1):
            if ((paths[n] != None and len(paths[n]) < len(min)) or min==[None]): # make sure [None] is not returned since that would be the shortest
                min = paths[n]
        return min
    def path_helper(self,visited,path,row,col,destR,destC): # destR and destC are the row and col of the target position
        if ((row,col) in visited or map[row][col] != 'road' or row < 0 or row > len(map)-1 or col < 0 or col > len(map[0])-1):
            return None # make sure the current position has not been visited, and is in bounds of the map
        path.append([row,col]) # add current position to the path
        visited.append((row,col)) # mark current position as visited
        if (row == destR and col == destC): # return the path if we found the destination
            return path
        others=[] # look in all four directions from the current position
        others.append(self.path_helper(visited,path[:],row-1,col,destR,destC))
        others.append(self.path_helper(visited,path[:],row+1,col,destR,destC))
        others.append(self.path_helper(visited,path[:],row,col-1,destR,destC))
        others.append(self.path_helper(visited,path[:],row,col+1,destR,destC))
        others.remove(None) # remove any path that did not find anything
        return self.getMin(others)
    def get_path(self,row,col):
        return self.path_helper([],[],self.row,self.col,row,col) #call to recursive helper function
    def get_building_path(self,type):
        all = []
        for b in buildings:
            if (b.type == type):
                all.append(b)
        target = all[randint(0,len(all)-1)] #get a random buildings of type 'type'
        return self.get_path(target.row,target.col)
class Building():
    def __init__(self,type,row,col):
        self.type = type
        self.row = row
        self.col = col

midrow = int(height/gridSize/2) #get midpoint of the map
midcol = int(width/gridSize/2)
people.append(Person(midrow+1,midcol+2))
for n in range(0,3,2): #add new buildings to buildings list, along with the map
    buildings.append(Building('house',midrow+n,midcol-2))
    map[midrow+n][midcol-2] = buildings[len(buildings)-1]
    buildings.append(Building('school',midrow+n,midcol-1))
    map[midrow+n][midcol-1] = buildings[len(buildings)-1]
    buildings.append(Building('workplace',midrow+n,midcol))
    map[midrow+n][midcol] = buildings[len(buildings)-1]
    buildings.append(Building('store',midrow+n,midcol+1))
    map[midrow+n][midcol+1] = buildings[len(buildings)-1]
    buildings.append(Building('restaurant',midrow+n,midcol+2))
    map[midrow+n][midcol+2] = buildings[len(buildings)-1]
for n in range(-2,3,1): #add roads to connect the buildings together
    map[midrow+1][midcol+n] = 'road'

testPath = people[0].get_building_path('house')
print(testPath)

If you would like to visually see how the buildings and roads are positioned, here is a picture of it:

From left to right, the buildings are 'house', 'school', 'workplace', 'store', 'restaurant'.

The blue circle represents the person.

(The top left building has a position of (17,33) (row,col)

Answer 1

A few issues:

• others.remove(None) only removes the first occurrence of None
• map[row][col] != 'road' will be True when arriving at the target, so this test should be only done after you have verified that you have not yet arrived at the target.
• map[row][col] != 'road' will potentially give an error when row or col are out of range, so you should first do that range check

So path_helper should be corrected to:

    def path_helper(self,visited,path,row,col,destR,destC):
        path.append([row,col])
        # next IF should come before the other IF:
        if row == destR and col == destC:  # no parentheses needed
            return path
        # reorder conditions in next IF statement
        if (row,col) in visited or row < 0 or row > len(map)-1 or col < 0 or col > len(map[0])-1 or map[row][col] != 'road':
            return None
        visited.append((row,col))
        others=[]
        others.append(self.path_helper(visited,path[:],row-1,col,destR,destC))
        others.append(self.path_helper(visited,path[:],row+1,col,destR,destC))
        others.append(self.path_helper(visited,path[:],row,col-1,destR,destC))
        others.append(self.path_helper(visited,path[:],row,col+1,destR,destC))
        others = list(filter(None, others))  # delete ALL occurrences of None
        return self.getMin(others)

There are some other things that could be improved (like using a set for visited, and not shadowing the native map function with your own variable), but the above mentioned changes will make it work.