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") 

입력 이미지가 이와 같은 흑백 이미지는

나는 미국을 생각 해왔다. 비슷하지만 대각선 방향에 더 상응하는 4 방향 추가.

좋은 결과를 얻으려면 다른 아이디어가 필요하십니까?

Answer 1

다음은 내가 생각해 낸 해결책입니다. 나는 깨지기가 너무 어렵지 않을 것이라고 생각하지만 테스트 세트에서 작동합니다. 또한 PIL과 함께 파이 게임 (pygame)을 사용하여 알고리즘이 작동 할 때 출력 경로 렌더링을 보았습니다. (난 그냥 파이 게임으로 갔다, 그래서는 Tkinter는 나를 위해 작동하지 않을 것입니다.)

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 

는 여기에 예제 솔루션입니다 :