Trying to create a program that solves mazes, but it is getting stuck in specific paths
So, basically, I'm trying to code a program that solves mazes. I did many tests with different mazes and I realize that my program isn't able to solve all kinds of mazes, only a few, since there some specific dead ends that my program gets stuck and cannot go back.
The logic behind my code is basically something that runs all over the maze until it finds the exit, and, if it finds a dead end during this processes, it should be able to go back and find a new unexplored path.
My code was working well until I start to test it with more complex mazes with different kinds of tricky dead ends. For Example:
maze = (
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,1,1,1,0,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,1,0,0,0,0,0,1],
[1,1,1,0,1,1,1,0,1,0,1,0,1,0,1],
[1,1,1,0,1,0,1,0,1,0,1,1,1,0,1],
[1,1,1,1,1,0,1,0,1,0,0,1,0,0,1],
[1,1,0,0,0,0,1,0,1,1,0,1,0,1,1],
[1,1,0,1,1,0,0,0,0,1,0,1,0,1,1],
[1,1,0,0,1,1,0,1,0,1,0,1,0,0,1],
[1,1,0,1,0,0,1,0,0,0,1,0,0,1,1],
[1,1,1,1,1,1,1,1,1,1,1,3,1,1,1]
)
This an example of a maze with dead ends that my program can solve, whereupon 1 is a wall, 0 is a free path, 3 is the end and the beginning is maze[1][1]
maze = (
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
[1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
[1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
[1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
[1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
[1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
[1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
[1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
[1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
)
Now a maze that my program cannot solve. I suppose that the problem with this maze is that it has dead ends with an "L" shape or something like a zigzag, but to be honest, I don't know what is happening. For example, the dead end in maze[5][5] (where my program is stuck)
Before showing the code I want to explain some topics about it:
- All the strings that I'm printing are in English and in Portuguese, the languages are separated by "/" so don't worry about that.
- To explore the maze the program uses a recursive strategy and mark with 2 the paths that were explored.
- The program works with x and y coordinates based on the array. x + 1 goes down, x - 1 goes up, y + 1 goes right and y - 1 goes left.
- If it gets stuck in a dead end, the strategy is looking at what is around to discover which kind of dead end it is, and then going back until it finds a new path marked with 0.
Those are the cases of dead ends that you will see in my code.
- If possible I want some tips about how can I improve my code or make it clean.
So, here we go:
maze = (
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
[1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
[1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
[1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
[1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
[1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
[1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
[1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
[1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
)
def solve(x, y):
if maze[x][y] == 0 or maze[x][y] == 2:
# To walk around and explore the maze
print('Visiting/Visitando xy({},{})'.format(x, y))
maze[x][y] = 2
if x < (len(maze) - 1) and (maze[x + 1][y] == 0 or maze[x + 1][y] == 3):
solve(x + 1, y)
elif y < (len(maze) - 1) and (maze[x][y + 1] == 0 or maze[x][y + 1] == 3):
solve(x, y + 1)
elif x > 0 and (maze[x - 1][y] == 0 or maze[x][y + 1] == 3):
solve(x - 1, y)
elif y > 0 and (maze[x][y - 1] == 0 or maze[x][y + 1] == 3):
solve(x, y - 1)
else:
# If it gets stuck in a dead end
step_back = 1
dead_end = True
# each possible kind of dead ends and the strategy to go back
if (maze[x + 1][y] == 1 or maze[x + 1][y] == 2) and maze[x][y - 1] == 1 and \
maze[x][y + 1] == 1 and maze[x - 1][y] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x - step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
solve(x - step_back, y - 1)
elif maze[x - step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
solve(x - step_back, y + 1)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x - step_back, y)
elif (maze[x - 1][y] == 1 or maze[x - 1][y] == 2) and maze[x][y - 1] == 1 and \
maze[x][y + 1] == 1 and maze[x + 1][y] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x + step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
solve(x + step_back, y - 1)
elif maze[x + step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
solve(x + step_back, y + 1)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x + step_back, y)
elif (maze[x][y + 1] == 1 or maze[x][y + 1] == 2) and maze[x + 1][y] == 1 and \
maze[x - 1][y] == 1 and maze[x][y - 1] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
solve(x - step_back, y)
elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
solve(x + step_back, y)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x, y + step_back)
elif (maze[x][y - 1] == 1 or maze[x][y - 1] == 2) and maze[x + 1][y] == 1 and \
maze[x - 1][y] == 1 and maze[x][y + 1] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
solve(x - step_back, y)
elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
solve(x + step_back, y)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x, y - step_back)
# to check if the end of the maze were found
if maze[x + 1][y] == 3 or maze[x - 1][y] == 3 or maze[x][y + 1] == 3 or maze[x][y - 1] == 3:
print('Exit found in/Saída encontrada em xy({},{})'.format(x, y))
solve(1,1)
Solution
A simple bfs/dfs is enough to solve this problem. just start from the initial position and keep track of all the nodes that have been covered. If you reach any deadend or if any of the positions is repeated, you can just terminate this path. If you reach the final state, output the current path.
You can find more information about this algorithm here.
- Precompiled sasl python 3.9+ package for windows
- Regex: Substitute pattern in string multiple times without leftovers
- How to render raw html in the PyHTML library
- Why does my implementation of trilateration give wrong results?
- Django admin: how to sort by one of the custom list_display fields that has no database field
- TypeError: not all arguments converted during string formatting - psycopg2
- How to cancel trigonometric expressions in SymPy
- Is there a Python equivalent of the C# null-coalescing operator?
- Kraken API - Account balances request returning Invalid Nonce
- configparser without whitespace surrounding operator
- Pytorch tensor to numpy array
- Django: How to get a person whose birthday is today from a database?
- How can I do a line break (line continuation) in Python (split up a long line of source code)?
- Using pydantic to change int to string
- Breaking long method chains into multiple lines in Python
- What do ** (double star/asterisk) and * (star/asterisk) mean in a function call?
- How to install Pygame on Python 3.4?
- Rotating values in a list [Python]
- Launch default image viewer from pygtk program
- what's the inverse of the quantile function on a pandas Series?
- How can I install packages using pip according to the requirements.txt file from a local directory?
- Python generate all n-permutations of n lists
- FastAPI error when handling file together with form-data defined in a Pydantic model
- How to pick just one item from a generator?
- How Can I Run a Streamlit App from within a Python Script?
- How to create possible sets of n numbers from m-sized prime number list?
- Scikit dendrogram: How to disable ouput?
- Gaussian Addition - Python Challenge
- How to compute scipy sparse matrix determinant without turning it to dense?
- Navigate Firefox with Selenium