自动生成迷宫的起点和目标位置 [英] Automatically generating start and goal positions for a maze

问题描述

以下代码是迷宫求解器（取自，因为我对PIL没有任何经验。这导致一些大的快捷方式，我没有时间写出完整的逐像素算法。但这就是我们拥有的库... ...

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

如果假设（1）迷宫延伸到图像边界，则下面的代码出错了， （2）只有两个开口，不符合。

  import numpy as np 
 import PyDIP as dip 
 
＃从你的`path_pixels`图像开始：
 img = np.array（path_pixels）＃通过复制转换为NumPy数组（所以我们不修改原文）
 img = dip .Image（img）＃转换为PyDIP图像（没有复制）
 img = img == 255＃binarize，path is True / 1 
 img = dip.Any（img，process = [False， False，True]）＃如果这是一个彩色图像，删除颜色维度
 img [1：-2,1：-2] = 0＃将图像内部设置为0，只留下外部路径
 img = dip.Label（img）#do connected component analysis  - 应该产生两个区域
m = dip.MeasurementTool.Measure（img，features = ['Center']）#find totrotroids for regions 
 start = m [1] ['中心'] ＃随机选择第一个区域作为起点
 goal = m [2] ['Center']＃...和第二个区域作为目标点
  

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:

解决方案

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

这篇关于自动生成迷宫的起点和目标位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！