Velocity Obstacle Prototype

I made a quick velocity obstacle prototype last night. Above is video shows of some example scenarios.

I used similar velocity sampling and side bias in HRVO. It is cool how some test cases result almost symmetrical results. The last bit in the video uses more random start locations and parameters which makes the movement more random too.

I'll release the sources once I get it a bit more cleaned up.

In order to get smooth results, the prototype clamps the max acceleration (which is the reason why the agents sometimes collide) and also slightly smooths out the perceived velocity which is used to calculate the VOs.

The test cases do not exhibit too much flickering in the velocity selection, but I think it is a problem. I will do a couple of other protos to see if there could be simple way to make more coherent velocity selection with some simple extra logic.

A Random Thought to Extend VOs to Gameplay Animations

Whilst pondering LogicalError's question to my previous post and sipping that second cup of coffee this morning, I got a pretty interesting idea.

One thing that adds a lot of realism to NPC locomotion animation and can be quite frustrating to implement is something that is usually called as idle-to-move and move-to-idle animations. The idea is that when you start moving, you have special kind of animations which are played before the locomotion animations kick in. This allows the animators to create cool animations which can do turns and have anticipation in them.

The usual implementation problem is: how to make sure that those animations can be played so that the AI is moving in right direction and doesn't bump into things? I've seen all kinds of solutions to this, ranging from just checks is the target point is in navigable idea, to batch of raycasts to iterative collision sweeps.

Navigation meshes will help quite a bit in that process, making the line checks cheaper. The problem is that that check can be too exact. What if you adjusted your target just by 0.745 degrees and you would be able to do your nice animation? Some more random samples? An even harder case is those other potentially moving agents. Usually the grand solution is postponed until it is time to ship the game and the feature will drop into the cut-features list.

The idea I got this morning was that, if the trajectory of the animation can be thought to be relatively straight, we could actually use velocity obstacles validate potential directions and lengths of animations and choose one that fits the best.

The velocity obstacles can be scaled to take the maximum time into account. If the max time is infinity, the VO will look like cone, but as the time horizon is scaled down, the tip will be more rounded and will move further away from the apex (FOVT). You can check more details in the Clear Path paper. This is useful if you need to calculate collision free movement for certain duration of time.

I assume that the multiple VO contains all nearby moving agents as well as solid navmesh edges as obstacles in the follow paragraphs.

So based on the animation, we would calculate how long it takes and based on the end location we could calculate the velocity during the animation. Then we could calculate the multiple velocity obstacle with max time set to the length of the animation and try to find a direction which is closest to the direction we would wish to move and which has exactly the same velocity as we are requesting.

In practice this means that if the target velocity is inside the MVO, then we would pick a point which is at the intersection of the VO edges and a circle which radius is the length of our velocity. Voila, problem solved!

Move-to-idles are usually even harder since we need to hit a point certain distance away from the target we want to reach. Potentially it might be possible to use VOs for that too. An idea could be to place the agent at the target location and maybe inverse all the velocities of the other agents or something weird like that to be able to project set of points which could be available to arrive to the target obstruction free. Or you could just trigger move-to-idle if at certain distance and the VO tells you that the path is clear for the duration of the animation.

Given the idle-to-move idea, of course nothing prevents you to extend that idea for stuff like jumps and rolls and other gameplay animations.

The idea is a bit sketchy still, but I see a certain potential to it. Let's use VOs to solve all our problems! ;)

Choosing the Right Velocity

I browsed through the RVO library code while checking the differences that HRVO added to it and I noticed that they smooth out the velocity quite a lot. I have to comb through the literature again to see if someone has mentioned anything about it. I remember seeing a mention in some paper that they assume that the velocities are valid at least a certain amount of time.

HRVO velocity selection is pretty nice and simple. Looks a lot like the ST (strategy) from Fiorinis paper. Basically it generates potential sample points at:

1. all intersection points of the velocity obstacles
2. all the intersection points of the velocity obstacle edges and the circle which has radius of max speed
3. plus the desired velocity projected pass apex of a VO (if I understood that bit of the code correctly).

Next all the points are validated, so that they lie out side the multiple velocity obstacle. And the sample point that is closest to the preferred velocity is chosen.

The above image shows a scenario of sample points. The valid sample points are blue and invalid red-ish.

A critical point is what happens after that. Instead of applying the whole velocity to steer the agent, they clamp the delta from current velocity to the new velocity by max acceleration. Sounds like the likely thing to do, but I did not expect it to be such dominating factor of making velocity obstacles to work. Games often fiddle with the velocity directly. It could be that I was making false assumptions.

I have to give the RVO library another spin and see how much the smoothing actually affects the results.

Not Bumping Into Things pt.2

I stumbled upon this paper again yesterday:

The Obstacle-Restriction Method (ORM) for Robot Obstacle Avoidance in Difficult Environments

I like how they form sub-goals to overcome the obstacles. I think that is what I meant when I mentioned the coherent silhouettes in my previous post.

So my gut feeling is that coherent sub-goals is the key to get VOs a notch more reliable. Let's see if I can squeeze in some prototyping time later this week to prove my point :)

I think this sort of thinking is generally really good in game AI. If something is way too complicated to tackle with one system, or too flickery, make it hierarchical. If there are some decision that can be made a lower pace, do that, and feed the results to the next system so that it has easier time to solve its' sub-problem.

Not Bumping Into Things

Usually when I do research to solve some problem, I get fond of some particular method, try it out, get disappointed because it did not quite solve all my cases, then I try to track back towards the root of the idea to try to figure out what might have been the original motivation behind the solution and try to find a better suiting method from there.

My relationship with velocity obstacles has reached the point that I have gotten a bit disappointed with the solution. I have a feeling it has gotten certain things right, but it does not quite deliver.

It looks like the basic idea has been invented in the literature over and over again. For example one of my Google searches led me back to the old Craig Raynolds (Mr. Boids) paper from SIGGRAPH 88 called: Not Bumping Into Things.

I must have read that paper numerous times, but it did not strike me until today that it is actually describing velocity obstacles. The left side of the picture at to top of the post is from Raynold's paper, and the scribble right to it is my drawing from another angle.

I also found Fiorini's disseration, Robot Motion Planning in Dynamic Environments, which goes a bit more into certain details as well as list of references, which is missing from the paper that is usually available on the net. I wonder if his website along with complete list of publications is available somewhere? The one at NASA does not respond anymore.

One reason which made me revisit Fiorini's work is that unlike many more recent papers he tries to build meaning to the different safe velocity areas. One thing I noticed while testing VOs is that it is really easy to get a lot of noise in the input data, that is the cones jump around quite a bit, and that seems to be the greatest reason for any sort of oscillation problems. Shit in shit out, surprise, suprise!

Just take a look at this youtube video. The flashing red rectangle at top right corner is the velocity obstacles of the agent. I have witnessed similar behavior in my tests. Also, because of the feedback nature of the system once you get noise, it will amplify. One way to get rid of that (and as a side effect, inject a horde of other problems) is to either lowpass filter the velocity that is passed to the VO calculation or, lowpass the change in velocity. RVOs is kinda-sorta doing that, by adjusting the velocity towards the safe velocity just by a fraction.

So my gut feeling is that it is possible to build better method to choose good safe velocity by analyzing the arrange of the VO structure. I also think it is possible have better temporal behavior using similar tricks as in Coherent Stylized Silhouettes. The better temporal behavior should fix the usual pitfalls of VOs such as oscillations and choosing side to pass and still keep the system responsive.

Recast Detail Mesh Fixes

I just update the detail mesh generation code in SVN, which should improve the possible bad cases of the detail mesh generation.

One case where the detail mesh generation failed previously was the Delaunay triangulation which is used to generate the triangulation of per polygon detail surface mesh. This should be now fixed.

Next time around I will design a system which will dodge any kind of triangulation.

The algorithm is a little slower than the previous one and has worse big O behavior too. So large areas will take longer time to compute. If you have really horrible performance, I suggest using the tiled mesh generation so that larger polys will be split because of the tiling.

Another case where the detail polymesh was sometimes bugging out was how the height samples were picked from the voxelized representation. This should be improved now a bit, but I was not able to create a simple fix for the case where radius is zero. It is surprisingly complicated task to gather all the height samples which fall under a polygon. Most of the time it works ok, but some corner cases are just nightmare to get right.

So, if you have had problems with the detail meshes, grab the latest source from the SVN and give it a go.

[EDIT] I also added few convenience versions of rcRasterizeTriangles. One which accepts indices as unsigned shorts and another which can be used to rasterize non-indexed meshes.

Delaunay Triangulations

I have a love-hate relationship to all kinds of triangulations. They are super useful tools for many problems, but at the same time they are super annoying to get robust. I have been pounding my head to the wall trying to get one Delaunay triangulator to work properly.

Bourke's code is broadly used and seems quite robust too, but it fails to deliver one feature, convex hull, which is really important for my use. This seems to be common problem with Delaunay triangulators which rely on super triangle as the initial state of the triangulator.

After browsing through countless of other implementations and papers I finally found a O(n^2) algorithm last night, which seems to suit my need very well (I'm talking about the O(N^2) algorithm of the Java applet). I'm not sure which algorithm it is, it does not look like any of the usual suspects. But it does not require super triangle, and there is a case which handles the hull too. Even better, the algorithm behaves well even if manually set the hull edges myself. And finally as an added bonus, the idea of the algorithm is easy to understand visually, hence, I'm able to debug it myself too when I run into problems with it again.

Most (if not all) of the existing Delaunay triangulation implementations I could find out there fail sooner or later if you have points in your input data which are along the same line. That is a condition which majority of my input points satisfies.

I'm yet to do full set of test, but so far it looks good. The Java implementation has a couple of bugs in it, especially how it handles face labels.

Looks like I can finally move the detail mesh generation off the TODO list...

[EDIT] The algorithm in question seems to be a gift wrapping variant of Delaunay triangulation. See A Comparison of Sequential Delaunay Triangulation Algorithms, the papers that paper refers to seem to be pretty hard to find.

Blast from the Past pt. 2

I was browsing my old hard drive last night while trying to find some old material in preparation for a lecture in a local game dev school. I found a couple of good docs I've written in 2006, which I thought would be worth sharing. The grammar in the docs is the same awful you are used when reading this blog.

Moppi Flower Explained
During the years, quite a few people have begged the source code for our demo from BP'04. Instead of sharing the code, I thought it was better to share the knowledge.

Proto Watch
I got a nice and shiny wrist watch for Christmas Present in 2006. It had the most horrible UI ever! Since I did not have internet at home during the Christmas breaks since my room mate took the ADSL modem with him, I thought I'll try to see if I can figure out a better UI for a wrist watch.

For the sake of proving my point, I also wrote a simple prototype of the concept. All the functionality was written in C using only unsigned bytes. I wanted to implement the using a micro-controller too, but then the company I was working for at the time decided it was time for yet another crunch. So we crunched instead.

Blast from the Past

I just found this nice repository of old from from International Joint Conference on Artificial Intelligence. Lots of good stuff all the way from 1969.

http://dli.iiit.ac.in/ijcai/


One of my favorite findings was this paper from 1989 (If not mistake, the classic paper on velocity obstacles was published a decade later):

A Maneuvering-Board Approach to Path Planning with Moving Obstacles
Lou Tychonievich, David Zaret, John Mantegna, Robert Evans, Eric Muehle and Scott Martin


The year 1989 was like 20 years ago and yet we manage to produce games where NPCs have trouble avoiding walls and other kinds of minor things. So nice we have Google nowadays.

One quite important trick present in that '89 paper, that is missing from the Fiorini paper (IIRC) is the cone truncation. Applying the truncation helps a lot in many practical cases. Especially when trying to reach your final destination. Gladly it is well represented in Reciprocal n-body Collision Avoidance.

Status Update

I decided to put the area stuff on hold for a while. The update was becoming too heavy, and I need to revise my plan of attack, and probably just simplify few things too.

I'm thinking about dropping the statNavMesh and just keeping the tileNavMesh and add helper functions to make the use similar as using the statmesh. It is already quite tedious to keep different generation processes as well as runtimes up to date when a new feature is added. In the same vain, I was thinking about to only use the monotone area partitioning. As it is way simpler than the watershed partitioning code, it is much easier to add new features to it, such as making it aware of the areas.

The current SVN version has several fixes which should make Recast to compile on Linux and 64bit systems. There's a couple of good bug fixes there too, which were kindly pointed to me by August Gustavsson. One was in the tile navmesh path finder and another was crash in the border vertex remove process.

The detail mesh has raised its hairy head again. The Delaunay triangulation algorithm I used to generate the triangles for the detail mesh does not always create a mesh which includes the convex hull of the points. Some of the Delaunay triangulators I have used in the past do that, though. I have tried a couple of alternative methods, but the ones which create the necessary convex hull usually create extra vertices along the tesselated edges or they crash in some sliver triangles. Do I just hate triangulations.

I will try to see if I can hack some sort of constraining code for the outer edges by flipping few triangles around after the triangulation so that removing the super triangle will not eat the useful triangles away.

I will fix the detail mesh edge vertex explosion on radius zero, too.