Question
Problems with recursive functions
I have recently challenged myself to write the Depth First Search algorithm for maze generation and am on the home stretch of completing it but I have been battling a specific error for most of the final half of the project.
I use binary for notating the connections between two neighboring nodes on the tree (learn network theory if you haven't already, it's absolutely wonderful and a very relevant field to programming) which goes as follows: 0:no directions,1:left,2:right,4:up,8:down, and any of these added together with produce their directions, ie: 3:left-right, 12:up-down, 7:left-right-up...
The following function is the primary function and theoretically works for any size 2d list (not considering Python cutting me off because of too many iterations >:^<).
def DepthFirstSearch(map,inX,inY,priorPoses,iteration,seed,mapSize):
if len(priorPoses) == mapSize:
print(F"Finished in {iteration} iterations")
print(map)
return map
x = inX
y = inY
mapHold = map
history = priorPoses
random.seed(seed + iteration)
if CheckNeighbors(map, x, y) == []:
CheckPriorPositions(map,priorPoses)
print(F"Check prior positions, {CheckNeighbors(map,x,y)}")
return DepthFirstSearch(mapHold,CheckPriorPositions(map,priorPoses)[0],CheckPriorPositions(map,priorPoses)[1],
priorPoses,iteration+1,seed,mapSize)
else:
move = CheckNeighbors(map, x, y)
move = random.choice(move)
if move == 1:
mapHold[inY][inX] += move
x -= 1
mapHold[y][x] += 2
else:
if move == 2:
mapHold[inY][inX] += move
x += 1
mapHold[y][x] += 1
else:
if move == 4:
mapHold[inY][inX] += move
y += 1
mapHold[y][x] += 8
else:
if move == 8:
mapHold[inY][inX] += move
y -= 1
mapHold[y][x] += 4
history.append([x,y])
return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
The CheckNeighbors
function works perfectly fine but the CheckPriorPositions
function has been cause for concern but I can't find a problem, I'll include it anyway though. If you have any tips on it then please give a tip, I somewhat feel like I'm missing something that would completeley trivialize this CheckPriorPositions
function.
def CheckPriorPositions(map,priorPoses):
posesToSearch = priorPoses
posesToSearch.reverse()
for poses in range(0,len(posesToSearch)):
if CheckNeighbors(map,posesToSearch[poses][0],posesToSearch[poses][1]) != []:
return posesToSearch[poses]
The particular error I keep getting thrown is as follows:
Traceback (most recent call last):
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 87, in <module>
DepthFirstSearch(testMapD,0,0,testHistoryD,0,5,4)
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 46, in DepthFirstSearch
return DepthFirstSearch(mapHold,CheckPriorPositions(map,priorPoses)[0],CheckPriorPositions(map,priorPoses)[1],
TypeError: 'NoneType' object is not subscriptable
I don't really know where to start, but I do have some test data to give.
The following scenarios are simplified versions of real scenarios meant to test the functions:
testMapA = [[0,0],[0,0],[0,0]]
testHistoryA = []
DepthFirstSearch(testMapA,0,0,testHistoryA,0,5,6)
testMapB = [[4,0],[10,5],[2,9]]
testHistoryB = [[0,0],[0,1],[1,1],[1,2],[0,2]]
DepthFirstSearch(testMapB,0,2,testHistoryB,5,5,6)
testMapC = [[4,0],[14,5],[8,8]]
testHistoryC = [[0,0],[0,1],[0,2],[1,1],[1,2]]
DepthFirstSearch(testMapC,1,2,testHistoryC,5,5,6)
testMapD = [[0,0],[0,0]]
testHistoryD = []
DepthFirstSearch(testMapD,0,0,testHistoryD,0,5,4)
testMapE = [[0,0]]
testHistoryE = []
DepthFirstSearch(testMapE,0,0,testHistoryE,0,5,2)