Automatically generating start and goal positions for a maze

Question

The code below is a maze solver (taken from this answer). It uses Start and Goal positions that were manually entered, and I need to change these coordinates each time I change the image to be solved.

Thus, I want to find a way to automatically generate these positions based on the image (it is a binary image, 0 means an empty square and 1 represents a wall).

My idea so far is to make a 'walk' outside the maze wall to determine these positions. The algorithm would visit each square and if its a zero than it would be considered as an entry/exit point.

So my question is: Does anyone know a way to visit all the squares of the outside wall to determine the entry and the goal positions? Or any other idea that would help me solve this problem?

import sys
import png
from PIL import Image

# using an A* Algorithm to solve the maze

def AStar(start, goal, neighbor_nodes, distance, cost_estimate):
    def reconstruct_path(came_from, current_node):
        path = []
        while current_node is not None:
            path.append(current_node)
            current_node = came_from[current_node]
        return list(reversed(path))
    g_score = {start: 0}
    f_score = {start: g_score[start] + cost_estimate(start, goal)}
    openset = {start}
    closedset = set()
    came_from = {start: None}
    while openset:
        current = min(openset, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, goal)
        openset.remove(current)
        closedset.add(current)
        for neighbor in neighbor_nodes(current):
            if neighbor in closedset:
                continue
            if neighbor not in openset:
                openset.add(neighbor)
            tentative_g_score = g_score[current] + distance(current, neighbor)
            if tentative_g_score >= g_score.get(neighbor, float('inf')):
                continue
            came_from[neighbor] = current
            g_score[neighbor] = tentative_g_score
            f_score[neighbor] = tentative_g_score + cost_estimate(neighbor, goal)
    return []
def is_blocked(p):
    x,y = p
    pixel = path_pixels[x,y]
    if any(c < 225 for c in pixel):
        return True
def von_neumann_neighbors(p):
    x, y = p
    neighbors = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
    return [p for p in neighbors if not is_blocked(p)]
def manhattan(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
def squared_euclidean(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2 

start = (400, 984)
goal = (398, 25)

path_img = Image.open(sys.argv[1])
path_pixels = path_img.load()
distance = manhattan
heuristic = manhattan
path = AStar(start, goal, von_neumann_neighbors, distance, heuristic)
for position in path:
    x,y = position
    path_pixels[x,y] = (255,0,0) # the solution color path is red
path_img.save(sys.argv[2]) # or path_img.save('<outputfile>[.gif|.png|etc.]')

Code output:

Answer 1

The example image you posted doesn't really have an opening at the start and the end, so finding these positions would require identifying the words written on the margin.

But in general, mazes have openings in their borders, like this one:

In this case, you can do as you suggest, walking along the image edge and finding the white pixels (value 0 in your case).

The simplest way to do this in Python is to extract each of the four edges as 1D arrays, and look for contiguous groups in those.

I'm using PyDIP, because I don't have any experience with PIL. This leads to some big shortcuts, I don't have time to write out a full pixel-by-pixel algorithm. But this is what we have libraries for...

I'm hoping you see the large-scale concept here: the connected component analysis finds groups of set pixels (path pixels) that are contiguous, and treats them as a single point. The 'Center' feature simply returns the geometric centroid for the set (average the coordinates). Instead, you could pick any one of the pixels in the set.

The code below goes wrong if the assumptions that (1) the maze stretches to the image boundaries, and (2) has only two openings, are not met.

import numpy as np
import PyDIP as dip

# Starting with your `path_pixels` image:
img = np.array(path_pixels)   # convert to NumPy array by copy (so we don't modify original)
img = dip.Image(img)          # convert to PyDIP image (no copy made)
img = img == 255              # binarize, path is True/1
img = dip.Any(img, process=[False,False,True]) # if this is a color image, remove color dimension
img[1:-2,1:-2] = 0            # set image interior to 0, leaving only outer path
img = dip.Label(img)          # do connected component analysis -- should result in two regions
m = dip.MeasurementTool.Measure(img,features=['Center']) # find centroids for regions
start = m[1]['Center']        # randomly pick first region as start point
goal = m[2]['Center']         # ... and second region as goal point