Behavior finite state machine
Behavior planning is used mainly for creating realistic motions of characters based on Behavior Finite State Machine (BFSM), path-finding algorithm (planner), set of captured motion clips, starting position and behavior of character, ending position and behavior of character and pre-defined environment. By the existence of these conditions, the path between start and end is computed and motion is generated automatically by the planner. The path-finding algorithm used in this technique is A* search and the optimal path is calculated based on the conditions such as cost, time, orientation and position.
2. Background of the research
To be able to generate motions for synthetic characters, many methods had been proposed. These methods use key framing, motion capture editing, motion capture interpolation that includes behavior scripting and natural dynamics simulations. These methods require high level control and may cost highly. Some planning methods use graph-like data structures of motions for static environment. In this motion graph approach, the graph is on the order of thousands of nodes corresponding to individual poses of motion and also need to reuse large amount of motion captured for each nodes. This may be inefficient and require too much storage space. Using BFSM and behavior planner solves these problems. The necessary and sufficient conditions are existence of BFSM, captured motion clips and pre-defined environment. The number of states in BFSM is relatively small compared to graph-like data structure. Also, the amount of data is relatively small. The computational cost is much lower than the others.
3. The proposed algorithm
As can be seen in figure 1, the system can be divided into several modules. The most important modules of the system are BFSM, environment and behavior planner. The start point (Sinit) and end point (Sgoal) is input to the planner.
3.1 Behavior Finite State Machine (BFSM)
BFSM defines the states of behavior and their transitions among these states. The states are represented as bubbles and transitions as directed edge. Each state has a set of motion clips captured as high-level behavior. These motion clips may have different length and they should be placed in different time and assigned different costs. The velocity of the characters in the clips must be taking into account. It is an important fact for smoothness and quality of the resultant animation. Another important fact is that every clip could be able to make transition to all others if the beginning and end of every clip are similar.
For static environment, the environment e is represented as 2D grid-map and it contains information about obstacles that the character cannot pass through, free space in which the character can move and other special obstacles such as gap over which the character can jump and archway under which the character can crawl. The obstacles are avoided by bounding the character with a cylinder of radius r. The bounded area cannot pass any obstacle. The algorithm used here can handle dynamic environment by defining the function E (t). It returns the environment condition at time t. So, the character can be re-planned by the algorithm.
3.3 The Behavior Planner
The behavior planner algorithm described in Algorithm 1 simply plans the motion of character. This algorithm is based on A* Search Planner. Briefly explaining, Tree.Initialize(Sinit) and Queue.Insert(Sinit,DistToGoal(Sinit,Sgoal)) functions initialize the tree and queue with starting state and remaining Euclidean distance to reach the goal state. The function E () is described earlier. The function F () takes environment e and Sbest and return the set of actions that are possible to be children node of the Sbest. In other word, F () retrieve the states to which Sbest can make transition from FSM and return the possible action set. T () function takes the input state Sin and action a and return Sout based on following equation.
The function G () tell the algorithm that whether Snext can be the child node of Sbest or not by checking the collision on the position Snext. It also checks the intermediate positions between Sbest and Snext.
When the search tree is generated by using A* search, the tree has 2241 nodes. If the truncated A* search is used, the number of nodes becomes 1977 and if inflated A* is used, the nodes becomes 1421. As A* search is moved to truncated and inflated A* techniques the size of the tree, the search time and the quality of solution decreases. Note that after sequence of behavior is calculated, the motion is created using smooth-in, smooth-out slerp interpolation function. The algorithm is implemented in dynamic environment with a falling tree. Before the tree is fallen, the character can jog normally. When the tree is falling, the character can do nothing and the character can jump over the tree after it has fallen (figure 3). Moreover, the algorithm is also tested with 100 characters. In this example, the characters have an action "stop-and-wait". This action is generated while the character meet with the another character (figure 4). The skateboarder animation is also created using this algorithm. The skateboarder stops and jumps over an obstacle (figure 5). Also in animation with 3 horses, horses avoid each other and moving obstacles simultaneously (figure 6). These examples use the common BFSM (figure 1). The ability to adapt to characters with different kinematic and movement style is the advantage of this algorithm. The most important fact is that the same FSM can be re-used for any number of characters.
5. Strengths and Limitations
This algorithm can be scaled easily to a large amount of data and need less memory than other methods. Its search algorithm has high efficiency and other properties such as generality, intuition and optimality. But from the limitation point of view, it requires motion clips that are segmented perfectly. If it is not well segmented, the motions will not be smooth and then it may have more computational cost. And it also needs BFSM with appropriate transitions.
If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please click on the link below to request removal: