Happy Holidays!

Merry Merry and Happy Happy!

Thank you for the past year, and good luck for the following one! Here's a little game to fill the idle moments during the holidays:

• Mottainai-1.0_OSX.zip (Mac only, sorry!)

See you next year!

Computational Geometry Sucks!

Computational Geometry is hard. Most of the examples out there are crap and the good stuff is without exception hard to understand.

You can usually whip up a 100 liner to solve a problems, if your input is cloud of random points. This is what pretty much all the Java code out there does, but the input data for your game is not a random point cloud!

I hate computation geometry, but yet it is so important! It drives me crazy.

I was recently looking for a robust 3D convex hull algorithm which would work for a couple of hundred points in realtime. That is, something sub 2.0 ms on a 2GHz Core Duo.

I wrote a couple of solutions myself, including one which was O(n^4) and surprisingly did not scale beyond 25 points. Finally I was hinted towards this patch for Bullet Physics, and it turned out to be a real gem!

It is fast, scales well (it's O(n log h)), and is robust too. My litmus test is a grid of 4x4x4 points. It passes that and even handles coplanar input. Pretty much all the Java code out there fails on that input.

So I took that patch, regexp'd it, copy pasted some Bullet code, deleted stuff I did not need, shuffled things around a bit, and made it output triangles and I'm finally a happy man!

Style vs. Technique

This is a very dear topic to me, I just wish I was able to output my through about it efficiently.

I recently posted a link to a paper and video in twitter:

Situation Agents: Agent-based Externalized Steering Logic

• http://www.cs.ucla.edu/~pfal/Petros_Faloutsos/Crowd_Simulation.html
• http://www.cs.ucla.edu/~mubbasir/pdfs/situation-agents-paper.pdf

I got a reply that the results are not very realistic. And it is very true, especially the formation examples look quite unrealistic indeed.

But compared to what? Some generic situation in real-life? Our generic assumption about how things should behave? Maybe you were in a similar situation yesterday and you comparing the video to that.

There was a one important lesson I learned from art school: when you critique someone's work, you better be able to explain your point of view. You have to define your point of view, your artistic vision and potentially references to existing methods.

In order to have a good critique over the above example both the presenter as well as the commenter needs to point out their artistic point of view. Otherwise the discussion is pointless.

More scientific way to justify your point of view is to hypothesize, collect data, build a model, and compare your method against it. This approach is well executed in the following research:

A Synthetic-Vision-Based Steering Approach for Crowd Simulation

• http://www.irisa.fr/bunraku/GENS/jpettre/

When the model is tuned based on the input data, the output looks and should look much like the data that was used to tune it.

My critique to the above method is that can it reproduce different kind of styles? For example if two actors would act out exaggerated situation where and a nerd and a bully avoid each other, could the method capture that style?

In my humble opinion in order to critique a technique you either have to have an artistic point of view (one that you can also explain to others) or if you compare things to realism, you better have good data! Otherwise the discussion will be just bike shedding.

Seeing potential of a method is not easy either. Ken Perlin showed an interesting picture pair during talk at Paris AI Conference this year. In one picture there was a raytraced marble sphere, picked from his original noise paper, on other picture there was a shot from a movie which had beautifully rendered stormy ocean, which was build using his noise function.

Examples are generic and try to show off the technicalities of the technique, but it takes an artistic vision to turn a technique into something worth watching.

Detour Return Codes Take 2

I just update the Detour status labels based on recent feedback. The code is in in R255. The return value is now bitfield instead of a single enum. This to pass both error messages as well as few bits of information about the quality of the result.

The high level statuses are DT_FAILURE, DT_SUCCESS, and DT_IN_PROGRESS. The rest of the bits are used to describe mode detail about the status. To test if a status is one of the above, you should use the helper functions dtStatusSucceed(), dtStatusFailed() or dtStatusInProgress().

Example:

dtStatus status = m_navQuery->init(m_navMesh, 2048);
if (dtStatusFailed(status))
 return false;

In many cases of success and failure, you can get one or more bits of extra information why things failed or if the quality of result is degraded. The detail flags are:

• DT_WRONG_MAGIC: the input data you passed had wrong magic number. In practice this means that you are trying deed bad data to Detour. Failure.
• DT_WRONG_VERSION: the input data is in different version than Detour expects. Failure.
• DT_OUT_OF_MEMORY: the operation could not allocate enough memory. Currently this applies to init methods. Failure.
• DT_INVALID_PARAM: one or more of the input parameters had invalid values. Usually this means that you passed a poly ref which is not valid. Failure.
• DT_BUFFER_TOO_SMALL: the buffer to store the result was too small. Success.
• DT_OUT_OF_NODES: query ran our of nodes during search. If this happens often, you should increase maxNodes. Success.
• DT_PARTIAL_RESULT: query did not reach the end location, returning best guess. Success.

In case a function call fails, it usually returns only one flag. If a function call succeeds, it may return multiple flags indicating the result quality. The flag DT_BUFFER_TOO_SMALL is also use store/restore tile state and in that case it is returned to describe why the function call failed.

Some more examples:

dtStatus status = m_navQuery->init(m_navMesh, 2048);
if (dtStatusFailed(status))
{
 if (dtStatusDetail(status, DT_OUT_OF_MEMORY))
  printf("Out of memory initializing navmesh query.\n");
 return false;
}

dtStatus status = m_navQuery->findPath(sref, eref, spos, epos, filter, polys, &npolys, MAX_POLYS);
if (dtStatusSucceed(status))
{
 if (dtStatusDetail(status, DT_BUFFER_TOO_SMALL))
  // The path result is longer than MAX_POLYS.
 if (dtStatusDetail(status, DT_PARTIAL_RESULT))
  // Could not reach end location, the path leads to a location near the end point.
}

Sundries - Visual Scripting

I found this old sketch of a visual language for AI behaviors while browsing through an old harddrive. I think it is from 2006 or 2007 or something. Few notes:

• Concurrency: tasks (blue stuff) can be run at parallel and a certain point of a task (percentage of completion, distance to end of path, etc) can trigger another parallel task.
• Variables: the usual flow diagrams break down when you have too many things to connect, solution? Use local variables!
• Ordered: the connections have order. This was important lesson learned from countless hours of debugging Crysis flowgraphs.

The arrows at the top of the tasks are execution points. When triggered, the task starting at that location will start executing.

There was also a syntax to define how the next tasks would have been triggered. In the above examples the next task is always triggered when the previous on is finished. I had an idea to also have some kind of notation to require all tasks to be finished before the next one was carried on.

The orange boxes are variables. Grey boxes are functions. Some functions take variables as input (could be stacked ala werkkzeug).

I think that "patrol point is not valid" should have a trigger line coming to it from the same bundle where the patrol point selection and restart is triggered (that eval would be 2 and restart would be 3). The grey text in the patrol box should actually read "Patrol(StartPoint)".

The overall design was much inspired by werkkzeug and PD.

Path Corridor Topology Optimization in Action

I just commited a change to the Crowd Manager which implements path corridor topology optimization (SVN R251).

In the above video, only the very first path is calculated using regular A* for all agents, after that the path end is adjusted by stretching the path corridor as I have explained earlier.

When the agents start to move, the path corridor is optimized as I explained in my previous blog post.

In the example the path topology optimization is done for only agent per update at most twice per second. Only 32 nodes are visited during the update. Search for optimizePathTopology in CrowdManager.cpp to see how it is implemented.

Feel free to try it our yourself!

Path Corridor Optimizations

Path corridor consists of a current start location, end location and list of polygons connecting the two. This is the structure which used at runtime to navigate from the current location to the end location. We can use A* or his bearded friends to find this path corridor in the first place.

When the agent wants to move, we first calculate the furthest visible corner along the corridor and move towards that point. As the agent moves we adjust the path corridor. If the agent moves from the current first polygon to the next on the corridor, the current first polygon is dropped and the corridor's length shrinks.

The same idea can be used to adjust the corridor even if the agent does not move towards the goal (i.e. is being pushed around by other agents). The corridor adjusts based on how the agent moves. Even despite the detours, we can always quickly query the next visible corner using the funnel algorithm and try to move towards it. Eventually we will reach the end location.

This is flexible and fast way to move the agent towards the end location. But there is room for improvement. There are several cases where the shape of the corridor may lead to visually poor results. For example, if the agent is following a target or it needs avoid other agents too much, the path can get tangled up. Often there would be a trivially shorter path to the goal only if we could adjust just few polygons in the corridor.

This kind of problems can be solved using two kinds of optimization methods: visibility optimizations and topology optimizations.

Visibility Optimizations

The idea of visibility optimizations is to try to alter the beginning of the path corridor so that we could take more direct route towards the next corner. This problem usually only occurs if there are vertices in the navmesh which do not belong to a border. In Recast & Detour this happens if you use tiled navmeshes.

If the extra corners are not removed, sometimes it looks like the agent is trying to avoid invisible obstacles or sometimes they are just small odd kinks in the road.

One way to optimize the beginning of the path is to do a walkability raycast from the current location to the corner which comes after the next corner. That is, try to shortcut the next corner.

Detour walkability raycast returns the list of polygons it visited during the trace and that data can be used to patch the beginning of the path. Note that the raycast is not used to optimize the string pulled path, but the path corridor. This is really important difference.

The visibility optimizations should be done as often as possible, potentially every update. If the optimization is not done often enough, you will get visible jerks in the agent motion. To keep the computation in bounds, you should limit the ray distance (something like 20-30 m is good range).

The walkability raycast works ok, but It would be interesting to try other methods too which might do better optimizations. One potential idea would be to treat the edges between the navmesh polygons as portals and use the well known portal visibility algorithm in 2D to try to optimize the path.

Topology Optimizations

If the agent follows a target, or if it is moving in a large crowd the topology of the path corridor can get tangled up, like in the above picture. The visibility optimization can only handle problems that are visible from the current location but there can be an obvious shortcut which needs a bit more reasoning.

One way to fix topology problems is replan the whole path, but this is very wasteful and the time it takes to complete an A* search is really unpredictable. At worst case when it cannot find the goal it will visit all your navigation polygons!

The topology problems that a human inspector would notice are usually quite local. Only if we could replan the first 20m of the path. Well, yes we can!

One way to efficiently implement path corridor topology optimization is to search towards the end locations using A*, but instead of doing the full search we limit the search to something like 30-50 nodes (step 1 in above picture). This makes sure that we can guarantee that the search returns in finite time.

When the search has been done, we start traversing the existing path corridor from the end (step 2 in above picture). As we move towards the start location, we check at every polygon if it was visited during the search. If that polygon was visited, we trace the graph back to the start and substitute the beginning of the corridor with the trace result.

Conclusion

There are two kinds of optimizations which can be used to optimize the path corridor. They make the visual appearance of the navigation more pleasing. Firstly, we can make sure that we try to aim as far as we can see by doing visibility optimization, and secondly we can periodically optimize the topology of the path so that the agent tries to move towards the goal without taking too obvious detour.

The intuition is that the visual optimization tries to optimize the very near term reactive plan, whilst the topology optimization tries to optimize the medium term plan. The reactive plan should be updated very often, but the mid term plan can be updated less frequently, say few times a second.

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.

Experimenting with ORCA

Ever since RVO2 library came out, I've been itching to dust off my old ORCA test and try to get it to work. I really like the simplicity of the method.

I don't have the required intuition to debug linear programming, so I opted to calculate the union of the constraints as polygon clipping instead. I start with a rectangle, which roughly describes all the admissible velocities, and chip away each of the constraints using poly-plane clipping algorithm in 2D. In above picture the result polygon is drawn in white.

As suggested in the RVO2 forums, in case the resulting polygon would be empty (no admissible velocities), I remove the constraints one at a time, starting from the furthest agent. You can see this effect in the above picture, the green constraints would make the polygon null, so it is discarded. This is simpler initial alternative to 3D linear programming.

While implementing the method I ran into quite a few problems. These can be due to my lack of understanding the method, or because my actual implementation differs somewhat from the RVO2 code.

Firstly, I'm visual person so I always need under-the-hood view before I can understand some method. There was quite a big leap from the agent position and velocity to the actual constraint plane. So I first spent some time trying to see where the planes come from.

Secondly, I have hard time understanding all the intrinsic details of optimal velocity, and I'm even more confused when I compare the paper vs. the library code.

When reading the paper I get the feeling that the planes should be recalculated if you choose another optimal velocity but the library does not do that. The lib calculates the planes once, as if optimal velocity would be current velocity and then uses linear programming to try to find solution to different optimal velocities.

I get super horrible feedback effect if I set optimal velocity to the current velocity, so I used desired velocity instead and things kinda work. Kinda.

Thirdly, I cannot see how the method is able to choose good constraint planes by selecting a single choice for each object. I hope I'm missing something big here.

For example, let's take a look at the picture at the top of this post. That green plane messes things up big time. Had the method chosen the other side of the obstacle, the case would have had good solution.

Even in slightly crowded scenes that kind of problems occur a lot. Many cases I traced through, calculating the constraint using optimal velocity of zero would have solved the problem. I could not figure out good rule when to choose which one of them. I tried some obvious ideas but there always was another case which failed after the change.

I would love to love the ORCA method, but I have had a lot of trouble getting it to work.

I have a hunch that the structure of the combined velocity obstacle plays big role in temporally coherent velocity selection. Fiorini & Shiller described the structure very well in their early papers, but I have not seem much research on that field ever since.

On Navigation Robustness

One important point of the Navigation Loop method is that the loop is robust. From one point of view, this is realized by making each successive step in the loop to produce more accurate solution. On the other hand, the robustness comes from the fact that system stays in control.

Steering velocity is passed for the local avoidance to not to produce velocity which will collide with others, after the final movement a collision detection is applied so that small errors can be corrected and finally the new location is ensured to be inside the navmesh so that the next iteration can work with solid data again.

Traditionally path following is implemented so that you first find spline (linear or curved) through the world and try to follow it. Two horrible things will happen with this method.

Don't Walk That Tight Rope

Following a spline iteratively will always result somewhat low pass filtered results. You will cut curners. There are several sources in the net to help you with that task, but regardless what you do, you will never be able to exactly follow that spline (unless you are just interpolating over it), which means that you will collide with something or get into areas where you cannot move away. This effect is further amplified if you use physics to move the NPC, since the navigation data and collision data never match exactly.

So the first source of problems comes with trying to follow the path and trying to detect when you are too far away from the path that you will need to replan the whole path. This method is usually really quick to get up and running, but the end result is either 90% success rate (we need at least 99.9%!) or horrible bowl of special case code spaghetti to capture fix all the known problem cases (most of which you will learn 1 week after you have shipped).

The lesson is that you should never ever ever try to follow a path as means of navigating through the world. Instead you should have more loose structure of the path (the path polygons) and find the next corner to steer to each update and adjust the path corridor as you move to next polygon. This way you never get out of the path and you always have correct direction to steer to regardless even if you veer of the ideal path.

Always On the Mesh

The second source of problems is that the NPC may get into location where it cannot reach the navmesh anymore. You should always constrain your NPCs to be inside navigation mesh when they are walking. The navigation mesh represents areas where the NPC can walk and stand with moderate effort. The input parameters for the mesh generation are adjusted so that this holds true [1].

You should have special case code to handle locations outside the navmesh like off-mesh connections (jump over things) or animations and actions around MGs or other entities. These actions should always enter/exit on navmesh.

When you keep the NPC inside the navmesh, you can always have good and valid data to use for pathfinding. Of course some sloppiness needs to be tolerated because of floating point accuracy.

If you don't keep the NPC inside the navmesh then you have similar problem as with trying to follow a spline. The two representations will get out of sync and you will spend a lot of time writing code to cope with it.

Physics... (sigh)

Robust navigation is not just "it kinda pulls this dude past this obstacle", it must pass the nastiest of the tests when the player sheds havoc on your NPCs.

The physics and navigation representation never match 100%. For this reason something that looks completely valid from navigation point if view may result dead lock collision with physics system.

So a lot of the problems comes from the fact that physics is always in control. If you want to have robust navigation it must be in control and instead you should treat physics system as a sensor for the NPC.

The physics should be used to plant the NPC firmly on ground, or you should use it to detect when someone is throwing a barrel at the NPC and blend to ragdoll, etc. There is nothing realistic or believable about things bouncing off an invisible capsule!

When you move your NPC, the navmesh boundary is the final hard constraint and is always satisfied. Before that you can have simple collision handling between the agents for cases where local avoidance fails (and it will, if not badly, you will get at least accuracy errors).

To sum it up, don't try to follow a tight rope, you will fail. Always keep the NPC on navmesh, or you will fail. Physics is good tool, but bad master.

I know removing the physics roundtrip will be hard to swallow, but give it a try! :)

_

[1] If the navmesh generator does not produce mesh for all the locations you wish to be navigable, then you need to change the params or add extra annotation to handle these locations. For example the NPC might be able to walk down certain steep slopes, but these may be rejected from the navmesh. It is not trivial to detect these areas as you would need to extract the direction the agent could move. Annotation and special navigation code is easier solution for this case.

My Summer of Code 2010

This where all the magic happened!

You may have noticed the increased traffic on the commits and the blog. But now Mikko's Summer of Code has come to an end. I used a few weeks of downtime between projects to flush my TODO queue. I'm starting a new project this week and I will be back to my 1 day a week schedule with RC&DT.

Here's some thoughts on what are likely to happen in near future.

Multi-Agent Navigation

I got the multi-agent navigation to much further state than I expected. The code is currently huge pile of spaghetti. The next step is put it all together. I have been trying to think about the API and it seems to be quite a big task. I think it is good that my progress is slowing down so that I can let things simmer in a bit.

If you have some thoughts how you would like to integrate the multi-agent navigation to your project, please let me know!

Would you like to use it as a component? Do you want a manager you can tick or do you prefer to do that yourself? Do you use physics for collision detection? Where in your agent update cycle you are planning to put the path following code? Any input is welcome. If you don't want to share the secrets here you can always send me email too.

Everyone is integrating path following slightly differently. I hope to support as many people as possible. On one extreme there are the folks who just would like to get plug'n'play, and on the other side are the folks who would like to get the max performance which means that I need to split the API so that you can tear everything apart as necessary.

My current idea is to roughly separate the code into roughly four pieces:

• mover
• steering
• obstacle avoidance
• collision detection

The mover takes care of handling path corridor and movement along navmesh surface. In theory you could use it to create NPCs or even player movement. It will also keep track if new path should be queried.

Steering is game and behavior specific so I think I will add some helper functions to the mover class which allows you to build your own. I will provide some examples how to do it too.

Obstacle avoidance will be separate class which can be used even without any of the mover stuff. Basically you feed in obstacles and the agent state (position, radius, velocity, desired velocity) and it will spit out new velocity which should result in less collisions than the desired one. The first implementation will be the sampled VO, I'm looking into adding ORCA stuff too later.

Collision detection will be responsible of finding the neighbors to avoid and to collide with. This is potentially something that your engine does already. I might include this only in the example code.

Many of the tasks required for multi-agent navigation are embarrassingly parallel (see all the for loops in the current CrowdManager::update()). My idea is to tailor the APIs so that when possible you just pass in the data that is absolutely necessary. For example the obstacle avoidance code will not figure out the neighbors itself, but you need to feed them.

I will create an example which can be used for learning and also something that can be integrated as is, for those who just like to get quick and dirty integration.

Detour Error Handling

There are some cases where Detour should be more verbose on error cases. My work on the multi-agent navigation has revealed some short comings in the error handling code too and the sliced pathfinder work surfaced some ideas too.

I'm planning to improve the Detour API at some point so that it will report errors better. The change will be most likely that every method will return a status instead. This allows me to report invalid input data and more elaborate reason why path finding may have failed or report that path finding succeed, but actually returned partial path. There are some discrepancies on the raycast() function return values too.

Temporary Obstacles

I got quite exited about the heightfield compression findings and got some really good feedback on it too. It is definitely something I wish to prototype more in detail.

This also ties into better Detour error handling. I will need to finally figure out how to handle interrupted and invalid paths. Detour will not replan automatically, but it will let you know what something went wrong or that something will go wrong in the future so that you can schedule new path query yourself.

RVO 2 Library

RVO2 Library has just been released. It uses optimal reciprocal collision avoidance (ORCA).

• http://gamma.cs.unc.edu/RVO2/

I have had tried to implement ORCA a couple of times before but did not succeed. It'll be interesting to compare my earlier attemps with the sources and give it another go. I did not quite get what they are doing in linearProgram3() with projLines stuff, though.

There is one comment in the examples, which I found particularly charming:

Perturb a little to avoid deadlocks due to perfect symmetry.

Handling Temporary Obstacles

I have been using some idle cycles every now and then to try to think about a nice method to update the navmesh without requiring to completely rasterize and rebuild a tile from scratch. This would be useful for obstacles, which may break and may be pushed around and usually only contribute blocking areas into the navmesh.

Cookie Cutter Obstacles

One method to do that is to punch holes in the navmesh using CSG. Some path finding middleware support that and some games shipped using it. So it definitely works, but I don't like the method.

Firstly, you have to work around the floating point accuracy, which is paramount pain. Secondly, it usually is too accurate, which means that you get some small polygons all over the place. Thirdly, it does not scale well when you have multiple overlapping obstacles. So it is an option, but very very low on my list of things to try.

Local Grid

Another option would be to use local grid and rasterize all the temporary obstacles into it and then use another simple pathfinder to find around the way.

The good thing about this method is that overlapping obstacles is not a performance issue anymore. Because grids often have lower resolution than actual world geometry, they tend to simplify the obstacle area too, so it solves the small triangle problem too.

The down side is that you have second representation of your world. The problem it creates is that what to do when the path is blocked? There is no way to reliably pass that data back to the navmesh and replan the path, as it would require to change the layout of the mesh. Simply blocking certain polygons temporarily does not fix it.

Recreate Piece of a Navmesh

Currently the way I prefer to handle dynamic obstacles is to recreate the tiles where an obstacle has changed. Tiling helps to limit the amount of work that needs to be done. While it works well in practice it is overkill for many situations, including the temporary obstacle case.

That has lead me to thinking that how much of the work that goes into rebuilding a tile could be cached?

In practice the answer is that at minimum you need to have the data that is stored in Recast compact heightfield to rebuild a tile and have the benefits of the grid. At the compact heightfield level each obstacle could be rasterized in the heightfield as specific area type and then the rest of the Recast pipeline would be run to obtain the final mesh for a tile.

There are some shortcuts that can be taken to make the rest of the Recast process quite a bit faster than usually. One optimization is to use monotone region building function. Another one is to use more loose parameters for detail mesh calculation. For small tiles, this can halve the build time which is spent after rasterization.

In practice it means, that if we could start from compact heighfield, we could rebuild a tile on 1 ms instead of 10 ms. And by using the simpler methods the work can by split into similar sized chunks so it is possible to handle the building over several frames.

But compact heightfield can be a lot of data which makes the idea impractical. Only if we could compress it...

Compressing 2.5D Heightfield Data

By inspecting the data stored in the compact heightfield, we can see that the data per span does not vary very much between neighbours. Also it happens to be stored in a way that helps usual compression algorithms to pack it well too.

The 2.5D heighfields in Recast are stored as columns stacked on top of each other. If there are multiple voxels on top of each other, they are stored as single span. This is often called run length encoding (RLE).

The spans in compact heightfield are stored in one flat array. In addition to that there is a grid of cells at XZ-plane, which stores index and span count for that column. So when you need to find all the spans at certain location, you first lookup the index to the large span array from the cell and loop through all the spans that belong to the column.

The layout is also awesome to store links to neighbours, you only need to store a small sub-index, which added to the index found from the neighbour cell to finally find the actualy span.

Because of the memory layout, all the parameters of spans can be easily stored in one contiguous array, which is good for compression since neighbour parameters are often the same. In practice only the span y and area type are needed to rebuild compact heightfield.

For the base grid, it is only necessary to store the span count per grid cell. The index can be recalculated by accumulating the counts.

The above picture shows 2.5D heightfield of size 208 x 503. The resulting compact heightfield data that is required by Recast to build the navmesh is 1662 kB.

When the data is stripped down to the minimum as explained above, the amount of data is 508 kB. Since the data is so similar it is only 29 kB after being compressed with zip! The height data should compress even better if delta encoding is added.

Conclusion

Using compressed compact heightfield could potentially be interesting solution to handle temporary obstacles. For small tiles, the rasterization can often take up to 90% of the total time required to build one tile worth of navmesh. The method would require extra data to be stored per tile, but the data should be manageable since it can be compressed by about 1:50.

Recast API Breakage Redux

I did some changes to the previous Recast API adjustments. The changes are not that big this time.

The first change you notice is that rcBuildContext is now called just rcContext. The second change you may notice that the time query functions are gone, and how there is startTimer()and stopTimer() instead. The third change is that you can disable the virtual function calls using a boolean flag if you want to.

These changes should make the rcContex simpler to implement and maintain.

Available in R206, the VC project is broken until I get back to my win machine again.

Path Following Performance pt. 2

Got the performance to quite constant sub 1 ms with adaptive sampling even in heavily crowded situations. The RVO samples (red) still dominate the performance. I think I'll stop here for a moment, remove a couple of quadratic loops, start figuring out how to package it better and open the flood gates for a couple of trillion bug reports.

That yellow spike is new path requests for all agents in a single frame. I'm quite happy about the Detour performance here. It stays about the same on larger meshes too. I'm particularly happy that I could keep the raycast there to optimize paths a little each update.

Path Following Performance

I started working a bit on the path following again. Naming things better and moving stuff around. I also added a simple profiler to the stuff too as seen on above picture. The case shows 25 agents moving in a quite simple level.

The bad news is that the performance is bad! The good news is that it's ok.

There are two times tracked in the above picture. The red-ish line shows how much time is spent in the brute force RVO sampling, and the lime-ish line shows the time taken by the total navigation loop calculation.

My goal is to get this case to around 0.5 ms, and I think it is doable.

Visibility Optimized Graph Experiment

I blogged earlier about A* node placement. I had the change to try out the visibility optimized node placement today. First impression, not impressed.

It generates quite aggressively goal directed paths, much like if you over estimate your heuristic (or was it vice verse). The final segment to the goal is always perfect, though.

In case someone wants to give it a try, here's the code I used:

static int isectSegSeg(const float* ap, const float* aq,
                      const float* bp, const float* bq,
                      float& s, float& t)
{
   float u[3], v[3], w[3];
   dtVsub(u,aq,ap);
   dtVsub(v,bq,bp);
   dtVsub(w,ap,bp);
   float d = dtVperp2D(u,v);
   if (fabsf(d) < 1e-6f) return 0;
   d = 1.0f/d;
   s = dtVperp2D(v,w) * d;
//    if (s < 0 || s > 1) return 0;
   t = dtVperp2D(u,w) * d;
   if (t < 0 || t > 1) return 0;
   return 1;
}

...

if (neighbourNode->flags == 0)
{
   float sa[3], sb[3];
   getPortalPoints(bestRef, bestPoly, bestTile,
                   neighbourRef, neighbourPoly, neighbourTile,
                   sa, sb);
   float s,t = 0.5f;
   if (!isectSegSeg(bestNode->pos,endPos, sa,sb, s, t))
       dtDistancePtSegSqr2D(endPos, sa,sb, t);
   t = dtClamp(t, 0.1f, 0.9f);
   dtVlerp(neighbourNode->pos, sa,sb, t);
}

Custom Detour Query Filters

I just committed the change for custom query filters and slight optimisation for the A* (SVN R200).

Custom Query Filters

I kept the earlier default behavior of the filter, so the API and functionality change is really small. Instead of calling dtNavMeshQuery.setAreaCost() you now call dtQueryFilter.setAreaCost().

There was quite some discussion if the passFilter() and getCost() should be virtual function calls or not. For people working on PowerPC processors it can be quite a big deal as both the functions are called per node during A*. On PC, the perfomance loss of using virtual function is not super bad (about 5-10%) compared to the flexibility it gives.

There is a define in the dtNavMeshQuery.h called DT_VIRTUAL_QUERYFILTER. If the define is set, the above mentioned functions are declared virtual and you can override them. In other case, the default implementations are inlined which should lead maximum performance. This was the best compromise I could think of.

Your custom query filter should be as fast as possible, as it can easily dominate the A* performance. If you want to query an agent flag, cache it locally inside the custom filter before you call pathFind(). If you need to do physics queries, try to cache them too before hand too. Use as little extra data as possible.

A* Optimization

While I was testing the impact of the virtual calls I noticed that the edge midpoint calculations were taking quite substantial time, so I tried caching the results. I earlier thought that having smaller node size and recalculating the edges on the fly would be more efficient than storing the node positions. It doubles the node struct size and all.

It turns out I was wrong (may vary per platform). Anyways, the node position is now stored for each node. This also opens up possibilities to try different node calculation methods. Caching the node positions resulted about 15% speed improvement.

This is the piece of code that calculates the node position:

            // If the node is visited the first time, calculate node position.
           if (neighbourNode->flags == 0)
           {
               getEdgeMidPoint(bestRef, bestPoly, bestTile,
                               neighbourRef, neighbourPoly, neighbourTile,
                               neighbourNode->pos);
           }

Be aware not to create neighbour nodes on top of each other (that is, zero length connections). For example if you want to place that new node so that it is the nearest point on the edge from parent node, then you should clamp the edge 't' to lie between for example 0.001 and 0.99, or something similar. You can use getPortalPoints() to query the segment which connects best and neighbour.

I also added a debug view mode which displays the nodes and link to their parents. This should help to see how well the node placement might work.

Navmesh Node Locations

I have previously calculated the A* node locations on the fly to save memory. That is when I expand to neighbour polygons, I calculate the edge mid location on the fly. While profiling the filter change proposal, I also tested caching the A* nodes locations. This gave me the benefit to also being able to draw them.

There was one particular location in one of my test levels which always bothered me. I had plotted it out few times in Photoshop, but now I can finally see what was going on.

The above picture also illustrates the reason why navmeshes sometimes produce unoptimal paths. The A* is actually ran on that "skeleton". The problems pretty much always occur where small and large polygon are next to each other.

To answer the question in the picture. That detour is selected because the route along the skeleton is shorter than crossing through that large polygon. When you see the skeleton it is easy to understand, but when it is not visible, it looks plain odd.

Proposal for Custom Cost and Polygon Filter for Detour

I have been recently discussing a potential solution to issues 47 and 103 with Neil Armstrong. That is, how to allow the user to pass custom cost values for A*. In some cases the different travel costs could be based on NPC type, or maybe even some local context like trying to avoid the polygon where the target is.

I think this kind of functionality is really important to achieve correct gameplay, and usually there is no one solution that fits all.

I'm proposing a change to the dtQueryFilter which would allow custom logic on polygon filtering as well as custom cost for searches. Here's the interface and the current implementation as an example:

struct dtQueryFilter
{
   dtQueryFilter() :
       includeFlags(0xffff),
       excludeFlags(0) {}
  
   virtual bool passFilter(const dtPolyRef ref,
                           const dtMeshTile* tile,
                           const dtPoly* poly) const
   {
       return (poly->flags & includeFlags) != 0 &&
              (poly->flags & excludeFlags) == 0;
   }
  
   virtual float getCost(const float* pa, const float* pb,
                         const dtPolyRef prevRef,
                         const dtMeshTile* prevTile,
                         const dtPoly* prevPoly,
                         const dtPolyRef curRef,
                         const dtMeshTile* curTile,
                         const dtPoly* curPoly) const
   {
       return dtVdist(pa, pb) * areaCost[curPoly->area];
   }
  
   float areaCost[DT_MAX_AREAS];

   unsigned short includeFlags;
   unsigned short excludeFlags;
};

The input to the cost function is a line segment from pa to pb which travels along curPoly and the previous and next polygons.

I'm not big fan of interfaces and I was worried how much overhead it would add. In my test case the path queries vary from 0.030 ms to 0.135 ms (there are some small fluctuations from run to run). When the passFilter() is virtual function instead of inlined function it adds 0.010 ms to 0.020 ms per path query. I think the interface is worth it.

So this post is request for comments. Unless anyone disagrees or proposes better solution, I will check in the changes.

[EDIT] I did few more tests and the above did not actually include the cost as virtual call, only the polygon filter as virtual function call. In total the virtual function call version is something around 5-10% slower.

Recast API Breakage

I just committed a change (SVN R197 R199) which adds rcBuildContext, and breaks that API. Sorry for the trouble! I hope you welcome the new changes.

The newly added rcBuildContext abstracts the timer, logging and build time reporting. I'm planning to add more error and warning handling support via that interface in the future, for example drawing and high-lighting bad geometry.

Majority of the Recast functions now expect a valid pointer to rcBuildContext as first parameter. Allocators and a couple of really simple utility functions are an excetion. If you don't care about build timing or logging, you can just pass a pointer to an instance of the default implementation of rcBuildContext. Like this:

rcBuildContext dummy;

...

rcErodeWalkableArea(&dummy, m_cfg.walkableRadius, *m_chf);

There is an example implementation in the SampleInterfaces.h/cpp. I also moved the other example implementations of interfaces there (FileIO, DebugDrawGL).

The files RecastTimer.h/cpp and RecastLog.h/cpp were removed in the process. I added RecastAssert.h which is used in some places to check that validity of the passed parameter (more validation later).

I wish a smooth migration! Let me know if there is something I overlooked.

Off to update the Win32 project. [EDIT] updated.

Detour Sliced Path Find

Well, while I was in teh mood, I though I'd give it a go.

I just checked in (SVN R196) some extra methods for dtNavMeshQuery which implements sliced path finding. It works as follows:

// Request
m_pathFindState = m_navQuery->initSlicedFindPath(m_startRef, m_endRef, m_spos, m_epos, &m_filter);

...

// On update
if (m_pathFindState == DT_QUERY_RUNNING)
    m_pathFindState = m_navQuery->updateSlicedFindPath(maxIter);

if (m_pathFindState == DT_QUERY_READY)
    m_npolys = m_navQuery->finalizeSlicedFindPath(m_polys, MAX_POLYS);

There is new tool called "Pathfind Sliced" which allows you to see it in action. The tool advances the search one node at a time so you can see how the closed list is update in realtime.

The actual path find is a tiny little slower than the findPath() because it does more validation. It should catch the case that some of the data is being removed while the query is in flight, and if the update encounters invalid data it will return DT_QUERY_FAILED.

If the removed data was already in the closed list of the search, the path result will contain invalid data. The rest of the API can handle that, but I recommend restarting all currently running path requests after you have added or removed a tile.

Detour Navmesh Data and Queries Separated

I just checked in code (SVN R194) which separates the navmesh data from the queries. In the process I also cleaned up how the data is accessed via dtNavMesh.

API Changes

In a nutshell this means that instead of using dtNavMesh, you use dtNavMeshQuery, except when you initialize the data of course. That is pretty much the only change if you are using Detour in single threaded system.

All the query methods have been moved to dtNavMeshQuery. The dtNavMesh class now only has methods to add, remove or change the data.

I removed bunch of getters. Now the right way to access the data pointed by dtPolyRef is:

bool getTileAndPolyByRef(const dtPolyRef ref, const dtMeshTile** tile, const dtPoly** poly) const;

It takes polygon ref as input, and stores pointer to tile and polygon as output. The function returns false if the poly ref is not valid.

Parallel Stuff

The new change allows you to better control the memory access of Detour for multi-threaded systems. The navigation mesh data stored in dtNavMesh is considered read-only by the dtNavMeshQuery. This also allows multiple dtNavMeshQueries to work on the same data. If you organize your data modifications and queries right, there is no need for locks.

The basic outline of multi-threaded use of Detour is as outline by Bjoern in [1]:

1. Update the navigation mesh (set flags, add or remove tiles)
2. Collect new pathfinding requests or pathfinding-change requests. Requests are deferred and not processed when posting them.
3. Process all pathfinding requests.
4. Make pathfinding results available.
5. Clear out all closed pathfinding requests and prepare for the next main loop cycle.
6. Back to stage 1.

I recommend reading Bjoern's post if you are interested in parallelizing your path finder. Also, any feedback is welcome. I will not be providing task scheduler, though, no point asking for it :)

So this is the first step towards more parallel Detour. The big task yet to tackle is to make all the queries to finish in more predictable time. The findPath() is really unpredictable in its' current form.

There are two options to improve that: 1) slice it, 2) add hierarchy. The final choice might be both.

Slicing means that only a set number of nodes are visited by the A* every update. It is simple to implement, but since the data can change between the updates, there needs to be much more bookkeeping in the process. Also, slicing means that the dtNavMeshQuery will store an intermediate state. That is, it would not be possible to run other query methods between the path find iterations, as they might mess up the open and closed lists.

I think in the long run the hierarchy is the way to go, but it needs new data structures and all sorts of things to be prototyped before it is ready to go in.

As an intermediate step, I'm probably going to implement iterative findPath() at some point.

__

[1] Parallel Detour navigation mesh

Some Recast & Detour Projects

The image is composed of a screen shot from the game Kingdoms of Amalur: Reckonin, GSoC10 projects for CrystalSpace and Blender.

Recast & Detour has seen quite nice adaptation during the past year. During the Paris Game AI Conference I run out of fingers to count the AAA projects currently in production which are using some part of Recast and Detour. In addition to that looks like there are countless indie, open source or hobby projects which I'm totally unaware of too.

Some projects have ported the code to different platforms, some have made quite heavy modifications to add features needed specifically for their game, and some are just using some parts of the code. It's awesome that Recast and Detour are being put in use! This also means that quite a few bugs have been reported and fixed too.

Here's some recent projects I'd like to highlight (if you like to share yours, drop me a line or comment below):

Kingdoms of Amalur: Reckoning
I'm glad that I'm allowed to share that up coming game Kingdoms of Amalur: Reckoning by Big Huge Games is using Recast and Detour.

Google Summer of Code 2010
Thanks to Nick and Leonardo, Blender Game Engine and CrystalSpace both leveled up on pathfinding this summer.

I'm thankful to all the people who have sent bug reports, fixes, improvements, suggestions or challenged me. It has made the toolkit so much better!

Heads Up, API Changes Coming Soon

I try to get two API breaking changes done this week.

1) Recast Context: This change will add additional parameter to most of the recast calls. I have yet to decide if the parameter will be the first or last. The idea behind this change is to remove platform dependancy of error/warning logging, timer and profiling code from Recast. See:

• Issue 67
• Issue 77

2) dtNavMesh & dtNavMeshQuery: This change will allow multiple simultaneous navmesh queries to happen at the same time. Basically it will strip dtNavMesh to just the data management, and add new class which has all the query functions. This makes Detour more concurrency friendly. See:

• Issue 99
• Parallel Detour navigation mesh queries

I will make separate posts describing the changes once I get things checked in.

Some More Movement Progress

Since last time, I implemented smooth steering, drunken movement style and sampled velocity obstacles.

The features are coming together, but the code is still huge pile of mess. I checked in first version (R193) so that the change list does not become too big.

When using tiled navmeshes and many agents, I got quite a bit of problems with agents trying to move backwards to catch up with their path. This happens mostly around the vertices which are at tile corners.

For the time being, I added that raycast trick which tries to optimize the path corridor by checking if there is line of sight from the current location to the corner after the next corner. If so, then the beginning of the path is patched to use the results from the raycast.

The performance is still realtime (it chokes when you have large group next to each other), but I bet it is actually really horrible. Once I get the structure of the code better, I'll start looking at the optimizations.

Oh, it moves!

The first test of a couple of agents moving around in a test level, yay!

I have implemented the navigation-loop stuff, simple steering, simple dynamic constraint, and simple collision handling. I need to rethink the way stuff is organized so that it is easier to grab the necessary code to your own projects.

It's always so amazing when it works the first time, even if it just barely does.

Detour Agent Movement Progress

I'm moving forward with the agent movement code for Detour. Today I added a couple of functions to Detour help me realize the goal. Check NavMeshTesterTool.cpp how to use the new functionality.

• dtNavMesh.moveAlongSurface() - This function tries to move an agent from start position to target position along the navigation mesh and constraints the position to be inside the navigation mesh at all times. The function is Detour implementation of the algorithm I explained in a previous post. In the process I removed the old moveAlongPathCorridor(), which supported only subset of the functionality anyways.

• dtNavMesh.findLocalNeighbourhood() - This function finds non-overlapping (in 2D) neighbourhood around a specified point. It is useful for local navigation. I have explained the algorithm earlier too.

• dtNavMesh.getPolyWallSegments() - This functions returns wall segments of a specified navmesh polygon. In conjunction with findLocalNeighbourhood() it can be used to generate 2D collision segments for local obstacle avoidance.

The image at the top of the post shows local neighbourhood segments queried using the new functions.

All the above functions assume that they operate on really small set of polygons. To achieve a bit better cache coherence, I added another tiny node pool, which currently only contains 64 nodes. The aim was to improve cache coherence. The node pool uses hash table to lookup nodes based on ID. When dealing with small number of nodes this actually slows things down because of the random access through the hash table.

Additionally, instead of using priority queue, the above functions use fixed size small stack and breath first search. The random access of the navmesh polygons is quite cache pooper already, but the above gives around 30-50% speed up compared to using the existing p-queue and larger node pool.

I'm planning to spend some more time this week in the agent movement stuff. The above functions are bound to change as I try to find my way through the implementation details.