game maker
Gebruikersnaam:
Wachtwoord:
Home Info Forums Help
Welkom, Gast. Alsjeblieft inloggen of registreren.
De activerings e-mail gemist?
+  Forums
|-+  Werken met Game Maker
| |-+  Tutorials en Uitbreidingen (Moderator: Maarten Baert)
| | |-+  [Gex/Gml] GmPathFinding (GPF) 0.9 - Node Based Motion Planning in GML
Pagina's: [1]
« vorige volgende »
Print
Advertenties

WBG
Globale moderator


Offline Offline

Berichten: 5034


« Gepost op: 10 September 2012, 08:55:40 »


GM-versie: GameMaker 8
Pro vereist: Ja
Niveau: Gevorderd

Wat is dit?
Bij deze presenteer ik GPF: een in GML geschreven pathfinder.

GPF werkt in tegenstelling tot de meeste pathfinding systemen niet met een grid, maar met een netwerk van nodes (ook wel graaf genoemd). Tussen de verschillende nodes kunnen connecties worden gelegd, waarover je het effectiefste pad kunt uitrekenen.
Bij het berekenen van een pad wordt sinds v0.8 gebruik gemaakt van een Best-First Search. Dit is een verbetering op v0.7, die van een Breadth-First Search gebruik maakte.

Het algoritme is sinds 0.8 gebaseerd op A*. (Met absolute afstand als heuristiek)

Uhh.. Waar heb je het over?
Het klinkt misschien wat ingewikkeld - en je kunt er ook best complexe dingen mee maken - maar het kan ook heel makkelijk!
- Installeer de extensie
- Maak een object genaamd obj_gpf_node
- Zet obj_gpf_node in de room op de belangrijke knooppunten
- Maak paths tussen de knooppunten (zorg dat ze niet "closed" zijn)
- Maak een object die de slimme route gaat berekenen
- Zet path = path_add(); en gpf_auto_link_paths(true); in het create event
- Dit object kan nu met gpf_move(x,y,DOELX,DOELY,path,SNELHEID) over de vooraf gemaakte paden lopen!

Waarom met nodes en geen grid?
De eerste overweging is dat het sneller is. Over het algemeen dan, want meestal gebruik je een stuk minder nodes dan cellen. Verder heb je meer vrijheid: je kunt de nodes zo inrichten dat paden niet alleen hoeken van 90 of 45 graden kunnen maken, maar veel rondere en natuurlijkere wegen mogen kiezen.
Nieuw in v0.8: Je kunt de links nu voorzien van paths. Dit houdt in dat je een kronkelig bergweggetje kunt maken, zonder dat elke kronkel berekend hoeft te worden. Alleen de totaalkosten zijn van belang voor de pathfinder.

Functies:
Hieronder de belangrijkste functies:
- gpf_node_create(x,y,[cost])
- gpf_node_destroy(node)
- gpf_link_create(from,to,[cost],[path],[maxwidth],[add_reverse])
- gpf_link_destroy(link)
- gpf_path(path,start,goal,[width])
- gpf_move(xstart,ystart,xgoal,ygoal,path,speed,[width])
- gpf_draw(link_color,node_color)
- gpf_auto_link_paths(reverse,[cost])
- gpf_auto_link_nodes(max_distance,block_object,[cost])
Verder zijn er nog 16 get en set functies om de eigenschappen van nodes of links op te vragen of aan te passen.

Globals:
- gpf_cost_weight = 0.75; Belangrijkheid van padkosten
- gpf_distance_weight = 0.25; Belangrijkheid van node afstand (tot doel)
- gpf_default_width = 1; Standaardbreedte van paden / links

Let op:
Als je in v0.9 handmatig een instantie van obj_gpf_node (of een child-object ervan) maakt, buiten de room editor om en zonder gpf_node_create - bijvoorbeeld door instance_create(x,y,obj_gpf_node) - moet je ook gpf_node_init(node) aanroepen. Dit zal niet veel voorkomen, maar handig te weten als je een foutmelding krijgt. Dit geldt ook voor links (doe daarvoor gpf_link_init). Uitzondering hierop is als je nog geen gpf functies hebt aangeroepen.

Nieuw in v0.8:
Bijna alles, deze versie is volledig herschreven. Hier een opsomming:
- Best-First-Search.
- Instelbare kosten voor zowel nodes als links.
- Subpaden.
- Maximumbreedte voor links.
- Links en nodes kunnen ge(de)activeerd worden.

Nieuw in v0.9:
- Extra argument in gpf_node_create voor twee richtingverkeer.
- Zoekt naar obj_gpf_node en obj_gpf_link in de objectenlijst.
- Maximumbreedte voor nodes.
- Functie om paden die op nodes aansluiten in links om te zetten.
- Functie om dichtbijgelegen nodes automatisch te verbinden.


Licentie
Gebruik op eigen risico.

« Laatste verandering: 13 Oktober 2013, 00:51:48 door WBG »
Naar boven Gelogd

WBG
Globale moderator


Offline Offline

Berichten: 5034


« Antwoord #1 Gepost op: 3 Oktober 2012, 03:13:23 »

Waarom zijn hier nog geen reacties op? Hebben jullie wel door hoe geniaal dit is? Rolt ogen

Dit is een in GML geschreven motion planning systeem. Het geeft je volledige vrijheid over de indeling van het level - zo kan je een vierkant grid maken, of een zeshoekige - of het hele grid laten vallen en een landkaart gebruiken.

Bovendien heeft het maximumbreedtes, subpaden en instelbare kosten, en het kan automatisch paths omzetten in links.
…n het is vrije, open source software met een GPL* vrijlatende licentie. Wat wil je nog meer?
Een voorbeeld zegt meer dan duizend woorden..

Download example


(Edit: Naar aanleiding van Maartens suggestie de licentie aangepast; GPL zou je inderdaad verplichten je spel open source te maken - iets wat ik je aanraad maar niet zou willen verplichten. Ik zal dit voor de XML extensie ook veranderen)
Met die licensie dwing je alle gebruikers om hun games ook open-source te maken, en om een of andere reden is iedereen paranoide dat hun geniale games gestolen zullen worden als ze dat doen.

« Laatste verandering: 8 Oktober 2012, 20:36:57 door WBG »
Naar boven Gelogd

StefanJanssen
Gebruiker


Offline Offline

Berichten: 5211

Was StefannafetS


WWW
« Antwoord #2 Gepost op: 3 Oktober 2012, 11:31:54 »

Ik zal thui is even wat luks en simpels proberen te maken.


Begrijp je iets niet in een uitleg van een gebruiker? Bekijk eerst de helpfile voor je iets vraagt
Naar boven Gelogd

Aquatic games
Gebruiker


Offline Offline

Berichten: 323


WWW
« Antwoord #3 Gepost op: 3 Oktober 2012, 14:32:08 »

Ik denk dat het voor de meeste wat overkill is, zelf weet ik ook niet zo een toepassing voor in mijn spellen.

Ik denk dat dit echt iets is voor de mensen die met vooraf gemaakte paths er niet meer komen.


Naar boven Gelogd

WBG
Globale moderator


Offline Offline

Berichten: 5034


« Antwoord #4 Gepost op: 3 Oktober 2012, 16:05:08 »

Ik denk dat het voor de meeste wat overkill is, zelf weet ik ook niet zo een toepassing voor in mijn spellen.
Simpele spelletjes zullen deze extensie waarschijnlijk inderdaad niet nodig hebben. Wanneer een spel uitgebreider wordt kan dit echter een onmisbare toepassing vormen.
Het plannen van beweging is bijvoorbeeld cruciaal voor elke AI die zich door een wereld beweegt. In strategie spellen (RTS, turn based) kan je niet zonder motion planning, tenzij je poppetjes door muren heen mogen lopen.
Deze extensie is ook erg praktisch voor een race spel, omdat de AI hiermee op intelligente manier tussen voorgedefinieerde paden kan kiezen.
Motionplanning is een basis-skill die elke (bewegende) AI nodig heeft. Maar technologie als deze wordt niet alleen voor spelletjes toegepast: de tomtom in de auto en de routeplanner op googlemaps maken er bijvoorbeeld ook gebruik van.

Ik denk dat dit echt iets is voor de mensen die met vooraf gemaakte paths er niet meer komen.
Integendeel Blij Deze extensie sluit haarfijn aan op vooraf gemaakte paths.
Al sinds v0.8 kan je paths in de route opnemen, en sinds v0.9 is dat nog veel makkelijker geworden:
- Installeer de extensie
- Maak een object genaamd obj_gpf_node
- Zet obj_gpf_node in de room op de belangrijke knooppunten
- Maak paths tussen de knooppunten (zorg dat ze niet "closed" zijn)
- Maak een object die de slimme route gaat berekenen
- Zet path = path_add(); en gpf_auto_link_paths(true); in het create event
- Dit object kan nu met gpf_move(x,y,DOELX,DOELY,path,SNELHEID) over de vooraf gemaakte paden lopen!

Wanneer je de bovenstaande stappen gevolgd hebt, heb je met 3 regels code een AI (vijand, speler, raceauto, wat je wilt) gemaakt die een slimme route kan kiezen over de vooraf ingestelde paths.

Ik zal thui is even wat luks en simpels proberen te maken.
Hierboven zie je hoe simpel het kan. Zie ook de example; de langste code (behalve de GPF scripts zelf natuurlijk) is het draw event van de controller:
GML:
gpf_draw(c_black, -1);

if(keyboard_check(vk_control)){
  draw_set_color(c_yellow);
  draw_path(obj_player.mypath,0,0,1);
}
De rest van de events bestaan uit max. 2 regels code.

« Laatste verandering: 5 Oktober 2012, 21:51:31 door WBG »
Naar boven Gelogd

generaallucas
Gebruiker


Offline Offline

Berichten: 2900

Verhalen: klaar terwijl u wacht.


WWW
« Antwoord #5 Gepost op: 3 Oktober 2012, 18:46:04 »

Dit is opzich wel leuk als je bijvoorbeeld iets als de ''risk spellen'' op GMOT wilt simuleren.


Actionscript 3 - C++ - C# - CSS3 - GML - HTML5 - Javascript - PHP - SQL - Visual Basic - VTask

3DS Max(VRay), Photoshop, Illustrator, Flash, Irrlicht, SDL, CML, OpenGL, Phonegap, Cordova
Naar boven Gelogd

Robert Geers
Jurylid


Offline Offline

Berichten: 1146


« Antwoord #6 Gepost op: 5 Oktober 2012, 16:15:17 »

De example ziet er indrukwekkend uit.  Gemoedelijk

Alleen je mini-tutorial in je vorige post werkt niet helemaal bij mij? link

Naar boven Gelogd

WBG
Globale moderator


Offline Offline

Berichten: 5034


« Antwoord #7 Gepost op: 5 Oktober 2012, 22:21:07 »

De example ziet er indrukwekkend uit.  Gemoedelijk
Thx!
Alleen je mini-tutorial in je vorige post werkt niet helemaal bij mij? link
Je paths staan op closed. Dat betekent dat de path-doorzoeker zowel het begin- als eindpunt op de node zelf vindt - elke node heeft dus zichzelf als enige connecties. Vandaar ook dat je wel naar de eerste node (waar de speler al staat) kunt.
Als je de paths niet-closed maakt werkt het wel. Ik zal in versie 1.0 automatisch paths naar non-closed omzetten (tenzij ze geen nodes verbinden)


Ik geef toe dat closed of niet closed een subtiel verschil is, en je er niet zomaar meteen op komt. De mini-tutorial is aangepast.

Dit is opzich wel leuk als je bijvoorbeeld iets als de ''risk spellen'' op GMOT wilt simuleren.
Goed idee! Gemoedelijk Wat er anders is aan de GMOT versies weet ik niet, maar je kunt dit prima voor een risk AI gebruiken.
Als je de vijandelijke troepenmacht als kosten voor de nodes instelt en alle links vaste kosten van 1 geeft, kan je een AI de skill geven om de meest kansrijke route naar een bepaald gebied te berekenen. Ik zou ook de vijandelijke troepenmachten van de buurlanden bij elke node (gedeeltelijk?) meerekenen in de kostenbepaling; met 5 man een landje met 2 verdedigers aanvallen is kansrijk, maar als daarnaast een leger van 25 staat is het risico al groter..

« Laatste verandering: 6 Oktober 2012, 05:02:23 door WBG »
Naar boven Gelogd

Robert Geers
Jurylid


Offline Offline

Berichten: 1146


« Antwoord #8 Gepost op: 6 Oktober 2012, 06:54:29 »

Je paths staan op closed. Dat betekent dat de path-doorzoeker zowel het begin- als eindpunt op de node zelf vindt - elke node heeft dus zichzelf als enige connecties. Vandaar ook dat je wel naar de eerste node (waar de speler al staat) kunt.
Dat maakt inderdaad nogal wat verschil  Tong
Thx, werkt nu prima.

Naar boven Gelogd

thoot-je
Gebruiker


Offline Offline

Berichten: 3232

Je kan me wakker maken voor een kop tomatensoep :D


WWW
« Antwoord #9 Gepost op: 6 Oktober 2012, 10:01:26 »

erg vet gedaan.
maar ja, ik zou zoiets nooit gebruiken.
ik maak nooit dat soort spellen Grijns


Mijn website: thomasbaake.nl

De 2 belangrijkste dingen in het leven: Productief zijn en extreem veel genieten
Naar boven Gelogd

instantnoedel
Gebruiker


Offline Offline

Berichten: 626

おねがいします。


« Antwoord #10 Gepost op: 9 November 2012, 12:00:23 »

Wooow, dit is echt super! Ik heb me er ook ooit aan gewaagd om een node based motion planning systeem te maken, maar dat heb ik toen toch ernstig onderschat en 't was me uiteindelijk ook niet gelukt. Misschien dat ik nu dan toch een keer dat spelletje kan realiseren wat ik in mijn hoofd had. Gemoedelijk

Je systeem wordt hier trouwens echt ernstig ondergewaardeerd, dit is een van de handigste dingen die ik hier in een lange tijd heb langs zien komen hier op 't board. *_* Ongelofelijk goed werk!


Naar boven Gelogd

StefanJanssen
Gebruiker


Offline Offline

Berichten: 5211

Was StefannafetS


WWW
« Antwoord #11 Gepost op: 25 November 2012, 09:55:59 »

als ik het goed begrijp moet je kruispunten (nodes) aanleggen om te laten weten waar ze mogen lopen. Maar als ze overal mogen lopen behalve waar gebouwen staan hoe doe je dit dan?


Begrijp je iets niet in een uitleg van een gebruiker? Bekijk eerst de helpfile voor je iets vraagt
Naar boven Gelogd

WBG
Globale moderator


Offline Offline

Berichten: 5034


« Antwoord #12 Gepost op: 4 December 2012, 14:45:55 »

als ik het goed begrijp moet je kruispunten (nodes) aanleggen om te laten weten waar ze mogen lopen. Maar als ze overal mogen lopen behalve waar gebouwen staan hoe doe je dit dan?
Je kunt met gpf_auto_link_nodes automatisch alle nodes van links voorzien. Met deze functie kun je een limiet in pixels en een te blokkeren object meegeven: Alle nodes die dicht genoeg bij elkaar liggen en waar geen instantie van het betreffende object tussen ligt, worden met elkaar verbonden.
De meest praktische manier is dus om een parent voor alle objecten die je pad blokkeren te maken en die in gpf_auto_link_nodes meegeven.

Wooow, dit is echt super! Ik heb me er ook ooit aan gewaagd om een node based motion planning systeem te maken, maar dat heb ik toen toch ernstig onderschat en 't was me uiteindelijk ook niet gelukt. Misschien dat ik nu dan toch een keer dat spelletje kan realiseren wat ik in mijn hoofd had. Gemoedelijk

Je systeem wordt hier trouwens echt ernstig ondergewaardeerd, dit is een van de handigste dingen die ik hier in een lange tijd heb langs zien komen hier op 't board. *_* Ongelofelijk goed werk!
Thanks dude, cheers me up! Ik hoop dat je er wat aan hebt Gemoedelijk

erg vet gedaan.
maar ja, ik zou zoiets nooit gebruiken.
ik maak nooit dat soort spellen Grijns
Komt nog wel Knipoog

Dat maakt inderdaad nogal wat verschil  Tong
Thx, werkt nu prima.
Mooi Blij



In dit topic staat een versie van deze extensie die met maximumrichtingen rekening kan houden.
Deze functionaliteit zal in de volgende "officiŽle" versie onder een aparte functie bruikbaar zijn. Ik denk momenteel aan 4 verschillende functies:
- gpf_path - doet wat 'ie nu doet
- gpf_path_angle - houdt ook rekening met hoeken
- gpf_path_ext - ontwijkt bewegende instanties
- gpf_path_angle_ext - houdt rekening met hoeken en bewegende instanties
Vooral die bewegende instantie ontwijk functie wordt heel cool. Jullie zien het wel als 'ie af is Gemoedelijk
Edit: Bij nader inzien gebruik ik liever een vector veld om bewegende instanties te ontwijken, een extensie daarvoor zal ik nog publiceren.

« Laatste verandering: 22 Februari 2013, 23:06:12 door WBG »
Naar boven Gelogd

Advertenties
« vorige volgende »
Pagina's: [1]
Print


Topic Informatie
0 geregistreerde leden en 1 gast bekijken dit topic.

Ga naar:  

Powered by SMF 1.1.21 | SMF © 2006-2007, Simple Machines
www.game-maker.nl © 2003-2020 Nederlandse Game Maker Community