The Daily Click ::. Forums ::. Klik Coding Help ::. Node-based pathfinding
 

Post Reply  Post Oekaki 
 

Posted By Message

Zi-Xiao



Registered
  29/07/2002
Points
  537

VIP Member
16th June, 2009 at 23:41:15 -

Just wondering if anyone has looked into the topic of node-based pathfinding before. I know pixelthief wrote an article about a year back on the subject but I can't get the example to load correctly in mmf2. Furthermore, theres supposedly a way to do what pixeltheif has done using full recurssion.

Anyways, please post your thoughts on, or implementations of, node-based pathfinding in a klik product.

 
n/a

MBK



Registered
  07/06/2007
Points
  1578

VIP Member
17th June, 2009 at 06:48:20 -

What exactly is full recursion? .. Isn't that just a fancy word for a loop? ... I've looked up several definitions and still don't get it.
Does node-based mean that you reach a section of a path (the node), then code executes to send you toward the next node?
If so, then it seems fairly simple to me ... what's the catch? ... it's really more difficult than that right?


 
Click Me! http://www.create-games.com/project.asp?view=main&id=1444

http://www.mediafire.com/download.php?aoo1dnnlq5i

Blood of the Ancient One, Seen only as Shadow, Faster than Lightning, Fierce as the Greatest Dragon, Nearly Invisible, Floating in a Dream, Entered through the Demon Door, Destroyer of Evil in a Realm with a Red Sky Scarred, Who could I be ?

[DELETED]

Likes to put dots on paper

Registered
  08/12/2008
Points
  118

MushroomVIP MemberARGH Sign
17th June, 2009 at 07:25:20 -


Originally Posted by MBK
What exactly is full recursion? .. Isn't that just a fancy word for a loop? ... I've looked up several definitions and still don't get it.
Does node-based mean that you reach a section of a path (the node), then code executes to send you toward the next node?
If so, then it seems fairly simple to me ... what's the catch? ... it's really more difficult than that right?



In theory, node-based paths are really easy to do but I believe when he says pathfinding it's a little more complicated, and open for (I'm assuming,) the AI to move around nodes.

Though, there should probably be a lot of "Object collides with node, set direction to next node and continue movement" actions in the event editor. And one to compare the distance between object and node to see where the closest node is and then move to it (no idea how to go about doing that).

Good luck on your quest, eitherway

 
n/a

Cecilectomy

noPE

Registered
  19/03/2005
Points
  305

Has Donated, Thank You!VIP MemberWeekly Picture Me This Winner!Cardboard BoxGhostbuster!Pokemon Ball!ComputerBox RedSanta HatSnowman
I am an April Fool
17th June, 2009 at 07:37:01 -

"What exactly is full recursion? .. Isn't that just a fancy word for a loop?"

not exactly. recursion is something that references itself. its closer to nesting.

if you understand c++ this is a very simple example of a recursive function.


int a(int x)
{
if (x >= 10)
{
return x;
}
else
{
a(x+1);
}
}


"using full recurssion."

as opposed to what other kind of recursion?

basically you would code loops that call loops in mmf. stepping through all nodes until it finds the destination node.

read up on trees, binary trees, graphs, and A* pathfinding.

 
n/a

Assault Andy

Administrator
I make other people create vaporware

Registered
  29/07/2002
Points
  5686

Game of the Week WinnerVIP Member360 OwnerGOTM JUNE - 2009 - WINNER!GOTM FEB - 2010 - WINNER!	I donated an open source project
17th June, 2009 at 11:54:51 -

I wrote this in 2007:
http://www.clickteam.com/epicenter/ubbthreads.php?ubb=showflat&Main=6887&Number=46016#Post46016

"Waypoint Linking Example for Pathfinding"

It generates a node/waypoint map at the start of the frame and then the enemies walk around randomly using those paths. This system was designed to automate the process of pathfinding without having to manually type in which nodes could see each other. I may use a different system today if I were to make a game with node-based-ai.

 
Creator of Faerie Solitaire:
http://www.create-games.com/download.asp?id=7792
Also creator of ZDay20 and Dungeon Dash.
http://www.Jigxor.com
http://twitter.com/JigxorAndy

MBK



Registered
  07/06/2007
Points
  1578

VIP Member
19th June, 2009 at 06:08:44 -

Kewl stuff guys. "almost" understand C++ ... (I read through part of a book real quick, lol) ...
That makes me want to learn C++ more though Cecil, good stuff.
I'll get around to it one of these days.
I knew this whole node pathfinding thing was more complex than what I was thinking. Thanks for clarifying some of the details.

Anyone know if that's the logic they used in King of Dragons for the bosses?


 
Click Me! http://www.create-games.com/project.asp?view=main&id=1444

http://www.mediafire.com/download.php?aoo1dnnlq5i

Blood of the Ancient One, Seen only as Shadow, Faster than Lightning, Fierce as the Greatest Dragon, Nearly Invisible, Floating in a Dream, Entered through the Demon Door, Destroyer of Evil in a Realm with a Red Sky Scarred, Who could I be ?

Pixelthief

Dedicated klik scientist

Registered
  02/01/2002
Points
  3419

Game of the Week WinnerWeekly Picture Me This Winner!You've Been Circy'd!VIP MemberI like Aliens!Evil klikerThe SpinsterI donated an open source project
19th June, 2009 at 06:45:33 -

Theres many much much much more efficient algorithms which give better results than that. For example, Dijkstra's applied to the graph of nodes can give the shortest path in a much more efficient manner. Especially if you were to do it in say lua instead of the MMF architecture.

In the very, very naive implementation I posted, it simply treated all the outward nodes of the current 'point' as a tree, and used a direct depth-first search of every node of the tree to find a path to the wanted point. So it wouldn't even return the best result. In essence, it was like this:

(have nodes at every junction in the map)
1) Find the closest node to the AI, mark this as "A" (make sure path to the node is passable, else repeat for next closest)
2) Find the closest node to the DESTINATION, mark this as "B" (make sure path to the node is passable, else repeat for next closest)
3) Use a depth-first search on the tree consisting of adjacent nodes to find a path from "A" to "B"; mark each visited point to not be re-visited, and once "B" is located, record all the nodes taken along that path.

Its very complicated and I'm not sure what the most efficient algorithm would be

 
Gridquest V2.00 is out!!
http://www.create-games.com/download.asp?id=7456

Pixelthief

Dedicated klik scientist

Registered
  02/01/2002
Points
  3419

Game of the Week WinnerWeekly Picture Me This Winner!You've Been Circy'd!VIP MemberI like Aliens!Evil klikerThe SpinsterI donated an open source project
19th June, 2009 at 06:56:21 -

I might consider making a Djikstra's algorithm example

 
Gridquest V2.00 is out!!
http://www.create-games.com/download.asp?id=7456

Cecilectomy

noPE

Registered
  19/03/2005
Points
  305

Has Donated, Thank You!VIP MemberWeekly Picture Me This Winner!Cardboard BoxGhostbuster!Pokemon Ball!ComputerBox RedSanta HatSnowman
I am an April Fool
19th June, 2009 at 07:28:00 -

if you do pixeltheif can you also include it to return a list of ALL complete node paths to the destination? not just the shortest.

 
n/a

Pixelthief

Dedicated klik scientist

Registered
  02/01/2002
Points
  3419

Game of the Week WinnerWeekly Picture Me This Winner!You've Been Circy'd!VIP MemberI like Aliens!Evil klikerThe SpinsterI donated an open source project
19th June, 2009 at 07:46:14 -

yeah. but then again, djikstra's isn't biased towards any direction so its not that great for pathfinding I guess, just finding the minimum path efficiently. I suppose something like A* would be better suited towards just finding a non-necessarily best but very efficient path to a point, and maybe giving it some recursion limit to avoid the worst case scenarios. Sure it might lead to moments like AI being trapped on the other side of a wall and just pacing back and forth instead of going around it to get at you, but I think thats better than a game that runs at 1 FPS.

 
Gridquest V2.00 is out!!
http://www.create-games.com/download.asp?id=7456

Cecilectomy

noPE

Registered
  19/03/2005
Points
  305

Has Donated, Thank You!VIP MemberWeekly Picture Me This Winner!Cardboard BoxGhostbuster!Pokemon Ball!ComputerBox RedSanta HatSnowman
I am an April Fool
19th June, 2009 at 07:56:42 -

it would be good for a turn based strategy game. cause it would only have to predetermine the node paths. "thinking..."

 
n/a
   

Post Reply



 



Advertisement

Worth A Click