I've written games using A* pathfinding before without any problems, and I know how to extend the algorithm to take into account other attributes too (e.g. some terrain may be more difficult to cross and therefore you'd increase the cost of crossing this terrain), however in my new game I have several requirements which I can't see are easily addressable using the normal A* algorithm.
Specifically my requirements are:
1. I need to be able to group many units and move them together
2. The units need to be able to move over massive distances.
3. The size and capabilities of my units vary greatly. For example one unit may be 100 times bigger than another unit in the group. Or one unit type may be able to get over a very rough terrain or steep incline, whereas another unit may require a smoother more level terrain.
On point 1: There are many algorithms that address group movement, and ensure that the units can 'flow' through pinch points without getting stuck etc, although I'm not sure if there are any that would work with units of such varying sizes? If so then please recommend, or recommend a starting algorithm that you think I may be able to extend to do what I need.
On point 2: I'm planning on doing this by having a 2 level pathfinding algorithm. The first level will be a very low resolution representation of the world (With nodes in a grid every 100m or so) . This will allow us to plan a rough path from A to B over a long distance. Then we will have a higher resolution grid (nodes every 1m)... this will be used to plan the precise path the units should take over a short distance.
So when we plan a long path we will first plan the low resolution path, and then as we approach each waypoint on that path we will calculate the high resolution path to follow.
I'm sure this technique already exists and is well documented (Probably called a heirachical A* algorithm, or similar).
On point 3: This is where things get really tricky.
For any particular type of unit I could use A*, and for each node I could factor in the units size and abilities (To go over different types of terrain, levels of incline etc) when calculating the routes cost. However, I could potentially have 100+ different types of units, each with their own properties and abilities, and when I plan he path I don't want to have to calculate the cost for every unit in my group as that would just take too long.
I guess I just need to consider the lowest abilities of the group as a whole.
For example, if I have a group containing the following 4 vehicles:
Vehicle 1: Width = 5m, Max incline = 40 degrees
Vehicle 2: Width = 2m, Max incline = 42 degrees
Vehicle 3: Width = 1.5m, Max incline = 30 degrees
Vehicle 4: Width = 3m, Max incline = 25 degrees
The we should look for a route that is always at least 5m wide and has no inclines over 25 degrees.
Hmmmm, it doesn't seem so difficult now.
Anyway, if you're aware of any good algorithms that already exist that may meet my requirements then please let me know.
Thanks
Ben
Group Pathfinding for Complex Groups
I think you solved your own problem by explaining it :-)
Typically for groups you'd run a pathfinder once, e.g. using A*, and set it to use the worst-case parameters. Where can't all units traverse, what are the worst case costs, etc. Then you have a path that reflects all units in the group. (If you want the group to have multiple paths, then split the group and start again.)
After that, it's "just" a question of path-following. You can probably use some kind of collapsible formation system, using local steering to move units around in relative positions.
Alex
Typically for groups you'd run a pathfinder once, e.g. using A*, and set it to use the worst-case parameters. Where can't all units traverse, what are the worst case costs, etc. Then you have a path that reflects all units in the group. (If you want the group to have multiple paths, then split the group and start again.)
After that, it's "just" a question of path-following. You can probably use some kind of collapsible formation system, using local steering to move units around in relative positions.
Alex
Author
Thanks Alex
Yes you're right, I did pretty much solve it just by explaining it.
I'll read up on collapsible formation systems and general group movement (Avoiding collisions and jamming etc), but I'm pretty comfortable with the A* part.
Thanks
Ben
Yes you're right, I did pretty much solve it just by explaining it.
I'll read up on collapsible formation systems and general group movement (Avoiding collisions and jamming etc), but I'm pretty comfortable with the A* part.
Thanks
Ben
Avoiding collisions and jamming
Collisions are easy enough to avoid with local navigation, but things like jamming and deadlocks will require a lot more work. There's arguably no general solution for it that works in all cases; academics have been working on it for decades! If you can come up with a simplification for your own game, or avoid really narrow passages and huge groups, then it'll be easier.
Alex
You could also combine pathfinding with flocking, assigning one unit as "commander" wich know all the statistics about the group such as how big it is, and what the size of the biggest unit is.
You pretty much figured it out while trying to ask the question, which happens a lot.
Group pathfinding should consider the group as one single entity.
The capacities of the group are the lowest best and the highest worst.
Flocking is usually the best approach to solving the movement of each agent within the group.
For very large paths consider sub dividing the world, such as in rooms, zones or similar large areas, connected through a graph of pre-calculated paths. You could call this hierarchic pathfinding.
When units are moving a very long distance it's not necessary to calculate the full path before they begin moving, do a first approach and start them moving and split the calculation between frames.
If the world has high traffic, it may be beneficial to perform short range pathfindings every now and then while moving along the long range path.
Including parameters such as known dangers, known resources locations, and so on, translated as movement cost could give a better "intelligence" feel to your path, if an explorer or gathering unit is ordered to move he should avoid danger if possible, while a military unit might want to go through the danger area to neutralize the danger. If we take group movement into account, a group including a few military units of low power might decide to avoid a known danger if its weight is greater than the collective firepower of the group, or a group that combines civilian units (explorers, gatherers, and other non military units) with military units could assume the purpose of the military units is to escort the civilians and assume an interest in evasion of danger even if the firepower is greater than a known danger.
Pathfinding + AI is such an interesting feature to work on! ^^
Group pathfinding should consider the group as one single entity.
The capacities of the group are the lowest best and the highest worst.
Flocking is usually the best approach to solving the movement of each agent within the group.
For very large paths consider sub dividing the world, such as in rooms, zones or similar large areas, connected through a graph of pre-calculated paths. You could call this hierarchic pathfinding.
When units are moving a very long distance it's not necessary to calculate the full path before they begin moving, do a first approach and start them moving and split the calculation between frames.
If the world has high traffic, it may be beneficial to perform short range pathfindings every now and then while moving along the long range path.
Including parameters such as known dangers, known resources locations, and so on, translated as movement cost could give a better "intelligence" feel to your path, if an explorer or gathering unit is ordered to move he should avoid danger if possible, while a military unit might want to go through the danger area to neutralize the danger. If we take group movement into account, a group including a few military units of low power might decide to avoid a known danger if its weight is greater than the collective firepower of the group, or a group that combines civilian units (explorers, gatherers, and other non military units) with military units could assume the purpose of the military units is to escort the civilians and assume an interest in evasion of danger even if the firepower is greater than a known danger.
Pathfinding + AI is such an interesting feature to work on! ^^
Author
Thanks Andres et al
I think I know how to do it now.
The only remaining problem is that I'm not sure flocking would work well in my case, as some of my vehicles may be small (e.g. 3mx3m) and others could be massive (100+m x 200+m or more), and complex shapes.
I've noticed that in Supreme Commander they had a similar problem (Although their biggest 'Experimental' units weren't as big as mine can be) and they simply allowed the big units to drive over buildings and small units like they weren't there. I'd like to do something better than that.
Thanks
Ben
I think I know how to do it now.
The only remaining problem is that I'm not sure flocking would work well in my case, as some of my vehicles may be small (e.g. 3mx3m) and others could be massive (100+m x 200+m or more), and complex shapes.
I've noticed that in Supreme Commander they had a similar problem (Although their biggest 'Experimental' units weren't as big as mine can be) and they simply allowed the big units to drive over buildings and small units like they weren't there. I'd like to do something better than that.
Thanks
Ben
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
