Wednesday, July 7, 2010

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:
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.


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.


  1. Great presentation, which I was taught VO this way !

  2. Putting the code up and all. You're a hero, Mikko.

  3. Amazing presentation Mikko - a great way to start the day!

  4. I wish there would more power-powerpoints like this. :-D

  5. Wow... very slick presentation.

  6. Looking to streamline your computer vision projects? Look no further than this site! With their cutting-edge tools and comprehensive services, you can easily annotate and label your visual data, accelerating the development of AI models. It does not matter, with what kind of project you’re coming, because the main goal of this company is to keep individuality and strengthen the best aspects of the product and get rid of the weak. Simplify your annotation process and enhance your computer vision workflows with this company today!

  7. Hi all! Optimize your word processing with our NLP Annotations! Our company offers professional annotation services that will save you time and resources by processing large amounts of text data. We will analyze your needs and budget and select the best specialists for you! >> click here now

  8. Many companies around the world have appreciated all the benefits of outsourcing data annotation specialists, which seems quite natural, given the number of benefits a company can get in just a few simple steps. Click on the link useful site to find out more information about data annotation for autonomous vehicle production that you can use to your advantage.

  9. Hi all! Outsourcing image annotation with our company's professional labeling service allows businesses to save time and resources. Our expert annotators meticulously annotate images, providing accurate and consistent labels for object recognition, image classification, and other computer vision tasks. >> this content

  10. This comment has been removed by the author.

  11. COCO DensePose is a unique technology that may be of interest to many companies that need high-quality and accurate data annotation. And to implement this unique technology can be much easier than it might seem at first glance, for this you just need to follow the link COCO DensePose Task and fill out a short questionnaire with the main tasks of your product.

  12. Hi all! Did your own search for an MOT annotation specialist fail? Our company offers MOT annotation services for accurate tracking of objects in video frames. Submit your MOT annotation to us for reliable tracking in your computer vision projects. Our assistants work both full and part time! >> recommended site

  13. Hello! If you want to unravel the complexities of audio analysis than our audio annotation services it's your choise !Our skilled annotators carefully label audio data, enabling AI models to comprehend and interpret sound effectively. Drive advancements in speech recognition and audio-based applications with our accurate annotations.

  14. This comment has been removed by the author.

  15. Point cloud annotation is a high-tech solution that helps the artificial intelligence of a huge number of companies around the world to become better. And if you want to learn how to use the services of real professionals in this field from abroad, absolutely not lose in the quality of the work done and save a lot - I just recommend that you click on this link and explore more.

  16. Outsourcing has become a strategic instrument for driving businesses to greater levels of success in the contemporary business world. Organizations can access a wealth of knowledge, creativity, and efficiency by hiring specialized individuals. These experts provide a lot of knowledge and a new point of view, enabling the business to benefit from cutting-edge solutions and creative concepts that might not have been used otherwise. Through outsourcing, businesses have access to a vast talent pool, allowing them to put together a dream team of experts suited to their unique requirements. Check more on this great site!

  17. Hello! As a trusted outsourcing partner, we bring precision, security and innovation to your document processing tasks. Our range of services transforms the way you work, from strengthening neural networks to advancing healthcare, streamlining document validation, and improving data analytics. Visit our site for articles that explore the breadth of our experience and the transformative potential of PDF annotations. >> natural language annotation for machine learning

  18. This website can assist you in writing better code more rapidly whether you work alone or in a big team. It might speed up your development process and produce high-quality apps in less time because of its robust debugging tools, integrated testing framework, and user-friendly interface. For more beneficial details, click the link below! Link:

  19. For forward-thinking businesses, text annotation outsourcing plays a vital role in maximizing profitability. Offline hiring methods may involve larger resource commitments, training costs, and labor costs. In contrast, outsourcing allows businesses to work with annotation professionals who have the required expertise, knowledge, and infrastructure for a small fraction of the price. This cost-effectiveness enables organizations to allocate resources to innovative and growth-oriented projects, which ultimately boosts profitability. Additionally, the efficiency and correctness of annotations made by specialist outside teams improve decision-making, resulting in better results and higher profitability. Source: