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. -- --- -- ------ - - / | | | | / | | |- | / | | __ / | | | | / -- --- | |