A* Padvinder

[Fatty Owl]

Ik ben gisteren begonnen met de tutorial over A* pathfinding (op http://www.policyalmanac.org/games/aStarTutorial.htm). Ik ben (denk ik) al redelijk ver, maar ik zit vast P) . Ik zoek namelijk telkens de F waardes van de tiles rond de tile die je het laatste gevonden hebt. Daarna pak ik de tile met de laagste F waarde en al de rest zet ik in de closed list. Dan kijk ik weer naar alle F waardes rond de gevonden tile en pak weer de laagste, enz :).
Maar er gaat al iets fout in het begin, de tile met de laagste F waarde is de tile rechts van de beginnende. Rechts van die tile staat een muur, Rechtsboven ook en rechtsonder ook. De tile onder hem is geblokkeerd en die boven hem ook. Hij kan dus geen kant meer uit.

dit is wat ik heb, en verder geraak ik niet:
http://www.policyalmanac.org/games/aStarT4.jpg

en dit zou het moeten worden:
http://www.policyalmanac.org/games/aStarT7.jpg

Hij moet dus in het begin de tile kiezen rechtsonder (of rechtsboven) de begintile, en niet die rechts ervan. Alleen de tile rechtsonder heeft een hogere F waarde als die gewoon rechts.

Hoe kan ik dus maken dat hij niet die rechts pakt? Ik weet niet of het antwoord op mijn vraag in die tutorial staat, want ik snap de tutorial niet als ik hem doorlees :) (mede door het moeilijke engels). Ik baseer me dus op de prentjes..

Hopelijk is het duidelijk wat ik bedoel :).

[Dauntless]

Hey,

Welkom in de wereld van A* :D.

Je zit fout met deze zin:
Daarna pak ik de tile met de laagste F waarde en al de rest zet ik in de closed list.
Je moet niet alle anderen in de closed list zetten ! Je zet enkel nodes die je al BEZOCHT hebt in de closed list. Dus in het begin gaat dat de tile rechts van het startpunt zijn. Daarna voeg je x aantal nodes toe aan de open list. Je kiest degene met de laagste F uit de open list en voegt die toe aan de closed list. Dan kijk je naar alle buren van de huidige node en die voeg je weer toe aan de open list, etc ...

Begrijp je ?

[matzo]

To continue the search, we simply choose the lowest F score square from all those that are on the open list. We then do the following with the selected square:

4) Drop it from the open list and add it to the closed list.

5) Check all of the adjacent squares. Ignoring those that are on the closed list or unwalkable (terrain with walls, water, or other illegal terrain), add squares to the open list if they are not on the open list already. Make the selected square the “parent” of the new squares.

6) If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don’t do anything.
ik denk dat je dit stuk nog eens moet lezen. je moet de square met de laagste F kost op de closed list zetten, niet het omgekeerde,(alle anderen op de closed list) en dat laatste is wat ik opmaak wat je doet uit de uitleg die je nu geeft. Anders moet je het nog eens puntje per puntje anders zeggen of code geven
*edit: lol sorry, daunt, om 42 was ik al lang bezig te typen.
ik krijg mijn muis alleen zo moeilijk op dat post knopje !!!!! :~

[Fatty Owl]

oke bedankt:). Maar dan volgt hij toch deze weg:

-rechts van het beginvakje
-rechtsonder van het beginvakje
-onder het beginvakje
-links van het beginvakje

en gaat hij helemaal fout? Want die tiles hebbek telkens de laagste F..:)

[Dauntless]

De F is de som van G en H. Aangezien de H de afstand is tot het einddoel en deze kleiner wordt als je naar rechts gaat, zal hij de tegel onder de tegel rechtsonder nemen.

Teken het anders eens uit op papier (inclusief G en H) en je zal zien dat hij nooit naar 'links van het begin' gaat gaan, omdat zowel G als H daar GROTER zijn en je wil de LAAGSTE F :).

[Fatty Owl]

http://www.policyalmanac.org/games/aStarT7.jpg

Hier heeft de tile onder de begintile een F waarde van 60 :). De tile waar hij naartoe moet gaan nadat hij de tile nam rechtsonder van de beginplek heeft een F van 74 :s.

Het F pad wat hij neemt op de tekening (en dus neemt) is zo: 54-74-74-74-68
Waarom gaat hij dan niet zo: 54-60-60, want dit is ook mogelijk.

(ik zit dus vast met de overgang van het tweede rode bollteje naar de derde op de tekening:))

[Dauntless]

De nodes die blauw gekleurd zijn, zijn wél bezocht. (dus hij neemt wel de tile 1 -links van de begin tile :#).

Maar uiteindelijk is degene met de laagste F toch die van 74 hoor...

[Fatty Owl]

Ok, je hebt gelijk :). Mijn code doet het nu ik al die items niet aan de closed list toevoeg :). Nu ga ik mijn code bug testen :) want ik voorspel dat hij het alleen doet met deze map :p.

Mijn voorspellingen komen uit ;)

[Dauntless]

Dat is vreemd :D (aangezien je dat ding bijna niet statisch kan maken :p)

[Fatty Owl]

Ja :D. Maar mijn A* verkiest om te vertrekken naar boven :). Hij gaat dus langs de bovenkant ipv de onderkant (wat voor mij geen verschil maakt). Maar als ik de bovenkant afsluit (dus daar de muur verleng:)) gaat hij gewoon terug (via andere vakjes) en gaat zo naar het eindpunt :p). Hij komt er dus wel maar met een omweg :P.


wat dus betekend dat ik hem ook kan gaan laten vastlopen in doodlopende eenrichtingswegen :D

dus zou er eigenlijk een manier moeten zijn om hem te laten vooruitdenken?:)

[Fatty Owl]

Okj...Ik weet nu hoe dit komt :) (maar niet hoe ik dit moet oplossen). Er is nog altijd iets mis met mijn closed list :) want de weg die hij nu neemt mag hij niet nemen, maar is wel degene met de laagste F waardes:

(onderste is G en bovenste H (dus samen F:p))
http://img54.imageshack.us/img54/2512/weg6jl.jpg (http://imageshack.us)

[matzo]

opgepast enkel verder lezen als deze bewering juist kan zijn.
'niet elke tile op de closed list wordt uiteindelijk gebruikt in het path'
ik DENK dat het zo zit
eerst wordt de square rechts van de start(=a) toegevoegd aan de closed list omdat hij de laagste fcost heeft, vervolgens wordt er weer nagekeken, en de square rechtsboven het startpunt wordt toegevoegd omdat hij de laagste f heeft. Maar zijn father blijft het startpunt, omdat als je eerst via de a gaat, wordt de G van deze tile(die ik b noem) 24 ipv 14.
vervolgens wordt er weer nagekeken vanuit b. degene links naast b heeft de laagste F cost samen met degene erboven, degene links stond al in de open list, dus we kijken of zijn G door via b te gaan lager wordt. --> nee. dus voegen we degene boven b(=c) toe aan de closed list met als father b zelf. Bij c zien we weer 2 tiles met de laagste Fcost. degene linksonder stond al in de openlist, wordt de G cost lager als we via c gaan --> nee(want dan wordt hij 38 ). degene rechtsboven c(=d) dan maar aan de closed list toevoegen...met als father 'c'. vanuit d zien we dat er slechts een tile is met de laagste Fcost, nl rechtsonder(=e) --> toevoegen aan de closed list met father d. Dan zien we dat ons stoppunt wordt toegevoegd aan de openlist(zie note bij website voor opmerking). we voegen deze toe aan de closed list met father e. dan nemen we de omgekeerde richting. we starten bij het stoppunt, zien wat zijn father is, dat is e dus die gebruiken we zeker bij het path, de father van e is d dus die gebruiken we ook, de father van d is c dus c gebruiken we ook. father van c is b, b heeft als father het startpunt dus we zijn er.
hij volgt startpunt, b, c, d, e, stoppunt
Ik hoop dat ik nu geen foute dingen zeg want dan flip ik(en fattyOwl miss ook voor de moeite die hij wel/niet heeft gedaan om dit te lezen)

[Fatty Owl]

ik snap je helemaal en je uitleg klopt helemaal :). Hij werkt nu goed, alleen vind hij nog niet het kortste pad :). Want hij gaat nog steeds via boven en niet via de onderkant :).

[Dauntless]

Fatty, het pad langs boven en langs onder zijn identiek. Dat heeft alleen te maken met het feit of je eerst bij het toevoegen van de buren eerst de bovenste doet of eerst de onderste. Als hij het pad langs boven kiest is dat even goed.

[matzo]

Yep, beide gebruiken ze vijf tegels.;)

[Fatty Owl]

hier niet kijk maar eens goed :):
http://img54.imageshack.us/img54/2512/weg6jl.jpg (http://imageshack.us)

[Dauntless]

Je bent waarschijnlijk deze regel vergeten:
6) If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don’t do anything.
On the other hand, if the G cost of the new path is lower, change the parent of the adjacent square to the selected square (in the diagram above, change the direction of the pointer to point at the selected square). Finally, recalculate both the F and G scores of that square. If this seems confusing, you will see it illustrated below.
Ben je zeker dat die er in zit (én goed werkt ?)

[matzo]

bij mijn uitleg volgt hij uiteindelijk deze weg(met de rode lijn): http://img97.imageshack.us/img97/8177/weg6jl8pp.th.jpg (http://img97.imageshack.us/my.php?image=weg6jl8pp.jpg)(en de blauwe lijntjes duiden aan wat de parent is van de tegel)

[Dauntless]

Denk er aan, wanneer je het eindpunt gevonden hebt, moet je van daaruit terug werken hé. Dus je stelt waarschijnlijk de parents verkeerd in of zo.

Ps, matzo, je tekening is ERG onduidelijk :p.

[Fatty Owl]

dit is het probleem nu wat ik bedoel:

Het groene is de weg die hij volgt, het gele de weg die hij moet volgen :).
http://img149.imageshack.us/img149/9955/pathfinding7tr.jpg (http://imageshack.us)

Hij werkt wel niet terug van het eindpunt, wat bedoel je hiermee :). (sorry als dit goed uitgelegd staat in de tutorial)

[matzo]

Je gebruikt nu je parents niet!

Op het einde heb je bijvoorbeeld een closed list zoals hier:

(tile name=> tile parent, 0=startpunt, 1 endpunt)
a=>0
b=>0
c=>b
d=>c
1=>d

en dan moet je terugwerken!!!
Dan weet je alleen nog maar zeker dat 1 je eindpunt in het path zit!
je moet dan gaan kijken wat je in de closed list hebt aangeduid als parent van 1, en dat is d, daarvan is de parent c, en daarvan is die dan weer b, en dan zijn we bij het begin.
dan wordt ons path dus 1, d,c,b,0. of omgekeerd: 0,b,c,d,1
en niet zoals je zou denken 0,a,b,c,d,1 of 0,a,c,d,1.
==klopt niet meer aangezien Gcosts op tekening fout zijn, zie ps==Het probleem hier heeft ook nog een andere rede, namelijk dat de eerste keer waar groen niet meer overeenkomt met geel, de tegel rechts er boven ten onrechte niet als lager wordt gezien als degene eronder.(degene boven de 2de muur, en degene tussen de twee muren in, het ene is namelijk honderd en 2 en het andere 108)
=======klopt vanaf hier weer wel====
Kom je bij het voorbeeld echter niet in de problemen omdat je wall clipping toestaat.(of zo lijkt het toch)
PS en heel belangrijk!!!je rode tegel is toch je begintegel, hoe kan het dan dat de movement cost van die tegel naar degene ernaast meer dan 10 is???? Daar ga je dus al een beetje fout. wat er dus voor zorgt dat hij eerst naar de tegel links gaat gaan, dan naar degene erboven, terwijl hij normaal direct naar de 2de gaat(degene rechtsboven het startpunt)
(en kijk nog eens goed naar je G costs, die zijn wel op meer !crusiale! plaatsen fout)

[Fatty Owl]

Het probleem aan de G costs is er niet echt :). Dit is alleen in de uitvoer naar de tekstfields. Ik heb clipping uitgezet, en dat lost het probleem bijna volledig op. Alleen zoekt hij nu nog steeds niet de kortste weg van A naar B. Hij zoekt nu gewoon 'een weg' naar B.

Dit omdat ik niet terugwerk, omdat ik niet goed snap hoe de parents werken, en wat de bedoeling is van terugwerken. Moet ik telkens de tegel opslaan die kwam voor de huidige tegel? dus de parent van tegel 2 is 1, van 3 2 enz?
En terugwerken heb ik geen idee van wat daar mee bedoelt word :S:).

http://img155.imageshack.us/img155/2579/pathfinding25qi.png (http://imageshack.us)

[matzo]

En dat probleem met de uitvoer naar de textfields, is dat te verhelpen, want dit maakt het natuurlijk niet echt veel duidelijker.
PS voeg me miss ook toe op msn via daar kan ik gemakkelijker dat van het terugwerken uitleggen. ('t staat wel redelijk in de tutorial hoor)