Tuesday, March 16, 2010

Game Logic VI : Finite State machines and Decision Tables

Finite state machines can easily be defined by existence in a table, this much should be apparent from the previous articles, but the alphabet (triggers that cause state change) can also be represented by row information. Decision tables are quite common in database tech, and they provide an easy to read, simple to reason about, really easy to modify setup for making decisions about multiple outcomes given multiple incoming data.

I'd recommend reading some stuff.

With a decision table per state, finding the next state is quite a simple task, and one that can be optimised algorithmically (using standard techniques for query optimisation, or specific ones for optimising join order on decision tables).

Also coming to mind as I type, things that are frame coherent, like renderables that have a state of "potentially visible" can use existence based processing and be ticked only when necessary. Using count-lodding to drop in sub-objects from larger size cullable groups when they become visible also allows for the traditional hierarchical approach to culling, while maintaining the benefits of FSM simplicity.

Oh and another thing, on debugging, I saw this on a data-oriented development post

"When debugging why a specific mesh is being culled, though, it really helps to see all the data about that entity in one place. Otherwise, you spend a lot of time traversing data structures in the watch window, just to find out what state an object got in that caused it to flip its visible bit to false. So the view of the data that humans need is another important piece of the puzzle"

No, think bigger dude!

As you can see, the preference for all the data in one place comes about because we're thinking about things as objects that have a state, but rethink these words with decision tables and we end up having a very good possibility of keeping tabs on what decisions were made. We can keep the resultant decision row of the culled items, and even the calculated values that lead to that row choice. This actually lets us look back in time rather than have to try to reproduce the same scenario multiple times. You could say that we're naturally stuck thinking that the only way we can debug something is by thinking about the system rather than just asking it questions directly. Microsoft have just released some cool stuff in Studio 2010 that lets you look at the history of a value, and there was a talk about a JVM that let you roll back the whole state machine, and now we can do the same without having to use managed code.

This actually makes debugging easier, not harder.

Think how often you've wondered "why" something happened. When you're homogenising the techniques you use to make decisions like this, debugging will be easier as logging decisionscan be written once and reused often. Ever heard of a reusable debugging framework before? You have now!

No comments: