Game AI Systems
C++ VS Project
Github Link: https://github.com/WatchPigs/AIPractice
Runable demo Download
[New Update]: Behavior Tree
Introduction
Although I often use game AI tools in common commercial game engines, I am trying to implement them from scratch here, including Movement, Pathfinding and Decision Making.
I used C++ and openFrameworks for technical implementation. Openframeworks is a concise framework for drawing shapes, but it does not include any other systems related to games. It allows me to have the opportunity to create low-level systems on my own, working like a game engine programmer.
Physical Movement & Steering Behaviors
Rigidbody
I used the structure Rigidbody ( Rigidbody.h / Rigidbody.cpp ) to represent the state of the character in space. It contains the character's position, orientation and linear and angular velocities. Furthermore, they can receive a KinematicSteeringOutput.h to change their linear and angular velocity directly, or a DynamicSteeringOutput.h to receive linear and angular acceleration to change their velocity smoothly over time.
Kinematic movement
We can create movement algorithms to calculate a target velocity based on position and orientation alone, allowing the output velocity to change instantly. However, if a character is moving in one direction and then instantly changes direction or speed, it may look odd. A worse case would be if the algorithm told the character to seek a position. And if the character is always moving at full speed, it's likely to deviate from an exact position and swing back and forth in successive frames trying to reach that position. This characteristic oscillation looks unacceptable.
We can use some kind of smoothing algorithm to improve it. Here, I created "Kinematic Arrive" ( KinematicArrive.h / KinematicArrive.cpp ) to let the character slow down as it approaches the target and set a satisfaction radius to let it stop when reaching the target.
Kinematic Arrive
Dynamic movement
If we use dynamic steering behavior, that is, using acceleration to change the character's movement, it will be more natural, especially for aircraft and vehicles in water, it will be necessary.
Dynamic Seek ( DynamicSeek.h / DynamicSeek.cpp )is the most direct method that keeps the character accelerating towards the target location. However, it will let the character orbits a bit and ends up oscillating.
Dynamic Arrive ( DynamicArrive.h / DynamicArrive.cpp ) uses two radii, in addition to the satisfaction radius, to let the character end up moving; there is also a slowing radius. The algorithm calculates an ideal speed for the character. At the slowing-down radius, this is equal to its maximum speed. At the target point, it is zero (we want to have zero speed when we arrive). In between, the desired speed is an interpolated intermediate value controlled by the distance from the target. The algorithm looks at the current velocity of the character and works out the acceleration needed to turn it into the target velocity. We can’t immediately change velocity, however, so the acceleration is calculated based on reaching the target velocity in a fixed time scale.
Dynamic Arrive VS Seek
Dynamic Pursue
If we are chasing a moving target, then constantly moving toward its current position will not be sufficient. By the time we reach where it is now, it will have moved. This isn’t too much of a problem when the target is close and we are reconsidering its location every frame. We’ll get there eventually. But if the character is a long distance from its target, it will set off in a visibly wrong direction.
Dynamic Pursue ( DynamicPursue.h / DynamicPursue.cpp ) works out the distance between character and target and works out how long it would take to get there, at maximum speed. It uses this time interval as its prediction lookahead. It calculates the position of the target if it continues to move with its current velocity. This new position is then used as the target of a standard seek behavior. If the character is moving slowly, or the target is a long way away, the prediction time could be very large. The target is less likely to follow the same path forever, so we’d like to set a limit on how far ahead we aim. The algorithm has a maximum time parameter for this reason. If the prediction time is beyond this, then the maximum time is used.
Dynamic Pursue VS Seek
Dynamic Align / Face / Look where you're going
The logic of these algorithms is the same as "Dynamic Arrive", except that they provide angular acceleration, letting the character smoothly accelerate toward the orientation it should be facing. "Dynamic Align" ( DynamicAlign.h / DynamicAlign.cpp ) is to make the character face the same orientation as the target character, "Dynamic Face" ( DynamicFace.h / DynamicFace.cpp ) is to make the character face the relative direction of the target character, and "Dynamic Look where you're going" ( DynamicLookWhereYoureGoing.h / DynamicLookWhereYoureGoing.cpp ) is to make the character face the direction of its own linear velocity. I used polymorphism to implement them with less code.
Dynamic Face
Dynamic Obstacle Avoidance
( DynamicObstacleAvoidance.h / DynamicObstacleAvoidance.cpp )
The moving character casts one or more rays out in the direction of its motion. If these rays collide with an obstacle, then a target is created that will avoid the collision, and the character does a basic seek on this target. Typically, the rays are not infinite. They extend a short distance ahead of the character (usually a distance corresponding to a few seconds of movement). Figure shows a character casting a single ray that collides with a wall. The point and normal of the collision with the wall are used to create a target location at a fixed distance from the surface.
Dynamic Wander
( DynamicWander.h / DynamicWander.cpp )
We can think of kinematic wander as behaving as a delegated seek behavior. There is a circle around the character on which the target is constrained. Each time the behavior is run, we move the target around the circle a little, by a random amount. The character then seeks the target. We can improve this by moving the circle around which the target is constrained. If we move it out in front of the character (where front is determined by its current facing direction) and shrink it down.
Dynamic Wander with Obstacle Avoidance
Dynamic Follow Path
( Path.h / Path.cpp , DynamicFollowPath.h / DynamicFollowPath.cpp )
The basic idea of path following is to calculate the position of a target based on the current character location and the shape of the path. It then hands its target off to seek. The target position is calculated in two stages. First, the current character position is mapped to the nearest point along the path. Second, a target is selected which is further along the path than the mapped point by some distance. To change the direction of motion along the path, we can change the sign of this distance.
I treat the path as a discrete point here to find the nearest point. Here is a problem that sometimes find the nearest point becomes confusing. Here I limit the algorithm to only considering areas of the path close to the previous parameter value. The character is unlikely to have moved far, after all. This technique, assuming the new value is close to the old one, is called coherence, and it is a feature of many geometric algorithms.
Dynamic Follow Path
Dynamic Separation
( DynamicSeparation.h / DynamicSeparation.cpp )
The separation behavior is common in crowd simulations, where a number of characters are all heading in roughly the same direction. It acts to keep the characters from getting too close and being crowded. Most of the time, the separation behavior has a zero output; it doesn’t recommend any movement at all. If the behavior detects another character closer than some threshold, it acts in a way similar to an evade behavior to move away from the character. Unlike the basic evade behavior, however, the strength of the movement is related to the distance from the target. The separation strength can decrease according to any formula, but a linear or an inverse square law decay is common.
Dynamic Velocity Match
( DynamicVelocityMatch.h / DynamicVelocityMatch.cpp )
The logic of "Dynamic Velocity Match" is the same as "Dynamic Align", it makes the character reach the same linear velocity as the target character.
Dynamic Flocking
( DynamicFlocking.h / DynamicFlocking.cpp )
Dynamic Flocking is based on movement patterns of flocks of simulated birds. It relies on weighted blending four simple steering behaviors: move away from boids that are too close (separation), move in the same direction and at the same velocity as the flock (alignment and velocity matching), and move toward the center of mass of the flock (cohesion). The cohesion steering behavior calculates its target by working out the center of mass of the flock. It then hands off this target to a regular arrive behavior.
In the demo below, the blue boid is a leader that moves with "Dynamic Wander", but has a large mass that can significantly affect the state of the center of mass, while the remaining boids moves with "Dynamic Flocking".
Dynamic Flocking
Pathfinding
Directed weighted graphs
For many situations, a weighted graph is sufficient to represent a game level. Directed graphs assume that connections are in one direction only. If you can get from node A to node B, and vice versa, then there will be two connections in the graph: one for A to B and one for B to A. This is useful in many situations. It is not always the case that the ability to move from A to B implies that B is reachable from A. Having two connections in different directions means that there can be two different costs.
I use these to build a basic directed weighted graph: Graph.h / Graph.cpp , Node.h / Node.cpp,
Tile graphs
There are many ways to convert the space in the game world into a directed weight graph. For example, Navigation Meshes (I will try it after completing other parts of the exercise), and Tiled Graphs. Nodes in the pathfinder’s graph represent tiles in the game world. Each tile in the game world normally has an obvious set of neighbors (the eight surrounding tiles in a rectangular grid, for example, or the six in a hexagonal grid). The connections between nodes correspond to a link between a tile and its immediate neighbors. Tile-based graphs are generated automatically. In fact, because they are so regular (always having the same possible connections and being simple to quantize), they can be generated at runtime. An implementation of a tile-based graph doesn’t need to store the connections for each node in advance.
I use these to build the tile graph for the demo: TileGraph.h / TileGraph.cpp , TileNode.h / TileNode.cpp,
Dijkstra's Pathfinding
( Dijkstra.cpp )
Dijkstra's algorithm is a pathfinding algorithm based on breadth-first search and greedy strategy. It has been popular for a long time, and there is a lot of information to describe details (like this). In short, it explores and greedily chooses low-cost paths by storing the cost of visited nodes with two lists.
Here, I demonstrate its process step by step using multithreading and sleep.
Pathfinding Dijkstra
A Star Pathfinding
( AStar.cpp )
The steps of AStar are similar to Dijkstra, but the difference is that when searching and selecting extended nodes, AStar considers not only the explored cost (cost so far), but also the estimated cost to go from this location. This cost is calculated based on another heuristic algorithm.
Here, I used the Manhattan distance as the heuristic to estimate the cost, and it shows that the AStar algorithm has a smaller search range and running time.
Pathfinding AStar
Decision Making
Behavior Tree
Behavior trees present some similarities to hierarchical state machines with the key difference that the main building block of a behavior is a task rather than a state.
Tasks are composed into sub-tree store present more complex actions. In turn, these complex actions can again be composed into higher level behaviors. It is this composability that gives behavior trees their power. Because all tasks have a common interface and are largely self-contained, they can be easily built up into hierarchies (i.e., behavior trees) without having to worry about the details of how each sub-task in the hierarchy is implemented.
Task
Tasks in a behavior tree all have the same basic structure. They are given some CPU time to do their thing, and when they are ready, they return with a status code indicating either success or failure (a Boolean value would suffice at this stage).
Concurrency and termination
In common games, we need tasks to be concurrent and terminable. For example, a character needs to perform a certain behavior while observing the environment and terminate the behavior when the environment changes. In modern game engines, there are Job systems or other systems to provide concurrency.
Here, I use multithreading to implement them. And when a task is terminated, its child or children must be terminated, so I created termination functions for different tasks.
Behavior Tree
( BehaviorTree.h / BehaviorTree.cpp )
The behavior tree class contains a blackboard (which I'll mention below), a root task as an entry point, and references to all the tasks. When the entire tree is returned, it re-executes the root task and loops.
When it is cleaned up, it terminates and cleans up all tasks first, making sure that all resources are properly freed and all threads are properly exited.
Common control flow tasks
Selector
( Selector.h / Selector.cpp )
The selector runs each of their child's behaviors in turn. It will return immediately with a success status code when one of its children runs successfully. As long as its children are failing, it will keep on trying. If it runs out of children completely, it will return a failure status code.
Sequence
( Sequence.h / Sequence.cpp )
The selector runs each of their child's behaviors in turn. It will return immediately with a failure status code when one of its children fails. As long as its children are succeeding, it will keep going. If it runs out of children, it will return in success.
Parallel
( Parallel.h / Parallel.cpp )
The Parallel task acts in a similar way to the Sequence task. It has a set of child tasks, and it runs them until one of them fails. At that point, the Parallel task as a whole fails. If all of the child tasks complete successfully, the Parallel task returns with success. In this way, it is identical to the Sequence task and its non-deterministic variations.
The difference is the way it runs those tasks. Rather than running them one at a time, it runs them all simultaneously. We can think of it as creating a bunch of new threads, one per child, and setting the child tasks off together.
When one of the child tasks ends in failure, Parallel will terminate all of the other child threads that are still running. Just unilaterally terminating the threads could cause problems, leaving the game inconsistent or failing to free resources (such as acquired semaphores). The termination procedure is usually implemented as a request rather than a direct termination of the thread. In order for this to work, all the tasks in the behavior tree also need to be able to receive a termination request and clean up after themselves accordingly.
Decorator
( Decorator.h / Decorator.cpp )
In the context of a behavior tree, a Decorator is a type of task that has one single child task and modifies its behavior in some way. You could think of it like a Composite task with a single child.
Here are some useful decorators down below:
Until fail
( UntilFail.h / UntilFail.cpp )
The "Until Fail" Decorator keep running a task until it fails.
Inverter
( Inverter.h / Inverter.cpp )
The "Inverter" Decorator modifies the status code of the child by reversing it.
Blackboard
( Blackboard.h / Blackboard.cpp )
Blackboard architecture is a software design pattern that is used to create flexible and scalable applications. Blackboard architecture is based on the principle of separating data from algorithms. This separation allows for different algorithms to be applied to the same data, which makes the application more flexible. The complete blackboard system for games has a set of different decision-making tools (called experts in blackboard-speak), a blackboard, and an arbiter.
Here, I use my simplified blackboard just for behavior trees, whichis only used to contain multiple types of data for exchange with other gameplay systems. These data are either atomized or have a corresponding mutex to make the data thread-safe. The code link above is just a very simple base class to be inherited, for details on how to use it check the examples below.
Example: Janitor robot driven by behavior tree
Game mechanics
The character of this demo simulates a janitor robot. When there are trashes in the space, it will go to the nearest trash and clean it up. Each cleaning will consume one unit of its power. When its power is not enough for the remaining trashes in the space, it will go to the nearest charging station to recharge until it has enough power to clean the trashes and return to cleaning them. When there is no trash in the space, it will go to the nearest charging station to recharge to full power. If it has full power, it will wander in the space.
Janitor robot driven by behavior tree video
Behavior Tree Design
Blackboard Design
( BlackboardJR.h / BlackboardJR.cpp )
In the blackboard, I included a series of interactive objects, including trashes, charging stations, and necessary information such as character rigidbody, power, notifications, etc. I have also put the GetSteering functions here(wrapped with std::function). When the character needs the steering output in updates, it only needs to call these functions without having steering behavior objects, which only exist in tasks.
The blackboard also contains a set of functions for accessing its data so that external users don't need to deal with mutexes and locks.
Custom tasks
Detect Trash, Detect Sufficient Power, Detect Full Power
( DetectTrash.h / DetectTrash.cpp ), ( DetectSufficientPower.h / DetectSufficientPower.cpp), ( DetectFullPower.h / DetectFullPower.cpp)
These tasks are used to detect the environment information, and they will check the data on the blackboard and quickly return status codes. When implementing these features, in order for them to execute quickly, I have to avoid the thread being blocked, such as using try_lock() instead of lock() to handle mutexes.
Set Nearest Trash As Target, Set Nearest Charging Station As Target
( SetNearestTrashAsTarget.h / SetNearestTrashAsTarget.cpp ), ( SetNearestChargingStationAsTarget.h / SetNearestChargingStationAsTarget.cpp)
These tasks will also be executed very quickly, and what they do is quickly check and modify the data on the blackboard. For example, one of them will search the nearest garbage and set the target pointer point to it.
Move to target
( MoveToTarget.h / MoveToTarget.cpp )
It contains two steering behavior objects: dynamic arrive and kinematic stop. When the task starts, it will call new requests of these steering behavior objects by using the character rigidbody and target rigidbody on the blackboard, and register the get steering function on the blackboard for the character to use in main updates of game loop. Then it will keep checking if the steering behavior is completed in while loop. Each steering behavior will be processed one by another. If all steering behaviors are completed, return true; Otherwise, if it is terminated externally, it will return false.
Tidy Trash, Recharge
( TidyTrash.h / TidyTrash.cpp ), ( Recharge.h / Recharge.cpp )
IThese behaviors simulate the character's interactions with interactable objects. So, I used sleep() to create a delay to simulate the time spent on the behaviors, but the delay was fragmented by the for loop so that the task could be terminated at any time. (Similar to waiting for a task). And they contain modifications to the data on the blackboard, and they will return true when the modifications have been finished.
State machine
Sorry, I'm still working on it. Once I have it done, I will update it here...