Идея этого метода весьма проста: в стороны от исходной точки распростроняется волна. Начальное значение волны - ноль. То есть ближайшие точки, в которые можно пойти, например, верх, низ, левая и правая, и которые еще не затронуты волной, получают значение волны+некоторый модификатор проходимости этой точки. Чем он больше - тем медленнее преодоление данного участка. Значение волны увеличивается на 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 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 ] // клетка, содеpжащая if(fillmap[y-1][x ] // минимальное значение if(fillmap[y ][x+1] if(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.  8  Комментарии к статье  8 8  Обсудить в чате