i create this simple maze solver in python following the right-hand rule, and i'm trying to save only the right path, how do i do it?
import matplotlib.pyplot as plt
m = [[0,0,1,0,0],
[0,0,1,1,0],
[0,0,0,1,1],
[0,1,1,1,0],
[0,1,0,1,0]]
Pf = (0,2)
w = (1,0)
a = (0,1)
s = (-1,0)
d = (0,-1)
Pi = (4,1)
Dir = (1,0)
# Almacenaremos nuestro recorrido, comenzando por la entrada
Recorrido = [Pi]
while Pi != Pf:
if Dir == w:
try:
op1 = m[Pi[0]][Pi[1]+1]
except IndexError:
op1 = None
try:
op2 = m[Pi[0]-1][Pi[1]]
except IndexError:
op2 = None
try:
op3 = m[Pi[0]][Pi[1]-1]
except IndexError:
op3 = None
try:
op4 = m[Pi[0]+1][Pi[1]]
except IndexError:
op4 = None
if op1 == 1:
Pa = (Pi[0],Pi[1]+1)
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op2 == 1:
Pa = (Pi[0]-1,Pi[1])
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op3 == 1:
Pa = (Pi[0],Pi[1]-1)
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op4 == 1:
Pa = (Pi[0]+1,Pi[1])
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif Dir == a:
try:
op1 = m[Pi[0]-1][Pi[1]]
except IndexError:
op1 = None
try:
op2 = m[Pi[0]][Pi[1]-1]
except IndexError:
op2 = None
try:
op3 = m[Pi[0]+1][Pi[1]]
except IndexError:
op3 = None
try:
op4 = m[Pi[0]][Pi[1]+1]
except IndexError:
op4 = None
if op1 == 1:
Pa = (Pi[0]-1,Pi[1])
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op2 == 1:
Pa = (Pi[0],Pi[1]-1)
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op3 == 1:
Pa = (Pi[0]+1,Pi[1])
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op4 == 1:
Pa = (Pi[0],Pi[1]+1)
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif Dir == s:
try:
op1 = m[Pi[0]][Pi[1]-1]
except IndexError:
op1 = None
try:
op2 = m[Pi[0]+1][Pi[1]]
except IndexError:
op2 = None
try:
op3 = m[Pi[0]][Pi[1]+1]
except IndexError:
op3 = None
try:
op4 = m[Pi[0]-1][Pi[1]]
except IndexError:
op4 = None
if op1 == 1:
Pa = (Pi[0],Pi[1]-1)
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op2 == 1:
Pa = (Pi[0]+1,Pi[1])
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op3 == 1:
Pa = (Pi[0],Pi[1]+1)
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op4 == 1:
Pa = (Pi[0]-1,Pi[1])
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif Dir == d:
try:
op1 = m[Pi[0]+1][Pi[1]]
except IndexError:
op1 = None
try:
op2 = m[Pi[0]][Pi[1]+1]
except IndexError:
op2 = None
try:
op3 = m[Pi[0]-1][Pi[1]]
except IndexError:
op3 = None
try:
op4 = m[Pi[0]][Pi[1]-1]
except IndexError:
op4 = None
if op1 == 1:
Pa = (Pi[0]+1,Pi[1])
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op2 == 1:
Pa = (Pi[0],Pi[1]+1)
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op3 == 1:
Pa = (Pi[0]-1,Pi[1])
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
elif op4 == 1:
Pa = (Pi[0],Pi[1]-1)
giro = (Pi[0]-Pa[0],Pi[1]-Pa[1])
if giro == w:
Dir = (1,0)
if giro == a:
Dir = (0,1)
if giro == s:
Dir = (-1,0)
if giro == d:
Dir = (0,-1)
Pi = Pa
Recorrido.append(Pi)
# Almacenamos el recorrido en coordenadas y lo mostramos en una imagen
x, y = zip(*Recorrido)
plt.imshow(m, cmap='gray')
for i in range(len(x)):
plt.plot(y[:i+1], x[:i+1], 'r')
plt.pause(0.25)
plt.pause(1.5)
plt.close()
In the final version i read an excel matrix of 50x50, but it's the same at the end.
I have tried created another parallel matriz of the same dimensions full of zeros, and increases the value of the element having a path where the right path is only 1's, but at the end of the dead end also have a 1, so when i plot the path, also plot that final element of the dead end.
How do i save the entrance of the dead end to go back to him and continue with the right path?
There is too much code repetition in your attempt. When you have several blocks of code which look similar or even the same, then look for ways to avoid this repetition.
In this particular case you'll benefit from storing all directions in a sequence instead of using separate variables for each direction.
To avoid that the path includes the backtracking out of a dead-end, compare the new position with the position you were at 2 steps before. If that position is the same, then it means you are backtracking, and instead of adding the new position to the list, remove the wrong one.
Here is an implementation:
def solve(m, start, end):
height = len(m)
width = len(m[0])
directions = ((0,1), (-1,0), (0,-1), (1,0))
direction = 0 # index in directions
y, x = start
path = [start]
while (y, x) != end:
for direction in range(direction + 3, direction + 7):
direction %= 4 # map the direction to a valid range
nexty = y + directions[direction][0]
nextx = x + directions[direction][1]
if 0 <= nextx < width and 0 <= nexty < height and m[nexty][nextx]:
break # Found a direction to go to
x, y = nextx, nexty # make the move
if len(path) > 1 and (y, x) == path[-2]: # did we go back?
path.pop() # remove the wrong place we went to
else:
path.append((y, x))
return path
Call it like this:
m = [[0,0,1,0,0],
[0,0,1,1,0],
[0,0,0,1,1],
[0,1,1,1,0],
[0,1,0,1,0]]
path = solve(m, (4, 1), (0, 2))
x, y = zip(*path)
# The drawing code comes here:
plt.imshow(m, cmap='gray')
for i in range(len(x)):
plt.plot(y[:i+1], x[:i+1], 'r')
plt.pause(0.25)
plt.pause(5)
plt.close()