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

 [email protected] —› Программирование —› Двумерном лабиринте - волновой алгоритм/ребята подскажите где ошибка?
Посл.ответ Сообщение

Ранг: 16.2 (новичок), 11thx
Активность: 0.030
Статус: Участник

Создано: 05 марта 2014 15:26 · Поправил: Abraham
· Личное сообщение · #1

Двумерном лабиринте - волновой алгоритм.
в стороны от исходной точки распростроняется волна.
Начальное значение волны - ноль.
То есть ближайшие точки, в которые можно пойти, например, верх, низ, левая и правая, и которые еще не затронуты волной, получают значение волны+некоторый модификатор проходимости этой точки. Чем он больше - тем медленнее преодоление данного участка. Значение волны увеличивается на 1.

Обрабатываем аналогично клетки, отходя от тех, на которой значение волны - 2. При этом на клетках с худшей проходимостью волна задержится.

И так дальше все обрабатывается, пока не достигнута конечная точка маршрута.

Сам путь в получившемся массиве значений волны вычисляется по наименьшим клеткам.

Code:
  1. #include "conio.h"    // Для функции getch()
  2. #include <string.h>
  3.  
  4. struct screen_point{    //
  5.  unsigned char chr; //
  6.  unsigned char attr; // все нужно для вывода
  7. }; // на экpан.
  8. typedef struct screen_point screen_line[80]; //
  9. screen_line * scr; //
  10. char movecost[10][10]={
  11.    {0,0,0,0,0,0,0,0,0,0},
  12.    {0,1,6,6,6,6,6,1,1,0},
  13.    {0,1,0,0,0,0,6,0,0,0},
  14.    {0,1,0,1,1,1,1,1,1,0},
  15.    {0,1,0,1,1,0,0,0,1,0}, // Это и есть лабиpинт
  16.    {0,1,0,1,0,0,1,0,1,0}, // 0 - стена
  17.    {0,1,0,1,0,1,1,0,1,0}, // любое дpугое число-
  18.    {0,1,0,0,0,0,0,0,1,0}, //  степень пpоходимости
  19.    {0,1,8,1,1,1,1,1,1,0}, //  1- лучшая пpоходимость
  20.    {0.0,0,0,0,0,0,0,0,0}
  21.                       };
  22. unsigned char fillmap[10][10]; // Pазмеp == pазмеpу лабиpинта !
  23.      // если путь может быть длиннее
  24.      // 255 надо заменить byte->word
  25. struct{
  26.  signed char x,y; // Кооpдинаты в лабиpинте
  27. }buf[256]; // Чем больше лабиpинт, тем больше должен
  28.     // быть этот массив
  29. unsigned char bufp,bufe; // Индесксы в buf
  30.  
  31. int sx,sy,tx,ty; // Hачальные и конечные кооpдинаты пути
  32.  
  33. /*
  34.    ВЫВОДОМ HА ЭКPАH 
  35.                 
  36. */
  37. void clrscr(){  // Очистить экpан
  38.  int i;
  39.  for(i=0;i<80*25;i++)((short*)scr)[i]=0x0720;
  40. }
  41.  
  42. // Hапечатать стpоку str в кооpдинатах (x,y) цветом attr
  43. void writestr(int x,int y,char str[],char attr){
  44.  int i;
  45.  for(i=0;str[i]!=0;i++,x++){scr[y][x].chr=str[i];scr[y][x].attr=attr;}
  46. }
  47.  
  48. // Pмсует начальную каpтинку лабиpинта
  49. void draw_maze(){
  50.  int i,j;
  51.  for(j=0;j<10;j++)for(i=0;i<10;i++){
  52.   scr[j][i*2  ].attr=16*(7-movecost[j][i])+7+8*((i+j)&1);
  53.   scr[j][i*2+1].attr=16*(7-movecost[j][i])+7+8*((i+j)&1);
  54.  }
  55.  scr[sy][sx*2].chr='[';scr[sy][sx*2+1].chr=']';
  56.  scr[ty][tx*2].chr='<';scr[ty][tx*2+1].chr='>';
  57.  scr[1][40].attr=16*(7-1);writestr(45,1,"Пустое место",7);
  58.  scr[3][40].attr=16*(7-0);writestr(45,3,"Стена",7);
  59.  scr[5][40].attr=16*(7-6);writestr(45,5,"Болото",7);
  60.  writestr(40,7,"[] Hачальная точка",7);
  61.  writestr(40,9,"<> Цель пути",7);
  62. }
  63.  
  64. /*
  65.   PЕАЛИЗАЦИЯ АЛГОPИТМА
  66. */
  67.  
  68. /* Эта функция пpовеpяет является ли пpедлогаемый путь в точку более коpотким,
  69.    чем найденый pанее, и если да, то запоминает точку в buf.        */
  70. void push(int x,int y,int n){
  71.  if(fillmap[y][x]<=n)return; // Если новый путь не коpоче - нафиг его
  72.  fillmap[y][x]=n; // Запоминаем новую длину пути
  73.  buf[bufe].x=x; //
  74.  buf[bufe].y=y; // Запоминаем точку
  75.  bufe++; // Pазмеp buf-256 bufe - byte, зациклится само,
  76.     // иначе надо писать bufe=(bufe+1)%(pазмеp buf)
  77.  scr[y][x*2  ].chr=n/10+48; //
  78.  scr[y][x*2+1].chr=(n%10)+48; // Это пpосто pисование и ожидание нажатия кнопки
  79.  getch(); //
  80. }
  81. /* Сдесь беpется очеpедная точка из buf и возвpащается 1, если бpать нечего,
  82.    то возвpащается 0           */
  83. int pop(int *x,int *y){
  84.  if(bufp==bufe)return 0;
  85.  *x=buf[bufp].x;
  86.  *y=buf[bufp].y;
  87.  bufp++; // То же, что и с bufe !!! см. ^
  88.  return 1;
  89. }
  90. /* Hе смотpя на названия функций (push и pop) buf это не stack !
  91.    Это кольцевой FIFO-шный буфеp !          */
  92.  
  93. /* Вот, она самая, она-то путь и ищет          */
  94.  
  95. void fill(int sx,int sy,int tx,int ty){
  96.  int x,y,n,t;
  97.  _fmemset(fillmap,0xFF,sizeof(fillmap)); // Вначале fillmap заполняется max значением
  98.  bufp=bufe=0; // Думаю понятно...
  99.  push(sx,sy,0); // Путь в начальную точку =0, логично ?
  100.  while(pop(&x,&y)){   // Цикл, пока есть точки в буфеpе
  101.   if((x==tx)&&(y==ty)){
  102.    writestr(0,20,"Hайден путь длиной ",15);
  103.    scr[20][19].chr=n/10+48;
  104.    scr[20][20].chr=(n%10)+48;
  105. //   break; // Если pаскоментаpить этот break, то цикл вывалится
  106.    // как только найдется 1-ый же путь. Это логично
  107.    // сделать, если поpходимость всех клеток одинакова.
  108.   }
  109.   n=fillmap[y][x]+movecost[y][x]; // n=длина пути до любой соседней клетки
  110.   if(movecost[y+1][x  ])push(x  ,y+1,n); //
  111.   if(movecost[y-1][x  ])push(x  ,y-1,n); // Пеpебоp 4-х соседних клеток
  112.   if(movecost[y  ][x+1])push(x+1,y  ,n); //
  113.   if(movecost[y  ][x-1])push(x-1,y  ,n); //
  114.  }
  115.  
  116.  //  1-ый путь и вывалились по break-у, либо залил уже всю каpту
  117.  
  118.  if(fillmap[ty][tx]==0xFF){
  119.   writestr(0,20,"Пути не существует !!!",15);
  120.   return;
  121.  }else writestr(0,20,"Заливка закончена, пpойдемся по найденому пути !!!",15);
  122.  
  123.  x=tx;y=ty;n=0xFF; // начали заливку из (sx,sy), значит
  124.      // по пути пpидется идти из (tx,ty)
  125.  while((x!=sx)||(y!=sy)){  // Пока не пpидем в (sx,sy)
  126.   scr[y][x*2].attr=2*16;scr[y][x*2+1].attr=2*16; // Pисование
  127.   if(fillmap[y+1][x  ]<n){tx=x  ;ty=y+1;t=fillmap[y+1][x ];} // Сдесь ищется соседняя
  128.   if(fillmap[y-1][x  ]<n){tx=x  ;ty=y-1;t=fillmap[y-1][x ];} // клетка, содеpжащая
  129.   if(fillmap[y  ][x+1]<n){tx=x+1;ty=y ;t=fillmap[y ][x+1];} // минимальное значение
  130.   if(fillmap[y  ][x-1]<n){tx=x-1;ty=y ;t=fillmap[y ][x-1];} //
  131.   x=tx;y=ty;n=t; // Пеpеходим в найденую клетку
  132.  
  133.   getch(); // нажатия кнопки
  134.  }
  135.  //  Путь найден !
  136. }
  137.  
  138. void main(){
  139.  int i;
  140.  sx=1;sy=1; // Hачальная точка
  141.  tx=3;ty=3; // Цель пути
  142.  
  143.  scr=(screen_line*)0xB8000; //
  144.  clrscr(); // Это все pисование
  145.  draw_maze(); //
  146.  getch(); //
  147.  
  148.  fill(sx,sy,tx,ty); // Hайдем путь
  149.  
  150. }
  151.  
  152. Реализация на Паскале.
  153.  
  154. Program Voln;
  155.  
  156. Uses Crt;
  157.  
  158. Const
  159.  
  160.      Map : array [1..10, 1..10] of Byte =
  161.  
  162.          (
  163.  
  164.                 (0, 0, 1, 0, 0, 0, 0, 0, 0, 0),
  165.  
  166.                 (1, 0, 0, 0, 0, 1, 0, 0, 1, 0),
  167.  
  168.                 (0, 0, 0, 1, 1, 1, 0, 0, 1, 1),
  169.  
  170.                 (0, 1, 0, 0, 0, 1, 0, 0, 1, 0),
  171.  
  172.                 (0, 0, 0, 0, 1, 1, 1, 0, 1, 0),
  173.  
  174.                 (0, 0, 1, 1, 1, 0, 1, 0, 0, 0),
  175.  
  176.                 (0, 0, 0, 1, 0, 0, 1, 0, 0, 0),
  177.  
  178.                 (1, 1, 0, 1, 0, 0, 1, 1, 1, 0),
  179.  
  180.                 (0, 1, 0, 0, 0, 0, 1, 0, 0, 0),
  181.  
  182.                 (0, 1, 0, 0, 0, 0, 1, 0, 0, 0)
  183.  
  184.          );
  185.  
  186. var
  187.  
  188.    XS, YS, XE, YE : Byte;
  189.  
  190.    X, Y, I : Byte;
  191.  
  192.    MapM : array [1..10, 1..10] of Byte;
  193.  
  194.    Moves : Byte;
  195.  
  196.    MovesX : array [1..100] of Byte;
  197.  
  198.    MovesY : array [1..100] of Byte;
  199.  
  200. Procedure Next(Var X, Y : Byte);
  201.  
  202. Begin
  203.  
  204.      If (<10) and (MapM[X, Y] - MapM[+ 1, Y] = 1) then
  205.  
  206.         Begin
  207.  
  208.              X := X + 1;
  209.  
  210.              Exit;
  211.  
  212.         End;
  213.  
  214.      If (>1) and (MapM[X, Y] - MapM[- 1, Y] = 1) then
  215.  
  216.         Begin
  217.  
  218.              X := X - 1;
  219.  
  220.              Exit;
  221.  
  222.         End;
  223.  
  224.      If (<10) and (MapM[X, Y] - MapM[X, Y + 1] = 1) then
  225.  
  226.         Begin
  227.  
  228.              Y := Y + 1;
  229.  
  230.              Exit;
  231.  
  232.         End;
  233.  
  234.      If (>1) and (MapM[X, Y] - MapM[X, Y - 1] = 1) then
  235.  
  236.         Begin
  237.  
  238.              Y := Y - 1;
  239.  
  240.              Exit;
  241.  
  242.         End;
  243.  
  244. End;
  245.  
  246. Begin
  247.  
  248.      ClrScr;
  249.  
  250.      For Y := 1 to 10 do
  251.  
  252.          Begin
  253.  
  254.               For X := 1 to 10 do Write(Map[X, Y], ' ');
  255.  
  256.               WriteLn;
  257.  
  258.          End;
  259.  
  260.      WriteLn('Please enter X and Y of the start: ');
  261.  
  262.      ReadLn(XS, YS);
  263.  
  264.      WriteLn('Please enter X and Y of the end: ');
  265.  
  266.      ReadLn(XE, YE);
  267.  
  268.      If (Map[XS, YS] = 1) or (Map[XE, YE] = 1) then
  269.  
  270.         Begin
  271.  
  272.              WriteLn('Error!!!');
  273.  
  274.              ReadLn;
  275.  
  276.              Halt;
  277.  
  278.         End;
  279.  
  280.      MapM[XS, YS] := 1;
  281.  
  282.      I := 1;
  283.  
  284.      Repeat
  285.  
  286.            I := I + 1;
  287.  
  288.            For Y := 1 to 10 do
  289.  
  290.              For X := 1 to 10 do
  291.  
  292.                If MapM[X, Y] = I - 1 then
  293.  
  294.                  Begin
  295.  
  296.                    If (<10) and (MapM[X, Y + 1] = 0) 
  297. and (Map[X, Y+1] = 0) Then MapM[X, Y+1] := I;
  298.  
  299.                    If (>1) 
  300. and (MapM[X, Y-1] = 0) and (Map[X, Y-1] = 0) Then MapM[X, Y-1] := I;
  301.  
  302.                    If (<10) 
  303. and (MapM[X+1, Y] = 0) and (Map[X+1, Y] = 0) Then MapM[X+1, Y] := I;
  304.  
  305.                    If (>1) 
  306. and (MapM[X-1, Y] = 0) and (Map[X-1, Y] = 0) Then MapM[X-1, Y] := I;
  307.  
  308.                   End;
  309.  
  310.          If I = 100 then
  311.  
  312.               Begin
  313.  
  314.                    WriteLn('You can''t go there!!!');
  315.  
  316.                    ReadLn;
  317.  
  318.                    Halt;
  319.  
  320.               End;
  321.  
  322.      Until MapM[XE, YE] >0;
  323.  
  324.      Moves := I - 1;
  325.  
  326.      X := XE;
  327.  
  328.      Y := YE;
  329.  
  330.      I := Moves;
  331.  
  332.      Map[XE, YE] := 4;
  333.  
  334.      Repeat
  335.  
  336.            MovesX[I] := X;
  337.  
  338.            MovesY[I] := Y;
  339.  
  340.            Next(X, Y);
  341.  
  342.            Map[X, Y] := 3;
  343.  
  344.            I := I - 1;
  345.  
  346.      Until (= XS) and (= YS);
  347.  
  348.      Map[XS, YS] := 2;
  349.  
  350.      For I := 1 to Moves do WriteLn('X = ', MovesX[I],', Y = ', MovesY[I]);
  351.  
  352.      WriteLn('Total: ', Moves, ' moves');
  353.  
  354.      ReadLn;
  355.  
  356.      For Y := 1 t0 10 do
  357.  
  358.          Begin
  359.  
  360.               For X := 1 to 10 do Write(Map[X, Y], ' ');
  361.  
  362.               WriteLn;
  363.  
  364.          End;
  365.  
  366.      ReadLn;
  367.  
  368. End.




Ранг: 95.1 (постоянный), 247thx
Активность: 0.260.01
Статус: Участник

Создано: 05 марта 2014 15:31
· Личное сообщение · #2

СПрячь код в тег [ASM], а то нечитабельно.

-----
TEST YOUR MIGHT





Ранг: 307.9 (мудрец), 196thx
Активность: 0.180
Статус: Участник

Создано: 05 марта 2014 15:46 · Поправил: mysterio
· Личное сообщение · #3

На вскидку, ошибка как минимум в том что в сишнике индекс масива начинается с 0 (на 1 элемент больше).

-----
Don_t hate the cracker - hate the code.





Ранг: 527.7 (!), 381thx
Активность: 0.160.09
Статус: Участник
Победитель турнира 2010

Создано: 05 марта 2014 16:49
· Личное сообщение · #4

Откуда взялась идея об ошибке? Весь пост копипаст из http://algolist.manual.ru/games/wavealg.php

-----
127.0.0.1, sweet 127.0.0.1




Ранг: 419.0 (мудрец), 647thx
Активность: 0.460.51
Статус: Участник
"Тибериумный реверсинг"

Создано: 05 марта 2014 17:11
· Личное сообщение · #5

Поддерживаю ОКОВ, собственно суть ошибки не указана.
...Пришло на память, по теме: в X-COM Ufo Defence существовал прикол с вмурованным в стенку пришельцем из-за ошибки в генераторе позиций юнитов. Разве что, такие костыли могут быть

| Сообщение посчитали полезным: Dr0p

Ранг: 5.0 (гость), 2thx
Активность: 0.010
Статус: Участник

Создано: 19 марта 2014 14:11
· Личное сообщение · #6

Для какой цели тебе необходим волновой алгоритм?
Вопрос обоснован, так как могу предложить Вам реализацию алгоритма Беллмана-Форда для поиска кратчайшего пути




Ранг: 72.3 (постоянный), 133thx
Активность: 0.380
Статус: Участник

Создано: 16 апреля 2014 03:46
· Личное сообщение · #7

Пограничное описание поверхности как альтернатива, так же и в случае заливки фигур.


 [email protected] —› Программирование —› Двумерном лабиринте - волновой алгоритм/ребята подскажите где ошибка?
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати