My Paris Game AI Conference Presentation

I have now successfully vacated my vacation, purged the most urgent work related queue, and finally got some time to clean up the "slides" from my AIGD10 presentation. Without further due, here's link to the presentation code and executables for Windows and OSX:

• AIGD10_MikkoMononen_NavLoop.zip

Use right mouse button to navigate the presentation. Some of the diagrams are interactive, I have included some usage notes below them. It is not meant to be intuitive, just a quickly hacked version of what I hope powerpoint would be :)

The code is quite ugly at points and probably not as efficient as you might like. I have tried to make comments around the important chunks of code where things need improvement. I left some things unoptimized for the sake of readability.

I'm still wondering what might be the best way to transcript the presentation. Here's quick overview of the navigation loop idea.

Navigation Loop

The idea of navigation loop is to cover all the things from A* to velocity selection which are needed to make character move in the world. One of the main goals was to make the agent movement as flexible as possible so that you can concentrate on movement styles or even multi-agent navigation instead of focusing all your energy to try to stay on path (that naked tight rope dancer is that).

Your system will get horribly, horribly, horribly convoluted when you try to follow (linear) spline path and especially when you mix and match collision representations!

The path to the goal is represented all the time as linear array of connected polygons. We never find straight string pulled path to the goal location. This linear array of polygons is found before we start to move the character. You can use your favorite search method to do that. It probably will be A*, I use breath first search in the demo.

Foreach (Simulation Step) {

At each simulation step you first calculate the next corner to move to. This can be implemented efficiently using the Funnel Algorithm. Instead of trying to stay on path, we can always query the next sub-goal towards the target using Funnel Algorithm.

The next step is to apply steering. The demo contain a couple of different styles from robotic straight path moving, to smooth path movement to drunken movement.

The next step is to move the agent. This is done so that the agent is always constrained to the navmesh. The result from this movement step is a linear array of polygons that we visited through when we moved the agent [1].

As final step is to finally fix up the corridor based on the visited array. Most of the time this fix up will shrink the path corridor, but in case the movement lead the character outside the corridor, new polygons will be added in the beginning of the array.

The result of this loop is that no matter how we steer, we are always able to query the next subgoal. If the steering is not totally stupid, the agent will reach the target with certain probability.

Later in the presentation you can find how to extend the loop to contain velocity planning stage.

Data Dependancies

The navigation loop idea assumes certain things about the data. The dynamic obstacles are always assumed to be traversable in one way or another. The system tries its' best to resolve collision conflicts, but in certain cases you need to detect dead-locks and figure alternative ways to handle them, i.e. disable collisions or use special animations to switch places.

The local velocity planning cannot deal with local minima (pockets, U-shapes, etc). If you have larger or more complicated obstacles they need to represented in the navigation graph.

Conclusion

I'd like to thanks David Miles and Thomas Young for laying down the ground work on their earlier articles and talks. I have not seen similar complete system represented before, but I don't claim it to be particularly unique. Such holistic systems as quite common in motion planning literature.

The sort of "anti-points" of this presentation were: 1) A* != navigation, 2) (Linear)Spline is horrible representation of a path. Unfortunately I know that the old fragments of wisdom on navigation will stick with us for years to come .

___

[1] I have blogged a couple of times about constrained movement along navigation meshes. I think the idea is sound, but I'm still figuring out a couple of implementation details.

Firstly, the idea works really when on triangles, but not so well on polys.

Secondly there are certain cases where the demo implementation fails when the next clamped location is at a vertex and both of the neighbour edges are valid exit edges. Need to have better heuristic for this. The system is always able to resolve this the next update, but it is annoying nonetheless.

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.