Sunday, October 23, 2011

Path Replanning

I've been picking on path replanning again. It is interestingly annoying problem. I have currently settled on following idea to make it somewhat manageable.

In ever dynamic game world, the path finding and path following becomes statistic. The changes are that most of the time your request does not pan out the way they were requested. It is really important to have good failure recovery, both on movement system level as well as on behavior level. Plan for the worst, hope for the best.

Movement Request
At the core of the problem is movement request. Movement request tells the crowd/movement system that a higher level logic would like an agent to move to a specific location. This call happens asynchronously.

Path to Target
When the request is processed, the movement system will find the best path to the goal location. If something is blocking the path, partial path will be used and the caller is signaled about the result. From this point on, the system will do it's best to move the agent along this route to the best location that was just found.

Path Following
If a disturbance is found during the following, the movement system will do a small local search (same as the topology optimization) in order to fix the disturbance. If the disturbance cannot be solved, the system will signal that path is blocked and continue to move the agent up until to the valid location on the current path unless it is interrupted.

This could lead to following interface between the high level logic and the movement request.

struct MovementRequestCallback
 // Called after path query is processed.
 // (Path result accessible via ag->corridor)
 // Return true if path result is accepted.
 virtual bool result(Agent* ag) = 0;

 // Called when path is blocked and
 // cannot be fixed.
 // Return true if movement should be continued.
 virtual bool blocked(Agent* ag) = 0;

 // Called when the agent has reached
 // the end of the path trigger area.
 // Return true if movement should be continued.
 virtual bool done(Agent* ag) = 0; 

bool dtCrowd::requestMovement(int agent,
 const float* pos, const dtPolyRef ref,
 MovementRequestCallback* cb);

The 'result' callback allows the high level behavior to cancel movement in case unfavorable path rest is found (i.e. partial path), or it allows the behavior to set some internal state based on the path result.

The 'blocked' function allows the higher level logic to handle more costly replans. For example the higher level logic can try to move to a location 3 times until it gives up and tries something else, and it can even react to replays if necessary.

The 'done' function allows to inject extra logic on what to do when path is finished. For example a 'follow enemy' behavior may want to keep on following the goal even if it is reached, whilst 'move to cover' might do a state transition to some other behavior when the movement is done.

The general idea is to move as much of the state handling behavior out from the general code, and try to make the replan to be as cheap as possible. The downside is that the replan cannot react to big changes in the game world, but I argue that that is not necessary and should be handled with higher level logic anyway (i.e. the path can be come much longer).

What do you think?


  1. I think it's a pretty elegant design. I'm in full agreement about seperating all locomotion systems from any high level behavior systems. That being said global replanning is unavoidable if you wish to be able to handle large changes and so diminishes the usefulness of the local replanning idea.

    Personally, I feel that local avoidance should not be handled through replanning but rather through steering/locomotion and that replanning should only be used for global route planning.

    Trying to use local replanning for avoidance especially within dense crowds is something that is non-trivial due to the increases reaction times stemming from this appraoch. In such case having avoidance based in steering is preferred. Tho for less dense environments I think there maybe merits for actual replanning but this can open up a whole new can of worms with regards to agent path following and once again response times, especially when trying to achieve high fidelity animation. There also needs to be a degree to future-planning especially for fast moving agents.

    Just my 2c.

  2. takinginitiative, the replanning is meant to happen in cases where the navmesh changes, for example when a bridge is up, or door closed, or "hard" obstacle has moved. Other agents and moving things should be handled using local obstacle avoidance.

    I agree that replanning is necessary, but the rules when to replan are non-trivial. For example in the "take cover" example, it might be better to find new cover location too.

  3. Yeh, but if the navmesh changes, it should generally be a good idea to replan for only agents which couldnt reach their previous goals. Although this implies that agents which require replanning are in some sort of a standby behavior is which they are still trying to achieve their previous goal, which in itself is probably a bad AI design.

    An unreachable goal shouldn't ever be chosen, if a goal is unreachable then another goal should be provided for the agent instead of simply moving towards an unachievable goal.

    If during an agents movement to a goal the path gets blocked (bridge collapsing, door locking), then a full replan is necessary as there are no guarantees a local replan will find a route. If a local replan fails then we fall back on a global replan after already paying the cost for the local. The cons in my opinion out weighs the cons and I dont see much benefit in local replanning.

    Although this might be my lack of experience talking so I would appreciate it if you can give me an example of a good use case for local replanning?

  4. @takinginitiative, In ever changing game world, there are no guarantees. You can only be sure of the current state of the world, and it is very likely to change in next time step.

    There are a lot of cases where only local portion of navmesh is changed. It could be a door, exploding barrel or a moving crate. In those cases the path can be recovered by making a local search around the location where the change happened. If the change is more drastic or blocks the path, then my method will fail, and you will need to do replan.

    I'm currently doing these small searches to optimize path topology (see my earlier posts), and the same system can handle small changes in the navmesh too. So there is no extra penalty if the navmesh change was quite small.

    Many of the things you stated in your reply are true, but equally many are hard to detect in dynamic world. Async queries require good standby behaviors. Unreachable goal can become reachable and vice versa while the agent is moving there. Good AI design is the one that fails gracefully.

  5. Love the idea.

    "I agree that replanning is necessary, but the rules when to replan are non-trivial."

    Yes, exactly. One particular case I've had is that real agents will often have a "can't be bothered" threshold, they won't replan around the map to get through a door. They'll do something else: like sound an alarm, or not bother, or wait.

    The idea that if the world changes, then character motives are likely to have changed is a really obvious one. But the kind of obvious that it takes someone smart to point out. Thanks!

  6. Mikko,

    Your notification approch sounds great. One thing that bothers me is the data which can be provided if a path apparently gets blocked. E.g. if a blocking barrel just got into the way which lead to a nav mesh recalculation, this piece of information might be very helpful to decide what to do next (e.g. "go to the barrel and crush it" or "check if its still moving and won´t be in our way for long etc.").

  7. I think you're providing more feedback and more control, without incurring significant extra cost, by exploiting features of the design - such as the existing topology optimisation. Which is exactly what a nicely refined API should do.

    And I say, the more cheap features you give me, the better :-)
    But hey, I'm greedy, so here's some more in that line:

    When you find any topology optimisation or a shorter route has opened up, you could offer a callback to tell me it happened, what changed, and confirm whether I actually want to take it.

    Consider a behaviour where we chase a target, trying to hunt them down.

    - I might want to give some kind of readability to show that I've noticed the shortcut - like perhaps pause and fire some shots after the target before taking the new branch
    - but that would only make sense if I do it at the point where the shortcut branches off so I need to know where that is
    - and consider, how much shorter is this new route anyhow? if my appearing to pursue is more important than catching the target, I should only take shortcuts that are 50% better - and if I'm totally crazed about catching this guy, it may better suit my behaviour if I don't notice shortcuts at all. Or on another tack, if there's two pursuers, it would be nice group behaviour to split up.

    Similarly with blockages - if the blockage just happened right in front of me, I probably want to display a reaction, and I might just give up in frustration rather than take the next best path.

    One other thought - do take care with callbacks. I take it you want the user to be able to set a new async goal as a result of a callback, but they could also do something like unregister the crowd agent. Making these things fully re-entrant can be a pain, and I try to do it with a polled stack of events rather than callbacks where I can.

  8. For my own implementation I created a macro path finding system based upon the internet networking border gateway routing protocol. The idea was to speed up long distance pathfinding by breaking down the pathable zones into grids conntected via portals. These portals become static waypoints along a trejectary and act like routers, comunicating -route to neighbouring portal- costing information. Any changes in the landscape results in an update in path cost. When a path cost moves within or exceeds a given threshold then the portal will announce the change to the navigating entity which can then make an informed decission on how to reach its destination (when traveling across multiple pathable zones).