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).