The latest open-source solution! Creator writes an ECS framework + behavior tree to implementation for fighting game AI
Introduction
There are many ways to implement game AI. The most commonly used ones are finite state machines and behavior trees. Compared with finite state machines, behavior trees have better scalability and flexibility and can implement more complex AI requirements. Developer “honmono” implemented a fighting AI Demo with an ECS + BehaviorTree framework in Cocos Creator. Let’s take a look at his solution.
Demo example
This fighting AI Demo includes patrolling, tracking, attacking, evading attacks, being injured to interrupt attacks, attack interrupting dodges, etc. See the source code at the end of the article.
Write an ECS framework
The full name of ECS is Entity - Component - System. A component has only properties, but no behavior, and a system has only behavior, but no properties.
What is ECS? There are already many articles about ECS on the Internet, so we won’t discuss it here, but post a video that we personally think is good and talks more about it in a game you know:
“On the ECS Architecture in Overwatch”
Overwatch Gameplay Architecture and Netcode
This video should be one of the first to introduce the ECS architecture. It introduces the ECS architecture comprehensively and compares the differences between ECS and traditional game development architectures and the processing during network synchronization.
The ECS model follows the principle of combination over inheritance, where each basic unit in the game is an entity. Each entity is composed of one or more components, each containing only data representing its characteristics (i.e., there are no methods in the component), e.g., the movement-related component MoveComponent includes properties such as speed, position, orientation, etc. Once an entity has a MoveComponent component, it is considered to have the ability to move, and the system is a tool to handle a collection of entities that have one or more of the same components and only have behaviors (i.e., no data in the system). Entities and updates to the entity’s position are based on the relevant data (speed, position, orientation, etc.).
Entities and components are a one-to-many relationship - what capabilities an entity has depends entirely on which components it has. By dynamically adding or removing components, the entity’s behavior can be changed at runtime.
The relationship of this passage for ECS is also the rule that the framework I designed abides by, i.e., the Component contains only properties, and the System contains only behavior.
What this ECS framework does
Diagram of World-Entity-Component-System
World calls all systems in sequence on every frame, and the corresponding Component is processed in their System. During this process, users can dynamically create or destroy Entity, and add or remove a Component in the Entity.
To maintain the relationship of Entity-Component-System more efficiently, I have taken some measures.
- All components are maintained through their corresponding ComponentPool.
For example, MoveComponent will generate a MoveComponentPool for maintenance, which is convenient for reuse. The component is not directly held outside, but the corresponding component can be obtained in the corresponding pool through the index of the component in the pool.
- Entity uses the self-incrementing Idx identifier. When an entity is destroyed, the idx will be recycled.
There is no need to hold Entity objects outside, or there is no Entity object. All Entity is an Idx, and operations are performed in the world through this Idx.
- System manages the concerned Entity through the Filter class.
As mentioned above, to process the ComponentA it cares about, System will traverse all the Entities that own the ComponentA. But how to judge which Entity has this ComponentA? The traditional method was traveling all Entities to determine whether it has ComponentA. This solution is obviously not efficient enough. Therefore, the Filter class is introduced here. The core of its method is to change space for time and have a set of judgment rules (receive certain types of components and reject certain types of components). When AddComponent and RemoveComponent or RemoveEntity are performed each time, it will affect the entity. When the operation is performed, all Filters will be notified that an entity has been modified. The Filter will determine whether the entity still meets the conditions (that is, whether there is ComponentA) and choose to retain the entity in the Filter. Then when the System needs to traverse some specific Entity, it can be obtained directly through the corresponding Filter.
- The relationship between Entity and Component can be maintained with a two-dimensional table.
As shown in the above table, the Component number means its index in the Pool, and -1 means no. So Entity1 has components ComponentB, ComponentD. Entity1 has components ComponentB, ComponentC.
The last question is how to convert Entity and Component into 0~N integers to facilitate the construction of two-dimensional arrays?
For Entity, it can be implemented by the self-increment of id, and each time an Entity is created, id++. The component can be uniquely identified based on the enumeration value of the type. Such as the following enumeration values.
export enum ComType {
ComCocosNode = 0,
ComMovable = 1,
ComNodeConfig = 2,
ComBehaviorTree = 3,
ComTransform = 4,
ComMonitor = 5,
ComRoleConfig = 6,
ComAttackable = 7,
ComBeAttacked = 8
}
In this way, the above two-dimensional table can be constructed.
Finally, the ComType can be injected into the corresponding Component class through the ts annotation. Match type and component one by one.
// A Component in the project.
@ECSComponent(ComType.ComMovable)
export class ComMovable {
public running = false;
public speed = 0;
public points: cc.Vec2[] = [];
public pointIdx = 0;
public keepDir = false;
public speedDirty = false;
}
At this point, the framework part has been completed. Let’s show the SysMovable corresponding to ComMovable. This System will calculate the ComMovable state of the next frame according to the current state of ComMovable every frame.
Insert a more detailed introduction to Filter here. The judgment rule of Filter is to accept certain types of components and reject certain types of components through parameter judgment. For example, this parameter [ComMovable, ComTransform, ComCocosNode] means that this Filter saves entities that contain ComMovable, ComTransform, and ComCocosNode components.
const FILTER_MOVE = GenFilterKey([ComMovable, ComTransform, ComCocosNode]);
export class SysMovable extends ECSSystem {
/** update */
public onUpdate(world: ECSWorld, dt:number): void {
world.getFilter(FILTER_MOVE).walk((entity: number) => {
let comMovable = world.getComponent(entity, ComMovable);
let comTrans = world.getComponent(entity, ComTransform);
if(comMovable.speed <= 0 || comMovable.pointIdx >= comMovable.points.length) {
return ;
}
if(!comMovable.running) {
comMovable.running = true;
}
let moveLen = comMovable.speed * dt;
while(moveLen > 0 && comMovable.pointIdx < comMovable.points.length) {
let nextPoint = comMovable.points[comMovable.pointIdx];
let offsetX = nextPoint.x - comTrans.x;
let offsetY = nextPoint.y - comTrans.y;
let offsetLen = Math.sqrt(offsetX * offsetX + offsetY * offsetY);
if(offsetLen <= moveLen) {
moveLen -= offsetLen;
comTrans.x = nextPoint.x;
comTrans.y = nextPoint.y;
comMovable.pointIdx ++;
continue;
}
if(!comMovable.keepDir) {
comTrans.dir.x = offsetX / offsetLen || comTrans.dir.x;
comTrans.dir.y = offsetY / offsetLen;
}
comTrans.x += moveLen * offsetX / offsetLen;
comTrans.y += moveLen * offsetY / offsetLen;
moveLen = -1;
}
if(comMovable.pointIdx >= comMovable.points.length) {
comMovable.speed = 0;
comMovable.speedDirty = true;
}
return false;
});
}
}
Combination of ECS framework and Cocos Creator
Implementing the ECS framework itself is not difficult. The core code is only a few hundred lines, but how to combine this framework with Cocos Creator, or how to display a Node, and can you control Node through ECS?
Take the above ComMovable and SysMovable as an example. ECS itself is more of a logical processing of data, and Entity gets the ability of SysMovable by adding a ComMovable component. Then add a component (ComCocosNode) to the Entity that displays the node, and then pass a System(SysCocosView) that handles the ComCocosNode to achieve the ability to display the node.
- Design components that combine Node in Cocos
Based on this idea, I designed ComCocosNode.
@ECSComponent(ComType.ComCocosNode)
export class ComCocosNode {
public node: cc.Node = null;
public loaded = false;
public events: EventBase[] = [];
}
There is a node property in ComCocosNode. By obtaining the ComCocosNode component through Entity, the node’s properties can be modified, and events are because we have synchronous processing for nodes and some asynchronous processing, such as playing a series of animations, which can be added by adding events. The system does not directly call the component method of the node but allows the component to read the event and process it by itself.
At this time, the node has not been assigned, so I designed another component, ComNodeConfig.
@ECSComponent(ComType.ComNodeConfig)
export class ComNodeConfig {
id = 0; //unique identifier
prefabUrl = ”
layer = 0; // hierarchy
}
Some people may have doubts here. Why not merge the properties of these two components? This is actually for the convenience of configuration. The properties of ComNodeConfig can be directly configured on the table so that it is convenient to configure the students.
- Design a System that handles ComNodeConfig
Finally, through a SysCocosView system, this system handles entities with a ComNodeConfig component but no ComCocosNode component. In each traversal, load the prefab according to the prefabUrl of the ComNodeConfig component to generate the node, add the node to the specified position according to the layer level, then add the ComCocosNode component to this entity, and assign the node value—this way the entity will not be processed next time. The following code is the code after the demo has been completed, and I will not restore it to how it was initially.
const FILTER_COCOS_NODE = GenFillterKey([ComNodeConfig], [ComCocosNode]);
const FILTER_NODE_EVENT = GenFillterKey([ComCocosNode, ComTransform]);
export class SysCocosView extends ECSSystem implements ITouchProcessor {
onUpdate(world:ECSWorld, dt:number) {
world.getFilter(FILTER_COCOS_NODE).walk((entity: number) => {
let comNodeConfig = world.getComponent(entity, ComNodeConfig);
let comView = world.addComponent(entity, ComCocosNode);
let comRoleConfig = world.getComponent(entity, ComRoleConfig);
this._loadView(world, entity, comNodeConfig).then((node: cc.Node) => {
console.log('load view success');
});
return false;
});
world.getFilter(FILTER_NODE_EVENT).walk((entity: number) => {
let comCocosNode = world.getComponent(entity, ComCocosNode);
if(!comCocosNode.loaded) return ;
let eventProcess = comCocosNode.node.getComponent(EventProcess);
if(!eventProcess) return ;
let comTrans = world.getComponent(entity, ComTransform);
eventProcess.sync(comTrans.x, comTrans.y, comTrans.dir);
while(comCocosNode.events.length) {
let event = comCocosNode.events.shift();
eventProcess.processEvent(event);
}
return true;
});
}
}
Write a Behavior Tree
There are also many articles on the Internet for the introduction of Behaviror Tree. If you are interested, you can learn more about it:
• What is a behavior tree?
What is a Behavior Tree? - Opsive
• Behavior Trees For Gaming
https://www.researchgate.net/publication/312869797_Behavior_Trees_for_Computer_Games
The name of the behavior tree is a good explanation of what it is. Unlike Finite State Machines or other systems used for AI programming, a behavior tree is a tree structure containing hierarchical nodes used to control the AI’s decision-making behavior. The very end of the tree, the leaves, are the commands for these AIs to do things; the branches connecting the leaves are various types of nodes, which determine how the AI will follow different situations from the top of the tree to different situations. The path comes to the final leaf in this process.
Behavior trees can be very “deep,” with layers of nodes extending down. By calling sub-behavior trees that implement specific functions, developers can build a library of interconnected behavior trees to make very convincing AI behaviors. Moreover, the development of behavior trees is highly iterative. You can start with a very simple behavior and then make some branches to deal with different situations or achieve different goals, let the demands of AI drive behavior, or allow AI to use fallbacks in situations not covered by the behavior tree, etc.
The last leaf of the tree is the command of what the AI actually does, which can be called behavior. Behavior is a specific action that needs to be written by the user, such as moving to a certain position, attacking, dodging, etc. The intermediate nodes connecting the nodes from the root to the leaves can be called decision nodes. The decision nodes have no actual behavior but decide whether to execute down to the leaf nodes.
So how is it decided?
Working principle
Each node will return a status after execution. There are three statuses: Success, Fail, and Running.
Success and Fail are easy to understand. For example, a monitoring node sees the enemy return a Success but does not see the return and gives a Fail.
But for a node that needs to execute for a period of time, such as moving five steps in 1s and seeing the status of the node in less than 1s, it is unreasonable to return success or failure at this time, so in this case, it should return Running to indicate this node It is still being executed, waiting for the next frame to continue judging.
At this time, we can design such a node whose state is linked to the state of the child nodes, execute the child nodes in sequence, return failure if a node that fails to execute is encountered, and return success if all executions are successful. Such a node can be called a Sequence.
Similar nodes are Selector. The state of this node is to execute the child nodes in sequence. If all execution fails, it returns failure, and if it encounters successful execution, it returns success.
The following is an example of the realization of an actual project Sequence.
/** Sequence node */
NodeHandlers[NodeType.Sequence] = {
onEnter(node: SequenceNode, context: ExecuteContext) : void {
node.currIdx = 0;
context.executor.onEnterBTNode(node.children[node.currIdx], context);
node.state = NodeState.Executing;
},
onUpdate(node: SequenceNode, context: ExecuteContext) : void {
if(node.currIdx < 0 || node.currIdx >= node.children.length) {
// It's out of bounds. It shouldn't have happened. Just consider it a failure.
node.state = NodeState.Fail;
return;
}
// Check that the preconditions are met
for(let i=0; i<node.currIdx; i++) {
context.executor.updateBTNode(node.children[i], context);
if(node.children[i].state !== NodeState.Success) return;
}
context.executor.updateBTNode(node.children[node.currIdx], context);
let state = node.children[node.currIdx].state;
if(state == NodeState.Executing) return;
if(state === NodeState.Fail && !node.ignoreFailure) {
node.state = NodeState.Fail;
return;
}
if(state === NodeState.Success && node.currIdx == node.children.length-1) {
node.state = NodeState.Success;
return ;
}
context.executor.onEnterBTNode(node.children[++node.currIdx], context);
}
};
The combination of these two nodes can achieve the if-else effect. Suppose that when the character is in front of the door, if there is a key, the door will be opened, and if there is no key, the door will be smashed:
- If there is a key, the first child node of the Sequence (checking whether there is a key) is successfully executed, then it will go to execute the second child node (key to open the door). If the Sequence is executed successfully, the following ax-smashing door nodes will not be executed.
- If there is no key, the execution of Sequence fails, then the following ax-smashing door node is executed.
Timeliness of decision
According to some documents I read, the decision for the behavior tree is updated every frame. For example, there is a scene where the user can enter text, enter a move to move to block A forward ten squares, and enter stop to stop block A. Then, for the behavior tree, each frame must determine whether the current user input is moving or stopping to issue a move or stop the behavior.
- For move, the action is a sequence([user input move, move]), replaced by ActionA;
- For stop, the action is sequence([user input stop, stop]), replaced by ActionB;
- The final behavior is select([ActionA, ActionB]).
Sequence means that the sub-behaviors are executed in sequence. If the execution of the sub-behavior fails, it will stop immediately and return the failure. If all the executions are successful, then return the success.
Select means to execute the sub-behavior in sequence. If the execution of the sub-behavior is successful, it will stop immediately and return to success. If all executions fail, return failure.
Suppose now that the user clicks, then each frame needs to be judged and executed from the top layer by layer until the judgment is made and then executed - of course, this is necessary, and behavior needs to determine whether it should be executed.
But this is not very friendly to perform a persistent behavior. Assuming the above scenario, the user enters sleep, and the block stops moving for 2s. It is sequence([user enters sleep, stop moving for 2s]), at this time the behavior tree is select([ActionA, ActionB, ActionC]);
Then when I enter sleep, when the block stops moving, enter a move, then the decision of the next frame enters ActionA, causing the block to move. The act of stopping movement for 2s was interrupted.
This problem I call the timeliness of the behavior tree decision. The decision obtained by the behavior cannot be maintained for a certain period of time. This decision is currently only owned by Sequence and Select.
How to solve it?
The solution may not be optimal since I thought it up independently.
First of all, I added the time-sensitive LockedSequence and LockedSelect. That is, once the decision of the current behavior is made, it must be modified after the current behavior is completely finished.
Introduce a bit of code. When onEnter, set the state of the current behavior to running, and judge in onUpdate. If the current state is not running, return. So once the state is determined, it will not be modified in onUpdate until the next time it enters onEnter.
class NodeHandler {
onEnter:(node: NodeBase, context: ExecuteContext) => void;
onUpdate:(node: NodeBase, context: ExecuteContext) => void;
}
At this time, it is no problem to bring the above scene. When the user enters sleep, the block stops moving for 2s. Entering move within 2s will not cause the decision of ActionC to change until the behavior of stopping moving for 2s ends and enter the next one. ActionA will be entered after the cycle.
But this also leads to another problem, which is parallel behavior. For example, suppose a scenario where soldiers patrol and observe whether there is an enemy. If there is an enemy, stop the patrol and go after the enemy.
The behavior tree is as follows:
- ActionA = Patrol
- ActionB = sequence([observe whether there is an enemy, chase the enemy]);
- repeat(sequence([ActionB, ActionA]))
Because the above method will not modify the decision before the end of the action, the soldiers will first observe whether there is an enemy and then go to patrol if there is no enemy.
My solution was to add a new decision Node that handles parallelism.
Parallel can process child nodes sequentially but does not need to wait for the previous node’s execution to complete the latter one. When any behavior returns failure, exit immediately and returns failure. When all behaviors return success, stop returning success.
The behavior tree is as follows:
repeat(selector([parallel([Inverter(observe whether there is an enemy), patrol]), chase the enemy]))
Note: Inverter means inversion.
At present, if no enemy is found, then the behavior is patrolling, and the parallel is still in the running phase because the patrol will not fail, so the last case is that if an enemy is found, then the parallel immediately returns to failure. The behavior is to chase the enemy.
Finally, show the complete behavior tree in the Demo:
