Saturday, December 31, 2005

state machine (t.a.g.)

This is the category of technical posts that discuss the use of (finite) state machine as the primary abstraction to build sophisticated behaviours for characters in video games (and side-scrolling platformers in particular).

This is to meet the observation that, in games I loved, one cannot really speak about "artificial intelligence" for ennemies. However, they have behaviours more sophisticated than a mere goomba. More like a Zelda boss, they alternate between states where they have different hit boxes corresponding to harmful blades or weak spots. A sophisticated state machine usually translates into deeper interplay with the game.

In my PhD thesis, I have observed that a strong design for the basic elements of a virtual execution engine allows a much more efficient handling of tasks. Reading open-sourced code from other games conforted me in the idea that a plain 'think()' method for handling all the possible cases of a complex character is a nightmare to work with. In an interpreted language, it would translate into repeated evaluation of tons of conditionals that could otherwise have been avoided.

As a result, the line between compiled and scripted code revolves around those state machines: the compiled code executes whatever is to happen in the current state, a data structure (built from script parsing) defines links between states, and interpreted expressions rule conditional transitions and side-effects, which allows strong reduction of the amount of interpreted symbols per game frame.

No comments: