Detour API Change

Heads up!

I changed the Detour API so that it always returns a status (success, failure and few others) instead of number of polygons on path, etc. When you sync to a version > R250, I suggest double checking the calls to Detour.

Many of the changes also changed the function signatures so you will get compiler errors and know where to changes stuff. Some functions such as init() can now have multiple failure cases si simply checking true/false will not result on correct behavior.

The biggest change was for the functions which previously returned number of results. Now the result count is passed as a parameter and the return value tells you if the operation succeed or failed. For example pathFind() changed from:

m_npolys = m_navQuery->findPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter, m_polys, MAX_POLYS);

to:

m_navQuery->findPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter, m_polys, &m_npolys, MAX_POLYS);

To ease the migration, I made the change so that result count is always initialized to 0 in the beginning of the call, so it is safe to use that as an indicator of success too.

Currently majority of the failure cases are reported when one of the input dtPolyRefs was null. There is only one succeed case, so it is good value to check for success.

If you have some ideas for more verbose error reporting or find bugs, let me know!

Following Moving Target

One interesting sub-problem of navigation is following a moving target. This could be a group of ninjas following your warrior, a horde of blood thirsty zombies trying to eat you, limping band of pirates on their patrol route.

So how do you go about implementing a moving movement target? Fire off new path request every frame (too expensive! decision aliasing!)... every few frames (still too expensive! still aliasing!)... when the target moves (it moves all the time, bad optimization!)?

The right answer is that you adjust your path corridor.

The path corridor consists of start point and end point and the list of polygons from the start to the end. When we move our character, we adjust the beginning of the path corridor so that the previous definition holds after the character has moved. We can do the same for the end of the path too!

Take a look at the case pictured at the top of the post. The looting party of three follows the target. The dark polygons represent the path polygons of each agents path corridor. When the target is moved along the navmesh as indicated by the arrow, following will happen.

When the target point is moved, we keep track of the polygons we moved through. Then we "fuse" those polygons to the end of the current path corridor. The fusing process tries to find the shortest common path amongst the two. Sounds complicated, but it is really simple algorithm really.

And that's it! Now we have a new path corridor which describes the navigation from the agents current position to the position it tries to follow.

Detour Implementation

The code is in SVN R249. If you use the Move Target tool with shift+click it will use the target adjusting instead of pathfinding. Turn on Show Path from the debug draw options to see the effect.

The CrowdManager example supports both adjusting the current path corridor of an agent as well as keeping track of the changes that might happen whilst a movement request is still being processed.

Future Improvements

This method of following comes with it own set of cons too.

The method does not try to find the shortest path, it just tries to patch the current path with minimal effort. Depending on your application this may be good or bad.

If you have quit small tile size, this may lead to odd behavior in open fields. Even if there is direct line of movement to the goal, the path will take detour based on how the target moved. The open field case eventually would optimize itself. Since the path optimization distance is limited, the agent will move to "old" direction for some time before the optimizer kicks in.

Conclusion

Patching the path corridor is really efficient way to implement path following. It has some limitations, but they are quite negligible when the follow distance is quite small, like when following player quite closely or when following a formation point.

My recent work on path following has surfaced and interesting problem to solve, that is the path corridor optimization. When the world is constantly in motion–and in games it always is–the quality of the initial path is less and less important. I hope I will have more time in near future to figure out how to optimize the path corridor in certain uses cases.

If the above method sounds crappy and limited, it still does solve the case for moving target for a whole range of the use cases. And did I mention it is really fast?

RVO Sample Pattern

I spent quite a lot of time last Friday on trying to fix some cases I had with ORCA and to implement line obstacles. I kept on running into cases which simply cannot be solved using it.

For example I could not solve the case in above picture. Regardless of my effort, I ended up having cases where the segments would block the movement completely. The ORCA planes would be aligned according to the dark edges and they would limit a convex region which is used to clamp the velocity. I think some of the problems might be due to the fact that the navmesh is offset by the agent radius.

I'm anxiously waiting for the next paper which improves ORCA. Until then, I'm sticking with the sampled approach. Which leads me to another thing I tried last week.

Improving Sampling

At the time when I was working on my first iteration of the adaptive sampling for RVOs Phil Carlisle's student Scott Bevin mailed me that he was using similar method in his thesis too.

One main difference between out methods were that I was using a regular grid as sampling pattern and he was using 8 samples on a circle aligned at the movement direction and subdivide towards the best sample. At the time I was too busy with my Paris presentation so I did not have any time to investigate it further.

I tried his method but it did not quite work in crowded situations. There simply was not enough initial samples to get good answers.

But the idea of aligning the sample grid helps a lot! I initially thought that it would cause a lot of problems because it might produce more feedback into the velocity control loop. I think I was wrong. The desired velocity usually is quite stable, so when the pattern is aligned towards it, I did not see any additional feedback effects.

As you might spot from the above picture, my implementation used two rings of 7 samples plus one sample at zero velocity. The inner circle's rotation is offset slightly to get better coverage. Since the samples are aligned towards the desired velocity there is always a sample exactly at the desired velocity too. This makes the overal control very smooth, the jaggies from the non-aligned method are gone.

Conclusion

In practice the new sampling pattern improved the movement through small corridors a lot. The hesitating movement is almost completely gone now. The agents do slow down quite a bit if they approach a choke point from an angle. From their point of view they are almost approaching a wall. Adding that extra sample at the zero velocity improved stopping a lot.

All in all, I'm pretty happy about the results now. Not perfect, but tolerable. I can now finally turn my attention into fixing the remainder code structure issues with the crowd code.

Crowd Manager Progress

The Crowd Manager stuff is slowly coming together. I think I have some of the bottom layers figured out now (i.e. that PathCorridor class). Still heaps to work to do. I was lucky to be able to do few weeks full time work earlier this Autumn and got a lot of progress, but now I'm back to my freetime schedule so things progress quite a bit slower.

The way the Crowd Manager has evolved in the SVN is pretty much the way I usually massage my code. I start with something that just works. In my case it was the ugly but working prototype I made for my Navigation Loop presentation. First I ported that code almost one-to-one to use Detour. After that I have tried to refactor the hell out of it until I have seen the code from arranged from many points of view.

The point is to find the best structure of the code based on the constraints you have. Fully explore the depth based on each constraint. My major constraints have been speed, concurrency and reusability.

Speed was my first goal, which I pretty much reached. I have recently worked more on the concurrency and a lot more on trying to find good structure how to organize the code so that it is reusable.

I don't have much experience writing concurrent [1] code, so my approach has been to make all the hard work–like A*–asynchronous (PathQueue) and try to arrange the other code so that the work is done embarrassingly parallel (to make the transition from concurrent to parallel easier), to use read-only data, and try to reduce the sync points to as few as possible. Very much like the Nulstein stuff.

One of the most complicated things about writing toolkit or library code is how to organize the public API. I don't like huge monolithic systems which want to control all the updates themselves. They are simple to get something rolling quickly, but once you need to shuffle your own code around a bit, you start to get pretty horrible problems in update orders and what not. I'm big fan of Casey what it comes to API design, but I don't think I master that yet.

One of the hardest parts of arranging the code has been how to facilitate custom implementations of parallelizing the code, steering, collision avoidance and dynamic constraints. They are right there in the middle.

As with the rest of the RC&DT, the Crowd Manager will be again piece of usable example glue code, which uses the "real" public API. Ideally it should show you how the relation ship between different parts of the navigation loop, where to put the sync points, and which steps rely on previous ones. Also the sample will include some example implementation of steering and dynamic constraints.

The public API will be some classes which implement path corridor management, local avoidance and such. The sample code should help you to get things up and running quickly, but I try to make the sample code simple, light and rough enough that you will not have problem later to tear it into parts and rewrite to fit into your code base.

So there is still a lot of work to do, and I will probably postpone some of the features [2] to get a working piece of code out in reasonable time frame.

ETA? Before Christmas (fingers crossed).

_

[1] Concurrent = code "in-flight" at the same time, Parallel = code executed in parallel

[2] Like using off-mesh connections and more robust handling of mesh changes. Not complicated code, just annoyingly puzzley to figure out correct state handling, and how to juggle that state around.