|
Нумерация клеток для Волнового алгоритма для игры от Виталия
Соколова (Украина)
Все найденные мною в Интернете алгоритмы казались мне
большими и сложными для понимания каждого шага. Поэтому я был вынужден изменить
алгоритм, чтобы он был компактным, быстрым и надежным. Прошу свою критику
оставлять в комментариях – буду учитывать ее обязательно.
Итак начнем с моего первого алгоритма на делфи. Написан для
демонстрационной программы, в которой смайлик обходит препятствия и доходит до
места, где мы кликаем мышкой:
//koordinati
geroya
x:=strtoint(label1.Caption);
y:=strtoint(label2.Caption);
start.x:=x;
start.y:=y;
//rasstanovka
vokrug 1
if
(map[x-1,y]<>-1) and (x-1>1) then map[x-1,y]:=1;
if
(map[x+1,y]<>-1) and (x+1<8)
then map[x+1,y]:=1;
if
(map[x,y-1]<>-1) and (y-1>1)
then map[x,y-1]:=1;
if
(map[x,y+1]<>-1) and (y+1<8)
then map[x,y+1]:=1;
//rasstanovka
shagov
n:=1;
while
n<=20 do
begin
for i:=1 to 8 do
begin
for j:=1 to 8 do
begin
if map[i,j]=n then
begin
//esli sleva ne kray karti
if (map[i-1,j]=0) and (i>1) then map[i-1,j]:=n+1;
//esli sprava ne kray karti
if (map[i+1,j]=0) and (i<8) then map[i+1,j]:=n+1;
//esli sverhu ne kray karti
if (map[i,j-1]=0) and (j>1) then map[i,j-1]:=n+1;
//esli snizu ne kray karti
if (map[i,j+1]=0) and (j<8) then map[i,j+1]:=n+1;
end;
end;
end;
n:=n+1;
end;
Место героя отмечаем нулем
map[x,y]:=0;
На мой взгляд довольно понятный алгоритм, но опять же размер
его меня не устроил и для игры я решил еще сократить его до более мелких
размеров. Таким образом получился такой алгоритм:
procedure
Put;
var n,i,j,z,x:Integer;
begin
//начальное обнуление
for i:=1 to 20 do
for j:=1 to 20 do
Begin
//отмечаем
непроходимы участки (деревья, другие человечки и тд)
if map[i,j]<0 then Hmap[i,j]:=-1
//отмечаем проходимые участки
else Hmap[i,j]:=0;
end;
//Отмечаем место с человечком
Hmap[Play.x,Play.y]:=99;
//На соседних клетках
ставим единицы потому что мы до них доберемся за один ход если они не заняты
for i:=Play.x-1 to Play.x+1 do
for j:=Play.y-1 to Play.y+1 do
if (Hmap[i,j]>-1) and
(Hmap[i,j]<>99) then Hmap[i,j]:=1;
//Проставляем цифры
(за сколько ходоа мы дойдем до точки)
n:=1;
while (n<=100) do
begin
for i:=1 to Xmap do
for j:=1 to Ymap do
if Hmap[i,j]=n then
begin
for z:=i-1 to i+1 do
for x:=j-1 to j+1 do
begin
if (z>0) and (z<=Xmap) and
(x>0) and (x<=Ymap) and (Hmap[z,x]=0) then
Hmap[z,x]:=n+1;
end;
end;
n:=n+1;
end;
Останется сделать только алгоритм, который выберит
кратчайший путь и все. Если Вы хотите запретить хождение по диагоналям героям
или замедлить скорость движения по диагоналям, то алгоритм нужно будет немного
изменить. Если кому-то это интерестно – пишите и я создам стать. Всем удачи!
Источник Delgame.at.ua
| 