Jump to content


Photo

Gm Node Path Finding Dll


  • Please log in to reply
26 replies to this topic

#1 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 26 March 2008 - 06:39 AM

Last Updated: January 25th, 2012

Dll source included
13 tutorial files (More to come) Last file is the merge file
From introduction to platform to top down use
GM7 Only for now, until I fully release it
v 0.2 BETA. Please test it out
Posted Image

Read the Info in each tutorial files. Each file is different in what it demonstrates or teaches.

Node path finding is complementary to A* path finding. Setup properly, and using the included DLL, you may even surpass GM's m_grid_path system (which is pretty efficient)

Why use nodes?
Well, consider an AI that needs to go to a destination. Using mp_grid_path and a grid set up, this is doable but there are a few problems.

1) Depending on your setup, mp_grid can actually be quite slow, especially if the path to the destination is complex with lots of twists and turns.
2) Consider a destination that is moving (such as a bus the AI needs to take) or the point that leads to a destination is moving… Such as if the way to the island is through a boat…mp_grid path cannot work efficiently in those situations.
3) Consider the cost of traveling to a destination… Would taking the bridge 3 miles away be faster or would taking the ferry be the best option.
4) Consider a platform AI… Can mp_grid be used in that setup? Well, yes, it can. But again, major work is needed in the AI. Using a node system you can easily locate the enemy and travel to jump spots on platforms. Or create a path that actually makes sense in a top down setup.
5) Consider that in some cases you cannot travel back from where you came using the same route because the route you came through is a one way street...

When you are done with the tutorials, you'll be able to create smart moving AIs for top down or platform…

I swear, you be able to make a AI walk from the office to the store, buy a loaf of bread, take the bus or its car home. Figure out the fastest way to get there and get there LOL… Well I hope…

I'm still working on tutorial files 14 to 20 which by then should cover all the uses of the dll.

Meanwhile check it out and see if everything is working right and tell me of any helper script you would like me to add.

IMPORTANT FIX

I have a typo whivh will yield this error

ERROR In script NodeAssociateWith:
Error in code at line 32:
while(object_get_parent(baseparent2) <> AllNodesObj)

at position 26: Unknown variable baseparent2


The declare above that code has the typo

var basedparent2;

remove the d...

Untill I update this, if I ever do.

Edited by icuurd12b42, 25 January 2012 - 10:56 PM.

  • 2

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#2 Krisando

Krisando

    GMC Member

  • New Member
  • 1351 posts

Posted 27 March 2008 - 08:52 AM

It sounds so smart I could make it turn on my computer and code frozzd in game maker :)
I have already thought of many uses for it, maybe evn a sims type game :unsure: hmm theres only 1 way to find out how good this is :snitch:
  • 0

Posted Image


#3 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 31 March 2008 - 01:39 AM

It tells me an error "Error Defining External Something", I use Vista and I unzipped it.

- Fede-lasse


After you load the gmk, save it and try again... It's a GM bug. I have the same problem with vista and I experienced the same bug with GMPhysics.dll.
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#4 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 31 March 2008 - 08:11 PM

Hah, same here. Will edit in a moment...

EDIT:
Wow! This is really cool! It's like a Counter-Strike waypoint system or something :)

I prefer making my own system in GML though. Less complicated, but also less powerful, but still...

- Fede-lasse



I have the original node path finding in GML. Very slow... Only 4 or 8 AIs could actually use it in the game. That's why I made the DLL.
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#5 liverol

liverol

    GMC Member

  • GMC Member
  • 179 posts

Posted 01 April 2008 - 02:02 PM

nice work,keep up the good work!!
  • 0

#6 blizter

blizter

    GMC Member

  • GMC Member
  • 50 posts

Posted 02 April 2008 - 04:34 AM

This dll is fantastic ! ^_^
  • 0

#7 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 02 April 2008 - 05:21 AM

Thanks guys.
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#8 SquareWheel

SquareWheel

    Square Wheel Games

  • New Member
  • 851 posts
  • Version:Unknown

Posted 02 April 2008 - 05:55 AM

It sounds like a neat idea for a dll. Why not turn it into an extension package? This is the kind of package people would keep around.
  • 0
Cook Console | Editor Engine | Mass File Namer

All of my examples are publicly available and can be found at

#9 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 02 April 2008 - 08:26 AM

It sounds like a neat idea for a dll. Why not turn it into an extension package? This is the kind of package people would keep around.


I hate extension packages. I have no plans to make one. The interface is clearly defined with scripts (that you can actually see) and you can actually see the script code and you don’t have to "Add Extension Package" to make the code run... When GM implements a more seamless extension package system, I'll reconsider.

Besides, It comes with a controller object in charge of the DLL and the fundamental NodeObj which I can't (don't think I can) add in an extension package.

Edited by icuurd12b42, 02 April 2008 - 08:28 AM.

  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#10 HaRRiKiRi

HaRRiKiRi

    GMC Member

  • GMC Member
  • 1364 posts

Posted 14 April 2008 - 07:55 PM

Nice dll.

and you don’t have to "Add Extension Package" to make the code run

Yeah, you have to Scripts>Import Scripts which is basically the same thing (thou you could delete script file or misplace it, but extension will stay if installed).

Besides, It comes with a controller object in charge of the DLL and the fundamental NodeObj which I can't (don't think I can) add in an extension package.

You can. NodeObj=object_add();. And if you will say that "Then users will not be able to change the name of the object!" or something like that, then remember there are ways to do it. :lol:

Edited by HaRRiKiRi, 14 April 2008 - 07:58 PM.

  • 0

#11 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 28 April 2008 - 03:45 AM

Nice dll.

and you don’t have to "Add Extension Package" to make the code run

Yeah, you have to Scripts>Import Scripts which is basically the same thing (thou you could delete script file or misplace it, but extension will stay if installed).

Besides, It comes with a controller object in charge of the DLL and the fundamental NodeObj which I can't (don't think I can) add in an extension package.

You can. NodeObj=object_add();. And if you will say that "Then users will not be able to change the name of the object!" or something like that, then remember there are ways to do it. :(



I could but you need to have acces to the NodeObj in order to store other meaningful data you might need for your AI. And/or you may need to set it as parent to your own nodes too. The red,green,blue and yellow nodes are an example of that. And the debug hud and mouse controller are great too to test the node setup for speed and to see what your AI would select for a path.

Not a big fan of encapsulation as you may have noticed.



OK, Anyone tried to do something with it yet?

Edited by icuurd12b42, 28 April 2008 - 03:47 AM.

  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#12 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 03 May 2008 - 09:44 PM

I hate extension packages.

What about those who love them?


Then let them make their own.
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#13 wurdup

wurdup

    GMC Member

  • GMC Member
  • 863 posts

Posted 12 August 2008 - 01:12 AM

this is awesome.. thx

what is your usage policy?
  • 0

#14 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 12 August 2008 - 04:07 AM

this is awesome.. thx

what is your usage policy?


If you have a credit section that seems empty without me in it, then go ahead and add me in there LOL.

Use as you wish. I'm not that fussy about credit for this particular dll.
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#15 wurdup

wurdup

    GMC Member

  • GMC Member
  • 863 posts

Posted 12 August 2008 - 11:11 AM

i have a strange problem with the nodes. Ive put the nodes in my game but changed them to 128x128 (tiles to simulate a road). All works well and the pathAI happily moves from node to node avoiding the blockers but at the moment the origin of the tiles is 0,0. This means the pathAI moves to the corner of the tile so I changed the origin to center but this makes the nodes not connect to each other at the start ie there are no blue arrows to each node. The pathAI just goes to the first nearest node when buggers off the screen at direction 0.
Any ideas what's causing this?

** its probably not a huge problem because I could in theory just create the original node on top of the 128x128 but then of course it would require twice the amount of objects/sprites

Edited by wurdup, 12 August 2008 - 11:14 AM.

  • 0

#16 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 12 August 2008 - 06:56 PM

i have a strange problem with the nodes. Ive put the nodes in my game but changed them to 128x128 (tiles to simulate a road). All works well and the pathAI happily moves from node to node avoiding the blockers but at the moment the origin of the tiles is 0,0. This means the pathAI moves to the corner of the tile so I changed the origin to center but this makes the nodes not connect to each other at the start ie there are no blue arrows to each node. The pathAI just goes to the first nearest node when buggers off the screen at direction 0.
Any ideas what's causing this?

** its probably not a huge problem because I could in theory just create the original node on top of the 128x128 but then of course it would require twice the amount of objects/sprites


You are not supposed to change the node to be actual tiles in your game (They cost nothing because they are step/draw codeless and have no collision event)... You see, when the room starts, each node tries to see if another note is visible... Looking in every direction if there is a node without a blocker in between. So, if you make them bigger, they will probably find nodes arround. The x,y origins define where the check is performed from. If the origins of the sprite is 0,0 intead of center... Trouble... If precision collision is off, again, trouble...

Drop a DebugMouseControllerObj in the room then you can hold 1,2,3,4,5 or 6 to see how the nodes linked themselves
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#17 wurdup

wurdup

    GMC Member

  • GMC Member
  • 863 posts

Posted 12 August 2008 - 09:02 PM

ah ok cheers
  • 0

#18 i_forget

i_forget

    GMC Member

  • New Member
  • 347 posts

Posted 13 August 2008 - 12:38 AM

Can the node system re-calculate which nodes can be seen? because I have a maze-type game where the walls can (eventually) be destroyed.
Like nodes that could not see each other see one another when the wall dividing them is gone?
  • 0

#19 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 13 August 2008 - 01:07 AM

Can the node system re-calculate which nodes can be seen? because I have a maze-type game where the walls can (eventually) be destroyed.
Like nodes that could not see each other see one another when the wall dividing them is gone?


//success = GMNPFNodeSetDisabled(node,disable)
//Used to disable a tile

//You can block the path system from going though a node by disabling it
//You cannot free/remove nodes from the system aside from nuking the entire system
//and recreating it. So this will allow you to disable destroyed regions of a map for example
//without having to redo the entire node system...

//Or temporarely prevent the AI from going to a spot in the map such as a locked or hidden area
//unloackable by an event

//node = GMNPFNodeAdd(nodesmemomy);
//GMNPFNodeSetDisabled(node,false);
//show_message(string(GMNPFNodeGetDisabled(node)));


So, drop a node on the door...When the door is closed, disable the node (using the (node instance).m_GMNPFNode)). When it opens, enable the node.

GMNPFNodeSetDisabled((ANodeGMinstanceid).m_GMNPFNo
de,true);
GMNPFNodeSetDisabled((ANodeGMinstanceid).m_GMNPFNo
de,false);

There is another way to disable a link between 2 nodes... But it's harder to reset the link later.
GMNPFNodeClearLink
GMNPFNodeAddLink
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#20 i_forget

i_forget

    GMC Member

  • New Member
  • 347 posts

Posted 13 August 2008 - 01:18 AM

Also, what do I put for the variable nodesmemory? Like, is there a minimum or a maximum?
  • 0

#21 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 13 August 2008 - 01:32 AM

You don't need to know that... Unless you plan to manually add nodes. That function that refers to that memory, it's only there as a code snippet showing the bare minimum to use it...

GMNPFControllerObj is in charge of allocating the nodes memory for you and tell all the GMNodes to relink themselves using NodeAdd and NodeAddLink. That happens the very first end step and any other step a new node is detected... You need not consern yourself with it....
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#22 i_forget

i_forget

    GMC Member

  • New Member
  • 347 posts

Posted 13 August 2008 - 03:32 AM

Also, even if you don't make it an extension, could you at least make a detailed help file? Some people (me) have trouble understanding examples.
  • 0

#23 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 13 August 2008 - 04:14 AM

Also, even if you don't make it an extension, could you at least make a detailed help file? Some people (me) have trouble understanding examples.



You should run each example in order and read the (i)nfo in each example. It's really minor introductions in each example... You will fail to grasp the last example, that is for certain.
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#24 i_forget

i_forget

    GMC Member

  • New Member
  • 347 posts

Posted 14 August 2008 - 01:49 AM

I easily grasped the last example, as well as the others but my coding isn't accepting your DLL. Do you think you can PM me about this? I want to keep my project a secret.
  • 0

#25 Ruub

Ruub

    Finn The Human

  • GMC Member
  • 762 posts
  • Version:GM:Studio

Posted 02 November 2011 - 10:10 AM

Great dll man!

I would love to use it but I can't since my game involves making your own lvls (and I don't want to bother people putting up nodes :c)
Also I have gm8 and it's a pain in the *** to try and fix every difference xD
  • 0

#26 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 02 November 2011 - 06:36 PM

Great dll man!

I would love to use it but I can't since my game involves making your own lvls (and I don't want to bother people putting up nodes :c)
Also I have gm8 and it's a pain in the *** to try and fix every difference xD

It works gm7,8 and 8.1. what difference have you spotted?
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button


#27 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • GMC Elder
  • 18181 posts
  • Version:GM:Studio

Posted 25 January 2012 - 10:54 PM

UPDATE: January 25th, 2012
Links are sorted by cost when added to the nodes. Make sure to set the nodes cost before linking them.
This should make cost based path finding more efficient as this increases the chances of finding the least costly path early in the search and provide an early exclusion of alternative paths. Were as before the costly path could have been determined first then a lesser cost, then a lesser cost and so on until the least costly path is found (worst case)

Changed the max number of connections from 10 to 20.
  • 0

gmcbanner.pnggmcbanner_tools.png

ICU Live Tutoring Through Slack or Skype | My Tools Page follow.png

I FRANTICALLY MADE MY 18000 POST TOPIC BEFORE MIKE ANNOUNCED A DELAY...
Now I'm squirming not to hit that reply button