Алгоритм лабринта

[Apophis]

hi народ
подскажите какой бы вы сделали алгоритм для прохождения лабиринта
такова к примеру

[ROD]

Обычно используют (в простых случаях) волновой алгоритм поиска пути.

[baster128]

Интересная штука. Два поля - два игрока? А второй - машина? Просто интересно - извини. Много видел примитивных игрушек но такую, в первый раз.

[Sparky]

вот когда-то писала:

program game;
const
     nmax=20;
     mmax=20;
type
    koord=record  //хранение координат
             x:integer;
             y:integer;
    end;
var
    i,j,n,m:integer;   //счетчики и границы массива
    sx,sy:integer;    //координаты старта
    pole:array [0..nmax-1,0..mmax-1] of char; //игрово поле
    left,rigth: integer;                    //границы очереди
    tx,ty:integer;                   //элементы смежные с текущим
    fx,fy:integer;
    ocher:array [0..1000] of koord;   //очередь
    d:array [0..nmax,0..mmax] of integer;        //расстояние
    p:koord;                  //значение взятое со стека
    dx,dy:array [0..3] of integer; //воозможные координаты х и у
    input,output:text;

{------------------------------------поиск минимального пути--------------------}
function min(a,b:integer):integer;
begin
     if a<b then min:=a
     else min:=b;
end;

{----------------------------запись значения в очередь--------------------------}
procedure push(xx,yy:integer);
begin
     ocher[rigth].x:=xx;
     ocher[rigth].y:=yy;
     rigth:=(rigth+1)mod (nmax*mmax);
end;

{----------------------------взятие значения из стека---------------------------}
procedure pop(var pp:koord);
begin
     pp.x:=ocher[left].x;
     pp.y:=ocher[left].y;
     ocher[left].x:=0;
     ocher[left].y:=0;
     left:=(left+1)  mod (nmax*mmax);
end;

{------------------------------ввод данных--------------------------------------}
procedure InputData;
begin
     assign(input,'input4.txt');
     assign(output,'output4.txt');
     reset(input);
     rewrite(output);
     left:=0;
     rigth:=0;
     dx[0]:=1;dx[1]:=-1;dx[2]:=0;dx[3]:=0;
     dy[0]:=0;dy[1]:=0;dy[2]:=1;dy[3]:=-1;
     read(input,n);
     readln(input,m);
     for i:=0 to n-1 do
     begin
          for j:=0 to m-1 do
          begin
              read(input,pole[i,j]);
          end;
          readln(input);
     end;
end;

{------------------------------ввывод данных------------------------------------}
procedure OutputData;
begin
     for i:=0 to n-1 do
     begin
         for j:=0 to m-1 do
         begin
             write(output,pole[i,j]);
         end;
         writeln(output);
     end;
     close(input);
     close(output);
end;

{------------------------------главная программа--------------------------------}
 begin
      InputData;
      for i:=0 to n-1 do
      begin
          for j:=0 to m-1 do
              write(pole[i,j]);
          writeln;
      end;
      for i:=0 to n-1 do
          for j:=0 to m-1 do
             if pole[i,j]='s' then
             begin
                  d[i,j]:=0;
                  push(i,j);
                  sx:=i;
                  sy:=j;
             end
             else
                 if pole[i,j]='f' then
                 begin
                      fx:=i;
                      fy:=j;
                      d[i,j]:=1000;
                 end
                 else d[i,j]:=1000;
      while left<>rigth do
      begin
           pop(p);
           for i:=0 to 3 do
           begin
                tx:=p.x+dx[i];
                ty:=p.y+dy[i];
                if (tx>=0)and(tx<n)and(ty>=0)and(ty<m) then
                   if(pole[tx,ty]<>'#')and(d[tx,ty]=1000) then
                                                          if (pole[tx,ty]='f') then
                                                             d[tx,ty]:=min(d[tx,ty],d[p.x,p.y]+1)
                                                          else
                                                          begin
                                                               push(tx,ty);
                                                               d[tx,ty]:=d[p.x,p.y]+1;
                                                          end;
           end;
      end;
      if d[fx,fy]=1000 then
      begin
           writeln(output,'puti net');
           close(input);
           close(output);
      end
      else
      begin
           writeln(output,d[fx,fy]);
           while d[fx,fy]<>0 do
                 for i:=0 to 3 do
                 begin
                      tx:=fx+dx[i];
                      ty:=fy+dy[i];
                      if (tx>=0)and(tx<n)and(ty>=0)and(ty<m) then
                         if d[tx,ty]=d[fx,fy]-1 then
                            begin
                                 pole[tx,ty]:='*';
                                 fx:=tx;
                                 fy:=ty;
                            end;
                 end;
                 pole[sx,sy]:='s';
                 for i:=0 to n-1 do
                 begin
                      for j:=0 to m-1 do
                          write(d[i,j]);
                      writeln;
                 end;
                 OutputData;
      end;
end.

[Levsha100]

Пожалуйста:

вверх 1
влево до_упора
вправо 1
вниз до_упора
вправо до_упора
влево 1
вверх до_упора
вправо до_упора
влево 2
вверх до_упора
вправо до_упора
влево 1
вниз до_упора
влево до_упора
вправо 1
вверх 1

[Snejnaya]

Предполагается, что алгоритм должен работать для любого лабиринта, а не только для этого?

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

ЗЫ: если предполагается, что будут соревноваться человек и компьютер, то человек, ИМХО, победит лабиринте любой конфигурации.

[Sparky]

эм я написала реализацию алгоритма прохода по лабиринту из одной точки в другую, метод вроде называется поиск в ширину, что мы еще обсуждаем?