Связь с администрацией сайта:       

demo

Среди толпы я одинок

Кратчайший маршрут. Выход из лабиринта

Предстоит непростая задачка. Хотя очень распространена, особенно в игровой индустрии. Где надо рассчитать кратчайший путь к врагу или найти самый оптимальный маршрут прохождения уровня. В это мы и углубимся, для начальной задачи будем использовать файлы, рекурсию и еще много чего интересного.
 
Определимся с исходными данными.
Дана матрица n:m, состоящая из 0 и 1, где 1 - это стенка, 0 - проход.
И надо найти оптимальный проход из точки is,js (начало) в точку ie, je (конец).
Входной файл LABIRINT.IN содержит:                                           
1-я строка - размер поля  
2-я строка - координаты начальной позиции (row,col) 
3-я строка - координаты конечной позиции (row,col)
4-я строка и далее - схему лабиринта из 0 и 1  
Файл LABIRINT.IN: 
10 10
2 10 
1 6
1 1 1 1 1 0 1 1 1 1
1 0 0 0 0 0 1 0 1 0
1 0 1 1 1 1 1 0 1 0
1 0 1 0 1 0 0 0 1 0
1 0 1 0 1 0 0 0 1 0
0 0 1 0 1 0 0 0 1 0
0 0 1 0 1 1 1 1 1 0
1 0 0 1 0 1 0 0 0 0 
1 1 0 0 0 0 0 1 0 0
1 1 1 1 1 1 1 1 1 1
Выходной файл LABIRINT.OUT содержит маршрут прохода (i1:j1 ... in:jn): 
1:10
2:10
3:10
.... 
Получаем следующий код, а потом разберемся подробнее:
const LN = 50; LM = 50;
var a:array[1..LN,1..LM] of  byte;
    p:array[1..LN*LM,1..2] of  byte;
    s:array[1..LN*LM,1..2] of  byte;
    n,m,si,sj,ei,ej,index,min:integer;
 
procedure INIT;
var i,j:integer;
begin
     assign(input,'labirint.in'); reset(input);
     assign(output,' labirint.out'); rewrite(output);
     readln(n,m);
     readln(si,sj);
     readln(ei,ej);
     for i:=1 to n do begin
         for j:=1 to n-1 do begin
             read(a[i,j]);
         end;
         readln(a[i,n]);
     end;
     index:=0; min:=ln*lm;
end;
 
procedure Store;
begin
    if (min > index) then begin
        move( p, s, sizeof(p) );
        min:=index;
    end;
end;
 
procedure DONE;
var i:integer;
begin
    for i:=1 to min do writeln(s[i,1],':',s[i,2]);
end;
 
procedure FindPath(i,j:integer);
begin
    a[i,j]:=2;
    inc(index);
    p[index,1]:=i; p[index,2]:=j;
    if (i=ei) and (j=ej) then begin
        Store;
    end else begin
        if (i>1) and (a[i-1,j]=0) then FindPath(i-1,j);
        if (i<n) and (a[i+1,j]=0) then FindPath(i+1,j);
        if (j>1) and (a[i,j-1]=0) then FindPath(i,j-1);
        if (j<m) and (a[i,j+1]=0) then FindPath(i,j+1);
    end;
    dec(index);
    a[i,j]:=0;
end;
 
begin
     INIT;
     FindPath(si,sj);
     DONE;
end.
 
 
Пройдемся по функциям и процедурам и их назначению.
procedure INIT
Процедура INITнужна для чтения файла и подготовки исходных данных в массивы. Считывает начальные и конечные координаты, размер поля и само поле.
procedure  FindPath
Рекурсивная функция для расчетов оптимального пути. Где происходит проверка, достигнут ли результат, и находимся ли в конечной точке, перебирая каждый элемент массива.
 procedure Store
Служит для проверки конечной позиции. Находимся ли мы в точке координат, где изначально был заложен выход из лабиринта.
procedure DONE
Выводит результат найденного пути выхода из лабиринта.
 
Это один из самых простых способов поиска выхода из лабиринта в pascal. Теперь изменяя параметры файла LABIRINT.IN можно делать лабиринты любых размеров.
 
 
Rate this item
(0 votes)
Login to post comments