Python: solve "n-to-n" maze

Question

I'm trying to write a script in python to solve a kind of maze with multiple starting points and multiple ending points. The correct path is obtained following straight lines from the starting point.

For example a maze with 4 paths:

At first I thought using the left-/right-hand rule but it does not make much sense due to the characteristics of the maze. I have tried making an algorithm to follow straight lines 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 one:

Which yields:

I have thought of using something similar but adding 4 directions more corresponding to diagonal direction.

Any other ideas to obtain good results?

Answer 1

Here is the solution that I came up with. I don't think it would be too hard to break, but it works on the test set. Also, I used pygame alongside PIL to watch the output path render as the algorithm worked. (Tkinter would not 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 is an example solution: