Lekce 3 - Jak najít nejkratší cestu z bodu A do bodu B?
V minulé lekci, Generování náhodného bludiště, jsme si popsali algoritmus pro generaci náhodného bludiště.
Velké množství strategických her (ať už tahových nebo realtime) se odehrává v terénu, který je tvořen dvojrozměrným polem políček, v podstatě čtvercovou sítí. Na té mapě na nějakém políčku A stojí náš hrdina/voják/dělník/tank/emzák apod. (nehodící se škrtněte). Nyní odscrolujeme na druhý konec mapy a tam klikneme na jiné políčko (B), kam chceme našeho výše uvedeného jedince poslat. A ten hrdina si teď musí rozmyslet, kudy přesně půjde, aby a) do cíle vůbec došel a b) mu to trvalo co nejkratší dobu.
Předpokládám, že souřadnice postaviček na mapě jsou celočíselné a chodí se vždycky z jednoho políčka na některé z osmi sousedních (rovně i šikmo, jako šachový král). Kdyby se chodilo jenom rovně, celý algoritmus by se hodně zjednodušil (zájemcům doporučuji článek o algoritmu vlny), ale my to teď zkusíme složitěji a obecněji.Začněme od nejjednodušších případů.Kdyby byl na celé mapě stejný terén a kdyby se na ní nevyskytovaly žádné překážky (prostě taková veliká rovná louka), stačilo by prostě vyrazit po přímce směrem z A do B. Na to stačí znát trochu geometrie (y=k*x+q) nebo rovnou použít Bresenhamův algoritmus. A nebo ještě primitivnější postup, který mnohdy docela dobře postačí:
while (X<>ciloveX)or(Y<>ciloveY) do
begin
if X>ciloveX then dec(X)
else if X<ciloveX then inc(X);
if Y>ciloveY then dec(Y)
else if Y<ciloveY then inc(Y);
...nejak zpracuj a uloz souradnice X,Y...
end;
Kdyby se na tu mapu dalo několik neprůchodných překážek (lesy, hory, rybníky...), mohli by vojáčci postupovat tak, že by nejdřív vyrazili přímo k cíli; když by narazili na překážku, zkusili by ji někudy obejít a kdyby se jim to nepovedlo, zastavili by se a čekali by na další rozkazy. Takhle nějak to fungovalo třeba ve Warcraftu 2.Konečně se dostáváme k té nejobecnější variantě: terén na mapě není všude stejný. Někde se chodí lépe a rychleji, jinde to jde ztuha. Políčka mapy jsou podle náročnosti terénu číselně ohodnocena: čím obtížnější terén, tím vyšší číslo (například pohodlná dlážděná cesta bude mít toto číslo nízké, zatímco bažina nebo hustý les vysoké; pokud chceme neprůchodnou překážku, použijeme "nekonečně velkou" hodnotu - prakticky stačí např. maximální hodnota, která se vejde do použitého číselného typu). A tohle je případ, který nás zajímá. Hráli jste někdy Heroes of Might and Magic (je jedno který díl)? V následujícím textu se pokusíme rekonstruovat, co se děje mezi okamžikem, kdy na mapě někam klikneme, a okamžikem, kdy se nám objeví šipkami vyznačená optimální cesta, kudy náš hrdina se svojí armádou půjde.
Krok nultý: nutné definice
Nejdřív si musíme ujasnit, jak vyhodnotíme obtížnost přechodu mezi dvěma políčky. Měla by se za směrodatnou považovat hodnota políčka, ze kterého vycházíme, nebo toho, na které se chystáme šlápnout, nebo nějaký průměr, nebo co vlastně? Odpověď je jednoduchá: to záleží na vás. Doporučuji (ale není to nutné) zvolit takový výraz, který vyjde stejný při cestě z prvního políčka na druhé i z druhého na první, takže se to potom neplete.Je tu ale ještě jedna záludnost. Pokud se ve čtvercové síti posuneme o pět políček šikmo, urazíme ve skutečnosti větší vzdálenost, než kdybychom šli vodorovně nebo svisle. Přesněji řečeno odmocnina-ze-dvou-krát, tj. 1,4142136krát větší. Což znamená, že při šikmém směru bychom měli obtížnost přechodu ještě násobit odmocninou ze dvou. Protože se ale nechceme pachtit s desetinnými čísly, zkusíme si s nimi trochu pohrát. 1:1.4142136 zaokrouhlíme na 1:1.4, vynásobíme deseti, vyjde 10:14, a nakonec vydělíme dvěma, aby nevycházela tak velká čísla, a vyjde 5:7. Takže při vodorovném nebo svislém pohybu násobíme pěti, při šikmém sedmi. Je jasné, že nám teď vyjdou větší čísla, ale to je jedno. Prostě pak postavičkám interně přidělíme pětkrát víc akčních bodů na chůzi, nebo jak tomu chcete říkat - stejně se většinou zobrazují na různých stupnicích, kde hráč žádná čísla nevidí.Pro svůj program jsem si nakonec zvolil vzorec:
ObtiznostPrechodu=((ObtiznostPrvnihoPolicka+ObtiznostDruhehoPolicka)*KorekceSmeru) shr 2
kde KorekceSměru je 5 nebo 7 a "shr 2" dá stejný výsledek jako "div 4", ale o pár taktů procesoru dříve, a dělám to proto, aby vycházela co nejmenší čísla a nebyly problémy s přetékáním na velkých mapách.
Krok první: ohodnocení mapy
Kdysi mi tento algoritmus na jednom fóru vysvětloval Lukáš Marek, za což
mu tímto ještě jednou děkuji. Později jsem zjistil, že se to jmenuje
Dijkstrův algoritmus pro nalezení optimální cesty v ohodnoceném grafu - to
jenom kdybyste potřebovali jeho pravé jméno pro účinnější provozování
googlovské magie 
.Nyní si
musíme nadefinovat, jak bude vypadat políčko mapy. Dejme tomu, že třeba
takhle:
type policko = record
ObtiznostTerenu:word;
Stav:byte;
Hodnota:word;
{...
a samozrejme dalsi, pro prakticke pouziti nezbytne
polozky, jako treba informace o tom, jestli uz je
policko odkryte, co je na nem za objekt a podobne
...}
end;
ObtiznostTerenu je jasná. Stav je třístavová proměnná. Může nabývat hodnot "zatím nic", "pracujem na něm" a "hotovo". Z praktických důvodů jsem zvolil typ Byte a hodnoty 0, 1 a 2.Do položky Hodnota budeme ukládat počet akčních bodů potřebných pro cestu z výchozího políčka (A) sem.
<odbočka>
Když už jsme u definic, pojďme si rovnou definovat celou mapu. Mohli bychom použít obyčejné dvojrozměrné pole typu array[1..výška,1..šířka] of policko, ale k tomu mám několik výhrad:
- Velikost mapy by byla pevně daná při kompilaci a nešla by za chodu programu změnit.
- Pokud programujete v reálném módu (např. v Turbo Pascalu), musela by se celá mapa vejít do 64 KB, což je maximální možná velikost proměnné, a nemohla by tedy být moc velká.
- Nebylo by to tak zajímavé .
Mapu si tedy můžeme definovat třeba jako dvojrozměrné dynamické pole:
{$R-} {vypnutí kontroly rozsahu, aby překladači nevadil rozsah pole 0..0}
type RadekMapy = array[0..0] of policko;
UkNaRadekMapy = ^RadekMapy;
SloupecMapy = array[0..0] of UkNaRadekMapy;
UkNaSloupecMapy = ^SloupecMapy;
Pak deklarujeme proměnné:
var Mapa:UkNaSloupecMapy;
VyskaMapy,SirkaMapy:word;
Jak se s takovou mapou pracuje? Nejdřív si nechte zadat šířku a výšku.
Potom pomocí funkce Getmem() alokujte za proměnnou
Mapa tak dlouhé pole ukazatelů, kolik chcete mít řádků:
Getmem(mapa,vyskamapy*sizeof(uknaradekmapy));
Potom za každým ukazatelem v tomto poli alokujte pole políček, které budou tvořit řádky mapy:
for i:=0 to vyskamapy-1 do getmem(mapa^[i],sirkamapy*sizeof(policko));
Samozřejmě taky průběžně testujte, jestli nedochází paměť (Maxavail). K políčkům mapy se přistupuje takto (například):
mapa^[y]^[x].obtiznostterenu:=neco;
Rozdíl oproti obyčejnému poli (mapa[y,x].obtiznostterenu) je téměř
zanedbatelný
</odbočka>
Takže mapu máme vytvořenou, v ní máme nějaký zajímavý terén (tj. jsou nějak vhodně nastavené položky ObtiznostTerenu u všech políček) a můžeme se konečně pustit do hledání cesty, vlastně do prvního kroku - ohodnocení mapy.
Počáteční inicializace:
- U všech políček na mapě nastavíme Stav na "zatím nic" a Hodnotu na "nekonečno" (zde použijeme číslo $FFFF, čili 65535).
- Výchozímu políčku (A) přiřadíme stav "pracujem na něm" a hodnotu 0.
Cyklus, který necháme běžet tak dlouho, dokud stav cílového políčka (B) není "hotovo":
- Z množiny všech políček ve stavu "pracujem na něm" vybereme to, které má nejmenší Hodnotu (dále Políčko).
- Stav tohoto Políčka změníme na "hotovo".
- Pro každého Souseda tohoto Políčka:
- Pokud je ve stavu "zatím nic", tak mu stav změníme na "pracujem na něm". Pokud je ve stavu "hotovo", neděláme nic a jdeme prohledávat dalšího souseda, jinak pokračujeme:
- Sečteme Hodnotu Políčka a obtížnost přechodu z Políčka na Souseda.
- Výsledek porovnáme s Hodnotou Souseda. Pokud je jeho Hodnota větší, nahradíme ji tímto výsledkem.
Na mapě nyní máme více nebo méně šišatou souvislou oblast políček s hodnotou "hotovo", která má přibližný střed v bodě A, rozlézá se do všech stran a nějakým cípem zasahuje až k políčku B. Okraj této oblasti tvoří políčka s hodnotou "pracujem na něm" a zbytek mapy zůstal ve stavu "zatím nic". Pokud byla políčka A a B blízko u sebe, bude tato oblast malá a algoritmus proběhne rychle. Jestli ale od sebe byla hodně daleko a terén na mapě je hodně komplikovaný, oblast bude hodně velká a výpočet potrvá déle.
Hodnota každého políčka ve stavu "hotovo" je rovna nejmenšímu možnému počtu "akčních bodů" potřebných na cestu do něj z políčka A.
Konečnost algoritmu je zajištěna tím, že v každém cyklu jedno políčko přejde do stavu "hotovo". Protože políček na mapě je konečný počet a jedno z nich je cíl B, určitě se k němu jednou dostaneme.
U každého políčka ve stavu "pracujem na něm" se postupně zkouší, jak dlouhá by byla cesta na něj ze sousedících políček, a nechává se tam vždycky délka té nejkratší. Protože pak v cyklu vybíráme vždycky políčko s nejmenší hodnotou, nemůže se stát, že bychom omylem nějaké políčko prohlásili za hotové, i když by třeba do něj ještě existovala nějaká kratší cesta, kterou jsme dosud neprozkoumali.
Z programátorského hlediska tu máme několik samostatných úkolů. Prvním je nalezení políčka ve stavu "pracujem na něm" s nejmenší Hodnotou. Dá se to udělat tak, že prohledáme celou mapu a u každého políčka zkontrolujeme, jestli se na něm pracuje a jakou má hodnotu. To je ovšem příšerně pomalé (hlavně u větších map). Lepší je udělat si nějaký pomocný seznam (nejlépe pole), do kterého budeme ukládat souřadnice políček ve chvíli, kdy jejich stav změníme ze "zatím nic" na "pracujem na něm". Projít takové pole a najít políčko s nejmenší hodnotou je rychlá záležitost, horší je to s jeho vyřazením. Já jsem to řešil přesunem části pole za mazaným políčkem tak, aby se vzniklá díra zakryla (je na to potřeba nějaká dostatečně rychlá varianta procedury Move). Nová políčka přidávám prostě na konec pole.
Druhým úkolem je ošetření sousedů. Na to je asi nejlepší napsat krátkou procedurku, které jako parametry předáme souřadnice souseda (relativní vzhledem k políčku, jehož je to soused) a korekci na směr (5 nebo 7). V této proceduře je hlavně potřeba ošetřit okraje mapy - nesmíme nic omylem zapsat mimo, protože to by způsobilo naši oblíbenou hláškou "Program provedl nepovolenou operaci a bude ukončen" (popř. v DOSu tvrdý zámrz).
Krok druhý: nalezení cesty v ohodnocené mapě
Tenhle krok bývá ve velkém množství článků, které můžete na síti najít, jaksi opomenut. A přitom bez něj je celá ohodnocená mapa k ničemu :-/ Předpokládám, že si jednotlivé kroky cesty chceme někam uložit. Pro jednoduchost bude nejlepší předvést si to na spojovém seznamu:
type UkNaKrok=^krok;
Krok = record
x,y:word;
dalsi:uknakrok;
end;
var PrvniKrok:uknakrok;
Z hlediska využití paměti by bylo lepší ukládat cestu do pole, ale takhle to bude názornější. Seznam bude jednosměrný, plnit ho budeme odzadu (tj. nové prvky budeme strkat před začátek). Ukazatel PrvniKrok ukazuje na začátek seznamu - první políčko cesty hned vedle A; poslední prvek seznamu obsahuje souřadnice políčka B.Začneme v cíli (políčku B). Možná teď někoho napadne, že bychom mohli prostě jít po nejmenších číslech - prozkoumat všechny sousedy a přejít na políčko s nejmenší Hodnotou. Mě to napadlo taky, vyzkoušel jsem to v praxi a zjistil jsem, že tudy ne, přátelé. Špatně se vysvětluje proč, ale takhle se prostě nejkratší cesta nenajde. Fungující algoritmus vypadá následovně:
Inicializace:
- Nastavíme se na políčko B a jeho souřadnice si uložíme.
Cyklus, který běží tak dlouho, dokud nejsme na políčku A:
- Projdeme všechny sousední políčka.
- U každého Souseda si spočítáme součet Hodnoty toho Souseda a obtížnost přechodu na aktuální políčko.
- Přesuneme se na to sousední políčko, které mělo tento součet nejmenší.
- Pokud to není A, uložíme si jeho souřadnice.
A jak by to všechno mohlo vypadat v praxi?
Třeba takhle:
procedure NajdiCestu(odkudX,odkudY,kamX,kamY:word);
const VelikostPole=1024; {velikost pomocneho pole pro ukladani policek ve stavu "pracujem na nem"}
type policko2 = record x,y:word; end; {tohle se do toho pole bude ukladat}
var i,j,tmpx,tmpy:integer; {\ruzne pomocne promenne}
tmphodnota,tmpindex:word; {/ }
p:uknakrok; {pro pridavani kroku cesty do spojoveho seznamu}
pole:array[0..velikostpole] of policko2; {pomocne pole na ukladani policek}
konec:word; {index za poslednim prvkem pole (misto, kam se do nej ma vlozit pristi policko)}
{}procedure prober(dx,dy:integer; korekce:word); {procedura pro osetrovani sousedu pri ohodnocovani mapy}
{}var soucet:longint; {dx,dy je relativni vzdalenost od policka tmpx,tmpy}
{}Begin
{}{osetreni okraju mapy:}
{}if (tmpx=0)and(dx<0) or
{} (tmpx=sirkamapy-1)and(dx>0) or
{} (tmpy=0)and(dy<0) or
{} (tmpy=vyskamapy-1)and(dy>0) then exit;
{}{vyreseni policka:}
{}with mapa^[tmpy+dy]^[tmpx+dx] do
{} begin
{} soucet:=mapa^[tmpy]^[tmpx].hodnota+(korekce*(mapa^[tmpy]^[tmpx].obtiznostterenu+obtiznostterenu)) shr 2;
{} if stav=0 then begin {policko je ve stavu "zatim nic"}
{} stav:=1; {prepis ho na "pracujem na nem"}
{} if konec<=velikostpole then {jestli se do pomocneho pole vejde...}
{} begin {...vlozime ho tam:}
{} with pole[konec] do begin x:=tmpx+dx; y:=tmpy+dy; end;
{} inc(konec);
{} end;
{} if soucet<$FFFF then hodnota:=soucet;
{} end
{} else if (stav=1) {uz bylo ve stavu "pracujem na nem"}
{} and(hodnota>soucet) then hodnota:=soucet;
{} end;
{}End;{prober}
{}procedure hledej(dx,dy:integer; korekce:word); {procedura pro prochazeni sousedu aktualniho policka }
{}var soucet:longint; {pri hledani cesty a nalezeni toho s nejmensim souctem}
{}Begin {Hodnoty a obtiznosti prechodu na aktualni policko. }
{}{okraje:} {dx,dy jsou opet relativni k tmpx,tmpy. }
{}if (tmpx=0)and(dx<0) or
{} (tmpx=sirkamapy-1)and(dx>0) or
{} (tmpy=0)and(dy<0) or
{} (tmpy=vyskamapy-1)and(dy>0) then exit;
{}with mapa^[tmpy+dy]^[tmpx+dx] do
{} begin
{} soucet:=hodnota+(korekce*(mapa^[tmpy]^[tmpx].obtiznostterenu+obtiznostterenu)) shr 2;
{} if soucet<tmphodnota then begin
{} i:=tmpy+dy;
{} j:=tmpx+dx;
{} tmphodnota:=soucet;
{} end;
{} end;
{}{Stav policka uz v tehle fazi neni potreba kontrolovat, protoze nejmensi}
{}{hodnoty maji vzdycky ta policka, ktera uz jsou ve stavu "hotovo".}
{}End;{hledej}
Begin{najdicestu}
{je dobre nejdriv smazat minulou cestu:}
while prvnikrok<>nil do begin
p:=prvnikrok;
prvnikrok:=prvnikrok^.dalsi;
dispose(p);
end;
{ohodnoceni mapy - inicializace:}
for i:=0 to vyskamapy-1 do
for j:=0 to sirkamapy-1 do with mapa^[i]^[j] do begin
stav:=0; {"zatim nic"}
hodnota:=$FFFF; {"nekonecno"}
end;
{pocatecni policko:}
with mapa^[odkudy]^[odkudx] do begin
stav:=1; {"pracujem na nem"}
hodnota:=0;
end;
{rovnou ho taky vlozime do pole:}
with pole[0] do begin x:=odkudx; y:=odkudy; end;
konec:=1;
{ohodnoceni mapy - cyklus:}
while (konec<>0) {pokud pomocne pole neni prazdne (coz by se mohlo stat, pokud by nestacila jeho
velikost, nektera policka by se do nej neulozila a pak by nam dosla driv nez
bychom se dostali do ciloveho policka)...}
and(mapa^[kamy]^[kamx].stav<>2) do {...a dokud cil neni ve stavu "hotovo"}
begin
{vybereme policko se stavem "pracujem na nem" s nejmensi hodnotou:}
tmphodnota:=$FFFF;
for i:=0 to konec-1 do {pro kazde policko ulozene v pomocnem poli}
with mapa^[pole[i].y]^[pole[i].x] do {najdeme odpovidajici policko na mape}
if hodnota<tmphodnota then begin
tmpx:=pole[i].x;
tmpy:=pole[i].y;
tmphodnota:=hodnota;
tmpindex:=i;
end;
{nyni mame jasno: hledane policko ma souradnice tmpx,tmpy,
hodnotu tmphodnota a v pomocnem poli se nachazi na pozici tmpindex}
{stav mu zmenime na "hotovo":}
mapa^[tmpy]^[tmpx].stav:=2;
{vyhodime ho z pomocneho pole (pouzijte tu nejrychlejsi variantu Move, jakou doma mate):}
if tmpindex<konec-1 then move(pole[tmpindex+1],pole[tmpindex],(konec-tmpindex-1)*sizeof(policko2));
dec(konec);
{probereme vsechna okolni policka:}
prober(-1, 0,5);
prober( 1, 0,5); {policka ve stavu "hotovo" ignorujeme, }
prober( 0,-1,5); {policka ve stavu "zatim nic" zmenime na "pracujem na nem",}
prober( 0, 1,5); {temto polickum dame takovou hodnotu, ktera je minimem }
prober(-1,-1,7); {z jejich aktualni hodnoty a vypocitane delky cesty do }
prober(-1, 1,7); {tohoto policka (viz drive) }
prober( 1,-1,7);
prober( 1, 1,7);
end;
if mapa^[kamy]^[kamx].hodnota=$FFFF then exit; {vidime, ze cesta je prilis dlouha takze koncime
(algoritmus by sice dobehl i tak, ale proc to utrpeni zbytecne prodluzovat)}
{nyni je mapa ohodnocena, zbyva nalezt kudy kudy cesticka:}
tmpx:=kamx; tmpy:=kamy; {zacneme v cili}
new(prvnikrok); cil:=prvnikrok; {cilove policko rovnou ulozime, je to taky soucast cesty}
with prvnikrok^ do begin
x:=tmpx;
y:=tmpy;
dalsi:=nil;
end;
j:=tmpx; i:=tmpy; {nutne pro pripad, kdy je cil = start}
repeat
tmphodnota:=$FFFF;
hledej(-1, 0,5);
hledej( 1, 0,5); {Ze sousedu policka tmpx,tmpy vybirame takove, ktere }
hledej( 0,-1,5); {ma nejmensi soucet sve hodnoty a hodnoty potrebne na }
hledej( 0, 1,5); {prechod z policka tmpx,tmpy. }
hledej(-1,-1,7);
hledej(-1, 1,7);
hledej( 1,-1,7);
hledej( 1, 1,7);
{nyni je v souradnicich j,i ulozena poloha hledaneho policka}
tmpx:=j; tmpy:=i; {presuneme se na to policko...}
{...a toto policko ulozime:}
if (tmpx<>odkudx)or(tmpy<>odkudy) {pocatecni policko uz ovsem ukladat nechceme, takze tohle jenom pro ty ostatni}
then begin {vlozime policko na zacatek seznamu}
new(p);
with p^ do begin
x:=tmpx;
y:=tmpy;
dalsi:=prvnikrok;
end;
prvnikrok:=p;
end;
until ((tmpx=odkudx)and(tmpy=odkudy)) {opakujeme cyklus, dokud nedojdeme do startu...}
or(tmphodnota=$FFFF); {...nebo dokud se nedostaneme na policko s hodnotou "nekonecno"
(coz by se mohlo stat, kdyby cesta byla extremne dlouha. Ovsem pak by se take
hodilo vymazat ty dva kroky, ktere jsou touhle dobou ulozene v seznamu)}
End;{najdicestu}
V proceduře nejsou obsaženy kontroly dostupné paměti (Maxavail) při
ukládání cesty do paměti, které si ale určitě každý doplní sám
(jestli ne, mohl by program umřít na Heap overflow).Když porovnáme
ohodnocování mapy a hledání cesty z hlediska výpočetní náročnosti,
zjistíme, že první část trvá mnohonásobně déle, protože se musí
pošťourat v daleko větším počtu políček. Ovšem můžeme využít toho,
že ohodnocení mapy je závislé pouze na poloze políčka A, ale ne už na
poloze B (ta nám udává jenom okamžik, kdy už můžeme s ohodnocováním
přestat, což ale nemusíme a můžeme si klidně ohodnotit celou mapu). Takže
si teoreticky můžeme proceduru rozdělit, mapu ohodnotit jednou a potom si
nechat rychle vyhledávat všechny možné cesty od místa, na kterém stojí
náš hrdina, a nakonec ho jednou z nich poslat. A když navíc výpočty
provádíme na pozadí (nebo spíš naopak, když výpočty běží v hlavním
cyklu programu a veškerá interakce s uživatelem visí na přerušeních),
můžeme hráče oblbnout natolik, že pak bude koukat, jak se ta cesta hledá
rychle (přitom se hledá poměrně pomalu, ale v okamžiku, kdy o tom neví).
Ale stejně by mě zajímalo, jak to machři z New World Computing u Heroes of
M. & M. vypiplali, že nalezení cesty přes celou mapu trvalo i na 486/66
MHz zanedbatelné zlomky sekundy - moje procedura se s tím na stejném
počítači (na mapě řádově 150x150 políček) dokáže piplat i 10 vteřin.
Ale hlavně že funguje
V další lekci, Průchod bludištěm - Theseus, si popíšeme algoritmus pro hledání nejkratší cesty z bodu A do bodu B se zdrojovými kódy.
