Мы пытаемся создать программу, которая решает любой лабиринт, распознавая все перекрестки и устраняя те, которые не ведут к входу. Нам удалось создать такую программу, но мы изо всех сил пытаемся заставить точки соединиться, чтобы создать правильный путь. У кого-нибудь есть идеи, как это сделать, потому что у нас нет подсказок ... Изображение результата, но точки не соединены линией
Лабиринт в основном(n) x (n) сетка в массиве пустышек со стенами (true) и путями (false), см .: изображение лабиринта, видимого из проводника переменных
import numpy as np
import maze_utils as mu
import matplotlib.pyplot as plt
size = 101
maze, start = mu.make_maze(size)
start = [start[1],start[0]]
#------------------------------------------------------------------------------
def junctions_finder(maze, size, start):
junctions = [start]
end = []
for y, row in enumerate(maze):
for x, column in enumerate(row):
if maze[x,y] == False:
if x == 0 or x == (size-1) or y == 0 or y == (size-1):
junctions.append([y,x])
end.append([y,x])
while True:
if x+1 < size and y+1 < size and\
maze[x+1,y] == False and maze[x,y+1] == False\
or x+1 < size and y-1 > 0 and\
maze[x+1,y] == False and maze[x,y-1] == False\
or x-1 > 0 and y-1 > 0 and\
maze[(x-1),y] == False and maze[x,(y-1)] == False\
or x-1 > 0 and y+1 < size and\
maze[(x-1),y] == False and maze[x,(y+1)] == False:
junctions.append([y,x])
break
else:
break
return junctions, end
#------------------------------------------------------------------------------
def eliminate_coor(junctions, end, start):
eliminated = []
for row in junctions:
a = row[1]
b = row[0]
connections = 0
U = False
D = False
L = False
R = False
UW = False
DW = False
LW = False
RW = False
SE = False
if row == start or row == end[0]:
connections = 2
SE = True
for i in range(1,size):
if SE == False:
if a+i <= size-1 and DW == False and D == False:
if maze[a+i, b] == True:
DW = True
else:
for coor in junctions:
if [coor[1],coor[0]] == [a+i,b]:
connections = connections + 1
D = True
if a-i >= 0 and UW == False and U == False:
if maze[a-i, b] == True:
UW = True
else:
for coor in junctions:
if [coor[1],coor[0]] == [a-i,b]:
connections = connections + 1
U = True
if b+i <= size-1 and RW == False and R == False:
if maze[a, b+i] == True:
RW = True
else:
for coor in junctions:
if [coor[1],coor[0]] == [a,b+i]:
connections = connections + 1
R = True
if b-i >= 0 and LW == False and L == False:
if maze[a, b-i] == True:
LW = True
else:
for coor in junctions:
if [coor[1],coor[0]] == [a,b-i]:
connections = connections + 1
L = True
if connections < 2:
eliminated.append([b,a])
return eliminated
#------------------------------------------------------------------------------
def junction_remover(junctions, eliminated):
counter = 0
for index, row in enumerate(junctions):
for erow in (eliminated):
if erow == row:
junctions[index] = -1
counter = counter + 1
for times in range(counter):
junctions.remove(-1)
return junctions, counter
#------------------------------------------------------------------------------
junctions, end = junctions_finder(maze, size, start)
counter = 1
while counter > 0:
eliminated = eliminate_coor(junctions, end, start)
junctions, counter = junction_remover(junctions, eliminated)
start = [start[1],start[0]]
junctions.pop(0)
pyjunc = np.array(junctions)
mu.plot_maze(maze, start=start)
plt.plot(pyjunc[:,0], pyjunc[:,1], 'o')