Sunday, May 20, 2012

Loose Navigation Grid Prototyping

I had a little time this weekend to work on AI again. I've blogged earlier about loose navigation grids, and now I finally got it to the point that it starts to look interesting. Above is a video showing the current prototype in action.

Path Planning in Dynamic Worlds

In addition to this example, I've been working on path replanning in DetourCrowd. It has become painfully obvious, that the most limiting factor for pathfinding is that we assume that it is perfect. Dynamic worlds make this pain a migraine.

If the world is constantly changing, the notion of "path to the goal" becomes really hard to define. Even the goal itself becomes uncertain. For example if we picked a cover point and the level around the AI and the cover changed, is the cover a good choice any more? The more I've thought about it, the broader the problem has spread.

I have earlier discussed that I think in changing worlds, the contract between the behavior and the pathfinder should be the initial path. If the initial path changes too much, then the behavior plan fails and the behavior should replan too. This does not seem to be well accepted idea, so I've started to rethink the problem.

The feedback I'm getting from the people who are using Recast is that they would just like everything to work. Out of the box, don't-tell-me-how-it-works.

Loosing Up the Constraints

So the idea I'm toying with the loose navigation grids is that you just drop your character in the world, tell it to go to some location and it happens or not. The important idea I'm testing here is that can we make the navigation system uncertain? There is no guarantee that the agent will find its' way to the goal, but it will try, with limited horizon of information.

This allows a couple of things. Firstly, since we know that we have limited view of the world, we can use greedy search algorithm and replan to our hearts content. We're side stepping A* worst case performance which means visiting all the nodes in the graph. Secondly, accepting the limited information again, interesting culinary opportunities open up as such as exploring the navigable space more locally, iteratively, patching things up as we go, throw away information that is too far.

The down side is that given the local nature of the search space, the system will get stuck in local minima. But then again, how big are local minimas in games? MMOs may have the nasties pathfinding problems of the all, but I think they should use hierarchies to hide the complexity. 

I think this has been interesting though process so far. I've been able to let loose a lot of preconceptions and limitations I had before.

The Prototype

In the above video you'll sees that the loose navigation grid is build on the fly by starting at a seed point (i.e. character location). The exploration step looks at open edges in the local nav grids (hilighted at the end of the video) and creates a new grid at such location. Path planning is done hierarchically, first between the grids and then within one small local 2D grid.

The navigation structure should be "self healing". If an obstruction is added or removed, the intersecting grids can be deleted and exploration phase can be rerun on the neighbors of the deleted nodes to fill in the space.

Next time I'll have a little time I will try to make the whole path finding and movement to work to see how good it looks and then it is time to test some destruction.


  1. Nice stuffs !

    While i agree the "don't-tell-me-how-it-works" would be nice, it has its limit also. At least you should get feedback when a path replanning occurs, and what are the changes, because, as you says it might lead to a reevaluation of the initial decision.

  2. @clodéric Lot's of maybes, mights and shoulds ;) But I do agree what you say. I'm sort of taking this opportunity to try to find another perspective on the problem and maybe redefine a bit what you might expect from navigation system. For example if path planning was fine graned and fast enough, could we interleave it with behavior planning? Maybe FPS "move-to-cover" would be some kind of continuous evaluation of trying to get into cover and the API to path planning would not be "move to this exact location in world"? What would that API look like then?

  3. Looks a lot like Rapidly-exploring Random Trees (RRT) that I stumbled upon this weekend :

    I thought the patterns were interesting and would probably give a better "external" impression of an AI trying to find its way.

    Can't wait to see what you come up with :)

  4. Very interesting thoughts, thanks for sharing.

    We are facing these problems while trying to simulate e.g. evacuation behavior of agents (lets ignore social behavior for a moment) in a dynamic environment. We kinda miss a link between Detour and the "semantic world" (e.g. the potential cover). At the moment we define places like rooms/corridors/floors in a separate representation but steering to them is tricky. Sometimes we would like to tell the agent to get to the ground floor (and search their for potential exits) instead of providing a 3D point.

    I´m wondering about e.g. dynamically grouping Navmesh polygons into (potentially overlapping) areas (similar to the definition of flags) where the area can be used as target. The agent reaches the target as soon as he enters the area. This would allow commands like:
    - "Get to the main corridor."
    - "Get to the 2nd floor."
    - "Get to the west wing of the building."
    - "Get to nearest cover area." (Which has just been defined by the game logic evaluating the current assault situation.)

    Areas and high level behavior:
    The high level AI could dynamically define areas while detour could invoke callback methods when an agent enters/exits an area for convenience.
    Another place where high level AI could kick in is when the path (re-)planning occurs. E.g. a callback could be called returning the result of path planning options (e.g. containing the (locally) expected areas passed and the distance inside them). The high level AI callback method could return which path to choose by evaluating the area and distance information.
    Following this approach it would be possible:

    - to avoid a drawbridge which will be surely closed as soon as the agent approaches it (the drawbridge is an area the AI evaluates as unpassable under current conditions)

    - to choose a way through an area which blocks/unblocks regularly (The AI understands the "nature" of e.g. "the moving platform" area and decides to go that way and wait there)

    - to go through a broad dominant corridor instead of a parallel bunch of rooms although the resulting path is 3 meters longer (the AI decides that the corridor should be favored for security/social reasons)

    A few of the cases could be simulated using flags (and indeed we do so atm).

    IMHO coupling Detour to an AI like this would also enable sharing information about apparent blocked path which need replanning.

  5. Thanks for creating this awesome post. It really informative. Checkout: University of Tennessee Acceptance Rate

  6. Thanks for writing this blog, You may also like the 3d Printing services , Prototype