Theodis PathFinder help

ID:159626
 
Feb 6 2009, 8:06 pm
I'm using Theodis's Pathfinder library and I'm hoping to tweak the parameters passed in to reduce any unnecessary processing. Can anyone explain the differences between these two args as defined by the library? I believe I can figure out the other two if I understand these two.

maxnodes - The maximum number of nodes that can be in the open list.  Pass in 0
for no limit.  Limiting the number of nodes may prevent certain paths from being
found but the the nodes removed are the least likely to lead to good paths so as
long as this value is sufficiently high this shouldn't be a problem.



maxnodedepth - Defines the maximum number of nodes that can be traversed to get
to the destination node.  This will prevent any extra long paths from being
found but will prevent the algorithm from spending too long if you don't care to
find these paths anyway.


ts
Feb 6 2009, 10:11 pm
The first one limits the size of the "open list" which is some internal thing that I don't know much about. The second limits the length of each path.
Feb 8 2009, 3:21 am
maxnodes limits the number of nodes on the open list. The open list is a list of tiles/nodes that the pathfinder needs to check. If the number goes beyond the maxnodes limit then the ones at the end of the list(least likely to get to the destination) just get dropped rather than tested. If those nodes could have lead to the destination then the pathfinder might fail even if there was a path. As long as the path doesn't have to go a long distance out of its way to get to the destination this shouldn't be a problem. If you have a really large map you need to pathfind on with no obstacles that might force a unit to head away from the destination a long ways to get to the destination then limiting the nodes on the open list can improve pathfinding speed a lot. Just start with a nice value like 1000 and see how it works out. If pathfinding works fine you can try reducing it to get more speed. If pathfinding fails too much you can raise it so it fails less often.


maxnodedepth limits the number of nodes/tiles that can be used to make a path so it's essentially a max number of moves cap. This is mainly for if you want a point and click style movement since you probably don't need the path to be much larger than the view. If you have a giant river or something similar you don't want to bog the game down by having the pathfinder find the long path around rather just make the player find their way around on their own and use the pathfinding for getting around minor obstacles. If you use this parameter you should also use the minnodedist parameter. This proc just needs to return the minimum number of moves between two nodes. For regular turf maps it'll just be get_dist() unless you're disallowing diagonal movement or something. Using both these params the pathfinding should be lightning fast.
Feb 11 2009, 7:42 am
In response to Theodis
Thanks for this info. I didn't see the reply until just now. I'll give your suggestions a try. Here's where I'm at right now. This shows about 15 seconds into my game using the following args.

pathList = AStar(loc, exit, /turf/proc/AdjacentTurfs,/turf/proc/Distance, 0, 110, 0, 0)



                               Profile results (total time)
Proc Name                                  Self CPU    Total CPU    Real Time        Calls
--------------------------------------    ---------    ---------    ---------    ---------
/turf/proc/Distance                           0.988        1.018        1.081       447127
/proc/PathWeightCompare                       0.139        0.139        0.189       164341
/PriorityQueue/proc/IsEmpty                   0.156        0.156        0.202       105978
/PriorityQueue/proc/Enqueue                   0.313        0.406        0.443       104895
/PriorityQueue/proc/Remove                    0.188        0.420        0.441       104895
/PriorityQueue/proc/Dequeue                   0.266        0.686        0.727       104895
/PathNode/New                                 0.405        0.420        0.425       104895
/turf/proc/AdjacentTurfs                      2.813        2.813        2.816        96342
/PriorityQueue/proc/_Fix                      0.186        0.232        0.251        27109


ts
Feb 11 2009, 8:05 am
In response to Tsfreaks
Hmm looks like you have a bit of a bottleneck in your AdjacentTurfs proc. Can you describe the problem a bit more. In one of my members posts you mentioned that it is a 13x13 maze. Is it done with turfs or some other datum? Is it static or dynamically generated? If you can get a screen shot of an example case and give me any special movement rules you're imposing that'd be helpful.
Feb 11 2009, 8:17 am
In response to Theodis
It's a tower defense game. The map is 13x13 grass (turf). Mobs move from the left side to the right side. The shortest path is straight across which is 14 moves into the goal. The longest path is 101 moves to the goal. The longest path is created by the player placing towers (obj) on the map (like a maze) WHILE the mobs are trying to move toward the goal. Each tower placement results in each mob calling astar to update their path. Mobs can only move in cardinal directions which is done in AdjacentTurfs.

ts
Feb 11 2009, 9:04 am
In response to Tsfreaks
Each tower placement results in each mob calling astar to update their path. Mobs can only move in cardinal directions which is done in AdjacentTurfs.

Yeah that can probably get process intensive with a lot of them. I suggest retooling it a bit. First build a complete path from start to finish ignoring mob density and store it. Then build an associative list with each turf being the key and the index into the path being the value

ie:
associativeMap = new()
for(var/i = 1; i <= path.len; i++)
associativeMap[path[i]] = i

Which will let us quickly find if a tile is in the main path and which index it is in the path. Then the mobs will first check to see if they are on a tile in the path and if they are just follow the main one. If not use Djikstra to find a path to the nearest tile on the path and follow that until they're on the path. For that I suggest storing the destination in a global variable and make tiles that go away from the final destination more costly so that the paths it generates to get to a tile on the path will lean towards the finish rather than backtrack to get on the main path.

Density checks on other mobs should only be in the pathfinding for the first tile since all their positions will change anyway after the next move so you'll probably need to store the start in a global as well before making the pathfinding calls so you can do a different AdjactentTiles calculation for the initial tile. If a mob runs into another dense mob on their way they should just recompute their path.

When a tower is dropped all paths should be cleared. Make sure all accessible tiles are still connected. If not you probably want to handle that case in some way or prevent it from happening. If the start and finish are reachable form each other repeat the process of making the major path and have all your mobs find their way to it again.