Free JavaScript Editor Ajax Editor

↑

Main Page

## OptimizationLet's assume a designer isn't too familiar with the tools provided and has generated an overly complex finite-state machine. If the finite-state machine is substantial in size, or if the number of NPCs using it is large, the computational overhead may be hard to neglect. Instead of having the AI developer check through each of them for optimality, why not create a tool to do so? Finite-state machines have the advantage of being a well-understood, simple computational model. Unlike more elaborate models such as Turing machines, there are known algorithms to optimize finite-state machines. In fact, creating canonical finite-state machines (that is, the simplest possible graph) is a proven technique to compare finite-state machines to one another. One algorithm to perform such optimizations compares all the states together and merges them where possible (see Figure 38.5). The state comparison is best done in pairs. Two states can be merged if all outgoing transitions point toward the same state. The two states are merged by using one set of the duplicate outbound transitions, but all the incoming transitions. It's a good idea to rename the merged state to something indicative of the previous two states. ## Figure 38.5. Optimization of the finite-state machine by folding states with identical outgoing transitions together.
A naive implementation of such an optimization process would be of complexity O(n Regardless of the technique used, finite-state optimization has mostly benefits. If we can simulate the same behavior with fewer states, it makes sense to do so. However, smaller finite-state machines are often less intuitive. If the designer added extra states, it's usually because they are easier to understand that way. As such, it is beneficial to keep the human-designed finite-state machine, and only compile them down to an optimized finite-state machine during the release build. |

↓

Ajax Editor JavaScript Editor