Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Игры, и все с ними связанное /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Путь в двумерном лабиринте - волновой алгоритм - Программирование от RIN.RU
Путь в двумерном лабиринте - волновой алгоритм

Идея этого метода весьма проста: в стороны от исходной точки распростроняется волна.


Начальное значение волны - ноль.


То есть ближайшие точки, в которые можно пойти, например, верх, низ, левая и правая, и которые еще не затронуты волной, получают значение волны+некоторый модификатор проходимости этой точки. Чем он больше - тем медленнее преодоление данного участка. Значение волны увеличивается на 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  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь