Greetings from Paris Game AI Conference 2010

The title image is a bit of an insider joke to those who had the pleasure to experience the technical problems of my talk.

I spent last week in Paris. Three of those days I spent with fellow game AI devs at Paris Game AI Conference. It is a rare situation to meet so many talented and enthusiastic people. I also had talk at the conference. I will post more about that soon, along with the demo and the slides. I think I will write more detailed posts on the topic too.

Bjoern has good coverage of the talks on other blogs and sites, I'm just going to give you few observations.

Empathy and AI

I had the feeling that this year there were more veteran devs in there–Bruce Bloomberg, Ken Perlin, Noah Falstein, just to name few. My big take away from them was to design with user experience in mind and engineer the simplest possible solution to achieve that.

That is, rather than asking if you should use behavior tree or finite state machine, you should ask what is that you want the user the experience and then work it out the easiest solution from there. It is not easy, though. I think such problem solving skill comes with experience. You sort of need to have a feeling of the potential solutions and their strengths. I think Ken's advice is really good rule of thumb, create the simples possible solution first and iterate from there.

You get a good head start by thinking the problem from the users point of view. For example, what kind of feedback is needed to understand the AI, or what kind of interactions you want to use to have with your AI?

Mikael Hedberg had interesting talk how that thinking evolved in the case Battlefield Bad Company. For example they measured that an average screen time of an AI is about 5 seconds. If the death of an AI opponent takes approx. 2 seconds, it is worth putting quite a bit of effort to get that part right.

Good death and hit reactions is the key to make the AI opponent to feel good interactive toy. When working on shooters, just make that awesome first. And while the designers are having good time killing all the foes, add some magic to make them fight back better.

Bruce Bloomberg's talk was also great example of this mindset. I don't think I can ever be so honest about how to simplify the content creation process and the technology based on how the player perceives things as they have been.

Few months back, there was a video of a magician called Jamy Ian Swiss circulating the nets. He used the word empathy to describe this property of user experience driven design. The video is worth watching.

Gameplay vs. AI

Another really welcome development I saw was how people categorize AI programming. In past there usually has bee really clear cut between what belongs to AI and what belongs to gameplay. It seems that a lot of people, from designers to programmers, consider game AI to be a broad concept.

And that is true! In current games the concepts from AI are being applied very broadly across all the gameplay related things from audio to animation. I think this is very good change. The biggest advantage is that the solutions that were before only "available" to AI programmers can now be used to solve other problems too. Sometimes the barriers are in our minds.

It was also interesting to note that this year most of the people were using really simple solutions to their problems. It may have been also the result of Alex's great choice of talks. Most people were using (hierarchical) finite state machines instead of more complex solutions. The reason could be that many talks were biased towards game characters, but it also resonates with the aim to find as simple as possible solutions.


All in all, it was awesome conference, can't wait to get there next year! Big thanks to Alex and Petra for all the arrangements. I'm going to enjoy the rest of my vacation and work hard next week to put the demo and code online.

Stealth Mode

I have been a bit in a stealth mode the past months. It has been less about doing something I cannot tell you about, but I have just put a lot of time and energy into finishing up my local navigation research and preparing a (hopefully!) kick ass presentation about it for the Paris Game AI Conference next week. The image above is a little teaser screenshot from my presentation.

I will make the presentation available after the conference along with the demo code. So that might be something to look forward to. More about that in few weeks.

I'm also planning to update Project Cane at some point this summer after I clean things up a bit. Project Cane was basically my testbed to test different local avoidance ideas. It will also come with the local navigation grid code I blogged earlier. It'll be bunch of proto code, but maybe someone will use it useful too.

Then at some point I will start working on multi-agent navigation which will be part of Recast & Detour. My current idea is that it will be separate library, just like Recast and Detour are separated but related. There will be some glue code in form of examples which will show you how to use them together.

I hope to see many of you in Paris next week, if not, stay tuned for the presentation :)

Towards Better Navmesh Path Planning

As many users of Detour have noticed, navmeshes sometimes create extra detours in the paths. This is due how the cost of traversal between different polygons are calculated. The distance to travel from one polygon to another is often approximated either calculating the distance between the centers of the navmesh polygons or, between the edge midpoints of the navmesh polygons. As seen on the above pictures.

Edge midpoints is slightly better in practice, but both will create odd paths when you have long thing triangles or large polygons next to smaller polygons.

There is a nice recent paper Shortest Paths with Arbitrary Clearance from Navigation Meshes which describes another method based on visibility. I'm itching to try that out!

That paper also reminds me why Recast subtracts the agent radius before building the navmesh. It is just really complicated to find thick paths. Even just selecting a valid end point is really complicated matter.

[EDIT] Here's how the visibility optimized heuristic should work (heuristic #3). The idea is that if there is direct line-of-sight from the current node (S) to goal (G) via the next edge (e), then the node at the next edge will be placed at the intersection of the edge and segment SG. Else, the node is placed at the vertex which is closest to G. (The picture below assumes that the node locations are calculated and cached as they are encountered.)

Constrained Movement Along Navmesh pt. 2

I have been really busy recently at work, with my Paris presentation and some other projects of mine. That has taken its' toll on the frequency of the blog posts too.

have few hours extra time, I though I'd blog a little bit about a problem in my old code I tried to solve just recently. Very little discussed topic and one of my favorites, moving along navigation mesh.

—

The goal of the movement code is to solve the case of moving constrained to the navigation mesh boundaries. Since the walkable areas are divided into convex regions we can use this to solve the movement only inside on polygon at a time and then move to the next polygon based on which edge we hit at the end of the current step.

In case the movement target is outside the current polygon, my earlier attempt clamped the point on the polygon boundary, and followed the edge where the point lied on. While this works most of the time and creates nice sliding movement when a non-traversable polygon edge is hit, it also misses some obvious cases.

The Problem

Such example is shown in above picture. The blue arrow indicates the desired movement delta, and the location labeled 'nearest point' shows where the old nearest-point-on-boundary method would move the character. If the bold edge was connected to the next polygon where the agent is supposed to move to, the test to see if we can move to there would fail when using the old method, even if there is obvious line of sight to it.

Improved Solution

An obvious choice would be to use line intersection or ray-casting to check if there is edge crossing the movement. Instead the new solution still avoids using raycasting since there are some corner cases which are hard or just annoying to handle when using intersections (i.e. hitting vertices and parallel edges). The basic idea of the improved old method is as follows.

If the movement target is inside the polygon, we just accept the new target location. If the movement target is outside the polygon, we first detect which edge the movement delta crosses on its way to the target location and follow the edge if it leads to the next polygon or use the old method if we hit obstacle.

Finding the crossing edge can be easily figured out by testing if the target is inside the sector formed by the movement start location and each edge at a time. This test can be quickly one using using 2D cross products. Dashed lines in the above picture show the sectors.

If the found edge (or its neighbour if we clamped to either end point) is connected to the next polygon to move to, we move the current location to the nearest point on the edge and continue to the next polygon and start the iteration over.

If we instead hit an edge which is an obstacle, we move current location to the nearest point on the boundary of the polygon from the target location, just like in the earlier algorithm, to get the nice sliding movement.

More Woes

There are some cases when the start point is not exactly inside current polygon. This can be because of the floating point accuracy or because some external collision resolution pushed the point away from the mesh or something similar. It is desired that our method works even in that kind of cases.

In case the start location is outside, the trick is to first clamp the start location to be inside the polygon and proceed as before. That's it! Because of the floating point accuracy, there is still need to add a little bit of slack into the sector test so that it handles the case where the start point lies close to the boundary.

—

Handling corner cases like this is really important when building robust navigation system. The earlier method was usually not a problem when you would use small delta movements, but it happened sometimes. It should not happen. Not even in 0.01% of the cases. Nothing is more annoying than that you have a valid path which cannot be traversed.

The Design Evolution of Zen Bound Level Tree

While cleaning up yesterday, I found some old sketch books. Some of then are from the era I was working on Zen Bound and early incarnation of Recast.

I thought I'd collect some sketches and screenshots how the Zen Bound level selection tree came to be and put them in a rough timeline. It was really hard process for many reasons. The total time span across about half a year, so many at many times we were diving in muddy waters. Now in retrospect it looks quite a bit more coherent process.

Here's the image, it is really wide image, zoom in!

The Moment You Get It

Pretty much every on project I have worked on–which have succeeded to a degree–I have had a moment when I know that it is going to work. The above image, named navtest.png dated December 3rd 2008, was the point when I knew that Recast is going to work.

Up to that point it had been a huge struggle to find a way to partition the surface. Based on the previous incarnations of the same idea (there were 2 or 3 version before that, depending how I count it) I knew that the the triangulation can easily become the bottleneck of the algorithm. So I worked really hard to reduce one dimension from the problem, and eventually it paid out.

The following months after that it was a cake walk to add tracing the contours, simplifying them and finally doing the triangulation. Four months later March 29th 2009 I made the first commit to Google Code.

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!