用数据结构解迷宫
发布网友
发布时间：2022-05-09 05:18
我来回答
共2个回答
懂视网
时间：2022-05-12 11:25
英文原文：Representing and solving a maze given an image
译注：原文是 StackOverflow 上一个如何用程序读取迷宫图片并求解的问题，几位参与者热烈地讨论并给出了自己的代码，涉及到用 Python 对图片的处理以及广度优先(BFS)算法等。
问题 by Whymarrh：
当给定上面那样一张 JPEG 图片，如何才能更好地将这张图转换为合适的数据结构并且解出这个迷宫？
我的第一直觉是将这张图按像素逐个读入，并存储在一个包含布尔类型元素的列表或数组中，其中 True 代表白色像素，False 代表非白色像素（或彩色可以被处理成二值图像）。但是这种做法存在一个问题，那就是给定的图片往往并不能完美的“像素化”。考虑到如果因为图片转换的原因，某个非预期的白色像素出现在迷宫的墙上，那么就可能会创造出一一条非预期的路径。
经过思考之后，我想出了另一种方法：首先将图片转换为一个可缩放适量图形(SVG)文件，这个文件由一个画布上的矢量线条列表组成，矢量线条按照列表的顺序读取，读取出的仍是布尔值：其中 True 表示墙，而 False 表示可通过的区域。但是这种方法如果无法保证图像能够做到百分之百的精确转换，尤其是如果不能将墙完全准确的连接，那么这个迷宫就可能出现裂缝。
图像转换为 SVG 的另一个问题是，线条并不是完美的直线。因为 SVG 的线条是三次贝塞尔曲线，而使用整数索引的布尔值列表增加了曲线转换的难度，迷宫线条上的所有点在曲线上都必须经过计算，但不一定能够完美对应列表中的索引值。
假设以上方法的确可以实现(虽然很可能都不行)，但当给定一张很大的图像时，它们还是不能胜任。那么是否存在一种更好地方法能够平衡效率和复杂度？
这就要讨论到如何解迷宫了。如果我使用以上两种方法中的任意一种，我最终将会得到一个矩阵。而根据这个问答(http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze/3097677#3097677)，一个比较好的迷宫表示方式应该是使用树的结构，并且使用A*搜索算法来解迷宫。那么如何从迷宫图片中构造出迷宫树呢？有比较好的方法么？
以上废话太多，总结起来问题就是：如何转换迷宫图片？转换成为什么样的数据结构？采用什么样的数据结构能够帮助或阻碍解迷宫？
回答 by Mikhail:
这是我的解决方案：
1. 将图片转换为灰度图像(不是直接二值)，调整不同颜色的权重使得最终的灰度看起来比较统一，你可以通过简单地调节 Photoshop 图像->调整->黑白菜单中的控制条来实现。
2. 将上一步得到的灰度图片转换为二值图片，可以通过在 PS 图像->调整->阈值菜单中设定适当的阈值来实现
3. 确保正确设置了阈值。使用魔棒工具(参数设置：容差 0、取样点、连续以及消除锯齿)选择空白区域，检查所选区域的边缘不是因为错误的阈值设置而产生的假边缘。事实上，这个迷宫中从 start 到 end 应该由联通的空白区域。
4. 人为地在迷宫外部加上边界，确保迷宫漫游者^_^不会从 start 绕着迷宫跑到终点。:)
5. 选择语言实现广度优先搜索算法(BFS)，从 start 处开始让程序运行。下面的代码我选择用 Matlab 实现。正如 Thomas 提到的，没必要纠结于图像的表示形式，你可以直接在二值图像上运行。
以下是用 MATLAB 实现的 BFS 代码：
function path = solve_maze(img_file)
%% Init data
img = imread(img_file);
img = rgb2gray(img);
maze = img > 0;
start = [985 398];
finish = [26 399];
%% Init BFS
n = numel(maze);
Q = zeros(n, 2);
M = zeros([size(maze) 2]);
front = 0;
back = 1;
function push(p, d)
q = p + d;
if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0
front = front + 1;
Q(front, :) = q;
M(q(1), q(2), :) = reshape(p, [1 1 2]);
end
end
push(start, [0 0]);
d = [0 1; 0 -1; 1 0; -1 0];
%% Run BFS
while back <= front
p = Q(back, :);
back = back + 1;
for i = 1:4
push(p, d(i, :));
end
end
%% Extracting path
path = finish;
while true
q = path(end, :);
p = reshape(M(q(1), q(2), :), 1, 2);
path(end + 1, :) = p;
if isequal(p, start)
break;
end
end
end
这是个简单的实现，应该很容易就能够改写为 Python 或其他语言，下面是程序的运行结果：
提问者更新：
我用 Python 实现了一下 Mikhail 的方法，其中用到了 numpy 库，感谢 Thomas 推荐。我感觉这个算法是正确的，但是效果不太如预期，以下是相关代码，使用了 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. """
frontier = Queue.Queue()
while s != e:
for d in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
np = tuple(map(operator.add, s, d))
if is_white(np, i) and np not in visited:
frontier.put(np)
visited.append(s)
s = frontier.get()
return visited
def main():
r = png.Reader(filename = "thescope-134.png")
rows, cols, pixels, meta = r.asDirect()
assert meta['planes'] == 3 # ensure the file is RGB
image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
start, end = (402, 985), (398, 27)
print bfs(start, end, image2d, [])
回答 by Joseph Kern：
#!/usr/bin/env python
import sys
from Queue import Queue
from PIL import Image
start = (400,984)
end = (398,25)
def iswhite(value):
if value == (255,255,255):
return True
def getadjacent(n):
x,y = n
return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]
def BFS(start, end, pixels):
queue = Queue()
queue.put([start]) # Wrapping the start tuple in a list
while not queue.empty():
path = queue.get()
pixel = path[-1]
if pixel == end:
return path
for adjacent in getadjacent(pixel):
x,y = adjacent
if iswhite(pixels[x,y]):
pixels[x,y] = (127,127,127) # see note
new_path = list(path)
new_path.append(adjacent)
queue.put(new_path)
print "Queue has been exhausted. No answer was found."
if __name__ == '__main__':
# invoke: python mazesolver.py [.jpg|.png|etc.]
base_img = Image.open(sys.argv[1])
base_pixels = base_img.load()
path = BFS(start, end, base_pixels)
path_img = Image.open(sys.argv[1])
path_pixels = path_img.load()
for position in path:
x,y = position
path_pixels[x,y] = (255,0,0) # red
path_img.save(sys.argv[2])
动态执行效果：
回答 by Jim
使用树搜索太繁杂了，迷宫本身就跟解路径是可分的。正因如此，你可以使用连通区域查找算法来标记迷宫中的连通区域，这将迭代搜索两次这些像素点。如果你想要更好地解决方法，你可以对结构单元使用二元运算(binary operations)来填充每个连通区域中的死路。
下面是相关的 MATLAB 代码及运行结果：
% read in and invert the image
im = 255 - imread('maze.jpg');
% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));
% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
[count,~] = size(find(result==i));
if count < 500
result(result==i) = 0;
end
end
% close dead-end channels
closed = zeros(1002,800);
for i = 1:max(reshape(result,1,1002*800))
k = zeros(1002,800);
k(result==i) = 1; k = imclose(k,strel('square',8));
closed(k==1) = i;
end
% do output
out = 255 - im;
for x = 1:1002
for y = 1:800
if closed(x,y) == 0
out(x,y,:) = 0;
end
end
end
imshow(out);
回答 by Stefano
stefano 童鞋给出了生成搜索过程 GIF 及 AVI 文件的代码 maze-solver-python (GitHub)
热心网友
时间：2022-05-12 08:33
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#define N 20/*迷宫的大小，可改变*/
int oldmap[N][N];/*递归用的数组,用全局变量节约时间*/
int yes=0;/*yes是判断是否找到路的标志,1找到，0没找到*/
int way[100][2],wayn=0;/*way数组是显示路线用的,wayn是统计走了几个格子*/
void Init(void);/*图形初始化*/
void Close(void);/*图形关闭*/
void DrawPeople(int *x,int *y,int n);/*画人工探索物图*/
void PeopleFind(int (*x)[N]);/*人工探索*/
void WayCopy(int (*x)[N],int (*y)[N]);/*为了8个方向的递归，把旧迷宫图拷贝给新数组*/
int FindWay(int (*x)[N],int i,int j);/*自动探索函数*/
void MapRand(int (*x)[N]);/*随机生成迷宫函数*/
void PrMap(int (*x)[N]);/*输出迷宫图函数*/
void Result(void);/*输出结果处理*/
void Find(void);/*成功处理*/
void NotFind(void);/*失败处理*/
void main(void)/*主函数*/
{
int map[N][N]; /*迷宫数组*/
char ch;
clrscr();
printf("\n Please select hand(1) else auto\n");/*选择探索方式*/
scanf("%c",&ch);
Init(); /*初始化*/
MapRand(map);/*生成迷宫*/
PrMap(map);/*显示迷宫图*/
if(ch=='1')
PeopleFind(map);/*人工探索*/
else
FindWay(map,1,1);/*系统自动从下标1,1的地方开始探索*/
Result();/*输出结果*/
Close();
}
void Init(void)/*图形初始化*/
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\tc");
}
void DrawPeople(int *x,int *y,int n)/*画人工控制图*/
{/*如果将以下两句注释掉，则显示人工走过的路径，*/
setfillstyle(SOLID_FILL,WHITE); /*设置白色实体填充样式*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
/*恢复原通路*/
switch(n)/*判断x,y的变化，8个方向的变化*/
{
case 1: (*x)--;break; /*上*/
case 2: (*x)--;(*y)++;break ;/*右上*/
case 3: (*y)++;break; /*右*/
case 4: (*x)++;(*y)++;break; /*右下*/
case 5: (*x)++;break; /*下*/
case 6: (*x)++;(*y)--;break; /*左下*/
case 7: (*y)--;break; /*左*/
case 8: (*x)--;(*y)--;break; /*左上*/
}
setfillstyle(SOLID_FILL,RED);/*新位置显示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
}
void PeopleFind(int (*map)[N])/*人工手动查找*/
{
int x,y;
char c=0;/*接收按键的变量*/
x=y=1;/*人工查找的初始位置*/
setcolor(11);
line(500,200,550,200);
outtextxy(570,197,"d");
line(500,200,450,200);
outtextxy(430,197,"a");
line(500,200,500,150);
outtextxy(497,130,"w");
line(500,200,500,250);
outtextxy(497,270,"x");
line(500,200,450,150);
outtextxy(445,130,"q");
line(500,200,550,150);
outtextxy(550,130,"e");
line(500,200,450,250);
outtextxy(445,270,"z");
line(500,200,550,250);
outtextxy(550,270,"c");/*以上是画8个方向的控制介绍*/
setcolor(YELLOW);
outtextxy(420,290,"Press 'Enter' to end");/*压回车键结束*/
setfillstyle(SOLID_FILL,RED);
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置显示*/
while(c!=13)/*如果按下的不是回车键*/
{
c=getch();/*接收字符后开始各个方向的探索*/
if(c=='w'&&map[x-1][y]!=1)
DrawPeople(&x,&y,1);/*上*/
else
if(c=='e'&&map[x-1][y+1]!=1)
DrawPeople(&x,&y,2);/*右上*/
else
if(c=='d'&&map[x][y+1]!=1)
DrawPeople(&x,&y,3);/*右*/
else
if(c=='c'&&map[x+1][y+1]!=1)
DrawPeople(&x,&y,4);/*右下*/
else
if(c=='x'&&map[x+1][y]!=1)
DrawPeople(&x,&y,5);/*下*/
else
if(c=='z'&&map[x+1][y-1]!=1)
DrawPeople(&x,&y,6); /*左下*/
else
if(c=='a'&&map[x][y-1]!=1)
DrawPeople(&x,&y,7); /*左*/
else if(c=='q'&&map[x-1][y-1]!=1)
DrawPeople(&x,&y,8); /*左上*/
}
setfillstyle(SOLID_FILL,WHITE); /*消去红色探索物，恢复原迷宫图*/
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);
if(x==N-2&&y==N-2)/*人工控制找成功的话*/
yes=1; /*如果成功标志为1*/
}
void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷贝迷宫数组 */
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
oldmap[i][j]=map[i][j];
}
int FindWay(int (*map)[N],int i,int j)/*递归找路*/
{
if(i==N-2&&j==N-2)/*走到出口*/
{
yes=1;/*标志为1,表示成功*/
return;
}
map[i][j]=1;/*走过的地方变为1*/
WayCopy(oldmap,map); /*拷贝迷宫图*/
if(oldmap[i+1][j+1]==0&&!yes)/*判断右下方是否可走*/
{
FindWay(oldmap,i+1,j+1);
if(yes)/*如果到达出口了，再把值赋给显示路线的way数组,也正是这个原因,所以具体路线是从最后开始保存*/
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j]==0&&!yes)/*判断下方是否可以走,如果标志yes已经是1也不用找下去了*/
{
FindWay(oldmap,i+1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j+1]==0&&!yes)/*判断右方是否可以走*/
{
FindWay(oldmap,i,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j]==0&&!yes)/*判断上方是否可以走*/
{
FindWay(oldmap,i-1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j+1]==0&&!yes)/*判断右上方是否可以走*/
{
FindWay(oldmap,i-1,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j-1]==0&&!yes)/*判断左下方是否可以走*/
{
FindWay(oldmap,i+1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j-1]==0&&!yes)/*判断左方是否可以走*/
{
FindWay(oldmap,i,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j-1]==0&&!yes)/*判断左上方是否可以走*/
{
FindWay(oldmap,i-1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
return;
}
void MapRand(int (*map)[N])/*开始的随机迷宫图*/
{
int i,j;
cleardevice();/*清屏*/
randomize(); /*随机数发生器*/
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈为墙壁*/
map[i][j]=1;
else
if(i==1&&j==1||i==N-2&&j==N-2)/*出发点与终点表示为可走的*/
map[i][j]=0;
else
map[i][j]=random(2);/*其它的随机生成0或1*/
}
}
}
void PrMap(int (*map)[N])/*输出迷宫图*/
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(map[i][j]==0)
{
setfillstyle(SOLID_FILL,WHITE);/*白色为可走的路*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
else
{
setfillstyle(SOLID_FILL,BLUE);/*蓝色为墙壁*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
}
void Find(void)/*找到通路*/
{
int i;
setfillstyle(SOLID_FILL,RED);/*红色输出走的具体路线*/
wayn--;
for(i=wayn;i>=0;i--)
{
bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+
way[i][1]*15+6,50+way[i][0]*15+6);
sleep(1);/*控制显示时间*/
}
bar(100+(N-2)*15-6,50+(N-2)*15-6,100+
(N-2)*15+6,50+(N-2)*15+6); /*在目标点标红色*/
setcolor(GREEN);
settextstyle(0,0,2);/*设置字体大小*/
outtextxy(130,400,"Find a way!");
}
void NotFind(void)/*没找到通路*/
{
setcolor(GREEN);
settextstyle(0,0,2);/*设置字体大小*/
outtextxy(130,400,"Not find a way!");
}
void Result(void)/*结果处理*/
{
if(yes)/*如果找到*/
Find();
else/*没找到路*/
NotFind();
getch();
}
void Close(void)/*图形关闭*/
{
closegraph();
}
另外一个，是数据结构的：
#include<stdio.h>
#define NUM 10/* 定义物品总数*/
#define CONTENT 10 /*定义包的容量*/
void knapsack(int v[NUM],int w[NUM],int c,int m[NUM ][CONTENT])
{
int n=NUM-1;
int i,j;
int jMax;
if((w[n]-1)< c)
jMax = w[n]-1;
else
jMax = c;
/* 初始化m[n][j] */
for(j = 0; j <= jMax; j++)
m[n][j] = 0;
for(j = jMax +1; j <= c; j++)
m[n][j] = v[n];
/*使用非递归的算法来求解m[i][j] */
for(i = n-1; i > 0; i--)
{
if((w[i]-1)< c)
jMax = w[i]-1;
else
jMax = c;
for(j = 0; j <= jMax; j++)
m[i][j] = m[i+1][j] ;
for(j = jMax +1; j <= c; j++)
{
if(m[i+1][j] >= (m[i+1][j-w[i]]+v[i]))
m[i][j] = m[i+1][j] ;
else
m[i][j] = m[i+1][j-w[i]]+v[i];
}
}
if(c>w[0])
{
if(m[1][c] >= (m[1][c-w[0]]+v[0]))
m[0][c]= m[1][c];
else
m[0][c]= m[1][c-w[0]]+v[0];
}
else
m[0][c]= m[1][c];
}
/*寻找最优解*/
void traceback(int flag[NUM],int w[NUM],int m[NUM][CONTENT])
{
int n = NUM -1;
int i;
int c = CONTENT;
for(i = 0; i < n; i++)
{
if(m[i][c] == m[i+1][c])
flag[i] = 0;
else
{
flag[i] = 1;
c-=w[i];
}
}
if(m[n][c] >0)
flag[n] = 1;
else
flag[n] = 0;
}
/* 打印最优解*/
void printResult(int flag[NUM],int w[NUM],int v[NUM],int m[NUM][CONTENT])
{
int i;
printf("the knapsack should contain:\n");
printf(" num weight value \n");
for(i = 0;i < NUM; i++)
{
if(flag[i] == 1)
printf(" %d %d %d\n",i,w[i],v[i]);
}
printf("the max value in the knapsack is: %d\n",m[0][CONTENT]);
}
int main()
{
int value[NUM]={5,2,3,4,3,6,5,7,8,2};
int weight[NUM]={2,1,3,2,4,3,5,6,2,2};
int c = CONTENT;
int maxvalue[NUM][CONTENT];
int flag[NUM]={0,0,0,0,0,0,0,0,0,0};
clrscr();
printf("****************************************\n");
printf("* this program will solve *\n");
printf("* the problem of 0-1knapsack *\n");
printf("****************************************\n");
/*计算最优值*/
knapsack(value,weight,c,maxvalue);
/*构造最优解*/
traceback(flag,weight,maxvalue);
/*打印程序的结果*/
printResult(flag,weight,value,maxvalue);
getch();
return 0;
}
