.[ ČeskéHry.cz ].
A* Pathfinding
Jdi na stránku 1, 2, 3  Další
 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> AI
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 14:08:41    Předmět: A* Pathfinding Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
pcmaster



Založen: 28. 07. 2007
Příspěvky: 1822

PříspěvekZaslal: 18. červenec 2012, 14:15:43    Předmět: Odpovědět s citátem

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 Smile

Inak by som povedal, ze si uz na velmi dobrej ceste a mas to zrejme skoro hotove Smile
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 14:31:10    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
rezna



Založen: 27. 07. 2007
Příspěvky: 2156

PříspěvekZaslal: 18. červenec 2012, 14:49:33    Předmět: Odpovědět s citátem

nebylo by jednodussi zacit treba timto - http://newwiki.ceske-hry.cz/Dijkstrův_algoritmus - a az pak zacit optimalizovat?
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 14:52:39    Předmět: Odpovědět s citátem

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


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 Wink.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 15:22:07    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
OndraSej



Založen: 28. 07. 2007
Příspěvky: 767
Bydliště: Brandýs nad Labem

PříspěvekZaslal: 18. červenec 2012, 15:23:40    Předmět: Odpovědět s citátem

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 Wink.


Neoptimalizuj, dokud to nefunguje bez optimalizaci Wink 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
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 15:53:21    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
sonic



Založen: 19. 01. 2009
Příspěvky: 194

PříspěvekZaslal: 18. červenec 2012, 15:56:31    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
pcmaster



Založen: 28. 07. 2007
Příspěvky: 1822

PříspěvekZaslal: 18. červenec 2012, 15:58:46    Předmět: Odpovědět s citátem

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
_________________
Off-topic flame-war addict since the very beginning. Registered since Oct. 2003!
Interproductum fimi omne est.
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 16:06:37    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
pcmaster



Založen: 28. 07. 2007
Příspěvky: 1822

PříspěvekZaslal: 18. červenec 2012, 16:09:29    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 16:12:07    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
mar



Založen: 16. 06. 2012
Příspěvky: 602

PříspěvekZaslal: 18. červenec 2012, 16:12:18    Předmět: Odpovědět s citátem

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 Smile

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
Lorin



Založen: 18. 07. 2012
Příspěvky: 16

PříspěvekZaslal: 18. červenec 2012, 16:23:12    Předmět: Odpovědět s citátem

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
Zobrazit informace o autorovi Odeslat soukromou zprávu
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> AI Časy uváděny v GMT + 1 hodina
Jdi na stránku 1, 2, 3  Další
Strana 1 z 3

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna