标签: maze

在给定图像的情况下,表示和解决迷宫的最佳方法是什么？

给定一个JPEG图像(如上所示),读取它的最佳方法是什么,将其解析为一些数据结构并解决迷宫？我的第一直觉是逐像素地读取图像并将其存储在布尔值的列表(数组)中:True对于白色像素,False对于非白色像素(可以丢弃颜色).这种方法的问题是图像可能不是"像素完美".我只是说,如果墙上的某个地方有白色像素,可能会造成意想不到的路径.

另一种方法(经过深思熟虑后来找我)是将图像转换为SVG文件 - 这是在画布上绘制的路径列表.这样,路径可以被读入相同类型的列表(布尔值),其中True指示路径或墙,False指示可行进空间.如果转换不是100%准确,并且未完全连接所有墙壁,从而产生间隙,则会出现此方法的问题.

转换为SVG的另一个问题是线条不是"完美"直线.这导致路径是立方贝塞尔曲线.使用由整数索引的布尔值列表(数组),曲线不会轻易转移,并且必须计算曲线上所有的点,但不会与列表索引完全匹配.

我假设虽然这些方法中的一种可能有用(尽管可能不是),但鉴于这么大的图像,它们的效率非常低,并且存在更好的方法.如何最好(最有效和/或最简单)完成？有没有最好的方法？

然后是迷宫的解决方案.如果我使用前两种方法中的任何一种,我基本上会得到一个矩阵.根据这个答案,表示迷宫的好方法是使用树,解决它的好方法是使用A*算法.如何从图像中创建树？有任何想法吗？

TL; DR
最好的解析方法？进入什么数据结构？该结构将如何帮助/阻碍解决？

更新
我已经尝试过实现@Mikhail用Python编写的东西numpy,正如@Thomas推荐的那样.我觉得这个算法是正确的,但它没有像希望的那样工作.(下面的代码.)PNG库是PyPNG.

import png, numpy, Queue, operator, itertools

def is_white(coord, image):
  """ Returns whether (x, y) is approx. a white pixel."""
  a = True
  for i in xrange(3):
    if not a: break
    a = image[coord[1]][coord[0] * 3 + i] > 240
  return a

def bfs(s, e, i, visited):
  """ Perform a breadth-first search. …

解决迷宫的可能方法有哪些？
我有两个想法,但我认为它们不是很优雅.

基本情况:我们有一个矩阵,在这个矩阵中的元素,因为它代表一个迷宫的方式是有序的,在一个途径,一个出.

我的第一个想法是将一个机器人穿过迷宫,沿着一侧,直到它离开迷宫.我认为这是一个非常缓慢的解决方案.

第二个通过标记1,检查它可以去(上,右,下,左)每个连续的项目选择的一种方式,它有继续它的路径.这甚至比第一个慢.

当然,如果我在每个交叉点使两个机器人多线程,它会更快一些,但这也不是最好的方法.

需要更好的解决方案来通过迷宫发送机器人.

编辑
第一:谢谢你的好答案!

我的问题的第二部分是:如果我们有一个多维图,该怎么办？有没有特殊的做法,或Justin L.的答案也适用于此？
我认为这不是这种情况的最佳方式.

第三个问题:
这些迷宫求解器算法中哪一个是最快的？(纯粹假设)

假设你想在一个N×M网格上有一个简单的迷宫,有一条路径通过,并且有很多死角,但看起来"正确"(就像有人手工制作而没有太多微小的死角而且所有那些).有没有一种已知的方法来做到这一点？

在塔防游戏中,你有一个NxM网格,有一个开始,一个完成和一些墙.

敌人从头到尾穿过最短路径而不穿过任何墙壁(它们通常不会被限制在网格上,但为了简单起见,我们可以说它们是.在任何一种情况下,它们都不能穿过对角线"洞")

问题(对于这个问题,至少)是将多达 K个追加墙壁最大化的敌人必须采取的路径.例如,对于K = 14

我的直觉告诉我这个问题是NP难的,如果(正如我希望的那样)我们将其概括为包括在移动到终点之前必须访问的路点,也可能没有路点.

但是,对于接近最优的解决方案,是否有任何体面的启发式方法？

[编辑]我在这里发布了一个相关的问题.

我正在寻找一种迷宫生成算法,可以生成没有死角但只有开始和结束的迷宫.像这样:

_{图片来自http://www.astrolog.org/labyrnth/maze/unicursl.gif}

我在哪里可以找到或者去构建这样的迷宫生成算法？

我遇到了这个非常有趣的问题,我们有一个4x4的迷宫和一个机器人试图进入目标.问题是,您必须找到一系列预定义命令,这些命令将始终导致机器人到达目标.

假设我们有一个像这样的迷宫:

x . . .
. # # .
. # # .
. . . g

这种特殊的迷宫可以用例如命令序列来解决,DDDRRR或者RRRDDD,其中R =右,L =左,U =上,D =下(duh).

然而,这些序列都不会解决这个迷宫:

x . # .
. . . .
# . . .
. . . g

机器人总是从左上角开始,目标总是在右下方,迷宫始终是2D 4x4矩阵.

我已经实现了一个算法,让我获得了78个命令的获胜序列.我确信至少存在29个命令的解决方案(其他人完成了这个).

这个问题实际上已经有几年了,所以我丢失了当时使用的算法,但基本的想法是在我生成的所有迷宫中搜索,并始终选择导致解决最多的路线迷宫.这实际上让我得到了一个略长于78的序列; 我手动减少了一些命令,我​​发现这些命令是多余的.

是的,暴力迫使需要几年的时间.

如果我的记忆服务,可能的迷宫少于4000(可能的迷宫是左上角和右下角之间的路径存在).

哦!机器人在执行命令期间至少一次访问目标就足够了.也就是说,在最后一个命令之后,它不必坐在目标上.

我有没有抓住任何人的兴趣？我应该如何处理这个问题以获得更有效的答案？谢谢你考虑:)

好玩的东西:Pastebin

这是一个(非常)匆忙拼凑的Java片段.它应该编译运行:)程序有点同时播放~4000个迷宫.程序对UP,LEFT,DOWN和RIGHT进行输入(w,a,s,d),然后模拟移动,显示一些统计数据.如果你尝试的话,你可以在屏幕上看到的是每个位置的每个迷宫中的障碍物总量,以及每个迷宫的当前位置总量.这很难解释:)问我是否有问题.

再说一遍......不要介意可怕的代码.它是在20分钟内写成的

进展

我从这个用户的答案中间接得到了这个想法(之后由于某种原因被删除),并在聊天中进一步用Mooing Duck建模.我们的想法是找到一个解决迷宫右侧的序列.也就是说,解决所有迷宫中至少一半的解决方案,并且从一开始就镜像并再次运行解决剩余的迷宫.

插图:

首先找到一个序列,其第一个命令是RIGHT,它解决了这个迷宫:

0 1 0 0
0 1 0 …

HTML

<div id="labirinth">
    <form style="text-align:center" name="forma1" autocomplete="on">
        <table style="margin:0 auto;">
            <tr>
                <td style="float:right;">Height:</td>
                <td><input type="text" id="height" name="height" autofocus="autofocus" maxlength="2" size="6" /></td>
            </tr>
            <tr>
                <td style="float:right;">Width:</td>
                <td><input type="text" id="width" name="width"  maxlength="2" size="6" /></td>
            </tr>
        </table>
    </form>
    <input type="button" alt="submit" onClick="datas();" value="New" style="margin-top:10px;" />
</div>
<pre id="out"></pre>

JavaScript的

function datas() {

    var height = parseInt(document.getElementById("height").value);
    var width = parseInt(document.getElementById("width").value);

    document.getElementById('out').innerHTML = display(maze(height,width));
}

function maze(x,y) {
    var n=x*y-1;
    if (n<0) {alert("Bad numbers!");return;}
    var horiz=[]; 
        for (var j= 0; j<x+1; j++) horiz[j]= []; …

考虑一个MxN位图,其中单元格为0或1."1"表示填充,"0"表示空.

找到位图中"孔"的数量,其中孔是空单元的连续区域.

例如,这有两个漏洞:

11111  
10101  
10101  
11111  

......这只有一个:

11111  
10001  
10101  
11111

什么是最快的方式,当M和N都在1到8之间？

澄清:对角线不被认为是连续的,只有侧面邻接很重要.

注意:我正在寻找利用数据格式的东西.我知道如何将其转换为图形和[BD] FS,但这看起来有点过分.

我正在编写一个动态迷宫游戏,每次迷宫的结构都会改变(有些门会关闭,有些门会打开.有些像HP4中的Triwazard).任何人都可以建议我哪种数据结构最适合代表这个？

你好我一直在研究一种生成随机pacman迷宫的算法.我看过几篇文章,但无法分解逻辑.我正在使用迷宫算法深度优先搜索,然后我镜像迷宫使每个迷宫对称.我遇到了清理死胡同等问题.如果这是不可能的,我也会尝试另一种算法,如果有人有自己的逻辑来生成随机迷宫.任何帮助表示赞赏.谢谢