Optimization

Let'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.

A naive implementation of such an optimization process would be of complexity O(n²). This proves more than satisfactory for modern computers; given the small size of finite-state machines, we're talking milliseconds and not seconds of optimization time, which is also an offline preprocess. By doubly linking the transitions to the start and end state, this can be optimized almost O(kn), where k is the degree of connectivity. In this optimized version, the algorithm checks the inbound links of each state. Each of the states connected is compared to each other state for similarity. The intuition is for two states to be identical; they need to be connected to the same state, so tracing inbound links reduces the total number of nodes that need to be compared to each other.

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.