Python 中迷宫求解程序的性能改进
Improvement of performance for a maze solving program in Python
各位程序员。我的一个项目需要帮助。我正在制作一个迷宫解决程序。它读取一个图像文件，它必须是黑白的（黑色像素是墙壁，白色像素是路径），顶部只有一个像素是迷宫的入口，底部只有一个白色像素是迷宫的入口出口。
代码主要分为三个部分：
1) 程序首先根据一组规则在迷宫中创建节点。例如这里有一个简单的迷宫：
这里是所有用红色绘制的节点：
节点就像拐角，十字路口，每一个可以改变方向的点。每个节点和迷宫出口之间的距离也被测量。当它生成所有节点时，它会将它们放在一个列表中。
2) 一旦生成了所有节点，程序将遍历列表中的所有节点，并尝试在每个可能的方向搜索其他节点，到 "link" 它们，建立可能的路径。例如，如果它检测到节点上方有一条路径，它将从该节点的坐标开始搜索一行中的每个像素，然后向上，再次遍历所有节点列表以查看是否有另一个节点匹配这些坐标。如果它在某个时候找到了一个，它会 link 发送它们，然后开始向右搜索（当然如果有一条向右的路径），等等每个方向。
3) 一旦所有的节点都link在一起并且每条可能的路径都建立了，它将从迷宫的入口节点开始，运行 我的A*算法的实现找出正确的道路，如果它处于死胡同，则返回。如您所见，它毫无困难地解决了迷宫问题。
所以我的程序有效。那有什么问题呢？
问题是节点 linking 部分。在小迷宫上，大约需要半秒钟。但是把迷宫弄大一些，那么节点的数量就会急剧增加。而且由于它遍历节点列表很多时间（它搜索每个节点的每个像素一次），你可以想象如果我有 600 000 个节点......这会花费很长时间。
这就是我寻求帮助的目的：更好、更快地 link 将节点组合在一起的方法。
我已经在 pastebin 上发布了整个代码（https://pastebin.com/xtmTm7wb，抱歉，如果它有点乱，我编程的时候已经很晚了）。节点 linking 部分从第 133 行开始到第 196 行结束。
这是节点 linking 代码：
counter = 0
last = 0
for node in nodelist:
a = node.pos[0]
b = node.pos[1]
if node.paths[0]:
for i in range(b-1,0,-1):
if mazepix[a,i] == blackpix:
break
if any(x.pos == (a,i) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (a,i):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
if node.paths[1]:
for i in range(a+1,maze.size[0]):
if mazepix[i,b] == blackpix:
break
if any(x.pos == (i,b) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (i,b):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
if node.paths[2]:
for i in range(b+1,maze.size[1]):
if mazepix[a,i] == blackpix:
break
if any(x.pos == (a,i) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (a,i):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
if node.paths[3]:
for i in range(a-1,0,-1):
if mazepix[i,b] == blackpix:
break
if any(x.pos == (i,b) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (i,b):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
counter += 1
percent = (counter/nbrofnodes)*100
if int(percent)%10 == 0 and int(percent) != last:
print("Linking %d%% done..."%percent)
last = int(percent)
print("All node linked.")
如果您阅读了所有这些内容，谢谢您，我知道这不是一个非常精确的问题，但是我花了很多时间来尝试使它起作用，现在它确实起作用了，我真的坚持我的方式可以改进它^^'。
你的程序超级慢，因为这部分需要很长时间，而且你对每个节点都做了很多次：
for iteration in nodelist:
if iteration.pos == (i,b):
indexofnodetolinkto = iteration.index
break
有很多方法可以让它更快。
您可以使用位置作为键将节点放入字典中，这样您就可以查找位置以找到那里的节点。
更好的是，您可以将节点放入行列表和列列表中，按位置排序，然后只尝试连接列表中的相邻节点。
但最好的办法是完全忘记这些节点，直接在位图上进行 BFS 搜索。
因为这是一个有趣的问题，我写了一个带有简单 BFS 的快速版本。我不想破坏你所有的乐趣，所以这里只是 BFS 部分，这样你就可以直接在图像上执行 BFS 来理解我的意思：
#Breadth-first search over the graph
#We use special colored pixels in the image to mark visited locations and their distance
nextlevel=[(entrypos,0)]
nextdist=0
mazepix[entrypos,0] = markerPixel(nextdist)
exitpos = -1
while exitpos<0:
if len(nextlevel) < 1:
print("Could not find exit!")
return
prevlevel = nextlevel
nextdist += 1
nextlevel = []
nextpix = markerPixel(nextdist)
for prevpos in prevlevel:
for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
x = prevpos[0]+dir[0]
y = prevpos[1]+dir[1]
if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==whitepix:
nextlevel.append((x,y))
#mark it used and distance mod 3
mazepix[x,y]=nextpix
if y>=H-1:
exitpos=x
我们没有使用包含对象和 link 的单独集合来记住路径，而是直接在图像中将像素标记为已访问。我们没有使用任何类型的实际 link 来 link 一个像素到另一个像素，而是在需要时检查所有 4 个方向以寻找相邻的白色像素。
这是逐级 BFS，因此我们始终知道新像素离入口有多远，我们标记已访问像素的颜色表示它与入口的距离 (mod 3)。这允许我们在找到出口时重建最短路径。
编辑：已经很长时间了，OP 玩得很开心，所以这是完整的 python 求解器：
from PIL import Image
import math
import sys
import time
import pickle
import os
whitepix = (255,255,255)
blackpix = (0,0,0)
redpix = (255,0,0)
greenpix = (0,255,0)
def markerPixel(distance):
val=120+(distance%3)*40
return (val,val,0)
def smallerMarker(pixel):
return markerPixel(pixel[0]-1)
def isMarker(pixel):
return pixel[2]==0 and pixel[0]==pixel[1] and pixel[0]>=120
def solve(imagename, outputname, showmarkers):
maze = Image.open(imagename)
maze = maze.convert('RGB')
mazepix = maze.load()
nodelist = []
print(maze.size)
starttime = time.time()
W = maze.size[0]
H = maze.size[1]
entrypos = -1
# Find the entry
for i in range(0,W):
if mazepix[i, 0] == whitepix:
entrypos=i
break
if entrypos < 0:
print("No entry!")
return
#Breadth-first search over the graph
#We use special colored pixels in the image to mark visited locations and their distance
nextlevel=[(entrypos,0)]
nextdist=0
mazepix[entrypos,0] = markerPixel(nextdist)
exitpos = -1
while exitpos<0:
if len(nextlevel) < 1:
print("Could not find exit!")
return
prevlevel = nextlevel
nextdist += 1
nextlevel = []
nextpix = markerPixel(nextdist)
for prevpos in prevlevel:
for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
x = prevpos[0]+dir[0]
y = prevpos[1]+dir[1]
if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==whitepix:
nextlevel.append((x,y))
#mark it used and distance mod 3
mazepix[x,y]=nextpix
if y>=H-1:
exitpos=x
#found the exit -- color the path green
nextpos = (exitpos,H-1)
while nextpos != None:
nextpix = smallerMarker(mazepix[nextpos[0],nextpos[1]])
prevpos = nextpos
mazepix[nextpos[0],nextpos[1]] = greenpix
nextpos = None
#find the next closest position -- all adjacent positions are either
#1 closer, 1 farther, or the same distance, so distance%3 is enough
#to distinguish them
for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
x = prevpos[0]+dir[0]
y = prevpos[1]+dir[1]
if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==nextpix:
nextpos=(x,y)
break
#Erase the marker pixels if desired
if not showmarkers:
for y in range(0,H):
for x in range(0,W):
if isMarker(mazepix[x,y]):
mazepix[x,y]=whitepix
maze.save(outputname)
solve("maze.gif", "solved.png", False)
您的迷宫只有 301x301 像素，所以我认为 0.5 秒对于解决方案来说时间过长。当我使用光栅 A* 方法时：
- How to speed up A* algorithm at large spatial scales?
整个解决方案只用了 ~1.873ms，这与你的 ~500ms 有很大的不同。粗图 A* 有更大的开销所以我很好奇并想测试它所以我编码了我的版本（在 C++ 中基于与上面 link 中相同的代码）结果是从图像中获取的图形占用了 ~3ms，图形 A* 占用了 ~0.18ms，因此与您的仍然存在巨大差异（+/- 计算机设置差异）。
那么首先要检查什么？
我不是 python 编码员，但我在您的代码中没有看到任何图像访问。您应该检查图像访问速度是否快。对于使用
之类的东西的新手来说，这是常见的错误
GetPixel/PutPixel
Pixels[][]
这些通常非常慢（根据我在 GDI Win32 上的经验，比直接像素访问慢 1000-10000 倍）并且如果更正会产生巨大的差异。有关详细信息，请参阅：
- Display an array of color in C
使用列表的另一个常见错误是在没有预分配的情况下向列表中增量添加元素。对于小列表，这不是问题，但是对于大量元素，在添加元素的情况下重新分配会通过一遍又一遍地复制内容来减慢速度。在列表中插入和删除元素也是如此。改进列表访问会产生巨大影响，尤其是对于 O(n^2) 和更慢的多项式复杂性...
算法
算法的微小变化会产生巨大的影响。在您的情况下，我结合使用了 DIP 边缘检测技术和加速拓扑排序边缘的结构。这会将 O(n) 或 O(n^2) 搜索更改为简单的 O(1) 操作。这个想法是按 xy 和 yx 排序迷宫所有顶点的有序列表。如果每个顶点都知道它在这种结构中的索引，它可以很容易地获得它的邻居顶点...
Stack/heap 垃圾处理
这会大大降低速度。尤其是递归函数。递归级别和操作数大小传递的越大，效果越差。
这里是我基于上面link的简单C++例子
//---------------------------------------------------------------------------
//--- A star class ver: 1.00 ------------------------------------------------
//---------------------------------------------------------------------------
#ifndef _A_star_h
#define _A_star_h
//---------------------------------------------------------------------------
#include "list.h"
//---------------------------------------------------------------------------
class A_star_graph
{
public:
// variables
struct _pnt
{
int x,y; // 2D position (image)
int mx; // mxy[y][mx] index
int my; // mxy[x][my] index
int pN,pS,pE,pW; // index of linked point in direction or -1
int lN,lS,lE,lW; // distance to linked point in direction or 0 (cost for A*)
int a; // value for A*
_pnt() {}
_pnt(_pnt& a) { *this=a; }
~_pnt() {}
_pnt* operator = (const _pnt *a) { *this=*a; return this; }
//_pnt* operator = (const _pnt &a) { ...copy... return this; }
};
List<_pnt> pnt; // list of all vertexes
List< List<int> > mxy,myx; // xy and yx index sorted pnt[] (indexes of points)
List<int> path; // found path (indexes of points)
int xs,ys; // map esolution
DWORD col_space; // colors for rendering
DWORD col_wall ;
DWORD col_path ;
// internals
A_star_graph();
A_star_graph(A_star_graph& a) { *this=a; }
~A_star_graph(){}
A_star_graph* operator = (const A_star_graph *a) { *this=*a; return this; }
//A_star_graph* operator = (const A_star_graph &a) { ...copy... return this; }
// inteface
void reset(); // clear all
void ld(Graphics::TBitmap *bmp,DWORD col_wall); // create graph from bitmap col_wall is 0x00RRGGBB
void draw(Graphics::TBitmap *bmp); // draw map to bitmap for debuging
void compute(int p0,int p1); // compute path from pnt[p0] to pnt[p1] into path[]
};
//---------------------------------------------------------------------------
A_star_graph::A_star_graph()
{ //BBGGRR
col_space=0x00FFFFFF;
col_wall =0x00000000;
col_path =0x00FFAA40;
reset();
}
//---------------------------------------------------------------------------
void A_star_graph::reset()
{
int x,y; xs=0; ys=0; pnt.num=0; path.num=0;
for (x=0;x<mxy.num;x++) mxy[x].num=0; mxy.num=0;
for (y=0;y<myx.num;y++) myx[y].num=0; myx.num=0;
}
//---------------------------------------------------------------------------
void A_star_graph::ld(Graphics::TBitmap *bmp,DWORD col_wall)
{
_pnt p,*pp,*qq;
int i,j,x,y,c[10]={0,0,0,0,0,0,0,0,0,0};
DWORD *p0,*p1,*p2;
reset();
xs=bmp->Width;
ys=bmp->Height;
mxy.allocate(xs); mxy.num=xs; for (x=0;x<xs;x++) mxy[x].num=0;
myx.allocate(ys); myx.num=ys; for (y=0;y<ys;y++) myx[y].num=0;
if (!ys) return;
p.pN=-1; p.pS=-1; p.pE=-1; p.pW=-1; p.mx=-1; p.my=-1;
p0=NULL; p1=NULL; p2=(DWORD*)bmp->ScanLine[0];
for (p.y=0;p.y<ys;p.y++)
{
p0=p1; p1=p2; p2=NULL;
if (p.y+1<ys) p2=(DWORD*)bmp->ScanLine[p.y+1];
for (p.x=0;p.x<xs;p.x++)
if ((p1[p.x]&0x00FFFFFF)!=col_wall) // ignore wall pixels
{
// init connection info
p.lN=0; p.lS=0; p.lE=0; p.lW=0;
// init c[] array with not a wall predicates for 4-neighbors
c[2]=0; c[4]=0; c[5]=1; c[6]=0; c[8]=0;
if (p0) if ((p0[p.x]&0x00FFFFFF)!=col_wall) c[8]=1;
if (p2) if ((p2[p.x]&0x00FFFFFF)!=col_wall) c[2]=1;
if (p1)
{
if (p.x-1> 0) if ((p1[p.x-1]&0x00FFFFFF)!=col_wall) c[4]=1;
if (p.x+1<xs) if ((p1[p.x+1]&0x00FFFFFF)!=col_wall) c[6]=1;
}
// detect vertex and its connection
i=0;
if (( c[2])&&(!c[8])){ i=1; p.lS=1; } // L
if ((!c[2])&&( c[8])){ i=1; p.lN=1; }
if (( c[4])&&(!c[6])){ i=1; p.lW=1; }
if ((!c[4])&&( c[6])){ i=1; p.lE=1; }
j=c[2]+c[4]+c[6]+c[8];
if (j==3) // T
{
i=1; p.lN=1; p.lS=1; p.lW=1; p.lE=1;
if (!c[2]) p.lS=0;
if (!c[8]) p.lN=0;
if (!c[6]) p.lE=0;
if (!c[4]) p.lW=0;
}
if (j==4) // +
{
i=1; p.lN=1; p.lS=1; p.lW=1; p.lE=1;
}
// add point
if (i)
{
p.mx=myx[p.y].num;
p.my=mxy[p.x].num;
mxy[p.x].add(pnt.num);
myx[p.y].add(pnt.num);
pnt.add(p);
}
}
}
// find connection between points
for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++)
{
if (pp->lE)
{
j=myx[pp->y][pp->mx+1]; qq=pnt.dat+j; pp->pE=j; qq->pW=i;
j=abs(qq->x-pp->x)+abs(qq->y-pp->y); pp->lE=j; qq->lW=j;
}
if (pp->lS)
{
j=mxy[pp->x][pp->my+1]; qq=pnt.dat+j; pp->pS=j; qq->pN=i;
j=abs(qq->x-pp->x)+abs(qq->y-pp->y); pp->lS=j; qq->lN=j;
}
}
}
//---------------------------------------------------------------------------
void A_star_graph::draw(Graphics::TBitmap *bmp)
{
int i;
_pnt *p0,*p1;
// init
bmp->SetSize(xs,ys);
// clear (walls)
bmp->Canvas->Pen->Color=TColor(col_wall);
bmp->Canvas->Brush->Color=TColor(col_wall);
bmp->Canvas->FillRect(TRect(0,0,xs,ys));
// space
bmp->Canvas->Pen->Color=TColor(col_space);
for (p0=pnt.dat,i=0;i<pnt.num;i++,p0++)
{
if (p0->pN>=0){ p1=pnt.dat+p0->pN; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
if (p0->pS>=0){ p1=pnt.dat+p0->pS; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
if (p0->pE>=0){ p1=pnt.dat+p0->pE; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
if (p0->pW>=0){ p1=pnt.dat+p0->pW; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
}
// found path
bmp->Canvas->Pen->Color=TColor(col_path);
for (i=0;i<path.num;i++)
{
p0=pnt.dat+path.dat[i];
if (!i) bmp->Canvas->MoveTo(p0->x,p0->y);
else bmp->Canvas->LineTo(p0->x,p0->y);
}
}
//---------------------------------------------------------------------------
void A_star_graph::compute(int p0,int p1)
{
_pnt *pp,*qq;
int i,a,e;
List<int> upd; // list of vertexes to update
// init
path.num=0;
if ((p0<0)||(p0>=pnt.num)) return;
if ((p1<0)||(p1>=pnt.num)) return;
// clear with max value
for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++) pp->a=0x7FFFFFFF;
// init A* to fill from p1
upd.allocate(xs+ys); upd.num=0; // preallocate
upd.add(p1); pnt[p1].a=0; // start from p1
// iterative A* filling
for (e=1;(e)&&(upd.num);) // loop until hit the start p0 or dead end
{
// process/remove last pnt in que
pp=pnt.dat+upd[upd.num-1]; upd.num--;
// link exist? compute cost if less update it reached p0?
i=pp->pN; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lN; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
i=pp->pS; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lS; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
i=pp->pE; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lE; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
i=pp->pW; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lW; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
}
// reconstruct path
e=p0; pp=pnt.dat+e; path.add(e);
for (;e!=p1;) // loop until path complete
{
a=0x7FFFFFFF; e=-1;
// e = select link with smallest cost
i=pp->pN; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
i=pp->pS; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
i=pp->pE; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
i=pp->pW; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
if (e<0) break; // dead end
pp=pnt.dat+e; path.add(e);
}
}
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
和用法：
Graphics::TBitmap *maze=new Graphics::TBitmap;
maze->LoadFromFile("maze.bmp");
maze->HandleType=bmDIB;
maze->PixelFormat=pf32bit;
A_star_graph map;
map.ld(maze,0);
map.compute(0,map.pnt.num-1);
map.draw(maze);
代码基于VCL（使用第二个link中描述的位图），我也使用我的动态列表模板：
List<double> xxx; 等同于 double xxx[];
xxx.add(5); 将 5 添加到列表末尾
xxx[7] 访问数组元素（安全）
xxx.dat[7]访问数组元素（不安全但直接访问速度快）
xxx.num是数组实际使用的大小
xxx.reset()清空数组并设置xxx.num=0
xxx.allocate(100) 为 100 项预分配 space
抱歉，我不是 python 编码员，但我认为代码足够直接......所以我希望你 port/adapt 对你的环境没有任何问题。
这里输出：
看起来它模仿你的...代码仍未优化，可以进一步改进...我认为您应该仔细查看 mx,my 和 mxy[][],myx[][] 变量。这些是拓扑索引排序的顶点，可以大大加快您的代码...
[编辑1]
我更新了 A* 搜索代码（感谢 Matt Timmermans）所以这里是更新的结果：
各位程序员。我的一个项目需要帮助。我正在制作一个迷宫解决程序。它读取一个图像文件，它必须是黑白的（黑色像素是墙壁，白色像素是路径），顶部只有一个像素是迷宫的入口，底部只有一个白色像素是迷宫的入口出口。
代码主要分为三个部分：
1) 程序首先根据一组规则在迷宫中创建节点。例如这里有一个简单的迷宫：
这里是所有用红色绘制的节点：
节点就像拐角，十字路口，每一个可以改变方向的点。每个节点和迷宫出口之间的距离也被测量。当它生成所有节点时，它会将它们放在一个列表中。
2) 一旦生成了所有节点，程序将遍历列表中的所有节点，并尝试在每个可能的方向搜索其他节点，到 "link" 它们，建立可能的路径。例如，如果它检测到节点上方有一条路径，它将从该节点的坐标开始搜索一行中的每个像素，然后向上，再次遍历所有节点列表以查看是否有另一个节点匹配这些坐标。如果它在某个时候找到了一个，它会 link 发送它们，然后开始向右搜索（当然如果有一条向右的路径），等等每个方向。
3) 一旦所有的节点都link在一起并且每条可能的路径都建立了，它将从迷宫的入口节点开始，运行 我的A*算法的实现找出正确的道路，如果它处于死胡同，则返回。如您所见，它毫无困难地解决了迷宫问题。
所以我的程序有效。那有什么问题呢？ 问题是节点 linking 部分。在小迷宫上，大约需要半秒钟。但是把迷宫弄大一些，那么节点的数量就会急剧增加。而且由于它遍历节点列表很多时间（它搜索每个节点的每个像素一次），你可以想象如果我有 600 000 个节点......这会花费很长时间。
这就是我寻求帮助的目的：更好、更快地 link 将节点组合在一起的方法。 我已经在 pastebin 上发布了整个代码（https://pastebin.com/xtmTm7wb，抱歉，如果它有点乱，我编程的时候已经很晚了）。节点 linking 部分从第 133 行开始到第 196 行结束。
这是节点 linking 代码：
counter = 0
last = 0
for node in nodelist:
a = node.pos[0]
b = node.pos[1]
if node.paths[0]:
for i in range(b-1,0,-1):
if mazepix[a,i] == blackpix:
break
if any(x.pos == (a,i) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (a,i):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
if node.paths[1]:
for i in range(a+1,maze.size[0]):
if mazepix[i,b] == blackpix:
break
if any(x.pos == (i,b) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (i,b):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
if node.paths[2]:
for i in range(b+1,maze.size[1]):
if mazepix[a,i] == blackpix:
break
if any(x.pos == (a,i) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (a,i):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
if node.paths[3]:
for i in range(a-1,0,-1):
if mazepix[i,b] == blackpix:
break
if any(x.pos == (i,b) for x in nodelist):
for iteration in nodelist:
if iteration.pos == (i,b):
indexofnodetolinkto = iteration.index
break
node.connections.append(indexofnodetolinkto)
# print("Linking node %d and node %d..."%(node.index, indexofnodetolinkto))
break
counter += 1
percent = (counter/nbrofnodes)*100
if int(percent)%10 == 0 and int(percent) != last:
print("Linking %d%% done..."%percent)
last = int(percent)
print("All node linked.")
如果您阅读了所有这些内容，谢谢您，我知道这不是一个非常精确的问题，但是我花了很多时间来尝试使它起作用，现在它确实起作用了，我真的坚持我的方式可以改进它^^'。
你的程序超级慢，因为这部分需要很长时间，而且你对每个节点都做了很多次：
for iteration in nodelist:
if iteration.pos == (i,b):
indexofnodetolinkto = iteration.index
break
有很多方法可以让它更快。
您可以使用位置作为键将节点放入字典中，这样您就可以查找位置以找到那里的节点。
更好的是，您可以将节点放入行列表和列列表中，按位置排序，然后只尝试连接列表中的相邻节点。
但最好的办法是完全忘记这些节点，直接在位图上进行 BFS 搜索。
因为这是一个有趣的问题，我写了一个带有简单 BFS 的快速版本。我不想破坏你所有的乐趣，所以这里只是 BFS 部分，这样你就可以直接在图像上执行 BFS 来理解我的意思：
#Breadth-first search over the graph
#We use special colored pixels in the image to mark visited locations and their distance
nextlevel=[(entrypos,0)]
nextdist=0
mazepix[entrypos,0] = markerPixel(nextdist)
exitpos = -1
while exitpos<0:
if len(nextlevel) < 1:
print("Could not find exit!")
return
prevlevel = nextlevel
nextdist += 1
nextlevel = []
nextpix = markerPixel(nextdist)
for prevpos in prevlevel:
for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
x = prevpos[0]+dir[0]
y = prevpos[1]+dir[1]
if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==whitepix:
nextlevel.append((x,y))
#mark it used and distance mod 3
mazepix[x,y]=nextpix
if y>=H-1:
exitpos=x
我们没有使用包含对象和 link 的单独集合来记住路径，而是直接在图像中将像素标记为已访问。我们没有使用任何类型的实际 link 来 link 一个像素到另一个像素，而是在需要时检查所有 4 个方向以寻找相邻的白色像素。
这是逐级 BFS，因此我们始终知道新像素离入口有多远，我们标记已访问像素的颜色表示它与入口的距离 (mod 3)。这允许我们在找到出口时重建最短路径。
编辑：已经很长时间了，OP 玩得很开心，所以这是完整的 python 求解器：
from PIL import Image
import math
import sys
import time
import pickle
import os
whitepix = (255,255,255)
blackpix = (0,0,0)
redpix = (255,0,0)
greenpix = (0,255,0)
def markerPixel(distance):
val=120+(distance%3)*40
return (val,val,0)
def smallerMarker(pixel):
return markerPixel(pixel[0]-1)
def isMarker(pixel):
return pixel[2]==0 and pixel[0]==pixel[1] and pixel[0]>=120
def solve(imagename, outputname, showmarkers):
maze = Image.open(imagename)
maze = maze.convert('RGB')
mazepix = maze.load()
nodelist = []
print(maze.size)
starttime = time.time()
W = maze.size[0]
H = maze.size[1]
entrypos = -1
# Find the entry
for i in range(0,W):
if mazepix[i, 0] == whitepix:
entrypos=i
break
if entrypos < 0:
print("No entry!")
return
#Breadth-first search over the graph
#We use special colored pixels in the image to mark visited locations and their distance
nextlevel=[(entrypos,0)]
nextdist=0
mazepix[entrypos,0] = markerPixel(nextdist)
exitpos = -1
while exitpos<0:
if len(nextlevel) < 1:
print("Could not find exit!")
return
prevlevel = nextlevel
nextdist += 1
nextlevel = []
nextpix = markerPixel(nextdist)
for prevpos in prevlevel:
for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
x = prevpos[0]+dir[0]
y = prevpos[1]+dir[1]
if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==whitepix:
nextlevel.append((x,y))
#mark it used and distance mod 3
mazepix[x,y]=nextpix
if y>=H-1:
exitpos=x
#found the exit -- color the path green
nextpos = (exitpos,H-1)
while nextpos != None:
nextpix = smallerMarker(mazepix[nextpos[0],nextpos[1]])
prevpos = nextpos
mazepix[nextpos[0],nextpos[1]] = greenpix
nextpos = None
#find the next closest position -- all adjacent positions are either
#1 closer, 1 farther, or the same distance, so distance%3 is enough
#to distinguish them
for dir in [(-1,0),(0,1),(1,0),(0,-1)]:
x = prevpos[0]+dir[0]
y = prevpos[1]+dir[1]
if x>=0 and y>=0 and x<W and y<H and mazepix[x,y]==nextpix:
nextpos=(x,y)
break
#Erase the marker pixels if desired
if not showmarkers:
for y in range(0,H):
for x in range(0,W):
if isMarker(mazepix[x,y]):
mazepix[x,y]=whitepix
maze.save(outputname)
solve("maze.gif", "solved.png", False)
您的迷宫只有 301x301 像素，所以我认为 0.5 秒对于解决方案来说时间过长。当我使用光栅 A* 方法时：
- How to speed up A* algorithm at large spatial scales?
整个解决方案只用了 ~1.873ms，这与你的 ~500ms 有很大的不同。粗图 A* 有更大的开销所以我很好奇并想测试它所以我编码了我的版本（在 C++ 中基于与上面 link 中相同的代码）结果是从图像中获取的图形占用了 ~3ms，图形 A* 占用了 ~0.18ms，因此与您的仍然存在巨大差异（+/- 计算机设置差异）。
那么首先要检查什么？
我不是 python 编码员，但我在您的代码中没有看到任何图像访问。您应该检查图像访问速度是否快。对于使用
之类的东西的新手来说，这是常见的错误GetPixel/PutPixel
Pixels[][]
这些通常非常慢（根据我在 GDI Win32 上的经验，比直接像素访问慢 1000-10000 倍）并且如果更正会产生巨大的差异。有关详细信息，请参阅：
- Display an array of color in C
使用列表的另一个常见错误是在没有预分配的情况下向列表中增量添加元素。对于小列表，这不是问题，但是对于大量元素，在添加元素的情况下重新分配会通过一遍又一遍地复制内容来减慢速度。在列表中插入和删除元素也是如此。改进列表访问会产生巨大影响，尤其是对于 O(n^2) 和更慢的多项式复杂性...
算法
算法的微小变化会产生巨大的影响。在您的情况下，我结合使用了 DIP 边缘检测技术和加速拓扑排序边缘的结构。这会将 O(n) 或 O(n^2) 搜索更改为简单的 O(1) 操作。这个想法是按 xy 和 yx 排序迷宫所有顶点的有序列表。如果每个顶点都知道它在这种结构中的索引，它可以很容易地获得它的邻居顶点...
Stack/heap 垃圾处理
这会大大降低速度。尤其是递归函数。递归级别和操作数大小传递的越大，效果越差。
这里是我基于上面link的简单C++例子
//---------------------------------------------------------------------------
//--- A star class ver: 1.00 ------------------------------------------------
//---------------------------------------------------------------------------
#ifndef _A_star_h
#define _A_star_h
//---------------------------------------------------------------------------
#include "list.h"
//---------------------------------------------------------------------------
class A_star_graph
{
public:
// variables
struct _pnt
{
int x,y; // 2D position (image)
int mx; // mxy[y][mx] index
int my; // mxy[x][my] index
int pN,pS,pE,pW; // index of linked point in direction or -1
int lN,lS,lE,lW; // distance to linked point in direction or 0 (cost for A*)
int a; // value for A*
_pnt() {}
_pnt(_pnt& a) { *this=a; }
~_pnt() {}
_pnt* operator = (const _pnt *a) { *this=*a; return this; }
//_pnt* operator = (const _pnt &a) { ...copy... return this; }
};
List<_pnt> pnt; // list of all vertexes
List< List<int> > mxy,myx; // xy and yx index sorted pnt[] (indexes of points)
List<int> path; // found path (indexes of points)
int xs,ys; // map esolution
DWORD col_space; // colors for rendering
DWORD col_wall ;
DWORD col_path ;
// internals
A_star_graph();
A_star_graph(A_star_graph& a) { *this=a; }
~A_star_graph(){}
A_star_graph* operator = (const A_star_graph *a) { *this=*a; return this; }
//A_star_graph* operator = (const A_star_graph &a) { ...copy... return this; }
// inteface
void reset(); // clear all
void ld(Graphics::TBitmap *bmp,DWORD col_wall); // create graph from bitmap col_wall is 0x00RRGGBB
void draw(Graphics::TBitmap *bmp); // draw map to bitmap for debuging
void compute(int p0,int p1); // compute path from pnt[p0] to pnt[p1] into path[]
};
//---------------------------------------------------------------------------
A_star_graph::A_star_graph()
{ //BBGGRR
col_space=0x00FFFFFF;
col_wall =0x00000000;
col_path =0x00FFAA40;
reset();
}
//---------------------------------------------------------------------------
void A_star_graph::reset()
{
int x,y; xs=0; ys=0; pnt.num=0; path.num=0;
for (x=0;x<mxy.num;x++) mxy[x].num=0; mxy.num=0;
for (y=0;y<myx.num;y++) myx[y].num=0; myx.num=0;
}
//---------------------------------------------------------------------------
void A_star_graph::ld(Graphics::TBitmap *bmp,DWORD col_wall)
{
_pnt p,*pp,*qq;
int i,j,x,y,c[10]={0,0,0,0,0,0,0,0,0,0};
DWORD *p0,*p1,*p2;
reset();
xs=bmp->Width;
ys=bmp->Height;
mxy.allocate(xs); mxy.num=xs; for (x=0;x<xs;x++) mxy[x].num=0;
myx.allocate(ys); myx.num=ys; for (y=0;y<ys;y++) myx[y].num=0;
if (!ys) return;
p.pN=-1; p.pS=-1; p.pE=-1; p.pW=-1; p.mx=-1; p.my=-1;
p0=NULL; p1=NULL; p2=(DWORD*)bmp->ScanLine[0];
for (p.y=0;p.y<ys;p.y++)
{
p0=p1; p1=p2; p2=NULL;
if (p.y+1<ys) p2=(DWORD*)bmp->ScanLine[p.y+1];
for (p.x=0;p.x<xs;p.x++)
if ((p1[p.x]&0x00FFFFFF)!=col_wall) // ignore wall pixels
{
// init connection info
p.lN=0; p.lS=0; p.lE=0; p.lW=0;
// init c[] array with not a wall predicates for 4-neighbors
c[2]=0; c[4]=0; c[5]=1; c[6]=0; c[8]=0;
if (p0) if ((p0[p.x]&0x00FFFFFF)!=col_wall) c[8]=1;
if (p2) if ((p2[p.x]&0x00FFFFFF)!=col_wall) c[2]=1;
if (p1)
{
if (p.x-1> 0) if ((p1[p.x-1]&0x00FFFFFF)!=col_wall) c[4]=1;
if (p.x+1<xs) if ((p1[p.x+1]&0x00FFFFFF)!=col_wall) c[6]=1;
}
// detect vertex and its connection
i=0;
if (( c[2])&&(!c[8])){ i=1; p.lS=1; } // L
if ((!c[2])&&( c[8])){ i=1; p.lN=1; }
if (( c[4])&&(!c[6])){ i=1; p.lW=1; }
if ((!c[4])&&( c[6])){ i=1; p.lE=1; }
j=c[2]+c[4]+c[6]+c[8];
if (j==3) // T
{
i=1; p.lN=1; p.lS=1; p.lW=1; p.lE=1;
if (!c[2]) p.lS=0;
if (!c[8]) p.lN=0;
if (!c[6]) p.lE=0;
if (!c[4]) p.lW=0;
}
if (j==4) // +
{
i=1; p.lN=1; p.lS=1; p.lW=1; p.lE=1;
}
// add point
if (i)
{
p.mx=myx[p.y].num;
p.my=mxy[p.x].num;
mxy[p.x].add(pnt.num);
myx[p.y].add(pnt.num);
pnt.add(p);
}
}
}
// find connection between points
for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++)
{
if (pp->lE)
{
j=myx[pp->y][pp->mx+1]; qq=pnt.dat+j; pp->pE=j; qq->pW=i;
j=abs(qq->x-pp->x)+abs(qq->y-pp->y); pp->lE=j; qq->lW=j;
}
if (pp->lS)
{
j=mxy[pp->x][pp->my+1]; qq=pnt.dat+j; pp->pS=j; qq->pN=i;
j=abs(qq->x-pp->x)+abs(qq->y-pp->y); pp->lS=j; qq->lN=j;
}
}
}
//---------------------------------------------------------------------------
void A_star_graph::draw(Graphics::TBitmap *bmp)
{
int i;
_pnt *p0,*p1;
// init
bmp->SetSize(xs,ys);
// clear (walls)
bmp->Canvas->Pen->Color=TColor(col_wall);
bmp->Canvas->Brush->Color=TColor(col_wall);
bmp->Canvas->FillRect(TRect(0,0,xs,ys));
// space
bmp->Canvas->Pen->Color=TColor(col_space);
for (p0=pnt.dat,i=0;i<pnt.num;i++,p0++)
{
if (p0->pN>=0){ p1=pnt.dat+p0->pN; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
if (p0->pS>=0){ p1=pnt.dat+p0->pS; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
if (p0->pE>=0){ p1=pnt.dat+p0->pE; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
if (p0->pW>=0){ p1=pnt.dat+p0->pW; bmp->Canvas->MoveTo(p0->x,p0->y); bmp->Canvas->LineTo(p1->x,p1->y); }
}
// found path
bmp->Canvas->Pen->Color=TColor(col_path);
for (i=0;i<path.num;i++)
{
p0=pnt.dat+path.dat[i];
if (!i) bmp->Canvas->MoveTo(p0->x,p0->y);
else bmp->Canvas->LineTo(p0->x,p0->y);
}
}
//---------------------------------------------------------------------------
void A_star_graph::compute(int p0,int p1)
{
_pnt *pp,*qq;
int i,a,e;
List<int> upd; // list of vertexes to update
// init
path.num=0;
if ((p0<0)||(p0>=pnt.num)) return;
if ((p1<0)||(p1>=pnt.num)) return;
// clear with max value
for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++) pp->a=0x7FFFFFFF;
// init A* to fill from p1
upd.allocate(xs+ys); upd.num=0; // preallocate
upd.add(p1); pnt[p1].a=0; // start from p1
// iterative A* filling
for (e=1;(e)&&(upd.num);) // loop until hit the start p0 or dead end
{
// process/remove last pnt in que
pp=pnt.dat+upd[upd.num-1]; upd.num--;
// link exist? compute cost if less update it reached p0?
i=pp->pN; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lN; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
i=pp->pS; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lS; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
i=pp->pE; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lE; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
i=pp->pW; if (i>=0){ qq=pnt.dat+i; a=pp->a+pp->lW; if (qq->a>a) { qq->a=a; upd.add(i); } if (i==p0) { e=0; break; }}
}
// reconstruct path
e=p0; pp=pnt.dat+e; path.add(e);
for (;e!=p1;) // loop until path complete
{
a=0x7FFFFFFF; e=-1;
// e = select link with smallest cost
i=pp->pN; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
i=pp->pS; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
i=pp->pE; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
i=pp->pW; if (i>=0){ qq=pnt.dat+i; if (qq->a<a) { a=qq->a; e=i; }}
if (e<0) break; // dead end
pp=pnt.dat+e; path.add(e);
}
}
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
和用法：
Graphics::TBitmap *maze=new Graphics::TBitmap;
maze->LoadFromFile("maze.bmp");
maze->HandleType=bmDIB;
maze->PixelFormat=pf32bit;
A_star_graph map;
map.ld(maze,0);
map.compute(0,map.pnt.num-1);
map.draw(maze);
代码基于VCL（使用第二个link中描述的位图），我也使用我的动态列表模板：
List<double> xxx; 等同于 double xxx[];
xxx.add(5); 将 5 添加到列表末尾
xxx[7] 访问数组元素（安全）
xxx.dat[7]访问数组元素（不安全但直接访问速度快）
xxx.num是数组实际使用的大小
xxx.reset()清空数组并设置xxx.num=0
xxx.allocate(100) 为 100 项预分配 space
抱歉，我不是 python 编码员，但我认为代码足够直接......所以我希望你 port/adapt 对你的环境没有任何问题。
这里输出：
看起来它模仿你的...代码仍未优化，可以进一步改进...我认为您应该仔细查看 mx,my 和 mxy[][],myx[][] 变量。这些是拓扑索引排序的顶点，可以大大加快您的代码...
[编辑1]
我更新了 A* 搜索代码（感谢 Matt Timmermans）所以这里是更新的结果：