problém s pathfindingem

[kr0pac]

Dobrý den,
napsal jsem si jednoduchou aplikaci pro vyhledávání cest, bohužel sem narazil na problém, který nevím jak odstranit, proto se obracím na Vás.

Problém nastane vždy, když zvolím počet směrů, kterými se může algoritmus z bodu vydat na 8. Heuristiku mám (v případě A* a GBFS) zvolenu na manhattan, ale ta samá věc se děje i u ostatních

Manhattan: h = abs(startx - endx) + abs(starty - endy)

Budu vděčnej za každou odpověď,..díky

EDIT: nenechte se zmást z obrázku, i GBFS má ten samí problém, jen jsem chtěl poukázat na to, jak si myslím, že by cesta měla vypadat v normálu

[OndraSej]

Jak máš nastavené ceny za kroky po diagonále? Pokud stejně jako cenu za krok vodorovně nebo svisle, tak ty cesty na obrázku jsou nejkratší (podle definice součet cen za všechny kroky) a jejich tvar je daný tím, v jakém pořadí ten algoritmus vybírá nová políčka do množiny Open.
_________________
http://trionteam.net

[nou]

skus h = max(abs(startx - endx), abs(starty - endy))
_________________
Najjednoduchšie chyby sa najtažšie hľadajú.

[kr0pac]

OndraSej: takže jestli to dobře chápu, tak bych měl buď pozměnit cenu za diagonální krok, nebo pozměnit výběr uzlu z OL,...zkusim

nou: pokud se nepletu, tak je to Diagonal, to mě bohužel taky dlěá problémy

díky moc za rady, jdu to vyzkoušet

[pcmaster]

Zmen cenu za diagonalu na sqrt(2) (v pripade, ze normalna je 1) a mozes skusit aj obycajnu L2 heuristiku (euklides, najlepsie kvadrat aby si sa vyhol odmocnine ) a bude ti to fachat, presne ako hovoria ostatni
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.