Python: Solve "n-to-n" Maze

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

Solution 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 defxfrange(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 boundsdeftestLocation(im, x, y) :
    # Make sure the X position is validif (x < 0) or (x >= im.size[0]):
        returnFalse# Make sure the Y position is validif (y < 0) or (y >= im.size[1]):
        returnFalseif im.getpixel((x, y)) == (255, 255, 255) :
        returnTrue;

    returnFalse;

# 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.defgetNextPoint(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 + 180for 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 anglewhileTrue :
         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 + 1else :
         # This distance failed so the previous distance was the valid one
         distance = distance - 1break# 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])))

   returnint(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 : 0if x < 1else255, '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 = Truewhile processing:
   # Process events to look for exitfor 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 + 1if count > 20or posX > 550:
      processing = False

Here is an example solution: