On Writing

The lack of the updates on the blog recently has been mostly due because I've been writing my Game AI Conference presentation. I have done tons of research and prototyping the past 9 months, and now it has been time to draw conclusions and somehow wrap things up.

Whilst doing so, I have tried a couple of new work habits too. I'm one of those people who has a bit hard time concentrating on writing. The words just don't make sense to me. Heck, I did not even pass my A-levels in Finnish language.

I think it is mostly dyslexia, I'm one of those people who read one letter at a time, getting stuck in the curves of the letters and wander off to wonderland–unless you go and scramble all the letters the words. When I first read about it, it was a post at Slashdot, and I got scared because I suddenly read one story so fast.

A Thousand Word Head-start

Over the years one way to escape that has been to first draw a picture or diagram about the stuff I'm about to write, and then just explain what I see in that picture. I used to be graphics designer, and my favorite tool for writing was FreeHand, yes that old vector drawing tool.

It allowed me to write pictures, write a couple of paragraphs about it, and continue to explain another picture and finally bring them all together and write some sentences to glue everything into a coherent piece.

On the other hand, I enjoy writing using just notepad too. That is, the crappies writing program out there. The lack of distractions allow me to focus to the task at hand.

Google Docs for the Win

When I started to write down the "story" version of my conference presentation, I learned that Google Docs had added a feature to draw diagrams. At first I thought it was the same horrible crap they have in Word, but I thought I'd try it out. To my surprise it worked awesomely!

Firstly, it has good default color palette. Not that crappy 4-bit VGA palette with just horrible colors to choose from, nor that 216 safe web-color palette with too many horrible choices, but a couple of well chosen nice colors with few tints each. Design win!

Secondly, the tools it offers are simple to use and work well. The things that I miss from the image editor are: gradients, boolean operators on shapes, and ability to crop the drawing. I think I can live without, it forces me to leave the picture to a sketch level and keep on writing. Simplicity win!

This means that I have been able to combine the two of my best old best practices. Simple, non-distracting text editor (the flickering of that Save button annoys me, though), and simple image editor, which allows me to sketch a picture and tell about it when I get stuck. I'm visual person after all and sometimes some things are just easier for me to describe with a picture. I'm liking writing again. Now, only if I could fix my English grammar :)

Dear Google, if you are listening, please allow me to write blogger posts in Google Docs, thankyousir!

—

I just got word from Alex, that Game AI Conference 2010 just got bigger and better! The line-up is awesome, and now it has larger venue too. The event was sold out, but you have a second change to be there. You can expect an announcement of the line-up and other news very soon now. See you in Paris in June!

More Accurate Tile Connection

I just fixed (R162) an old and forgotten bug in tile connection. When I was working on the tiles, there were a lot of things to do, and one thing that was left to do was more accurate overlap test.

At the time of writing the code, I took a little shortcut and make the edge overlap test to use axis aligned rectangles instead of something more accurate. While most of the time this is ok, it fails when a tilted surface is on top (or under) of another surface. In that case the edge check test becomes too liberal.

I fixed this now so that the edge connection test uses tilted rectangle, instead of axis-aligned bounding box. If you get tile border connection error, let me know.

Adaptive RVO Sampling

I spent a little time trying to bring slim down the sample count of the sampled RVO method, while still trying to get really good accuracy and quality. The above pictures shows two cases brute force and adaptive versions of a scene where the accuracy and quality of the resulting movement is comparable. One takes 890 samples (think 500 would be fair comparison too in terms of accuracy) and another 50 samples. An order of magnitude optimization, my favorite!

The method now takes something between 0.01–0.04ms per agent to calculate (2.4GHz Core Duo), of course depending on the number of obstacles. My goal is to get around 25 agents at 0.5ms per frame, so that is just about there! There are still quite a lot of potential optimizations (remove square roots and divisions, vectorizations, etc) in the sampling code, so I'm quite happy with it so far.

It is possible to run the simulation at lower rate too. I'm currently testing at 20Hz, but the method works well down to 5Hz. I have not investigated on adapting the sample count based on the surroundings, so I think with some cleverness and LOD tricks, it is possible to slim the timings even more.

One more thing to note in the above picture picture is the sampling area. Instead of the full circle around the agent, the sampling area is biased towards the desired movement direction and the radius is reduced too. The rationale behind it is that more evasive movements happen at lower speed. It cuts down the sample count quite dramatically, around 40%.

Well, I think I'll will save some details to my up coming presentation at Game AI Conference 2010 too :)

Geometric vs. Sampling pt. 2

I made a little test the other day to see what is actually the difference between sharp (geometric) and smooth (sampling) velocity obstacle. The first segment shows hard boundary and the second shows soft boundary.

The code in both cases are the same, but in the first case, the time of collision is threshold to imitate geometric solution to velocity obstacles. If time to collision is < 1.5 seconds, then full collision penalty is applied to the sample, else no collision penalty is added.

In the second case, the collision penalty is inversely proportional to time of collision, making the velocity obstacle to appear softer. Even in cases where the geometric method would totally block the movement, the smooth boundary allows to find the best movement direction.

There are some twitching and bugs in the first segment when the velocity obstacle completely covers the sampling area.

—

On another note, Phil's comment on the one of my previous posts put me thinking. I think he's right. Obstacle avoidance alone will not create believable locomotion. There are a lot of nuances which can be only captured in the simulation if you simulate the perception, social forces, etc.

Instead of turning this project into a behavior simulation project, I will narrow my focus even more. It is such a monster research field already. I don't think an individual can successfully research and get something done in the human/crowd behavior simulation stuff in reasonable time.

Multi-agent obstacle avoidance is one of the sub-problems, and I'm going to focus on just that. I can later build some behavior stuff on top of this research if I choose so. Actually acknowledging that there is some higher logic above the obstacle avoidance, allows me to leave some things unsolved and expose them as parameters of the model.

For example if the agent always chooses the fastest possible speed, the result is rush or panic like behavior. If you always choose the nearest speed towards your target, the agent appears shy, or stubborn.

Even if I felt a bit despaired the week following Phil's post, I think it has really helped me to define the problem I'm trying to solve more clearly. Sometimes, it is actually harder to find the problem than to solve it.