The Art of Recursively Decomposing Problems

Alex J. Champandard on September 30, 2007

In the previous sketches, you learned what a behavior lookup table looks like in practice, and how it can grow very quickly in size as you add more variables to the problem.

The way to reduce complexity in practice is to “divide and conquer” by breaking down the table into smaller parts. To do this, try identifying important sub-problems where variables remain constant (e.g. there are no enemies) while others are ignored (e.g. the amount of ammunition).

When you solve these smaller problems, you essentially make assumptions about the actor’s state variables or external situation. The more assumptions you make, the smaller the lookup table for that problem.

For example, the small problem could be about finding the right behavior when being flanked by an enemy, having low health, whilst under fire from elsewhere. The bigger problem could be what to do without ammo. What’s interesting and useful to note is that these problems can be nested within each other.

So, within each problem, you can implement custom logic to refine your assumptions even further, like behavior trees do. But likewise, within each problem, you’ll need logic to determine when your assumptions are broken, and find out which other sub-problem has become active.

This basic mechanism can be implemented easily as a finite state machine.

Next week’s Sketches tackle a specific problem in depth using these ideas; you’ll learn how to build attack behaviors for a typical action game.

Discussion 2 Comments

Dil on October 7th, 2007

*Avidly Awaiting the next part* My MSc project is directly related to these sketches.

alexjc on October 7th, 2007

Heh, nice to know Florian. Did you have anything particular in mind? What are you working on anyway? I'm curious now :-) I'm taking the series in a more practical direction to help fulfill its potential, but if there's more theory you'd like covered, let me know. 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!