Detour Crowd Path Replanning

Path replanning for Detour Crowd has been a long time pet peeve of mine. I've blogged about the problems surrounding it earlier, but very little code has been submitted. I've been testing some ideas along the way, but never managed to have the few hours of solid coding to get all the pieces together.

Here's what happens in the above video:

• At start all the agents find a short parts towards the goal. In the video they intentionally get stuck at local minima at start. Generally this improves responsiveness, but sometimes the agents move to wrong direction for a moment.

• During movement the agents will replan their paths if they notice that the navmesh has changed in front of them. When the agents turn to purple, it means that they are replanning their paths. Similar small search is performend when the replanning occurs, but polygons along the existing path are favored. This makes changes close the agent responsive and changes further away does not make any visual change at all.

• When the agent approaches the end of the path and the last polygon on the path is not the goal polygon, the agent will periodically replan the path. When a pathway to the goal opens, the agent will use that path.

On top of that there is the path topology optimization going on too. I think the recent changes made that pretty much irrelevant–I think it might be better to just fire a replan every now and then just for the kicks.

I think that summarizes my thinking about path following in general. Once the world is constantly changing, the system ends up replanning the whole time. You cannot replan as much as you would like to since it is hard to determine how long A* will take, so the system becomes this weird scheduler-caching-magic-fudge-latency-hiding-box. There are these dynamic planning algos, like D*, but they all require too much memory.

I hope to get to have the change to put another pass on Detour Crowd replanner to make it much simpler and more robust. Now there is too much state management spaghetti in there.

The changes are available in SVN, please not that I removed the adjust move target function as it was complicating the logic too much. If you are using it, please let me know and I'll try to figure out similar functionality. I also added velocity control for agents (for player characters and such).

Crafting 3D User Interfaces for the Web

I had a talk a little while ago at local frontend dev event called Webshaped. My talk was about how to craft easy to use, tangible 3D UIs. This is one of the dearest topics to me, and I think I overdid the presentation a bit. It kinda became a mash-up between a game design talk and UI talk for kinda designers and sorta programmers (or developers as web folks like to call them).

I think I will redo the presentation at some point in the future if such an opportunity presents itself. Maybe more focused on some of the sub topics, or more maybe with interactive things to try out etc.

I have not talked much about Tinkercad on my blog so far. A lot of the interesting stuff about Tinkercad does not quite fit the voice of this blog, but I think I'll write a thing or two about it.

For those who don't know, Tinkercad is super easy to use 3D modeling tool for makers, artist and tinkerers alike. It works directly in your browser. Under the hood Tinkercad is a solid modeler, which means that all the stuff you make with Tinkercad can be 3D printed.

Here's something we did just recently, an embeddable viewer for your projects. The project shown below is a plan of our deck with summer furniture and some gardening stuff.

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.