Python: 解决“n对n”迷宫问题

Question

我正在尝试用Python编写脚本解决一种迷宫问题，该问题有多个起点和终点。正确的路径是从起点沿直线到达终点。

例如，一个具有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")

输入图像是一张黑白图像，就像这一张：。最终结果如下：。我考虑过类似的方法，但同时添加了四个对角方向。还有别的想法可以得到好的结果吗？

- Sabo-Tabby

---

这似乎是一个有趣的问题。我认为关键洞见是“直线”指的是通过交点，而不一定是在基准方向上。我正在研究一种实现方法，从X点开始沿着一条直线移动，直到此路线无效，然后选择新的路线。另一个有趣的方法是使用线检测器并构建线网。 - Chris

Answer 1

这是我想出来的解决方案。我认为它不会太难被破解，但它在测试集上运行良好。此外，我使用了pygame和PIL一起观察输出路径在算法工作时的渲染。(Tkinter对我来说无法工作，所以我选择了pygame。)

import sys

import math
from PIL import Image
#from pygame import *
import pygame, pygame.gfxdraw

# Float range utility - grabbed off Stackoverflow 
def xfrange(start, stop, step):
    while start < stop:
        yield start
        start += step

# Test a pixel for validity - fully white is valid if coordinate is within the image bounds
def testLocation(im, x, y) :
    # Make sure the X position is valid
    if (x < 0) or (x >= im.size[0]):
        return False

    # Make sure the Y position is valid
    if (y < 0) or (y >= im.size[1]):
        return False

    if im.getpixel((x, y)) == (255, 255, 255) :
        return True;

    return False;

# Get the next point in the path - this is brute force.  It looks for the longest
# path possible by extending a line from the current point in all directions
# (except the angle it came from - so it doesn't retrace its route) and then
# follows the longest straight line.
def getNextPoint(im, x, y, angle) :
   strengthMap = []

   # Sweep across the whole circle
   # Note: the original step of '1' did not provide enough angular resolution
   # for solving this problem.  Change this back to one and solve for the violet
   # path and it will end up following the blue path.  For thinner or longer paths,
   # this resolution might have to be even finer.
   # Also, -120:120 is not a general case range - it is a slight optimization to
   # solve this maze.  A more general solution would be +/- 175'ish - the point is
   # to prevent the "best solution" to be the last position (i.e. back tracking).
   # This should happen when the angle = angle + 180
   for i in xfrange(angle - 120.0, angle + 120.0, 0.25) :
      # Choosing a better starting value for this would be a great optimization
      distance = 2

      # Find the longest possible line at this angle
      while True :
         nextX = int(x + distance * math.cos(math.radians(i)))
         nextY = int(y + distance * math.sin(math.radians(i)))

         if testLocation(im, nextX, nextY) :
         distance = distance + 1
      else :
         # This distance failed so the previous distance was the valid one
         distance = distance - 1
         break

      # append the angle and distance to the strengthMap
      strengthMap.append((i, distance))

   # Sort the strengthMap based on the distances in descending order
   sortedMap = sorted(strengthMap, key=lambda entry: entry[1], reverse=True)

   # Choose the first point in the sorted map
   nextX = int(x + sortedMap[0][1] * math.cos(math.radians(sortedMap[0][0])))
   nextY = int(y + sortedMap[0][1] * math.sin(math.radians(sortedMap[0][0])))

   return int(nextX), int(nextY), sortedMap[0][0]

## Init Environment
path = 'c:\\maze problem\\';
maze_input = "maze_1.png";

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
    ]

defaultAngle = 0

pathToSolve = 3

pygame.init() 

image_file = Image.open(path + maze_input) # open color image
im = image_file.convert('L');
im = im.point(lambda x : 0 if x < 1 else 255, '1') # the image wasn't cleanly black and white, so do a simple threshold
im = im.convert('RGB');

# Working Globals
posX = paths[pathToSolve][0]
posY = paths[pathToSolve][1]
color = (255, 255, 255)
angle = defaultAngle

#create the screen
window = pygame.display.set_mode((640, 480))

# Load the image for rendering to the screen - this is NOT the one used for processing
maze = pygame.image.load(path + maze_input)
imagerect = maze.get_rect()

window.blit(maze, imagerect)

# Iteration counter in case the solution doesn't work
count = 0

processing = True
while processing:
   # Process events to look for exit
   for event in pygame.event.get(): 
      if event.type == pygame.QUIT: 
          sys.exit(0) 

   # Get the next point in the path
   nextPosX, nextPosY, angle = getNextPoint(im, posX, posY, angle)

   pygame.gfxdraw.line(window, posX, posY, nextPosX, nextPosY, color)
   posX = nextPosX
   posY = nextPosY

   #draw it to the screen
   pygame.display.flip() 

   count = count + 1
   if count > 20 or posX > 550:
      processing = False

这是一个示例解决方案：

- Chris

---

谢谢！我通过在初始代码中添加更多自由度的解决方案来解决了问题。然而，我必须承认从一个点找到最长的线是更好的解决方案。我将尝试使用该修改来调整我的当前解决方案。顺便说一下，我认为可能存在缩进错误，您可能希望修复它，以便其他用户不会感到困惑。再次感谢。;) - Sabo-Tabby