A* Pathfinding

[if.then]

No kód je zdokumentovaný málo a hlavně špatně (v metodě find je třeba velikost openedListu na výstupu popsána jako "počet sousedů", což mi prostě hlava nebere).

Heuristiku máš velmi zajímavou, pro začátek bys měl použít asi Euklideovskou vzdálenost, protože ta by v otevřeném terénu měla nacházet ideální cesty /tipuji, kdyžtak mě opravte/ (hm, co se teď koukám na svůj kód, tak používám jenom Manhattanskou vzdálenost a taky to funguje dobře... takže jednu z těchto dvou).

Co jsem opravdu nepochopil (a v čem asi bude chyba) je tenhle kus kódu v metodě find:

[OndraSej]

if.then> Opravuji te. Pokud mas ctvercove dlazdice s pohybem sikmo, pak Manhattanska metrika je spatne (neni pripustna) a Euklidovska dava prilis nizke odkazy, ta pouzita je optimalni (to jsme tu resili nekde na prvni/zacatku druhe stranky).

Ten setParent spatne je, to by se melo dit pri aktualizaci G. Ale tohle je cele o tom, ze cestu nejde stavit uvnitr toho cyklu, kde se presouvaji uzly z OPEN do CLOSED.
_________________
http://trionteam.net

[if.then]

OK, díky za opravu.
_________________
For guns and glory, go to www.ceske-hry.cz.
For work and worry, execute VC++.

[Lorin]

[mar]

Ještě poslední poznámka k té heuristice: problém u čtvercových dlaždic je, že existuje (může a v 99% případů to tak bude) víc cest se stejnou kvalitou, takže ani při té správné heuristice to neprojde nejmenší možný počet.

Je potřeba vyrešit shody drobnou modifikací heuristiky, viz
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#a-stars-use-of-the-heuristic

[rezna]

heuristik a jejich uprav existuji kvanta - a to vse uz zalezi od aplikace dane heuristiky - resp. taky ve spravnem oceneni pohybu - a to treba jestli neni v danem okamziku zpomalujici zatacet - pak je treba manhattanskou heuristiku doplnit o preferenci rovneho pohybu a zatacet jen v nutnych pripadech ...

[mar]

@rezna: bavil jsem se o vyřešení shod v konkrétním případě.
penalizaci otáčení bych asi radši přidal do costu hrany. Je jedno, kam to dát, ale přijde mi to logičtější takhle. Penalizace uzlu můžu dát do heuristiky, protože ve výsledku se to stejně sečte. Prostě pro mě je heuristika něco, co mě táhne k cíli, nic víc.

Obecně prostě zvolit heuristiku takovou, která mi bude v mém případě nejvíc vyhovovat. Takže si napsat referenční implementaci a vizualizovat si, co mi to všechno prolezlo a podle toho se dál zařídit je IMHO nejlepší cesta.

[rezna]

mar proto tady uz nejakou dobu bojuju za to at si prvne naimplementi dijkstru bez heuristik a pak zacne resit dal ....

[mar]

No tady je asi koukám zvykem se na něco zeptat a pak si to buď udělat stejně podle sebe nebo to nevnímat a zeptat se znova na totéž.
V obou případech pak postrádám logiku toho, proč se tedy vůbec ptát...
Jinak naprosto souhlasím. Pokud jsem sváteční plavec tak asi rovnou nepůjdu přeplavat La Manche.