Noodle Soup Considered Harmful

I just saw a report of the enchangements they are planning for Blender 2.5. One of the enchangements was a node graph to create game logic in Blender Game Engine. While the proposal is definitely and improvement over what they have in there, I think in general boxes and arrows are super horrible way to create game logic. Let me elaborate.

This idea has been bubling under for quite a few years now. I've been in two projects where the game logic has been build using some sort of flow graph. While it is intuitive model to create something a bit more complicated than when this do that, the final noodle soups look really horrible and are impossible for anyone to debug.

I have been trying to put the frustration of using the boxes-and-arrows editors into words, abd finally when I read a book called The Back of the Napkin, I realised what was the problem. The problem is that the designers are forced to answer all the questions with one answer.

The Back of the Napkin is about visual problem solving. One of its' ideas is that certain types of pictures answer certain types of questions the best. If the only means to create game mechanics is flowgraphs, then the designer is most of hte time answering to question How. If your level editor also supports some sort of timelines, you may be able to answer the When question too. Trigger volumes give opportunities to asnwer few where questions too.

In all system I've seen so far all these questions are answered using separate tools. This breaks the big picture. You do something in timeline editor and then something somewhere else, even if technically you could be editing the game in one unified view, zoom in when necessary, and build the best picture (and representation) to describe the required task.

Mashing up these different representations is really important to let the designers to get their work done. Trapcode Soundkeys is good example of such mash up. It kind of is against all programmers reason. Draw boxes to get output of an audio analyzer? That's a lot of bullnoodle right there! But it works, its intuitive and you immediate get it. It answer the the questions where and how much really well and you can adjust it easily based on what you see coming in.

That is why the idea logic blocks and flowgraphs as main means of gameplay logic must die. Creating gameplay logic is not about logic only, it is about answering complex questions with understandable "pictures"!

P.S. Yes, the MAX/MSP/PD crowd gets some of these things right, but not all.

Making Velocity Selection More Stable

I have done a couple of tests the get my velocity obstacle prototype to reduce the flicker in the velocity selection. Here's a couple of things that seem to work well.

1. Iterations: Just like you can improve collision detection by iterations, you can help the velocity selection with iterations too. By adjusting the sensed velocity slowly towards the selected velocity allows the other agents to react to the gradual change. Even after this change I often get jitter when two agents are about to start avoiding each other.
   
2. Samples Selection: I originally used the sample selection presented in HRVO code, but I noticed that I get more stable results if I just use the samples at the max velocity circle. This sometimes results full stops, but it might not be a bad solution at all. It should be possible to use a bit of higher level logic, which could choose between several states based on how crowded the situation is. This should help the animation play too.
   
3. Finite Time Threshold: Truncating the tip of the VO cone helps certain situations a lot, especially approaching to the goal location. There seems to be some correlation between how well the avoidance works versus how far the time threshold is, but it varies quite a lot from situation to situation. I think it is possible to adjust the threshold and get better results.
   
4. Velocity Obstacle Shape: The shape of the velocity cone has big impact on how smooth the velocity selection is. It is a no-brainer but it definitely was not the first thing in my list to try to get the system running smoother. Making the tip of the truncated cone more sharp helps a lot the first contact velocity selection (the problem that was unsolved by the iterations).
   

I think my further prototyping will concentrate on investigating how the shape of the velocity obstacle affects the avoidance. For example what happens if the shape of the VO is more like a parabola, or what if it is more like a trumpet. Another thing to prototype is how different avoidance region types affect the movement.

I also did a quick prototype of the directive circle approach based on this paper: Robot Motion Planning in Dynamic Environments with Moving Obstacles and Target. It uses similar max velocity selection method which I found more stable and has interesting trick to combine the VOs. Sampling artifacts aside, it seems to have some problems when approaching the goal location. I will test it a little more. The way the obstacles are combined in that approach allows me to test if adding more clearance might help the steering too.

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.