Actor Behaviors and the Curse of Dimensionality

Alex J. Champandard on September 23, 2007

Last week’s sketches introduced the idea of a lookup table, where each situation in the game corresponds to a cell in the table. Each of these situations has a corresponding behavioral response.

To help illustrate these lookup tables in practice, here’s a simple example of the behavior of a lazy soldier (long story :), represented as a lookup table.

The lookup table makes it easy to understand this simple situation, but if you simply add one boolean variable to represent the situation more accurately, the table doubles in size. In effect, you have twice as much work to do to edit the behaviors.

Now, the problem is that the average actor needs many variables to model the situation, and even more for the internal state. Having to take into account two dozen of these variables is not uncommon. This makes the table grow very quickly in size.

The number of necessary behaviors grows exponentially larger very quickly along with the variables. This is known as the curse of dimensionality, as each variable can be considered as a separate dimension to the problem.

White tables have their advantages for understanding simple problems, it becomes almost impossible to edit the behaviors exhaustively using a large table. Thus, an alternative solution is required…

Next week’s Sketches explain how game developers cope with this curse by dealing with all these problem variables selectively.

Discussion 3 Comments

mihaic on September 24th, 2007

Useful information as always on your articles. Looking forward for the next part of this article.

Dil on September 24th, 2007

We are next week! Hum, it depends if for you the week begins sundays or mondays... Just that I am expecting that the next part will save me days of implementation: this subject is exactly what I am strugling with currently. PS: Do not forget to update your "Practice" section, it was very useful.

alexjc on September 24th, 2007

Maybe I should have said "In a week from now" or "Next Sunday" :-) Thanks for your feedback. I'm still finding my feet with this series (it takes more time than I expected to make the sketches look ok), but I'm happy to hear it's going somewhere useful. Alex

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!