Ваш лабиринт всего 301x301 пикселей, поэтому, на мой взгляд, 0,5 секунды - слишком большое время для решения. Когда я использовал растровый A * подход:
Все решение заняло всего ~1.873ms, что является огромной разницей с вашим ~500ms. Грубый граф A * имеет большие издержки, поэтому мне было любопытно, и я хотел проверить его, поэтому я кодировал свою версию (в C ++ на основе того же кода, что и в приведенной выше ссылке), и в результате было получено получение графика из изображение заняло до ~3ms, а график A * - до ~0.18ms, поэтому по-прежнему огромная разница с вашей (+/- разница в настройках компьютера).
Так что проверить в первую очередь?
Я не программист Python, но я не вижу доступа к изображениям в вашем коде. Вы должны проверить, быстрый ли доступ к вашему изображению или нет. Это распространенная ошибка для новичков, использующих такие вещи, как
GetPixel/PutPixel
Pixels[][]
Они обычно мучительно медленны (по моему опыту на GDI Win32, например, в 1000-10000 раз медленнее, чем прямой пиксельный доступ) и имеют огромное значение, если их исправить. для получения дополнительной информации см .:
Другая обычная ошибка при использовании списков - постепенное добавление элемента в список без предварительного выделения. Для небольшого списка это не проблема, но при большом количестве элементов перераспределение в случае добавления элемента замедляет процесс, копируя его снова и снова. То же самое касается вставки и удаления элемента в списках. Улучшение доступа к списку оказывает огромное влияние, особенно для полиномиальных сложностей, таких как O(n^2) и медленнее ...
Алгоритм
Небольшие изменения в алгоритме могут оказать огромное влияние. В вашем случае я использовал комбинацию DIP методов обнаружения ребер и ускоряющих структур для топологически отсортированных ребер. Это изменяет поиск O(n) или O(n^2) на простые операции O(1). Идея состоит в том, чтобы упорядочить список всех вершин лабиринта, отсортированный по xy и yx. Если каждая вершина знает свой индекс в такой структуре, она может легко получить соседние вершины ...
Перебор стека / кучи
это сильно тормозит. Особенно с рекурсивными функциями. Чем больше уровень рекурсии и размер операндов, тем хуже эффект.
Вот мой простой пример 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 (с использованием растрового изображения, описанного во второй ссылке), и я также использую мой шаблон динамического списка так:
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 элементов
Извините, я не программист на python, но думаю, что код достаточно прост ... поэтому я подумал, что у вас не будет проблем с переносом / адаптацией к вашей среде.
Вот вывод:
похоже, что он имитирует ваш ... Код по-прежнему не оптимизирован и может быть улучшен еще ... Я думаю, вам стоит присмотреться к переменным mx,my и mxy[][],myx[][]. Это вершины, отсортированные по индексу топологии, позволяющие значительно ускорить работу вашего кода ...
[Edit1]
Я обновил код поиска A * (спасибо Мэтту Тиммермансу), поэтому здесь обновляются результаты:
