Posted By: Qwertis (Qwertis) on 'CZprogram'
Title:     Re: Routing ...
Date:      Thu Apr 22 15:26:14 1999

> 
>    Ahoj:)
> 
>    Zajimalo by me, jak pracuji algoritmy na vyhledavani cest mezi dvema body
> 
> (npr. ve hrach - pajdrlaci obhazi prekazky). Nevite, kde k tomu sehnat
> nejake 
> info ?
> 
>    Diky :)
> 
>    Medula 

No nevim jak pracuji algoritmy v ruznych hrach, ale zadna slava to nebude. 
Vzpomenme si na ruzne strategicke hry (nejvic je to videt na hre 
Civilization), kde se jednotky dostavaji na misto urceni jen velice obtizne a 
casto se nekde cestou zaseknou.
Ja jsem jednou resil podobny problem a vymyslel jsem tento algoritmus:
Dejme tomu, ze se ma nejaka jednotka dostat z mista 1 do mista 2 a musi pri 
tom obchazet ruzne prek8zky a hrozi i realne nebezpeci, ze vleze do slepe 
ulicky -  jako napr v bludisti.
Algoritmus je zalozen na principu rekurzivniho vyplnovani seminkem (seedfill).
Nejdriv musim mit pomocnou strukturu (nejlepe dvourozmerne pole) o stejn7ch 
rozmerech jako ma "mapa" na ktere se pohybyji jednotky.
Dejme tomu, ze mapa ma 100x100 policek a ja se chci pohybovat z mista o 
souradnicich x1, y1 do mista o souradnicich x2,y2.
Pro jednoduchost predpokladejme, ze mam jen ctyri moznosti pohybu (nahoru 
dolu, doprava, doleva).
1. Vytvorim si pole o rozmerech 100x100 typu byte.
2. Toto pole vynuluju.
3. Na pozice v tomto poli, na kterych je na mape nepruchozi prekazka dam 
jednicky.
4. a ted pro kazdy ze ctyr smeru udelam toto:
5.  pro pohyb nahoru nebo dolu vyplnym jednickami radek cislo y1, tj ten radek 
co je na nem pohybyjici se jednotka. Pro pohyb vpravo nebo vlevo vyplnim zase 
odpovidajici sloupec. viz obrazek.
6.  Zacnu "vvyplnovat" pole barvou 2 s hranicni barvou 1, pri rekurzivnim 
zanorovani si pamatuju hloubku zanoreni a neustale kontroluji jestli uz 
nevyplnuji cilove misto x2,y2. Jakmile se to stane, zapamatuji si hloubku a 
zkusim sousedni smery. Potom porovnam hloubky zanoreni potrebne k dosazeni 
cilove pozice a vyberu smer, u ktereho bylla nejmensi, to je optimalni smer a 
timto smerem posunu pajdrlaka.

obrazek
    Pole   pri testu pohybu nahoru
|----------------------|    
|                      |  A zdrojova pozice 
|           1       B  |  B cilova pozice
|          1           |  1 reprezentuji prekazky a pomocnou hraz vytvorenou
|           1          |    pro test pohybu nahoru
|           1          |  P misto odkud zacinam vyplnovat seminko
|  1111          1     |  
|                1     |   V momente kdy vyplnym pozici B ukoncim vyplnovani
|   P            1     |   a hroubka zanoreni je optimalni pocet kroku k cili
|111A111111111111111111|   Pokud vsechno vyplnim a nedosahnu cile, pak tento 
|                      |   smer k cili nevede a zkusim dalsi.
|----------------------| 
 
Tato metoda je uplna a optimalni.
           --    ---   --   ------    -      -
         /      |     |      |      |    /   
         |    |  |-    |  /    |      |    __
            /  |     |      |      |       /
           --   ---   |   |   

Search the boards