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.