🔒 Locked

Path Finding for Complex Vehicles

Started by BenS1 May 28, 2012 at 11:54 AM 3 replies 2.5k views

Original Post

May 28, 2012 at 11:54 AM

Hi

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.

Ben

nigo

May 29, 2012 at 1:25 AM

At each node expantion step of your A* loop: filter out neighbour nodes that do not pass your vehicle requirements, that is, consider them non-reachable even if they actually are connected (adjacent) to your current node

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.
-Terrain type.

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.

jefferytitan

May 29, 2012 at 5:36 AM

Nigo beat me to it. I've been doing some pondering on similar matters (but creature rather than vehicle based). If you make some basic assumptions, e.g. rectangular, a small set of locomotion possibilities, don't allow 3 point turns, the problem can be manageable. Storing the distance to the closest obstacle allows accommodating vehicle width by only considering nodes with distance >= width / 2. Essentially you just need to call a custom function each time you evaluate an open node to filter possibilities.

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.

BenS1

May 29, 2012 at 8:21 AM

Thanks both for your replies.

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.

Thanks
Ben

slicer4ever

Jun 2, 2012 at 2:52 AM

one method i came up with when i was working on variable sized agents in A* was to allow the unit to exist on several nodes at once, and pick one of the node's to be the center/movement controlled node(generally it was the center node, but you can determine this however you'd like). when the centeral node was evaluating the next node to move to, it'd check all the node's that the agent will reside on, to ensure that they are legal. it's possible to speed this up since with agents that sit on more than 4 square nodes would already be occupying the many of the nodes.

for example:
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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.