A* Pathfinding

[Lorin]

Ahoj. Učím se principům A* pathfindingu. Nějaké ty základy znám a tak jsem si zkusil udělat jednoduchý obrázek do kterého bych (podle výpočtů) dosadil správnou cestu k cíli. Cestu najdu, problém je v tom, že je trochu neefektivní a já nikde nenašel způsob, jak cestu trochu zefektivnit.

Používám vzorec F = G + H.

H vypočítávám pomocí Euklidovy metriky (H = sqrt((start.x - cil.x)^2 + (start.y - cil.y)^2) ).

G - Základní hodnoty jsou 10 (vertikální a horizontální posun) nebo 14 (šikmý posun). Hodnoty se sčítají po cestě.

Tady je obrázek s cestou a ohodnocením jednotlivých polí. První číslo je hodnota G, druhá je hodnota H a poslední je F. Azurové pole jsou místa, kudy vede cesta.



Pro jistotu, zde je vyznačena cesta:


Potřeboval bych se zbavit těch dvou polí, které tvoří malou zatáčku u zeleného pole.

Děkuji za jakoukoli pomoc.

[pcmaster]

Toto by ti fakt nemalo nastat, mala by sa o to postarat relaxacia.

Napada ma par chyb:
1. Nepustas to nahodou v DFS poradi a hned ako najdes ciel tak koncis?
2. Neostavaju ti na zasobniku nejake neohodnotene/neprehodnotene nody?
3. Ulozis na zasobnik na zaciatku uplne vsetky nody okolo zeleneho? Predsa by si ich mal mat ohodnotene vsetky! Mi nechci povedat, ze ten rovno nad zelenym ma fakt G = 30, ked je to uplne zjavne 10

Inak by som povedal, ze si uz na velmi dobrej ceste a mas to zrejme skoro hotove
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[Lorin]

Ohodnotil jsem všechny potřebné pole, ale jejich hodnocení jsem v tomto obrázku vynechal. Zde je ukázka ohodnocení všech polí kolem zeleného čtverce.

[rezna]

nebylo by jednodussi zacit treba timto - http://newwiki.ceske-hry.cz/Dijkstrův_algoritmus - a az pak zacit optimalizovat?

[Lorin]

[Lorin]

Zkoušel jsem i neaktualizovat hodnoty G (a tedy i F), po vygenerování je prostě nechat tak, jak jsou a použít je. Výsledkem by byl postup:

Zelený > Pole s F = 17 (napravo od zeleného) > Pole s F = 18.06 (nad zeleným)

Dál je cesta stejná.

[OndraSej]

[Lorin]

[sonic]

No já jsem zkoušel A* asi před 3 měsíci a problém jsem neměl, jel jsem konkrétně podle http://www.policyalmanac.org/games/aStarTutorial.htm

Pokud jedeš přesně podle odstavce "Summary of the A* Method", tak nemůže nastat problém, hlavně jestli jsi nezapoměl na to, že když v cestě narazíš na políčko, které jsi ještě nekontroloval, tak zjistit jestli k tomu políčku nevede kratší cesta než ta, kterou jsi právě zvolil (pomocí G)
_________________
Programovat pod Windows je jako hrát hry na Macu.

[pcmaster]

Je uplne jedno, aka je heuristika (teda pokial je furt vhodna), pretoze aj blbe BFS/DFS, aj Dijkstra aj A* so suboptimalnou (ci nijakou) heuristikou VZDY najde optimalnu cestu! Prejdi si svoj algoritmus proti tomu, co vidis v skriptach a nejaka primitivna chyba tam niekde bude schovana (napriklad v relaxacii)
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[Lorin]

[pcmaster]

Ak si to pamatam dobre, tak neexistuje nic ako "aktualna cesta". Kazdy uzol ma v sebe predsa ulozeneho predchodcu, cez ktoreho k nemu vedie najkratsia cesta zo startu.
Vyslednu cestu zistis az v momente, ked dosiahnes cielovy uzol a to tak, ze budes skakat po ulozenych predkoch dozadu po konca po start.
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.

[Lorin]

[mar]

[Lorin]