自动生成迷宫的起点和终点位置

Question

下面的代码是一个迷宫求解器（取自this answer）。它使用手动输入的开始和目标位置，每次更改要求解的图像时都需要更改这些坐标。

因此，我想找到一种方法来根据图像自动生成这些位置（它是二值图像，0表示空方块，1表示墙）。

目前我的想法是在迷宫墙外做一个'walk'来确定这些位置。该算法将访问每个正方形，如果它是零，则它将被视为 entry/exit 点。

所以我的问题是：有谁知道访问外墙所有方格以确定入口和目标位置的方法吗？或者任何其他可以帮助我解决这个问题的想法？

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.]')

代码输出：

Answer 1

您发布的示例图片在开始和结束时并没有真正的开口，因此找到这些位置需要识别页边空白处的文字。

但一般来说，迷宫的边界都有开口，就像这个：

在这种情况下，您可以按照您的建议进行，沿着图像边缘行走并找到白色像素（在您的情况下值为 0）。

在 Python 中执行此操作的最简单方法是将四个边缘中的每一个提取为一维数组，并在其中寻找连续的组。

我正在使用 PyDIP，因为我没有任何 PIL 经验。这导致了一些大的捷径，我没有时间写出一个完整的逐像素算法。但这就是我们拥有图书馆的目的...

我希望你在这里看到大尺度的概念：连通分量分析找到一组连续的集合像素（路径像素），并将它们视为一个点。 'Center' 特征只是 returns 集合的几何质心（平均坐标）。相反，您可以选择集合中的任何一个像素。

如果不满足 (1) 迷宫延伸到图像边界，以及 (2) 只有两个开口的假设，下面的代码就会出错。

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

自动生成迷宫的起点和终点位置

Automatically generating start and goal positions for a maze

python

maze

image-processing