Path Finding for Complex Vehicles
Members - Reputation: 311
Posted 28 May 2012 - 05:54 AM
I'm developing a RTS game where the player can create their own units (Vehicles) in game. This means that there is potentially massively differences between the different units in the game.
For example, there may be a big difference in unit sizes, such as one type of unit that is 3m x 2m x 2m, and nother that is 100m x 100m x 20m and another that is 80m x 10m x 10m etc.
Its not onyl sizes that may differ either, there are other things such as the weight, power, the actual way its driven (e.g. does it have wheels or catapilar tracks etc).
All these things effect which parts of the terrain the units can drive on. For example, there may be a narrow canyon that a 3x2x2 unit can travel down but a larger unit can't. Or there may be a steep incline that a powerful or light vehicle with catapilar tracks can get up but other vehicles cannot, etc.
This is a bit problem for pathfinding.... I've used A* successfully in the past but it seems like there are just too many variables for me to be able to use it here.
If size was the only variable then I could create 8 different A* maps, one for 1x1 units, the next for 2x2 units, next for 4x4 etc, up to 256m x 256m units, but that assumes all units are square and doesn't help with other variables such as weight, power, drivetrain etc.
Is there another type of pathfinding algorithm that is better suited?
The only other solution I can think of is to use A* but to calculate the node to node costs (And indeed whether its even possible to get from one node to another) in realtime. This would potentially be computationally expensive but probably do-able.
Any other suggestions?
Thanks in advance.
Members - Reputation: 156
Posted 28 May 2012 - 07:25 PM
There are ways to speed those validation computations up by precalculating data at map generation time.
Things you can store per cell:
- Distance to closest static obstacle, AKA, largest unit size that can stay on the cell.
- Cell slope.
- Average height difference at each edge, AKA, stair-step height when crossing to that neighbour. Useful for determining if legged entities can consider that cell accesible or not.
If any of those conditions fail to meet your vehicle requirements for that particular adjacent cell then consider it not connected to the node you are evaluating at that point in your A* search.
Members - Reputation: 1039
Posted 28 May 2012 - 11:36 PM
You could also store some state at each node, e.g. vehicle orientation and speed. This does break the optimality of A* if you handle it wrong, but generally vehicles aren't used in super constrained environments, so an acceptable solution would still be found. If you can quantize your states (e.g. 8 directions and 3 speeds) you could add another dimension to your A* graph which would allow basic problem solving, e.g. cover the same ground multiple times to achieve a goal like 3 point turns or jumping. Alternately you could tag difficult places on your map or detect them automatically and use canned techniques to solve problems, e.g. add a temporary node from your current position to behind you that executes a 3 point turn with cost x.
Members - Reputation: 311
Posted 29 May 2012 - 02:21 AM
I think what you're saying will work.
The only thing to mention is with reference to "Distance to closest static obstacle" is that its not quite that simple as its not clear what an obstacle is. For example, something that is an obstacle for a 3m x 3m vehicle may not be considered an obstacle for a 100m x 100m vehicle that can just drive over it.
But in general I think what you're saying works.... I'll just have to calculate the costs and node connectivity at runtime as opposed to having a nice fast precalculated map of data.
Crossbones+ - Reputation: 2221
Posted 01 June 2012 - 08:52 PM
a unit that sits on 6x6 nodes, moves exactly one node to the left, would only have to evaluate 6 nodes for legal movement, as the rest of the 5x6 we were already sitting on, so they must still in theory be legal, a diagnal node would require evaluating 11 nodes, as the other 5x5 nodes are were we used to be sitting.
their are probably potentials for it to be sped up more, but this imo, created a decent result for variable sized units on a fixed sized grid.
as for problem's with terrain movement, that's as nigo said, simple filter's applied to checking if the move is legal.