Rychlejší Pathfinding

[Akhera]

Pro svou hru používám algoritmus A*, bohužel se ukazuje, že ve Flashi je jeho základní verze příliš pomalá - průměrně trvá 0,5 až 1 sekundu, ale v nejhorších případech i 4, což je i pro tahovou strategii neúnosné.

Vím, že problém není v technologii, protože tenhle http://www.schuirink.net/~casper/flash/AI/path-flasm.html program to samé zvládá 10-15x rychleji, což by mi bohatě stačilo, jenže zdrojový kód nikde... Nevíte náhodou, jak by se dal algoritmus A* optimalizovat, nebo kde je na to nějaký návod? Na netu nemůžu nic najít...

[adragon]

na flash existuji decompilery http://www.sothink.com/product/flashdecompiler/

treba by mohly pomoci

[Weny Sky]

Pouzivas pro ulozeni seznamu kandidatu na dalsi krok haldu nebo ty prvky hazes do pole a pak je v nem hledas?

Jinak rychlost zvysis zmenou heuristiky. Treba tak, ze uzly jdouci k cili ohodnotis vyhodnej, nez uzly, ktere jsou opacnym smerem od cile. Timto dosahnes toho ze se algorimus bude hnat za cilem rychlej nez normalne, ale nevyhodou muze byt, ze jiz nemusi nalezt opravdu nejkratsi cestu, ale treba cestu o par policek delsi

[Pavel]

hmm...ja myslel, ze A* je Dijkstra, rozsirena o heuristiku a plati, ze pokud se jedna o "admissible" heuristiku pak je cesta i nejkratsi....

[Akhera]

Díky za pomoc, ale nakonec jsem to vyřešila sama
Původně se seznam dalších kandidátů srovnával podle ceny, ale překvapivě se ukázalo, že nesrovnávat seznam a místo toho v něm hledat je skoro 10x rychlejší. Byl to zoufalý pokus, ale dopadl dobře

[Fila]

Tomu uplne nerozumim -- co je to srovnavat seznam? Jako stovnavat, zdali obsahuji dva seznamy stejne prvky (v libovolne permutaci)? To je sakra pomale . Hledas v nem nejak sofistikovane, nebo tak, ze jej projdes cely? Kdyztak sem hod kod, treba by se dal jeste urychlit... I ta 1/10 sekundy je i na ActionScript moc, pokud nemas fakt velkou mapu.

[Quiark]

Podle mě bylo myšleno řadit ho. V závislosti na použitém třídícím algoritmu může třídění setřízených dat trvat docela dlouho a proto je rozdíl mezi "udržovat seznam setřízený" a "po každém přidání prvku ho znovu setřídit".
_________________
Mám strach

[Fila]

Jasne, uz to tam vydim. Kdyby jsi chtela rychle hledani i rychlou aktualizaci seznamu, sahni po nejakem automaticky balancovanem vyhledavacim strome, treba AVL nebo cernobilem. Pokud by ti to prislo zbytecne slozite a nedelas v seznamu moc velke zmeny (jakoze treba pridas jednu dve hodnoty), pouzij bubblesort, jen ho pust odzadu, pokud pridavas nove prvky na konec .

Ale asi by to chtelo fakt videt cely ten kod, jestli pouzivas razeny seznam jako prioritni frontu, bylo by spis lepsi implementovat haldu.

[Akhera]

No nakonec seřazování seznamu vůbec není potřeba, upravila jsem pathfinding tak, aby nehledal, jak se nejrychleji dostat na nějaké místo, ale aby našel a označil všechna místa, kam jednotka se svými akčními body může jet. Sice výpočet trvá asi 0,2s, ale děje se to vždy jen při označení jednotky, pak už žádné další výpočty nejsou třeba