Zobrazit předchozí téma :: Zobrazit následující téma |
Autor |
Zpráva |
Lorin
Založen: 18. 07. 2012 Příspěvky: 16
|
Zaslal: 18. červenec 2012, 14:08:41 Předmět: A* Pathfinding |
|
|
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. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
pcmaster
![](images/avatars/26669701046dd3ed68e21f.jpg)
Založen: 28. 07. 2007 Příspěvky: 1824
|
Zaslal: 18. červenec 2012, 14:15:43 Předmět: |
|
|
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 ![Smile](images/smiles/icon_smile.gif) _________________ Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
Lorin
Založen: 18. 07. 2012 Příspěvky: 16
|
Zaslal: 18. červenec 2012, 14:31:10 Předmět: |
|
|
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.
citace: |
Mi nechci povedat, ze ten rovno nad zelenym ma fakt G = 30, ked je to uplne zjavne 10 |
Ano, to má, ale jelikož je nejdříve vybráno pole vedle zeleného F = 17 jsou všechna další ohodnocení G (a tedy i F) přepočítána znovu. Protože G by mělo zahrnovat součet hodnot G všech polí, přes které jsem na aktuální pole přišel. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
rezna
Založen: 27. 07. 2007 Příspěvky: 2156
|
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
Lorin
Založen: 18. 07. 2012 Příspěvky: 16
|
Zaslal: 18. červenec 2012, 14:52:39 Předmět: |
|
|
Jediný rozdíl mezi Dijkstrovým a A* algoritmem je v použití hodnoty H. Takže když se to tak vezme, tak já už optimalizuji . |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
Lorin
Založen: 18. 07. 2012 Příspěvky: 16
|
Zaslal: 18. červenec 2012, 15:22:07 Předmět: |
|
|
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á. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
OndraSej
![](images/avatars/199514602546ab340a5d041.jpg)
Založen: 28. 07. 2007 Příspěvky: 767 Bydliště: Brandýs nad Labem
|
Zaslal: 18. červenec 2012, 15:23:40 Předmět: |
|
|
Lorin napsal: |
Jediný rozdíl mezi Dijkstrovým a A* algoritmem je v použití hodnoty H. Takže když se to tak vezme, tak já už optimalizuji . |
Neoptimalizuj, dokud to nefunguje bez optimalizaci Pro zacatek je lepsi zacit s Dijkstrou (staci vzdy brat H = 0), odladit to na tom a az pak si hrat s heuristickymi funkcemi.
Lorin napsal: |
Ano, to má, ale jelikož je nejdříve vybráno pole vedle zeleného F = 17 jsou všechna další ohodnocení G (a tedy i F) přepočítána znovu. Protože G by mělo zahrnovat součet hodnot G všech polí, přes které jsem na aktuální pole přišel. |
G je delka nejkratsi cesty na aktualni pole, takze musi obsahovat minimum pres vsechny pole, ze kterych se na aktualni da dostat. Soucet na tohle nedava smysl.
Jinak pro tenhle typ mapy dostanes lepsi heuristiku z
dx = abs(start.x - cil.x)
dy = abs(start.y - cil.y)
H = 14*min(dx, dy) + 10*(max(dx, dy) - min(dx, dy)) = 4*min(dx, dy) + 10*max(dx, dy),
jednak dava lepsi odhady (vzhledem k tomu, jak mas definovane vzdalenosti) a navic bude rychlejsi na vypocet. _________________ http://trionteam.net |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
Lorin
Založen: 18. 07. 2012 Příspěvky: 16
|
Zaslal: 18. červenec 2012, 15:53:21 Předmět: |
|
|
OndraSej napsal: |
Jinak pro tenhle typ mapy dostanes lepsi heuristiku z
dx = abs(start.x - cil.x)
dy = abs(start.y - cil.y)
H = 14*min(dx, dy) + 10*(max(dx, dy) - min(dx, dy)) = 4*min(dx, dy) + 10*max(dx, dy),
jednak dava lepsi odhady (vzhledem k tomu, jak mas definovane vzdalenosti) a navic bude rychlejsi na vypocet. |
dx = | 3 - 10 | = 7
dy = | 4 - 6 | = 2
H = 14 * 2 + 10 * (7 - 2) = 78
Nevím, jestli jsem neudělal chybu ve výpočtu, ale vzdálenost 78 se mi zdá trochu moc. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
sonic
![](images/avatars/3733485194db140b2c3ca0.png)
Založen: 19. 01. 2009 Příspěvky: 194
|
Zaslal: 18. červenec 2012, 15:56:31 Předmět: |
|
|
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. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
pcmaster
![](images/avatars/26669701046dd3ed68e21f.jpg)
Založen: 28. 07. 2007 Příspěvky: 1824
|
Zaslal: 18. červenec 2012, 15:58:46 Předmět: |
|
|
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) ![Wink](images/smiles/icon_wink.gif) _________________ Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
Lorin
Založen: 18. 07. 2012 Příspěvky: 16
|
Zaslal: 18. červenec 2012, 16:06:37 Předmět: |
|
|
sonic napsal: |
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) |
Jestli to chápu dobře, pokud narazím na pole, které již je v Otevřeném seznamu, zkontroluju, jestli G aktuálního pole je větší než G toho v Otevřeném seznamu.
Pokud ano, přepočítám hodnoty (G, F) toho v Otevřeném seznamu a přidám si ho na Uzavřený seznam. Pokud ne, znamená to, že k tomu poli existuje lepší cesta a tak můžu aktuální cestu smazat a nějak se dobrat té kratší?
Naposledy upravil Lorin dne 18. červenec 2012, 16:24:14, celkově upraveno 1 krát |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
pcmaster
![](images/avatars/26669701046dd3ed68e21f.jpg)
Založen: 28. 07. 2007 Příspěvky: 1824
|
Zaslal: 18. červenec 2012, 16:09:29 Předmět: |
|
|
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. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
Lorin
Založen: 18. 07. 2012 Příspěvky: 16
|
Zaslal: 18. červenec 2012, 16:12:07 Předmět: |
|
|
pcmaster napsal: |
Ak si to pamatam dobre, tak neexistuje nic ako "aktualna cesta". Cestu zistis az v momente, ked dosiahnes cielovy uzol a to tak, ze budes skakat po ulozenych predkoch dozadu po konca po start. |
To ano, za cestu beru i její část, která byla zatím vygenerována. |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
mar
Založen: 16. 06. 2012 Příspěvky: 607
|
Zaslal: 18. červenec 2012, 16:12:18 Předmět: |
|
|
pcmaster napsal: |
Je uplne jedno, aka je heuristika (teda pokial je furt vhodna) |
No pokud je heuristika delší, než nejkratší teoreticky možná cesta, pak bude (resp. s vysokou pravděpodobností může) řešení suboptimální. Ale někdy to může být výhoda ("cena vs kvalita").
A viděl jsem počítat heuristiku |start - uzel| místo |cíl - uzel|, a tam A* nedopadl nejlíp
Lorin napsal: |
Jestli to chápu dobře, pokud narazím na pole, které již je v Otevřeném seznamu, zkontroluju, jestli G aktuálního pole je menší než G toho v Otevřeném seznamu.
|
Ne. Pokud je G aktuálního uzlu + cost (aktuální, nový) < G nového, pak se změní G u nového (=relaxace) a updatne se nový uzel v prioritní frontě |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
Lorin
Založen: 18. 07. 2012 Příspěvky: 16
|
Zaslal: 18. červenec 2012, 16:23:12 Předmět: |
|
|
mar napsal: |
Ne. Pokud je G aktuálního uzlu + cost (aktuální, nový) < G nového, pak se změní G u nového (=relaxace) a updatne se nový uzel v prioritní frontě |
Co přesně má dělat cost(aktuální, nový)?
Co je prioritní fronta? |
|
Návrat nahoru |
|
![](templates/subSilver/images/spacer.gif) |
|