[Java] Pathfinding in doolhof

[osorkon!]

Hoi,

Ik ben momenteel bezig aan een mini game, waarin je begint als een speler in een doolhof met verschillende monsters, waartegen je kan vechten.

Momenteel bewegen die monsters nog niet, maar ik zou ze graag willen doen bewegen zodat ze de speler aanvallen, ( ze dus naar hem toelopen ). Zonder dat ze daarbij vast geraken of niet rondom een muurtje kunnen geraken. Een soort pathfinder functie heb ik dus nodig.

Men doolhof is opgebouwd uit een 3dim array, waarbij array[x-coord][y-coord][wat-ligt-er-op-dit-vakje],
Het is ongeveer 11op11 groot.

Adhv [wat-ligt-er-op-dit-vakje] kan je dus zien als er een muur voor je staat (of iets anders dat je weg blokkeerd).

Nu heb ik al wat opzoekingswerk gedaan en verschillende A* pathfinding algoritmen bekeken, maar ik weet nog steeds niet goed hoe hier zo goed mogelijk aan te beginnen.

Kan iemand me hierbij wat op weg helpen?

[Theuno]

Je wilt ze dus ook echt naar de speler toe laten bewegen ?

Dan moet je per monster en per vakje wat hij beweegt in elk geval een complete weg bepalen richting de speler. Dat zorgt ervoor dat ze niet random rond gaan dwalen.
Dat word een behoorlijke zoekboom die je dan krijgt, maar ik zou zeggen maak eens een opzet voor een monster.
Begin bij het monster, en kijk welke kanten hij op kan vanuit dat vakje. Reken dit door voor elk vakje dat hij op kan tot hij de speler op een vakje tegen komt, die kan ga je dan op.

[Janoz]

Ik denk dat het grootste probleem dat je nu hebt je vreemde datastructuur is. Waarom gebruik je een 3 dimensionale array om een 2d vlak weer te geven. Om fatsoenlijk met je doolhof te kunnen werken is het belangrijk dat je een goede datastructuur kiest voor je doolhof.

Zorg vervolgens dat je snel kunt opvragen of je ergens kunt staan en wat er naast staat. Eventueel zou je een graaf kunnen maken. Als alle monsters naar je speler moeten lopen kan het ook handig zijn om een dijkstra's kortste pad algoritme te gebruiken. Hierbij reken je vervolgens voor elke plek in het doolhof uit hoeveel stappen het is naar de speler en moet je je mostertjes alleen maar verplaatsen naar het aanliggende hokje waarbij die afstand lager is.

[Verwijderd]

osorkon! schreef op woensdag 21 maart 2007 @ 10:54:
Nu heb ik al wat opzoekingswerk gedaan en verschillende A* pathfinding algoritmen bekeken, maar ik weet nog steeds niet goed hoe hier zo goed mogelijk aan te beginnen.

Zelf heb ik een paar jaar geleden met weinig programmeerervaring het A*-algoritme in Java geïmplementeerd. Dat was vrij eenvoudig. A* is als je het eenmaal snapt ook een eenvoudig algoritme.

[OnTracK]

A* in een doolhof lijkt me niet zo heel nuttig aangezien je nooit een (ook maar enigzins) correcte voorspelling over de nog te maken padkosten kunt geven. Sterker nog, doolhoven zijn toch meestal zo ontworpen dat je juist langere wegen moet maken om ergens aan te komen.

[IntToStr]

Een aantal jaren geleden heb ik eens een progsel gemaakt waarbij ik op een aantal manieren een pad/oplossing voor een doolhof moest implementeren. Dit was vrij eenvoudig en snel te berekenen voor een niet al te groot doolhof als ik me niet vergis.

Makkelijk te maken, maar niet noodzakelijk het kortste pad: de "rechterhand" methode. Als je ooit nog eens vastzit in een (spiegel)doolhof: raak met je rechterhand de muur aan en blijf deze volgen. Je komt gegarandeerd altijd bij de uitgang (of waar je ook moet zijn). Probleem: de "uitgang" beweegt hier en je loopt (waarschijnlijk) om

Wat ook mogelijk is: de kortste route berekenen (uiteraard...). Dit ging ook vrij eenvoudig met wat backtracking in de berekening. Weet niet precies meer hoe dit exact ging. Reken gewoon bij elke stap deze route uit en laat m hierop lopen. Met wat google werk over maze solver of iets dergelijks komt deze methode vast ergens opduiken.

[Janoz]

Rechterhand methode werkt ook alleen als de uitgang zich aan de buitenkant bevindt. Anders zou je immers altijd langs de buitenkant kunnen blijven lopen.

Simpelste implementatie lijkt mij nog steeds dijkstra's kortste pad uitrekenen voor het gehele doolhof (dus eigenlijk alleen de eerste helft van het algoritme) Deze berekening hoef je maar 1x te doen per stap. Alle monsters kunnen deze data vervolgens gebruiken om naar de speler toe te lopen.

Probleem wordt dan wel dat het spelletje wat lastig wordt omdat de monsters altijd zo efficient mogelijk naar de speler lopen .

[IntToStr]

Janoz schreef op woensdag 21 maart 2007 @ 13:38:
Rechterhand methode werkt ook alleen als de uitgang zich aan de buitenkant bevindt. Anders zou je immers altijd langs de buitenkant kunnen blijven lopen.

Uiteraard, vergeten te vermelden. Was meer als extra info bedoeld

Simpelste implementatie lijkt mij nog steeds dijkstra's kortste pad uitrekenen voor het gehele doolhof (dus eigenlijk alleen de eerste helft van het algoritme) Deze berekening hoef je maar 1x te doen per stap. Alle monsters kunnen deze data vervolgens gebruiken om naar de speler toe te lopen.

Ik herinner me ook weer wat van dat andere algoritme dat ik wilde vermelden. Je kunt beginnen bij de positie van een monster en dan in alle mogelijke richtingen telkens 1 stap maken. Bij elke vakje het minimale aantal stappen tot aan dit vakje opslaan totdat de speler is bereikt en er geen vakjes meer zijn met een waarde lager dan die van het vakje van de speler. Nu backtracken naar het monster door telkens naar grenzend vakje met waarde van 1 lager gaan en je hebt je route. Volgens mij lijkt dit best veel op Dijkstra's algo, alleen is het wat makkelijker in de praktijk te brengen omdat je geen graaf hoeft te bouwen en zo. Het is wel minder efficient volgens mij...

Probleem wordt dan wel dat het spelletje wat lastig wordt omdat de monsters altijd zo efficient mogelijk naar de speler lopen .

Het wordt natuurlijk helemaal leuk als je nog verder gaat rekenen en kijken wat de verwachte positie van de speler is over een x aantal stappen en dan daarheen te lopen

[Janoz]

Wat je beschrijft is inderdaad ongeveer dijsktra. Om er echt dijkstra van te maken moet je inderdaad alle buren de waarde 'huidige waarde + 1' geven tenzij het buur hokje al een lagere waarde heeft. Vervolgens moet je de verwijzing naar de aangepaste hokjes in een lijst opslaan. Deze lijst gebruik je om te kijken van welk volgende hokje je de buren aan gaat passen. Uit de lijst moet je altijd het hokje nemen met het laagste aantal stappen. Als je deze stappen doorloopt zul je eindigen met een doolhof waarin in elk hokje staat in hoeveel stappen je bij het startpunt komt.

Je moet echter niet bij het monster beginnen, maar bij de speler. Je hoeft dan namelijk maar 1x alles te berekenen en kunt vervolgens de waardes in de hokjes gebruiken voor al je monsters. Pas als de speler ergens anders gaat staan moet je alles opnieuw uitrekenen. Je hoeft je monsters alleen maar naar een hokje te verplaatsen die een lagere waarde heeft dan het hokje waar het monster nu staat.

[Zerora]

Ik heb ooit zelf weleens geprobeerd om een game te maken met een doolhof.

in mijn doolhof kon je 4 richtingen uit; boven, onder, links en rechts.

Bij de richtingen van het monster had ik dan het volgende ingesteld:

richting links:
Is er geen muur in de richting links?
- Zo ja, Is de X positie van player lager dan monster?
- - - Zo ja, ga 1 vakje naar links > ga naar "richting boven"
- - - Zo nee, ga naar "richting boven"
- Zo nee, ga naar "richting boven"

richting boven
Is er geen muur in de richting boven?
- Zo ja, Is de Y positie van player hoger dan monster?
- - - Zo ja, ga 1 vakje naar boven > ga naar "richting rechts"
- - - Zo nee, ga naar "richting rechts"
- Zo nee, ga naar "richting rechts"

richting rechts
Is er geen muur in de richting rechts?
- Zo ja, Is de X positie van player hoger dan monster?
- - - Zo ja, ga 1 vakje naar rechts > ga naar "richting onder"
- - - Zo nee, ga naar "richting onder"
- Zo nee, ga naar "richting onder"

richting onder
Is er geen muur in de richting onder?
- Zo ja, Is de Y positie van player lager dan monster?
- - - Zo ja, ga 1 vakje naar onder > ga naar "richting links"
- - - Zo nee, ga naar "richting links"
- Zo nee, ga naar "richting links"

En dan constant door laten gaan
Opzich werkte dit wel aardig, maar het monster kwam regelmatig vast te zitten. Lag ook een beetje aan mijn doolhof.

[ Voor 8% gewijzigd door Zerora op 21-03-2007 15:29 ]

[osorkon!]

Janoz schreef op woensdag 21 maart 2007 @ 11:33:
Ik denk dat het grootste probleem dat je nu hebt je vreemde datastructuur is. Waarom gebruik je een 3 dimensionale array om een 2d vlak weer te geven. Om fatsoenlijk met je doolhof te kunnen werken is het belangrijk dat je een goede datastructuur kiest voor je doolhof.

Dit doe ik zodat ik weet per vakje wat erop aanwezig is, kan meer zijn dan alleen een speler, monster of muur, bv een val of een drankje of een wapen.

Janoz schreef op woensdag 21 maart 2007 @ 11:33:
Als alle monsters naar je speler moeten lopen kan het ook handig zijn om een dijkstra's kortste pad algoritme te gebruiken.

Heb je soms een klein voorbeeldje in java hoe dit dan best werkt met men situatie (is pseudocode ofzo)

[BtM909]

Waarom zou A* Pathfinding geen goede oplossing zijn?

[NetForce1]

osorkon! schreef op woensdag 21 maart 2007 @ 21:06:
[...]
Dit doe ik zodat ik weet per vakje wat erop aanwezig is, kan meer zijn dan alleen een speler, monster of muur, bv een val of een drankje of een wapen.

Dat maakt toch niet uit? Je kunt evengoed een 2d array gebruiken:

Java:

GameObject[][] = {
  {new Speler(), new Wall(), null, null},
  {new Gem(), new Wall(), new Monster(), null},
};

[ Voor 4% gewijzigd door NetForce1 op 22-03-2007 09:10 ]

[Janoz]

osorkon! schreef op woensdag 21 maart 2007 @ 21:06:
Dit doe ik zodat ik weet per vakje wat erop aanwezig is, kan meer zijn dan alleen een speler, monster of muur, bv een val of een drankje of een wapen.

Zie boven mij

Heb je soms een klein voorbeeldje in java hoe dit dan best werkt met men situatie (is pseudocode ofzo)

In een latere reactie heb ik het algorithme behoorlijk uitgeschreven. Daarnaast is psuedocode voor dit algorithme ook wel te vinden op wikipedia (zoeken naar dijkstra levert de pagina over de professor zelf. Daarop staat wel een link naar zijn algoritme).


hier dus

[ Voor 5% gewijzigd door Janoz op 22-03-2007 09:50 ]

[OnTracK]

BtM909 schreef op donderdag 22 maart 2007 @ 09:08:
Waarom zou A* Pathfinding geen goede oplossing zijn?

Ik kan het verkeerd hebben, maar voor zover ik weet werkt A* alleen als je heuristiek goede voorspellingen kan doen. Maar dat is nou juist het punt van een doolhof, dat kan je eigenlijk niet zonder het doolhof te doorzoeken / bij voorbaat de juiste route te weten. Padkosten zijn altijd "1", dus daar valt ook niets te winnen. En met een niet werkende heuristiek is A* eigenlijk niets anders dan random kiezen. Sterker nog, als je heuristiek niet optimistisch is (verwachte kosten zijn altijd lager dan uiteindelijke kosten), ben je niet eens zeker dat je gevonden oplossing wel de beste is.

[killercow]

Als heuristiek gebruikt A* toch gewoon manhattan distance?
Aka, diffX + diffY is distance.

Maar omdat je in een doolhof nergens zeker van bent. (iig in een perfect doolhof) kun je niets anders dan gewoon alles doorzoeken.

Enige optimalisatie die je kunt maken is een soort flood fill.

A* is juist voor dit soort dingen prachtig, want het stopt met zoeken zodra het de target gevonden heeft, en zoekt "paralel" alle mogelijke richtingen op zodat je ook zonder voorkennis goede resultaten boekt.

[osorkon!]

NetForce1 schreef op donderdag 22 maart 2007 @ 09:09:
[...]

Dat maakt toch niet uit? Je kunt evengoed een 2d array gebruiken:

Java:

GameObject[][] = {
  {new Speler(), new Wall(), null, null},
  {new Gem(), new Wall(), new Monster(), null},
};

Als je het zo bekijkt niet aan gedacht eerlijk gezegt

[JozyDaPozy]

De source zit er niet bij, maar kwam dit toevallig tegen en moest toen aan dit topic denken. Wel strak gemaakt..

[Not Pingu]

OnTracK schreef op donderdag 22 maart 2007 @ 11:43:

Ik kan het verkeerd hebben, maar voor zover ik weet werkt A* alleen als je heuristiek goede voorspellingen kan doen. Maar dat is nou juist het punt van een doolhof, dat kan je eigenlijk niet zonder het doolhof te doorzoeken / bij voorbaat de juiste route te weten.

A* is in de basis gewoon Dijkstra, heuristiek wordt alleen gebruikt om de hoeveelheid werk te verminderen. Dat dit in een doolhof misleidend en contraproductief kan zijn, ben ik met je eens. Maar het A* algorithme zal net zoals Dijkstra gewoon altijd gegarandeerd een pad vinden als dit mogelijk is.

De toevoeging van heuristiek betekent dat je afhankelijk van het doolhof een kleine of grotere tijdwinst kan boeken in vergelijking met puur Dijkstra.

.oisyn schreef op donderdag 22 maart 2007 @ 18:13:
Een ander verschil is dat A* stopt zodra een pad is gevonden (die door een goede heuristiek wel enigszins efficient is), terwijl het algoritme van Dijkstra het pad vind dat echt het kortst is (of een van de paden bij een gedeelde eerste plek).

Even ervan uitgaande dat er in een doolhof maar 1 uitgang is, is dit iig geen probleem.

[ Voor 21% gewijzigd door Not Pingu op 22-03-2007 18:30 ]

[.oisyn]

Een ander verschil is dat A* stopt zodra een pad is gevonden (die door een goede heuristiek wel enigszins efficient is), terwijl het algoritme van Dijkstra het pad vind dat echt het kortst is (of een van de paden bij een gedeelde eerste plek).

[OnTracK]

nvm

[ Voor 98% gewijzigd door OnTracK op 22-03-2007 19:19 ]

[Mark Lor]

.oisyn schreef op donderdag 22 maart 2007 @ 18:13:
Een ander verschil is dat A* stopt zodra een pad is gevonden (die door een goede heuristiek wel enigszins efficient is), terwijl het algoritme van Dijkstra het pad vind dat echt het kortst is (of een van de paden bij een gedeelde eerste plek).

Met A* kun je afaik ook gewoon garanderen dat het gevonden pad het kortst is. Je verliest echter dan wel veel snelheid van het algoritme.

[Soultaker]

Even onderstrepen wat Not Pingu zegt: Dijkstra is A* met een nul-heuristiek. A* levert altijd een optimaal pad, mits je een permissible heuristiek gebruikt; dat wil zeggen, een heuristiek die de werkelijke afstand tot het doel nooit overschat. Hoe dichter de heuristiek bij de werkelijke kosten komt, hoe beter, maar hij mag die nooit overschatten. De nul-heuristiek (geschatte afstand altijd 0) is duidelijk permissible, en Dijkstra is natuurlijk ook optimaal. Manhattan distance is ook permissible als je elke keer één stap in een van de vier richtingen mag doen (maar niet als je bijvoorbeeld teleporters of wormholes of iets dergelijks in je spel hebt), en zeker beter dan de nul-heuristiek.

Het is misschien een definitiekwestie, maar naar mijn idee is A* met een non-permissible heuristiek geen A* meer. Als je daar van uitgaat komt komt het er dus op neer dat A* net als Dijkstra een optimale oplossing geeft, en worst case niet meer toestanden bezoekt dan Dijkstra. Met een beetje zinnige heuristiek zal A* in de praktijk dus meestal sneller zijn, hoewel het mogelijk is dat Dijkstra sneller is als de overhead van het berekenen van je schatting te groot is. Dijkstra is dan niet sneller omdat er minder nodes bekeken worden, maar omdat de tijd besteed per node minder is.

[Verwijderd]

Even zoekmethoden buiten beschouwing gelaten... is het niet veel realistischer als monsters je pas kunnen vinden als ze je zien? Dat betekent dat je pas door je pathnodes hoeft te gaan zoeken zodra het monster de speler in z'n line of sight heeft.

Eigenlijk kan je het dan zelfs heel simpel optimaliseren: zoek eerst door de paden die het meest richting de speler gaan. Zo zal een monster zodra hij je ziet op je af gaan lopen, eventuele obstakels ontwijkend.

[The - DDD]

killercow schreef op donderdag 22 maart 2007 @ 16:11:
Als heuristiek gebruikt A* toch gewoon manhattan distance?
Aka, diffX + diffY is distance.

Maar omdat je in een doolhof nergens zeker van bent. (iig in een perfect doolhof) kun je niets anders dan gewoon alles doorzoeken.

Enige optimalisatie die je kunt maken is een soort flood fill.

A* is juist voor dit soort dingen prachtig, want het stopt met zoeken zodra het de target gevonden heeft, en zoekt "paralel" alle mogelijke richtingen op zodat je ook zonder voorkennis goede resultaten boekt.

En daar tref je dus juist de spijker op zijn kop. In problemen als deze kun je het beste gebruik maken van voorgedefinieerde paden. Leg over het "probleem" een netwerk heen met acceptabele paden. Vervolgens is je navigatie probleem een netwerk probleem geworden tussen twee knopen op je netwerk. Zodra er een directe zichtslijn is tussen je doel en pion kun je afstappen van dit netwerk. Zie het als het transwarp netwerk in Star Trek. Je komt snel (lees goedkoop) redelijk in de buurt. Het laatste stukje van en naar het netwerk is daarna een eenvoudig probleem. Namelijk het dichtsbijzijnde knooppunt waar een zichtlijn naar is.

Overigens is zo'n netwerk redelijk makkelijk slim te maken. Een AI kan waarden toekenen aan de netwerk paden: afstand, tegengekomen weerstand, sterfte op het pad, etc...

Kijk maar is heel erg goed wat units in strategie spellen doen. 1 van de redenen dat je een map in de C&C editors dient te "compilen" is het genereren van dit netwerk. Het is namelijk gewoon een stap die gedaan kan worden zodra de data statisch is geworden. Wat je overigens niet verbied paden toe te voegen of verwijderen.

Overigens klinkt het alsof je een soort pacman aan het maken bent. Die vier spoken in pacman hebben echt achterlijk simpele strategien. 1 spook wil alleen maar van je weg tot een bepaalde afstand, 1 spook neemt altijd de route die dichterbij jou is, wat kan betekenen dat hij tussen twee posities heen en weer gaat stuiteren, 1 spook doet iets soortgelijks, maar neemt altijd een 1 mogelijke richting verder naar links en de 4de doet geloof ik hetzelfde maar dan over rechts. Met zijn vieren maken ze het je een stuk moeilijker. De kunst van goed pacman spelen is weten welk spook van je wegrent. Daar kun je namelijk altijd veilig achteraan hobbelen.

(Probleem is alleen dat de strategie soms regelmatig omgegooid wordt tussen de vier spoken.) Overigens proef ik een hoog huiswerk gehalte in deze vraag.

(Nu ga ik mijn bed weer in, heb de afgelopen dagen zoveel ziek in bed gelegen dat mijn hele dag/nacht ritme verknoeid is. Goed teken dat ik nu wakker ben, want dan ben ik aan de beterende hand.)

[ Voor 19% gewijzigd door The - DDD op 23-03-2007 02:51 ]

[Verwijderd]

ik wil effen er op inhaken over pathfinden

hier effen een plaatjes voor duidelijkheid over mijn vraag


de bedoeling is dat s(de speler) de diamant(d1 en d2) naar de plaatsen schuift(geel 1 en 2)

misschien dat mensen het spel sokuban kennen.


probleem is als ik dijkstra zou toepassen zal de speler de diamant 1 op plaats 1 zetten.. dat is opzich wel goed. maar het spel is niet uit gespeeld.
hij zou namelijk eerst diamant 2 naar plaats 2 moeten zetten en dan pas diamant 1 naar plaats 1..


of zit ik nu verkeert te denken en is dijkstra zeker een oplossing voor deze pathfinding

[dusty]

Het probleem voor sokuban is dat de korste path niet altijd correct is, waardoor je juist niet alleen de korste path-algoritmen kan gebruiken.

Bovendien kan het zijn dat je ook eerst een blok A een aantal zetten moet verschuiven, dan blok B een aantal, daarna A op zijn plaats te zetten en weer terug te gaan naar blok B om die op zijn plaats te zetten. Het komt ook voor bij sokuban dat een blok dat al op de juiste plaats staat uit de weg moet schuiven om een ander blok op de juiste plaats te krijgen.

Bij sokuban zal je meer naar een 'chess'-algoritme moeten kijken dan een path. Laat staan een shortest path algoritme.

[Zerora]

@sonicred,
Volgens mij heb je helemaal geen pathfinding nodig als je alleen een speler + wat schuifblokken hebt.
Alleen een script dat er voor zorgt dat die blokken schuiven.
Dan maak je een eenmalige optelling (begin level) die checkt of de vlakken al een diamant hebben. Indien dit niet het geval is, wat uiteraard de bedoeling is, laat je die bij elkaar optellen.
Daarna geef iedere keer als je een diamant op zo'n vlak schuift opnieuw een check voor alle vlakken (leeg = +1 erbij tellen). Als uiteindelijk dit aantal 0 is, dan is je level uitgespeelt.

Zo zou ik het doen denk ik iig

[Verwijderd]

@dusty
dan ga ik es uitzoeken wat dat 'chess'-algoritme precies inhoud

@Rakkerzero
nou heb het wel nodig.. de bedoeling is wanneer de speler er niet uit zou komen dat hij dan op de knop drukt en krijgt het path te zien om het uit te kunnen spelen. als dat nog mogelijk is zeg maar..


zelf ben ik nog op de gedachten gekomen om een binair-boom constructie te maken.. die de hoogste orde zal laten zien... dan krijg hem zeker opgelost alleen ja je zult ook overbodige stappen te zien krijgen..

[Soultaker]

dusty schreef op vrijdag 23 maart 2007 @ 04:33:
Het probleem voor sokuban is dat de korste path niet altijd correct is, waardoor je juist niet alleen de korste path-algoritmen kan gebruiken.
[..]
Bij sokuban zal je meer naar een 'chess'-algoritme moeten kijken dan een path. Laat staan een shortest path algoritme.

Toch doet A* het bijzonder goed voor Sokoban, en ik ken eerlijk gezegd geen methode die beter werkt. Wat het belangrijkste is voor elk A* algoritme, is het vinden van een goede heuristiek. Als je bij Sokoban doodlopende stellingen wegsnoeit en als heuristiek het aantal toch te plaatsen dozen neemt (als dat 0 is, ben je klaar), heb je al een goed Sokoban-algoritme.

Verder moet je korste pad niet altijd concreet zien. Bij Sokoban is een 'pad' een aantal transities van toestanden, van de begintoestand naar de eindtoestand. Zo bezien is het korste pad wél wat je zoekt.

Verwijderd schreef op vrijdag 23 maart 2007 @ 01:59:
Even zoekmethoden buiten beschouwing gelaten... is het niet veel realistischer als monsters je pas kunnen vinden als ze je zien? Dat betekent dat je pas door je pathnodes hoeft te gaan zoeken zodra het monster de speler in z'n line of sight heeft.

Dat is sowieso wel de moeite van het overwegen waard: is het wel leuk als de tegenstander helemaal optimaal speelt? Als de tegenstanders in Pacman optimaal zouden spelen was er niets aan geweest. Misschien kun je met veel simpelere (niet perfecte) methoden veel leukere tegenstanders maken.