Python: resolve "n-to-n" maze
I am trying to write a script in python to solve some kind of maze with multiple start points and multiple end points. The correct path is obtained in straight lines from the starting point.
For example, a maze with 4 tracks:
At first I thought using the left / right rule, but that doesn't make much sense due to the characteristics of the maze. I tried to make an algorithm to follow straight lines by following 4 directions (up, down, left, right).
What I have at the moment:
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")
The input image is a black and white image like this:
What gives:
I thought about using something like this, but added 4 directions more in line with the diagonal direction.
Any other ideas for getting good results?
+3
source to share
1 answer
Here is the solution I came across. I don't think it would be too hard to break, but it works on a test suite. Also, I used pygame along with PIL to watch the output path how the algorithm works. (Tkinter doesn't work for me, so I just went with 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
Here's an example solution:
+1
source to share