我想在Python中编写一个脚本来解决一种具有多个起点和多个终点的迷宫。从起点开始沿着直线获得正确的路径。Python:解决“n对n”的迷宫
例如,具有4路的迷宫:
起初我以为使用左/右手法则,但它不因迷宫的特点太大的意义。我试图制定一个遵循4个方向(上,下,左,右)的直线算法。
我有什么的时刻:
from PIL import Image
UP='up'
DOWN='down'
LEFT='left'
RIGHT='right'
directionOld=RIGHT
def checkAdjacents(im,x,y):
matrix=[]
for Y in range(y-1,y+2):
r=[]
for X in range(x-1,x+2):
if im.getpixel((X,Y))==255:
r.append(True)
else:
r.append(False)
matrix.append(r)
return matrix
def testDirection(adj,direction):
if direction==UP and adj[0][1]:
return False
if direction==LEFT and adj[1][0]:
return False
if direction==RIGHT and adj[1][2]:
return False
if direction==DOWN and adj[2][1]:
return False
return True
def changeDirection(adj,direction):
if direction==UP or direction==DOWN:
if adj[1][2]:
direction=RIGHT
else:
direction=LEFT
else:
if adj[2][1]:
direction=DOWN
else:
direction=UP
return direction
def move(im,im2,x,y,directionOld,color):
im2.putpixel((x,y),color)
adj=checkAdjacents(im,x,y)
change=testDirection(adj,directionOld)
directionNew=directionOld
if change:
directionNew=changeDirection(adj,directionOld)
print "New direction ->",directionNew
if directionNew==UP:
y-=1
elif directionNew==DOWN:
y+=1
elif directionNew==RIGHT:
x+=1
else:
x-=1
return (x,y,directionNew)
image_file = Image.open("maze.png") # open colour image
im = image_file.convert('1') # convert image to black and white
im.save("2.png")
im2=im.copy() #duplicate to store results
im2=im2.convert("RGB") #results in color
paths=[(114,110,(255,0,255)),#Path1
(114,178,(255,0,0)),#Path2
(114,250,(0,255,0)),#Path3
(114,321,(0,0,255)),#Path4
]
for path in paths:
print "------------------------------------"
print "----------------Path"+str(paths.index(path))+"---------------"
print "------------------------------------"
x,y,color=path
for i in range(0,750):#number of steps
x,y,directionOld=move(im,im2,x,y,directionOld,color)
im2.save("maze_solved.png")
输入图像是这样一个黑白图像:
其中产量:
我想到了usi类似的东西,但增加4个方向更对应的对角线方向。
任何其他想法,以获得良好的结果?
这似乎是一个有趣的问题。我认为关键的见解是“直线”意味着通过交叉点,而不一定是在主要方向。我正在玩一个从X点开始的实现,并沿着一条直线移动,直到路径沿着该线无效,此时它将选择一条新线。另一个有趣的方法是使用线路检测器并建立线路网络。 – Chris 2014-10-23 21:34:39