Двумерном лабиринте - волновой алгоритм/ребята подскажите где ошибка?

Сейчас на форуме: zds (+5 невидимых)

Посл.ответ	Сообщение
Abraham Ранг: 16.2 (новичок), 11thx Активность: 0.03↘0 Статус: Участник	Создано: 05 марта 2014 15:26 · Поправил: Abraham · Личное сообщение · #1 Двумерном лабиринте - волновой алгоритм. в стороны от исходной точки распростроняется волна. Начальное значение волны - ноль. То есть ближайшие точки, в которые можно пойти, например, верх, низ, левая и правая, и которые еще не затронуты волной, получают значение волны+некоторый модификатор проходимости этой точки. Чем он больше - тем медленнее преодоление данного участка. Значение волны увеличивается на 1. Обрабатываем аналогично клетки, отходя от тех, на которой значение волны - 2. При этом на клетках с худшей проходимостью волна задержится. И так дальше все обрабатывается, пока не достигнута конечная точка маршрута. Сам путь в получившемся массиве значений волны вычисляется по наименьшим клеткам. Code: #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А ЭКPАH / void* clrscr(){ // Очистить экpан int i; for(i=0;i<8025;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][i2 ].attr=16(7-movecost[j][i])+7+8((i+j)&1); scr[j][i2+1].attr=16(7-movecost[j][i])+7+8((i+j)&1); } scr[sy][sx2].chr='[';scr[sy][sx2+1].chr=']'; scr[ty][tx2].chr='<';scr[ty][tx2+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][x2 ].chr=n/10+48; // scr[y][x2+1].chr=(n%10)+48; // Это пpосто pисование и ожидание нажатия кнопки 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е смотpя на названия функций (push и pop) buf это не stack ! Это кольцевой FIFO-шный буфеp ! / / Вот, она самая, она-то путь и ищет / void* fill(int sx,int sy,int tx,int ty){ int x,y,n,t; _fmemset(fillmap,0xFF,sizeof(fillmap)); // Вначале fillmap заполняется max значением 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=fillmap[y][x]+movecost[y][x]; // n=длина пути до любой соседней клетки if(movecost[y+1][x ])push(x ,y+1,n); // if(movecost[y-1][x ])push(x ,y-1,n); // Пеpебоp 4-х соседних клеток 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][x2].attr=216;scr[y][x2+1].attr=216; // Pисование if(fillmap[y+1][x ]<n){tx=x ;ty=y+1;t=fillmap[y+1][x ];} // Сдесь ищется соседняя if(fillmap[y-1][x ]<n){tx=x ;ty=y-1;t=fillmap[y-1][x ];} // клетка, содеpжащая 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 t0 10 do Begin For X := 1 to 10 do Write(Map[X, Y], ' '); WriteLn; End; ReadLn; End.

unknownproject Ранг: 95.1 (постоянный), 247thx Активность: 0.26↘0.01 Статус: Участник	Создано: 05 марта 2014 15:31 · Личное сообщение · #2 СПрячь код в тег [ASM], а то нечитабельно. ----- TEST YOUR MIGHT
mysterio Ранг: 307.9 (мудрец), 196thx Активность: 0.18↘0 Статус: Участник	Создано: 05 марта 2014 15:46 · Поправил: mysterio · Личное сообщение · #3 На вскидку, ошибка как минимум в том что в сишнике индекс масива начинается с 0 (на 1 элемент больше). ----- Don_t hate the cracker - hate the code.
OKOB Ранг: 527.7 (!), 381thx Активность: 0.16↘0.09 Статус: Участник Победитель турнира 2010	Создано: 05 марта 2014 16:49 · Личное сообщение · #4 Откуда взялась идея об ошибке? Весь пост копипаст из http://algolist.manual.ru/games/wavealg.php ----- 127.0.0.1, sweet 127.0.0.1
ELF_7719116 Ранг: 419.0 (мудрец), 647thx Активность: 0.46↗0.51 Статус: Участник "Тибериумный реверсинг"	Создано: 05 марта 2014 17:11 · Личное сообщение · #5 Поддерживаю ОКОВ, собственно суть ошибки не указана. ...Пришло на память, по теме: в X-COM Ufo Defence существовал прикол с вмурованным в стенку пришельцем из-за ошибки в генераторе позиций юнитов. Разве что, такие костыли могут быть \| Сообщение посчитали полезным: Dr0p
Excelvrn Ранг: 5.0 (гость), 2thx Активность: 0.01↘0 Статус: Участник	Создано: 19 марта 2014 14:11 · Личное сообщение · #6 Для какой цели тебе необходим волновой алгоритм? Вопрос обоснован, так как могу предложить Вам реализацию алгоритма Беллмана-Форда для поиска кратчайшего пути
Dr0p Ранг: 72.3 (постоянный), 133thx Активность: 0.38↘0 Статус: Участник	Создано: 16 апреля 2014 03:46 · Личное сообщение · #7 Пограничное описание поверхности как альтернатива, так же и в случае заливки фигур.

Для печати