Ako nájsť najkratšiu cestu z bodu A do bodu B?

Veľké množstvo strategických hier (či už ťahových alebo realtime) sa odohráva v teréne, ktorý je tvorený dvojrozmerným poľom políčok, v podstate štvorcovou sietí. Na tej mape na nejakom políčku A stojí náš hrdina / vojak / robotník / tank / emzákem pod. (Nehodiace sa prečiarknite). Teraz odscrolujeme na druhý koniec mapy a tam klikneme na iné políčko (B), kam chceme nášho vyššie uvedeného jedinca poslať. A ten hrdina si teraz musí rozmyslieť, kadiaľ presne pôjde, aby a) do cieľa vôbec došiel ab) mu to trvalo čo najkratšie.

Predpokladám, že súradnice postavičiek na mape sú celočíselné a chodí sa vždy z jedného políčka na niektoré z ôsmich susedných (rovno aj šikmo, ako šachový kráľ). Keby sa chodilo len rovno, celý algoritmus by sa veľa zjednodušil (záujemcom odporúčam článok o algoritmu vlny), ale my to teraz skúsime zložitejšie a všeobecnejšie.
Začnime od najjednoduchších prípadov.

Keby bol na celej mape rovnaký terén a keby sa na nej nevyskytovali žiadne prekážky (proste taká veľká rovná lúka), stačilo by jednoducho vyraziť po priamke smerom z A do B. Na to stačí poznať trochu geometrie (y = k * x + q) alebo rovno použiť Bresenhamův algoritmus. A alebo ešte primitívnejší postup, ktorý mnohokrát celkom dobre 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;

Keby sa na tú mapu dalo niekoľko nepriechodných prekážok (lesy, hory, rybníky ...), mohli by vojačikovia postupovať tak, že by najskôr vyrazili priamo k cieľu; keď by narazili na prekážku, skúsili by ju Nekuda obísť a keby sa im to nepodarilo, zastavili by sa a čakali by na ďalšie rozkazy. Takto nejako to fungovalo napríklad vo Warcraftu 2.

Konečne sa dostávame k tej najvšeobecnejšej variante: terén na mape nie je všade rovnaký. Niekde sa chodí lepšie a rýchlejšie, inde to ide ťažko. Políčka mapy sú podľa náročnosti terénu číselne ohodnotená: čím ťažšie terén, tým vyššie číslo (napríklad pohodlná dláždená cesta bude mať toto číslo nízke, zatiaľ čo močiar alebo hustý les vysoké; ak chceme neprechodnou prekážku, použijeme "nekonečne veľkú" hodnotu - prakticky stačí napr. maximálna hodnota, ktorá sa zmestí do použitého číselného typu). A toto je prípad, ktorý nás zaujíma.

Hrali ste niekedy Heroes of Might and Magic (je jedno ktorý diel)? V nasledujúcom texte sa pokúsime rekonštruovať, čo sa deje medzi okamihom, kedy na mape niekam klikneme, a okamihom, kedy sa nám objaví šípkami vyznačená optimálna cesta, kadiaľ náš hrdina so svojou armádou pôjde.

Krok nultý: nutné definícia

Najskôr si musíme ujasniť, ako vyhodnotíme obtiažnosť prechodu medzi dvoma políčkami. Mala by sa za smerodajnú považovať hodnota políčka, z ktorého vychádzame, alebo toho, na ktoré sa chystáme šliapnuť, alebo nejaký priemer, alebo čo vlastne? Odpoveď je jednoduchá: to záleží na vás. Odporúčam (ale nie je to nutné) zvoliť taký výraz, ktorý vyjde rovnaký pri ceste z prvého políčka na druhej aj z druhého na prvý, takže sa to potom nepletie.

Je tu ale ešte jedna záludnosť. Ak sa v štvorcovej sieti posunieme o päť políčok šikmo, urážate v skutočnosti väčšiu vzdialenosť, než keby sme išli vodorovne alebo zvisle. Presnejšie povedané odmocnina-z-dvoch-krát, tj. 1,4142136krát väčšie. Čo znamená, že pri šikmom smere by sme mali obtiažnosť prechodu ešte násobiť odmocninou z dvoch. Pretože sa ale nechceme pachtit s desatinnými číslami, skúsime sa s nimi trochu pohrať. 1: 1.4142136 zaokrúhlime na 1: 1.4, vynásobíme desiatimi, vyjde 10:14, a nakoniec vydelíme dvoma, aby nevychádzala tak veľké čísla, a vyjde 5: 7. Takže pri horizontálnom alebo vertikálnom pohybe násobíme piatich, pri šikmom siedmich. Je jasné, že nám teraz vyjdú väčšie čísla, ale to je jedno. Proste potom postavičkám interne pridelíme päťkrát viac akčných bodov na chôdzu, alebo ako tomu chcete hovoriť - rovnako sa väčšinou zobrazujú na rôznych stupniciach, kde hráč žiadne čísla nevidí.

Pre svoj program som si nakoniec zvolil vzorec:

ObtiznostPrechodu=((ObtiznostPrvnihoPolicka+ObtiznostDruhehoPolicka)*KorekceSmeru) shr 2

kde KorekceSměru je 5 alebo 7 a "shr 2" dá rovnaký výsledok ako "div 4", ale o pár taktov procesora skôr, a robím to preto, aby vychádzala čo najmenšie čísla a neboli problémy s pretekaním na veľkých mapách.

Krok prvý: ohodnotenie mapy

Kedysi mi tento algoritmus na jednom fóre vysvetľoval Lukáš Marek, za čo mu týmto ešte raz ďakujem. Neskôr som zistil, že sa to volá Dijkstrov algoritmus pre nájdenie optimálnej cesty v Ohodnotenie grafe - to len keby ste potrebovali jeho pravé meno pre efektívnejšiu prevádzku googlovské mágie .

Teraz si musíme nadefinovať, ako bude vyzerať políčko mapy. Dajme tomu, že napríklad takto:

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á premenná. Môže nadobúdať hodnoty "zatiaľ nič", "pracujem na ňom" a "hotovo". Z praktických dôvodov som zvolil typ Byte a hodnoty 0, 1 a 2.
Do položky Hodnota budeme ukladať počet akčných bodov potrebných pre cestu z východiskového políčka (A) sem.

<odbočka>
Keď už sme pri definícií, poďme si rovno definovať celú mapu. Mohli by sme použiť obyčajné dvojrozmerné pole typu array [1..výška, 1..šířka] of policko, ale k tomu mám niekoľko výhrad:

1. Veľkosť mapy by bola pevne daná pri kompilácii a nešla by za chodu programu zmeniť.
2. Ak programujete v reálnom móde (napr. V Turbo Pascal), musela by sa celá mapa vojsť do 64 KB, čo je maximálna možná veľkosť premennej, a nemohla by teda byť moc veľká.
3. Nebolo by to tak zaujímavé .

Mapu si teda môžeme definovať napríklad ako dvojrozmerné 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;

Potom deklarujeme premenné:

var Mapa:UkNaSloupecMapy;
    VyskaMapy,SirkaMapy:word;

Ako sa s takou mapou pracuje? Najskôr si nechajte zadať šírku a výšku. Potom pomocou Getmem vyhraďte za premennú Mapa tak dlhé pole ukazovateľov, koľko chcete mať riadkov:

Getmem(mapa,vyskamapy*sizeof(uknaradekmapy));

Potom za každým ukazovateľom v tomto poli vyhraďte pole políčok, ktoré budú tvoriť riadky mapy:

for i:=0 to vyskamapy-1 do getmem(mapa^[i],sirkamapy*sizeof(policko));

Samozrejme taky priebežne testujte, či nedochádza pamäť (Maxavail).

K políčkam mapy sa pristupuje takto (napríklad):

mapa^[y]^[x].obtiznostterenu:=neco;

Rozdiel oproti obyčajnému poli (mapa [y, x] .obtiznostterenu) je takmer zanedbateľný .
</ odbočka>

Takže mapu máme vytvorenú, v nej máme nejaký zaujímavý terén (tj. Sú nejako vhodne nastavené položky ObtiznostTerenu u všetkých políčok) a môžeme sa konečne pustiť do hľadania cesty, vlastne do prvého kroku - ohodnotenie mapy.

Počiatočná inicializácia:

• Pri všetkých políčok na mape nastavíme Stav na "zatiaľ nič" a Hodnotu na "nekonečno" (tu použijeme číslo $ FFFF, čiže 65535).
• Predvolenému políčku (A) priradíme stav "pracujem na ňom" a hodnotu 0.

Cyklus, ktorý necháme bežať tak dlhú, kým stav cieľového políčka (B) nie je "hotovo":

• Z množiny všetkých políčok v stave "pracujem na ňom" vyberieme to, ktoré má najmenší Hodnotu (ďalej Políčko).
• Stav tohto Políčka zmeníme na "hotovo".
• Pre každého Suseda tohto Políčka: Pokiaľ je v stave "zatiaľ nič", tak mu stav zmeníme na "pracujem na ňom". Pokiaľ je v stave "hotovo", nerobíme nič a ideme prehľadávať ďalšieho suseda, inak pokračujeme:

  Sčítame Hodnotu Políčka a obtiažnosť prechodu z Políčka na Suseda.

  Výsledok porovnáme s Hodnotou Suseda. Ak je jeho hodnota väčšia, nahradíme ju týmto výsledkom.

• Pokiaľ je v stave "zatiaľ nič", tak mu stav zmeníme na "pracujem na ňom". Pokiaľ je v stave "hotovo", nerobíme nič a ideme prehľadávať ďalšieho suseda, inak pokračujeme:
• Sčítame Hodnotu Políčka a obtiažnosť prechodu z Políčka na Suseda.
• Výsledok porovnáme s Hodnotou Suseda. Ak je jeho hodnota väčšia, nahradíme ju týmto výsledkom.

Na mape teraz máme viac alebo menej zdeformovaný súvislú oblasť políčok s hodnotou "hotovo", ktorá má približný stred v bode A, rozlieza sa do všetkých strán a nejakým cípom zasahuje až k políčku B. Okraj tejto oblasti tvoria políčka s hodnotou "pracujem na ňom "a zvyšok mapy zostal v stave" zatiaľ nič ". Ak bola políčka A a B blízko pri sebe, bude táto oblasť malá a algoritmus prebehne rýchlo. Ak ale od seba bola veľmi ďaleko a terén na mape je veľa komplikovaný, oblasť bude veľa veľká a výpočet potrvá dlhšie.

Hodnota každého políčka v stave "hotovo" je rovná najmenšiemu možnému počtu "akčných bodov" potrebných na cestu do neho z políčka A.

Konečnosť algoritmu je zabezpečená tým, že v každom cykle jedno políčko prejde do stavu "hotovo". Pretože políčok na mape je konečný počet a jedno z nich je cieľ B, určite sa k nemu raz dostaneme.

Pri každom políčka v stave "pracujem na ňom" sa postupne skúša, ako dlhá by bola cesta na neho zo susediacich políčok, a necháva sa tam vždy dĺžka tej najkratšej. Pretože potom v cykle vyberáme vždy políčko s najmenšou hodnotou, nemôže sa stať, že by sme omylom nejaké políčko vyhlásili za hotové, aj keď by napríklad do neho ešte existovala nejaká kratšia cesta, ktorú sme doteraz nepreskúmali.

Z programátorského hľadiska tu máme niekoľko samostatných úloh.
Prvým je nájdenie políčka v stave "pracujem na ňom" s najmenšou Hodnotou. Dá sa to urobiť tak, že prehľadáme celú mapu au každého políčka skontrolujeme, či sa na ňom pracuje a akú má hodnotu. To je však príšerne pomalé (hlavne u väčších máp). Lepšie je urobiť si nejaký pomocný zoznam (najlepšie polia), do ktorého budeme ukladať súradnice políčok vo chvíli, keď ich stav zmeníme zo "zatiaľ nič" na "pracujem na ňom". Prejsť také pole a nájsť políčko s najmenšou hodnotou je rýchla záležitosť, horšie je to s jeho vyradením. Ja som to riešil presunom časti poľa za mazaným políčkom tak, aby sa vzniknutá diera zakryla (je na to potrebné nejaká dostatočne rýchla varianta procedúry Move). Nová políčka pridávam jednoducho na koniec poľa.

Druhou úlohou je ošetrenie susedov. Na to je asi najlepšie napísať krátku procedurku, ktoré ako parametre odovzdáme súradnice suseda (relatívna vzhľadom k políčku, ktorého je to sused) a korekciu na smer (5 alebo 7). V tejto procedúre je hlavne potrebné ošetriť okraje mapy - nesmieme nič omylom zapísať mimo, pretože to by spôsobilo našu obľúbenú hláškou "Program vykonal nepovolenú operáciu a bude ukončený" (príp. V DOSe tvrdý zamŕza).

Krok druhý: nájdenie cesty v ohodnotené mape

Tento krok býva vo veľkom množstve článkov, ktoré môžete na sieti nájsť, akosi opomenutý. A pritom bez neho je celá ohodnotená mapa k ničomu: - /.

Predpokladám, že si jednotlivé kroky cesty chceme niekam uložiť. Pre jednoduchosť bude najlepšie predviesť si to na spájať zoznamu:

type UkNaKrok=^krok;
Krok = record
       x,y:word;
       dalsi:uknakrok;
       end;

var PrvniKrok:uknakrok;

Z hľadiska využitia pamäte by bolo lepšie ukladať cestu do poľa, ale takto to bude názornejšie. Zoznam bude jednosmerný, plniť ho budeme odzadu (tj. Nové prvky budeme strkať pred začiatok). Ukazovateľ PrvniKrok ukazuje na začiatok zoznamu - prvé políčko cesty hneď vedľa A; posledný prvok zoznamu obsahuje súradnice políčka B.

Začneme v cieli (políčku B). Možno teraz niekoho napadne, že by sme mohli jednoducho ísť po najmenších číslach - preskúmať všetky susedov a prejsť na políčko s najmenšou Hodnotou. Mňa to napadlo taky, vyskúšal som to v praxi a zistil som, že tadiaľ nie, priatelia. Zle sa vysvetľuje prečo, ale takto sa jednoducho najkratšia cesta nenájde. Fungujúce algoritmus vyzerá nasledovne:

Inicializácia:

• Nastavíme sa na políčko B a jeho súradnice si uložíme.

Cyklus, ktorý beží tak dlho, kým nie sme na políčku A:

• Prejdeme všetky susedné políčka.
• Pri každom Suseda si spočítame súčet Hodnoty toho Suseda a obtiažnosť prechodu na aktuálnu políčko.
• Presunieme sa na to susedné políčko, ktoré malo tento súčet najmenších.
• Ak to nie je A, uložíme si jeho súradnice.

A ako by to všetko mohlo vyzerať v praxi?

Napríklad takto:

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 procedúre nie sú obsiahnuté kontroly dostupnej pamäte (Maxavail) pri ukladaní cesty do pamäte, ktoré si ale určite každý doplní sám (ak nie, mohol by program umrieť na Heap overflow).

Keď porovnáme ohodnocovanie mapy a hľadanie cesty z hľadiska výpočtovej náročnosti, zistíme, že prvá časť trvá mnohonásobne dlhšie, pretože sa musí pošťourat v ďaleko väčšom počte políčok. Ovšem môžeme využiť to, že ohodnotenie mapy je závislé iba od polohy políčka A, ale nie už na polohe B (tá nám udáva iba okamih, kedy už môžeme s ohodnocováním prestať, čo ale nemusíme a môžeme si pokojne ohodnotiť celú mapu). Takže si teoreticky môžeme procedúru rozdeliť, mapu ohodnotiť raz a potom si nechať rýchlo vyhľadávať všetky možné cesty od miesta, na ktorom stojí náš hrdina, a nakoniec ho jednou z nich poslať. A keď navyše výpočty robíme na pozadí (alebo skôr naopak, keď výpočty beží v hlavnom cykle programu a všetky interakcie s užívateľom visí na prerušeniach), môžeme hráča oblbnúť natoľko, že potom bude pozerať, ako sa tá cesta hľadá rýchlo (pritom sa hľadá pomerne pomaly, ale v okamihu, keď o tom nevie). Ale rovnako by ma zaujímalo, ako to machri z New World Computing u Heroes of M. & M. vypiplali, že nájdenie cesty cez celú mapu trvalo aj na 486/66 MHz zanedbateľné zlomky sekundy - moja procedúra sa s tým na rovnakom počítači (na mape rádovo 150x150 políčok) dokáže piplat aj 10 sekúnd. Ale hlavne že funguje .