|
Posted By
|
Message
|
Zi-Xiao
Registered
29/07/2002
Points
537
|
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
|
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
 
|
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
        
|
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
   
|
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
|
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
    
|
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
|
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
|
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
|
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
|
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
|
|
|
|
Advertisement
Post Reply