I've been thinking about how to do complex pathfinding with momentum, e.g. not just steering behaviours. A* can work over an arbitrary graph, so my thought is to extend it into other dimensions.
You have your regular A* graph which is used when starting from a full stop. Then you generate 8 x 3 subgraphs for the 8 directions and 3 movement speeds. The subgraphs are weighted essentially the same, but smeared in the direction of travel by the speed. So obstacles get bigger in the direction of travel (don't want to run into them at full speed) and small gaps in terrain become traversable by jumping. Costs of turning are increased according to speed. The subgraphs are joined to neighbouring speed subgraphs but only in the current direction of travel, or perhaps diagonals at lower speeds. Therefore the same physical terrain can be explored multiple times by A* for different speeds, if the higher speeds can be attained in the space given. It would even allow backing away from a gap to get up speed to jump across it.
The downside of course is a huge search space, and only rough equivalence with the actual physics model. I haven't had the chance to think it through, but I expect that some of the common ways of speeding it up such as Hierarchical A* wouldn't work without modification, as many make topographical assumptions. I suppose you could set a benchmark by using the lowest speed subgraph, and use this as an upper limit on the full graph A*. Also it's not clear how acceleration comes into it, e.g. how big a run-up to get from speed 1 to speed 2.
Thoughts? Comments?
A*-like Pathfinding with Momentum
It would seem that if your network is so granular as to fall well within the momentum-based turning radius of your agents, that you are going to have a shitload of nodes.
Author
It would seem that if your network is so granular as to fall well within the momentum-based turning radius of your agents, that you are going to have a shitload of nodes.
It would seem that you're correct. ;) I know this, but not sure what else one can do. I saw a few other questions on this sort of thing, but the answer was invariably "use steering behaviours" or hand place nodes where special movement activities can happen.
Author
My perspective is that if the pathfinding is totally unaware of the effects of momentum then it will plot a safe-and-steady course which will not give the steering an opportunity to shine. For example, the pathfinding would plot a course around the small gap that the steering could jump over. The steering won't get to try the jump because it will never be anywhere near the gap.
An alternative I suppose would be a static analysis of the map which determines which gaps have a big enough run-up nearby to potentially jump over, then give those cells a highish (but not infinite) cost. If the steering behaviour later determines the jump is impossible, then the A* map would need to be revised to make the gap impassible, e.g. the agent would go for the gap, chicken out, then try another way.
An alternative I suppose would be a static analysis of the map which determines which gaps have a big enough run-up nearby to potentially jump over, then give those cells a highish (but not infinite) cost. If the steering behaviour later determines the jump is impossible, then the A* map would need to be revised to make the gap impassible, e.g. the agent would go for the gap, chicken out, then try another way.
I solved a similar problem by not hard-coding the cost of edges in my graphs. Instead, each edge is considered by a context which is passed to the A* implementation at pathing time. The context code looks at the edge and the nodes it connects and determines the cost on the fly. (This is of course improved for performance reasons using caches, precomputation, etc. as necessary, but that's the basic idea.) Contexts have full access to the currently known shortest path as well as other internal data of the A* implementation, so they can make very complex decisions trivially.
In your case, you would create edges over gaps statically, and assign them some kind of flag which indicates they are jumpable. The context then marks the point in the generated path where the jump would occur along with how "hard" it is to make the jump itself. In your steering layer, you approach the jump and look up the difficulty of the jump. If the difficulty is too high, you stop, and recompute the path from that point, this time informing the context that you can't make the leap. In the majority of cases, your agents can make the jump fine; if they happen to be slowed down for some reason on the way, you simply re-path and figure it out as though the jump isn't available.
There is certainly a bit of an art form to getting pathing and steering to work nicely together, but it's more about handing off decisions back and forth at appropriate times than about trying to cram all the logic into one or the other of the layers. They need to stay balanced between the two approaches to movement; think of it as a yin/yang sort of situation rather than "oh crap I have two competing things and one of them should go away." There's a harmony there that works best at a certain mixture (which varies based on the game you're making of course) and tending too heavily towards steering or pathing just introduces lots of complication.
In your case, you would create edges over gaps statically, and assign them some kind of flag which indicates they are jumpable. The context then marks the point in the generated path where the jump would occur along with how "hard" it is to make the jump itself. In your steering layer, you approach the jump and look up the difficulty of the jump. If the difficulty is too high, you stop, and recompute the path from that point, this time informing the context that you can't make the leap. In the majority of cases, your agents can make the jump fine; if they happen to be slowed down for some reason on the way, you simply re-path and figure it out as though the jump isn't available.
There is certainly a bit of an art form to getting pathing and steering to work nicely together, but it's more about handing off decisions back and forth at appropriate times than about trying to cram all the logic into one or the other of the layers. They need to stay balanced between the two approaches to movement; think of it as a yin/yang sort of situation rather than "oh crap I have two competing things and one of them should go away." There's a harmony there that works best at a certain mixture (which varies based on the game you're making of course) and tending too heavily towards steering or pathing just introduces lots of complication.
Author
Thanks Apoch, that sounds like a good start. I thought about using a context too, but the thing that got me was the symmetry problem, e.g. the number of ways of reaching the same cell with the same cost, but coming from different directions. Is there a way of resolving that, or does it not prove to be a problem in practice? Maybe just leave steering to take over at that point?
I think that these kinds of questions of responsibility are often tricky. Where do you hand off between animation, steering, pathfinding, planning and group planning? Every answer that I see seems to cut it slightly differently. ;)
I think that these kinds of questions of responsibility are often tricky. Where do you hand off between animation, steering, pathfinding, planning and group planning? Every answer that I see seems to cut it slightly differently. ;)
If you have a copy of AI Game Programming Wisdom 4 sitting around, Chris Jurney did a good bit on the vehicle navigation in Company of Heroes. It wasn't the same as momentum, but using turning radii as a calculation in the process invokes some of the same issues.
Also, remember to not just think of momentum as an aftereffect that you can't control. Think in terms of how your agents might be aware of their own momentum and plan on it for turns. So, for example, if they have plotted a path that goes through a narrow gap, they will adjust accordingly before they get to the gap. The only time momentum really screws with you is when you have to repath suddenly.
Another thing to remember is to use changes in speed. In the example of planning ahead, a common technique that we would use is to slow down so as to make our momentum more controllable. Many games don't adequately use speed control to "sell" their movement.
Also, remember to not just think of momentum as an aftereffect that you can't control. Think in terms of how your agents might be aware of their own momentum and plan on it for turns. So, for example, if they have plotted a path that goes through a narrow gap, they will adjust accordingly before they get to the gap. The only time momentum really screws with you is when you have to repath suddenly.
Another thing to remember is to use changes in speed. In the example of planning ahead, a common technique that we would use is to slow down so as to make our momentum more controllable. Many games don't adequately use speed control to "sell" their movement.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement