Article

The Catch for Multi-threading Decision Making, Q&A with Alex Champandard (Video)

Alex J. Champandard on September 23, 2008

This weekend was rather hectic; the site was moved to a new improved server, and was down for about 10 minutes. What I didn’t realize, however, is that I left the “Under Maintenance” page active all afternoon — so only the forums and wiki were accessible!

Now, the astute readers among you will remember that this weekend was the first Q&A in a series of free seminars about game AI. So you can imagine my surprise 2 minutes before the meeting, having posted the links for the meeting, to find than nobody was around except my wife Petra doing the recording! Luckily, Twitter saved the day (thanks Michael Kofman :), and within a minute after I fixed the site, over two dozen people poured in. And in the end, we even got started on time!

Benefits of Multi-Threading

To jump right in, here’s one questions by DDd was about multi-threading, specifically the ways it can be applied to games. I think this a particularly relevant topic, which seems to come up very often here at AiGameDev.com:

  1. Recently, in the Insider’s Area (free registration required), I posted an article on the theory of applying multi-threading to hierarchical logic (using Intel’s TBB). In theory there’s some potential there, but while preparing the next articles, and thanks to discussions with our resident experts here, I realize there’s a huge up-hill battle for applying threading within a single AI character.

  2. On Sunday also, there’s a live Masterclass with Phil Carlisle and myself (if you can join, the event is completely free). We will look into the implementation of behavior trees. One part of that will cover schedulers, and using tasks as building blocks. No doubt we’ll discuss the threading problems I mentioned just above too, and we’ll also be happy to take questions!

With that in mind, here’s the answer to the question:



More Coming Soon…

We made a high-quality local recording of this session (like all others), and I mentioned we’d release the best bits in the future. This one was a good place to start since it was one of my most interesting answers — in my humble opinion! Once we’ve figured out how to edit the 4h recording and distill the 1.3 Gb into a useful blog format, we’ll put it online as well.

During the Q&A, a lot of questions came up about the membership site, and we talked about its various components over half an hour. I know I haven’t mentioned too much about the details yet, other than it’s a separate new part of AiGameDev.com entirely dedicated to professional game AI development. We’ve preferred to let the content speak for itself so far…

However, over the next couple days, I’ll explain everything we have in mind, including our masterplan for the community around the site too… (If we were in this for the money I’d still be a full time consultant right now :-) On that subject, there’s still a second contest open to win a year of membership for figuring out how AiGameDev.com can best help the community as a whole, so check it out! That deadline is now Wednesday 24th, midnight. The results of the other contest will follow shortly. Exciting times; stay tuned!

Discussion 1 Comments

bknafla on September 24th, 2008

Hi Alex, While I attended the online conference I was distracted by other important stuff to do aside - so I missed the part shown above and am very happy that you posted it! All experience and info I have point to the same conclusion that you came to - one decision making process itself can be parallelized but with very limited "return in investment". First and foremost you want to distribute agents to threads or even better and preferably - to model agent decision making as tasks that are then distributed automatically to threads. Putting each agent decision making onto its own thread would need too many threads and the chance is pretty high that the computations per agent per decision making process aren't enough to regain the setup cost per thread. Tasks for the rescue. However, this coarse parallelization granularity at maximum scales to one agent decision making task per thread. With thousands of cores in the future this wouldn't deploy enough cores if a game would only have hundredths of agents per scene. If other tasks would be scheduled to the cores concurrently everything would be fine again. Or we have to tap into finer grained parallelism - like parallelization of the behavior tree - to really deploy every ounce of computational capacity of all the cores. I immediately sign your other conclusion - that the sensor gathering is the primary candidate for parallelization as it takes more and more processing power. And, as parallelization of physics systems shows - there is a lot of parallelization potential and therefore great chances to develop better and better sensor models (neighbors, neighbors in field of view, neighbors that are in attention focus, colors or movements that take attention, occlusion checks, camouflage checks, different sensor informations that is merged (sound + smell + vision) that increases attention, etc.) The work on putting physics onto GPUs, which conceptually boast ten thousands of threads, shows that you can deploy a lot of threads (or tasks) and therefore a lot of cores for the sensor job.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!