Hi,
I'm currently prototyping a pathfinding system for my game. The goal is to get a efficient result on getting 20 to 30 entities (usually enemies) to a moving object (usually the player). This all in a range of 30 to 40 tiles from the destination (the moving object). Currently i'm using a Dijkstra algorithm for this since i only have to call this once to get all the paths of the entities to the moving object, if it's not moving. Currently I'm struggling with a efficient way of finding paths on this since i want smooth movement, well, directional movement not tile by tile which would be very easy and cheap.
Currently making the "smooth" path using this Dijkstra outcome is giving me a headache. It takes 300ms to find the next tile a entity should move to on a fairly large area. This is because I traverse the whole list of nodes to see if the entity can get there. So what can I need some ideas to refine this.
Prior to actually moving the entity, I thought of traversing the path tile by tile keeping all the nodes in some 5*5 area around it, but this would add a lot of overheat again when I get more entities to move.
I have also been thinking of a way to add a extra int to the node and increment this if the path splits. But i'm still clueless about how this is going to work if it's even a viable way.
To sum up my thoughts,
Pros,
1, All the entities will be using the same Dijkstra to find the target. Doing a Dijkstra on 1 80*80 tile region takes less then 100ms. This only needs to be called every couple of seconds when adding a smaller one for closer entities more often.
2, If there are collisions between moving objects i can calculate a new path based on the current Dijkstra. If i'm correct this can easily made in some nice flocking of multiple units.
Cons,
1, The dijkstra algorithm has to be called everytime the target changes from tile. Like mentioned above, I Could split this up into 2 dijkstra's, 1 close to the target that gets updated very often and another that gets updated once every couple of seconds.
2. Finding straight paths are very expensive since every time a entity moves to another tile it has to go through each node and do collision checks on these from current position. Since there is a possibility there is a new (and faster) straight line to be found.
I have been working with pathfinding some time now without very good results when i get a lot of objects asking for a path. I haven't bothered with binary heaps in combination with A* yet but for this project i don't need path finding over very large area's just a lot of pathfinding on smaller area's. I'd like some thoughts on what i got so far, how to improve it and how you would approach this.
Multiple entities to same tile using Dijkstra.
Some thoughts:
1. When you need to execute the dijkstra only each X seconds, try to split it over several frames (each frames calculates up to X iterations). This way you can easily avoid choppy gameplay and you are not forced to use any multithreading approach (yet).
When the player moves, just add this movement in form of nodes to the last valid paths until your new path has been updated.
2. Transform the path of each agent into a simple waypoint array and keep track of the next waypoint your agent want to move to, this way you save all the look-up overhead you've mentioned.
3. What about steering behaviour ? Once you have your paths calculated, try to use steering behaviour to navigate your agents along each path. This way you have many options to make the movement smooth, avoid other agents (=collision avoidance), grouping (flock) and many more. It really works great.
1. When you need to execute the dijkstra only each X seconds, try to split it over several frames (each frames calculates up to X iterations). This way you can easily avoid choppy gameplay and you are not forced to use any multithreading approach (yet).
When the player moves, just add this movement in form of nodes to the last valid paths until your new path has been updated.
2. Transform the path of each agent into a simple waypoint array and keep track of the next waypoint your agent want to move to, this way you save all the look-up overhead you've mentioned.
3. What about steering behaviour ? Once you have your paths calculated, try to use steering behaviour to navigate your agents along each path. This way you have many options to make the movement smooth, avoid other agents (=collision avoidance), grouping (flock) and many more. It really works great.
Hmm, one possibility that comes to mind is this:
1. Every x frames you do Dijkstra for the whole map, maybe break calculation over multiple frames.
2. Every frame you don't have a fresh Dijkstra result you do a Dijkstra on the 2x by 2x area surrounding the new position of the moving object.
3. When an NPC gets within that 2x by 2x area you use those results instead.
There are many path smoothing approaches. An easy one is here: http://digestingduck.blogspot.co.nz/2010/03/simple-stupid-funnel-algorithm.html
1. Every x frames you do Dijkstra for the whole map, maybe break calculation over multiple frames.
2. Every frame you don't have a fresh Dijkstra result you do a Dijkstra on the 2x by 2x area surrounding the new position of the moving object.
3. When an NPC gets within that 2x by 2x area you use those results instead.
There are many path smoothing approaches. An easy one is here: http://digestingduck.blogspot.co.nz/2010/03/simple-stupid-funnel-algorithm.html
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
