Python: разрешить лабиринт n-to-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") 

Исходное изображение представляет собой черно-белое изображение, как это:

Что дает:

Я думал о usi что-то похожее, но добавив еще 4 направления, соответствующие диагональному направлению.

Любые другие идеи для получения хороших результатов?

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 

Вот пример решения: