next up previous contents
Next: Searching Up: Data-Oriented Design Previous: Condition Tables   Contents

New version now available here at www.dataorienteddesign.com/dodbook/

This page is from the beta release of the Data-Oriented Design book. There are errors, spelling and factual, and this page is only kept for purposes of maintaining old links.
Subsections

Finite State Machines

Finite state machines are a solid solution to many game logic problems. They are the building block of most medium level AI code, and provide testable frameworks for user interfaces. Notoriously convoluted finite state machines rule the world of memory card operations and network lobbies, while simple ones hold domain over point and click adventure puzzle logic. Finite state machines are highly data driven in that they react to an alphabet of signals, and change state based on both the signal received, and their current state.

Tables as States

If we wish to implement finite state machines without objects to contain them, and without state variables to instruct their flow, we can call on the runtime dynamic polymorphism inherent in the data oriented approach to provide these characteristics based only on the existence of rows in tables. We do not need an instruction cache trashing state variable that would divert the flow according to internal state. We don't need an object to contain any state dependent data for analysis of the alphabet.

At the fundamental level, a finite state machine requires a reaction to an alphabet. If we replace the alphabet handling code with condition tables, then we can produce output tables of transitions to commit. If each state is represented by a condition table, and any entity in that state represented by a row in a state table, then we can run each state in turn, collecting any transitions in buffers, then committing these changes after everything has finished a single update step.

Finite state machines can be difficult to debug due to their data-driven nature, so being able to move to a easier to debug framework should reduce development time. In my experience, being able to log all the transitions over time has reduced some AI problems down to merely looking through some logs before fixing an errant condition based only on an unexpected transion logged with its cause data.

Keeping the state as a table entry can also let the FSM do some more advanced work, such as managing level of detail or culling. If your renderables have a state of potentially visible, then you can run the culling checks on just these entities rather than those not even up for consideration this frame. Using count lodding with FSMs allows for game flow logic as allowing the triggering of a game state change to emit the state's linked entities could provide a good point for debugging any problems. Also, using condition tables makes it very easy to change the reactions and add new alphabet without having to change a lot of code.

Implementing Transitions

Finite state machines normally have an input stream that modifies the internal state as fast as new signals arrive. This can lead to very fast state switching, but to maintain the parallelism, transform oriented finite state machines only run one update based on all signals available at the time of the tick. There is no ambiguity however, as if there are more than one conditional responses matching the input state, then it is fine to go to more than one state at once as a result.

Consider the finite state machine in a point and click adventure, where the character has to find three objects. In most games, the logic would be defined as a state waiting for all objects to be found. In a condition table finite state machine, there could be three different tables representing each of the objects, and while any table is populated, the game will not progress.

In a transform oriented finite state machine, the transitions are generated by the condition tables transforming the input signals into table insertions and deletions. Whenever a condition is matched, it emits an entity ID and a bool into a transition table (or a null if you intend to reduce the table in a separate process) ready for processing in the commit stage. This means that a finite state machine can react to multiple signals in a deterministic way because the state will not change before it has finished processing all the possible condition matches. There is no inherent temporal coupling in this design. Traditional finite state machines don't allow for multiple reactions at once as they transition from one state to another, naturally reacting on the order of signals, which is perfect for a finite state machine built for a lexer or parser, but possibly not for a generic gameplay state machine.

Condition tables as Triggers

Sometimes a finite state machine transition has side effects. Some finite state machines allow you to add callbacks on transitions, so you can attach onEnter, onExit, and onTransition effects. Because the transform oriented approach has a natural rhythm of state transforms to transition request transforms to new state, it's simple to hook into any state transition request table and add a little processing before the state table row modifications are committed.

You can use hooks for logging, telemetry, or game logic that is watching certain states. If you have a finite state machine for mapping input to player movement, it's important to have it react to a player state that adjusts the control method. For example, if the player has different controls when under water, the onEnter of the inWater state table could change the player input mapping to allow for floating up or sinking down. It would also be a good idea to attach any oxygen-level gauge hooks here to. If there is meant to be a renderable for the oxygen-level, it should be created by the player entering the inWater state. It should also be hooked into the inWater onExit transition table, as it will probably want to reset or begin regenerating at that point.

One of the greatest benefits of being able to hook into transitions, is being able to keep track of changes in game state for syncing. If you are trying to keep a network game sycnronised, knowing exactly what happened and why can be the difference between a 5 minute and 5 day debugging session.

Conditions as Events

The entries in a condition table represent the events that are interesting, the ones that affect the flow of the game and the way in which the data is transformed. This means that the condition tables drive the flow, but they themselves are tables that can be manipulated, so they can self modify, which means we can use this technique to provide high perfomance data-driven, yet data-oriented development practices.

Condition tables are tables that can have rows inserted or deleted just like any other table. If the rows are added, modified, or removed based on the same rules as everything else, then you have a data-driven general purpose development model. One that doesn't even sacrifice performance for flexibility.


next up previous contents
Next: Searching Up: Data-Oriented Design Previous: Condition Tables   Contents Beta release of Data-Oriented Design :
Expect errors, spelling and factual. Expect out of date data, or missing stuff. Expect to be bored stiff in some sections, and rushed in others, but most of all, please send any feedback on any of these and any other things that you spot, to support@dataorienteddesign.com

Richard Fabian 2013-06-25