AI objects: DecisionNode
When designing the bot AI, the question that comes over and over is
"what should the bot do now(next)?".
To answer that question, starting from high level concerns, the bot-ai designer must identify and formalize the nature
of the next choice to be made( does it pertain to a destination to reach, a weapon to fire, a tactical manoeuver to execute...).
each nature of choice is then hard-coded as a DecisionNode class
( derived from a DecisionNodeBaseClass class), which is created( instanciated) then
executed when the decision/choice has to be made. The bot-ai designer must take
care about keeping each decision as "atomic" as possible in order to avoid rapidly locking the bot into
a too restricted set of possible variables/behaviours. This is also helps in the process of
re-considering past decisions due to changes in the world: the more "atomic" the decisions, the more "surgical"
the later decisions validation/invalidation+recomputation process.
Making a decision , ie executing a DecisionNode
Executing a DecisionNode means performing basically four steps, two of them involving sub-systems.
The two sub-systems are:
.
the SelPerceptionSystem: it is run to get all the data relevant to the decision that is not readily available to the bot; these depend on the nature of the decision but also on the parameters/variables required as input by the SelectionSystem.
.
the SelectionSystem: it is run to propose a unique decision among all possible outcomes as defined by the ai-designer.
The four steps are:
1. -execute the SelPerceptionSystem.
At this stage, the values of all the variables influencing the decision process, called the "context" of the decision, are known.
Some variables are the outputs of the SelPerceptionSystem. The other variables are readily available,
like those deriving from decisions made at higher levels in the decision tree
, ie decisions already made that lead to the considered DecisionNode.
2. -(optional) set some parameters of the SelectionSystem ( eg constraints on some variables to be selected, requirement for a partial or sub-optimal execution of the selection routine,...);
3. -execute the SelectionSystem.
4. -implement the decision, ie at least store the "volatile" proposal output of the SelectorSystem
in a dedicated bot variable so it is persistent, making it available to the other processes by the same token.
Then perform complementary computations related the decision made if needed.
Endly, as a DecisionNode is "atomic",
a particular outcome will in most cases not set all bot variables; it will lead to
another decision to make ie to another DecisionNode one step lower in the decision tree ( the sequence of
"what to do?" questions and answers progessively narrows the options):
in this case, a child DecisionNode dealing with the decision to be made is instanciated,
that will immediatly performs the same four steps.
A pointer to its child is actually returned by the DecisionNode execution member function.
So the thinking process of the bot is conceptually a decision tree, where the decision nodes are hard coded,
but the only instanciated data-structure is not the tree but the
(made) Decisions Path. The Decisions Path is a linked list,
starting at the root node TopLevelDecisionNode, of DecisionNodes
selected by their parent DecisionNode.
In other words, this list represents the state of the whole decision process once fully performed.
Secondly, using such a list winds up to a skeleton of an "AI-engine", looping until no child DecisionNode
is created by the current node:
DN_ct * p=& TopLevelDecisionNode;
while( p)// p is a pointer to the current DecisionNode, ie the last on the Decisions Path
{
p= p-> exec();// make a decision and possibly return a pointer to a child DecisionNode
}
In almost all cases, the sequence of selected DecisionNodes will end
by a node the implementation step of which requires one or more
processes that cannot be completed in one (the current) frame: these "non-null-time" processes are called
Tasks and are also implemented as classes deriving from a TaskBase base class. They basically refer to bot actions ( reloading its weapon, navigating along a waypoint path, walking on a straightline to a near and reachable point,...), but may also refer to non-gameplay
processes sliced over several frames because they are too CPU consuming( eg: a SelectorSystem like A*).
A Decision Path must never be designed to include twice the same task nor conflicting tasks.
It is a progressive refinement of consistent decisions and tasks.
Hence, when a DecisionNode creates only Tasks, its child DecisionNode is NULL
and the AI-engine stops for that Decision tree.
When a DecisionNode creates a Task, it feeds the Task with the set of variables
the Task requires to be executed: Commands (ie Goals, WishedValue,..) and sometimes Constraints ( like max speed,...) and a pointer to its parent/creator.
The DecisionNode owns the Task( it creates it and is in charge of its deletion),
but it inserts a pointer to it in a "Task-to-be-executed" list where all the Tasks are sorted by priority ( highest on the top).
The "Task-to-be-executed" list at bot level is in general fed in by more than one decision tree:
the bot, like a human player, has different and possibly conflicting standpoints, like Survive vs Complete-the-mission.
the SelPerceptionSystem
The first move is to implement it as a component of the DecisionNode,
especially if it is specific and uses a lot of CPU time. Still, more often than not,
its Perception action is actually performed in the generic bot Perception phase occuring before the AI phase,
mostly because the same data is used by many bot-ai processes.
the SelectionSystem
It is encapsulated in the DecisionNode. It is activated by the DecisionNode whenever
a selection is required ( like a real decision maker would require the advice of an expert).
It does not change any world state excepting its own, and its member variables
if any -including the ouput "proposal"- are meaningless once the Decision Maker which
called it returns from its exec() function.
Its practical "life" is restricted to the selection process, ie it can be created when
a selection is required and deleted when the selection is completed.
This implementation allows for the same DecisionNode to call different SelectorSystems as
blackboxes ( very useful for debugging), and for the same SelectorSystem class to be used
in different DecisionNodes.
Examples of SelectionSystems:
- the simplest one which returns always the same value: this obviously does not deserve an implementation as a class ( except for easy substitution ) but a simple line of code as "proposal= FixedValue;"
- a randomizer returning a random value within a fixed or given range, with a given distribution function: this also does not require an implementation as a class, but just by a call to the a randomizing function with possibly some arguments as "proposal= random(x,y,...)"
- A*( the A-star shortest path algorithm), or the Floyd matrix.
- a firefight optimizer, which select the best ( target, weapon, weapon mode) triplet.
- optimizers which do not select values as above, but select processes.
When are decisions made, ie when are DecisionNodes executed?
The AI-skeleton-engine presented hereabove provides an answer, but it has to be modifed:
it is implicitely assumed that the AI-skeleton is run each frame, starting at the top nodes, and making a decision in each DecisionNode.
This is wrong, for at least 2 reasons:
-firstly because some SelectionSystems are too CPU consuming to be fully executed each frame( eg: A*, my (target, weapon, weapon mode) triplet combat optimizer),
-secondly because the player the bot is supposed to simulate does not change his/her mind every frame.
This justifies the introduction of
DecisionNodes Activation: by definition, an existing DecisionNode that becomes activated must be executed ( ie its decision process must be called), but not necessarily right afterwards.
In the AI-skeleton-engine, Activation is implicitely triggered right after the child DecisionNode is created, and execution follows.
Now separating Activation from execution allows for Activation checking on already existing DecisionNodes ( created in a previous frame) to happen before and even outside the AI loop from above, and also selectively.
Reducing polling requirement
The Activation causes outside DecisionNode creation are:
a. a Decision Path has no Task ( resulting from a previous frame deletion of its Task(s) during conflict solving): its top level node is activated.
b. a child Task is completed or cancelled: its parent is immediatly aware through a call from the Task of its parent ontaskCompletion() member function; this does not require polling.
c. the game world changes between frame, so the context for a given DecisionNode is different
from the one that justified its creation.
For a DecisionNode that is influenced by an
event that occurs only from time to time,
the perception process for this event is moved out of the PerceptionSystem of the node.
The event generator is implemented as a Publisher and the DecisionNode subscribes once at its
creation time as an Observer to this Publisher (
Observer/Publisher pattern).
the DecisionNode is consequently implemented with a function in charge of processing events received:
polling on that event is no longer required, and not running the
AI-engine each frame does not prevent from catching key events nor creates delay in event acknowledgement.
When more than one node is Activated in the Decision Path, only the highest level
node needs to be activated, not necessarily the Top level node.
Reducing the DecisionNode decision process CPU use
Instead of making a ( fully optimized) decision ( implicitely from scratch) for each
already existing Activated DecisionNode, one can consider to only
check if the
current decision
is
still acceptable. Being acceptable covers different criteria, which greatly enhances flexibility.
Partial optimization is also interesting, for DecisionNodes deciding two or more variables( typically firefight decisions which select a target, a weapon and a weapon mode).
When an activated and already existing DecisionNode has run ( part of) its decision process,
and whenever the selection output happens to be the same as before, its child remains
the same and there is consequently no need to consider its children down the current
Decisions Path ( except the first one which is activated if any).
