My pathfinder library is very robust, powerful, and I get the feeling is underused compared to what it is capable of. To demonstrate the power of the library I whipped up a demo to show how the library could be used for non standard movement.
The limitations on movement in the demo are as follows
Mob can move forward or backward
Mob can only turn by 45 degrees when also making a move in that direction
Mob can't clip corners when moving diagonal
Originally I was going to use a tank graphic but then I remembered I can't draw and just went with an arrow instead. Just click on the map to move to that tile.
http://www.byond.com/developer/Theodis/ ComplexPathfindingDemo
And if you cut out the comments the amount of code to make that work is actually pretty small for quite an impressive effect.
This library has many potential applications and the demo provided with the library just shows the basics of how to use it. Since I haven't really used it myself I don't have too many ideas for practical applications in BYOND that people might need it for. So I'm open to suggestions for demo ideas if people are having specific pathfinding issues they need an example of a solution for.
[Edit] And if you want to have more fun with you can easily control the possible movement since I did it on a case by case basis in the AdjacentNodes proc. If you want to see it pathfind without moving straight forward just comment out the line that tests and adds nodes for forward. Or if you want to disable turning while moving backwards, or just left turns it's real easy to do with the code and interesting to see how it comes up with paths without certain kinds of movement.
ID:53981
Feb 8 2009, 6:45 pm (Edited on Feb 8 2009, 6:55 pm)
|
|
Well the way I have it set up there is no limit to how much it tries to find a path. So if no path exists it'll try every possible move available to it to find a path. And since the same location only different directions constitutes a different node there are many many more potential nodes than usual. If you were to seriously do something like this for a game you'd want to design the map so that such a thing isn't possible or limit the pathfinder in some way so that you don't have it testing every possibility when no solution is present.
|
I know what you're saying. Just didn't know you were aware that the more complex paths caused issues in your demo.
|
And looking at the error message I realize it is the stupid mistake that it's trying to find a path into a wall. I guess I should at the very least check to make sure the target isn't dense!
|
I sent you a message the other day asking for help. Not sure if you got it or not. I wanted help figuring out what the best configuration would be for the following scenario
13x13 non scrollable maze which is generated randomly. What should I pass in for maxnodes, maxnodedepth,mintargetdist, and minnodedist to get the best performance? I already have it working but I was hoping to reduce the processing time by tweaking the args. AStar(start,end,adjacent,dist,maxnodes,maxnodedepth,mintargetdist,minnodedist) If you could explain these args with examples and/or more details, that would be super helpful. Thanks, ts |
Underused or not, I like this library and use it all the time when its applicable. I used it in Solar Conquest to allow the AI to navigate their ships as quickly as possible using warp gates, while occupying as many planets as possible along the way to make sure that the ships don't spend all of their time out in space.
Of course, the AI still sucked, but at least some of its features were cool. Sadly, my little colony simulation, where the colonists were supposed to use pathfinding to find their way through the maze of interconnected buildings in order to get to the next closest building that they wanted to reach, didn't like pathfinder so well, and it crashed BYOND. Repeatedly. |
13x13 maze? That shouldn't take too long to make a complete search. Make sure your adjacent nodes and distance procs are well optimized since pathfinder will call them a lot. As for the params you probably don't want to use most of them because in a maze the path isn't mostly in the direction of the target and is very likely you might need to go well out of your way to find the right way to the end of the maze.
|
Sadly, my little colony simulation, where the colonists were supposed to use pathfinding to find their way through the maze of interconnected buildings in order to get to the next closest building that they wanted to reach, didn't like pathfinder so well, and it crashed BYOND. Repeatedly. Yeah sometimes it's hard to debug this stuff and a tiny mistake will lead to the pathfinder never making it anywhere. Took some debugging before I got this demo to not crash with every attempt because I forgot to add the end node to the node list for it to ever find. As well as returning incorrect nodes in the AdjacentNodes proc. And I'm not totally sure of the size of the problem. Some complex scenarios can rapidly grow in the size of nodes needed to test to find a solution and with bad estimations it might be testing more than it needs. |
Infinite loop suspected--switching proc to background.
If it is not an infinite loop, either do 'set background=1' or set world.loop_checks=0.
proc name: AStar (/proc/AStar)
source file: Pathfinder.dm,231
usr: Vermolius (/mob)
src: null
call stack:
AStar(/MoveNode (/MoveNode), /MoveNode (/MoveNode), /MoveNode/proc/AdjacentNodes (/MoveNode/proc/AdjacentNodes), /MoveNode/proc/NodeDistance (/MoveNode/proc/NodeDistance), null, null, 0.1, null)
the wall (19,17,1) (/turf/wall): Click(the wall (19,17,1) (/turf/wall), "mapwindow.map", "icon-x=5;icon-y=29;left=1;scre...")
I got it to bog down pretty bad as you can see.