Portfolio von
Immanuel Scholz
Table of Content
AI - Design in NightwatchThe problem of flow logic
Polling or Events?
Strategy lists
Resumé
New Insights
AI - Design in Nightwatch
AI is often a big state machine. Every agent contains one or more states and at every frame, he interacts regarding to these states. A transition of states either happen as response of events (event system) or as designated queries during the execution frame of the AI (polling). I made bad experiences with big state machines in the past. The number of different states are growing quite quickly. Hidden dependencies (cross-agent dependencies not explicitly modelled as states) are a big problem. They increase the complexity of the state machine a lot. In the worst case, the number of logical states for all other agents double for every additional state to one agent. Polling kills performance. Ways to increase perforamce are often complex and clumsy and bring a lot of other problems (complex data structures, caches). On the other hand, event systems are typical harder to read and understood. The flow logic is hard to follow and feels unnatural. Many events have to be cached. If caching is avoided, bursts happen. (Punctual performance break, mostly because event handler do too much logic). The program logic is spread over the code and time. This increases the problem of hidden dependencies.The problem of flow logic
What do I mean when saying "unnatural flow logic" when using event systems? I'd like to demonstrate this with a small example. Imagine, a unit (an agent) should run toward an enemy, attack him and go back to its original place. Using "polling", this would look like: ngspunkt zurückkehren. Mit "polling" würde das so aussehen:
// pseudo code, not from Nightwatch
void Unit::update()
{
if (!unit_.touches(enemy_)) // collision polling.
{
moveToward(enemy_); // moves one step
return;
}
if (enemy_.isAlive())
{
attackEnemy(enemy_); // attack one time
return;
}
moveToward(origPosition_);
}
About the problem when enemies die because of other things, see below.
The function is pretty simple and easy to follow. Please note, that update
must not block for a longer time, but has to do only a short update of the
units state. This problem is independend from "events vs. polling" and
discussed elsewhere.
Using an event system, a typical implementation would look like this:
// pseudo code, not from Nightwatch
void Unit::init()
{
CollisionManager::touchingEvent().connect(&onTouching);
enemy_.destroyedEvent().connect(&onVictory);
}
void Unit::onTouching(const Enemy& e) {if (e == enemy_) state_ = ATTACK;}
void Unit::onVictory(const Unit& u) {state_ = MOVE_BACK;}
void Unit::update()
{
switch (state_)
{
case MOVE: moveToward(enemy_); break;
case ATTACK: attackEnemy(enemy_); break;
case MOVE_BACK: moveToward(origPosition_); break;
};
}
For programmer who are used to event systems, this may not look too complex,
but it definitely has a bigger potential to get messed up.
Polling or Events?
It's unlikely, that I run into real performance troubles because of polling in such a small project, so this is a nice scenario to try out polling. Due to my work with Java and Swing, I feel familar with event systems, so I wanted to try the pros and cons of polling. I wanted to test whether it's worth the effort or even hurts the code. My specific hopes were:- I can avoid complex event systems. The flow of logic is not spread.
- When parting complex states into sub strategies, I can minimize the number of cross-agent dependencies
Strategy lists
First of all, I model states as objects, called "strategy". Instead of giving every unit only one active, I gave them a stack of strategies. On every tick, the top-most strategy will be executed. Examples for strategies are "deal damage to X" or "flee from Y". A strategy can end itself and is then removed from the stack. At the next tick, the previous strategy (now beeing at the top of the stack) is executed. This way, strategies have a very simple way of "calling substrategies" by just pushing them on the stack. Complex actions are broken up into a set of simple strategies. For example, an arrow shot by an archer gets the two strategies "move" and "suicide" (deal damage and kill yourself). Another example: "Forward" from the zombies first look for enemies in its sensing range (polling). If found, it writes "chase" on the stack. If not, it tries to move the zombie towards the city. If the zombie bumbs into an obstacle, it pushes "pillage". If the substrategies like "chase" and "pillage" finished, "forward" is executed at the next tick automatically.Resumé
Up to now, my hopes have fulfilled partially. I liked the ease of changing to sub strategies. Using the stack enables a very easy way of modelling state transitions, which is also easy to understand for programmers. Complex strategies were still easy to model. As example, the logic for the described "Forward":
void Forward::update(float elapsed)
{
auto p = nearestEnemy(unit.pos, unit.party);
if (p.enemy && p.distance < unit.sense
&& lineOfSight(unit.pos, p.enemy->pos))
{
// I see someone. CHARGE!
unit.addStrategy(new Chase(unit, *p.enemy, true, true));
return;
}
// steer towards the target destination, if completely out of order
float alpha = Vector::normalize(unit.direction)-direction;
if (abs(alpha) > 0.25)
{
unit.direction -= alpha * elapsed;
return;
}
Vector d = Vector::polar(unit.direction, unit.speed) * elapsed;
// sometimes, change direction a bit (dizzy walking)
if (randf() < elapsed*unit.speed)
{
if (d.cross(target) > 0)
d = d.rotate(randf()/4-0.1f); // rotate clockwise
else
d = d.rotate(-(randf()/4-0.1f)); // rotate counter-clockwise
}
if (!unit.tryMove(d))
unit.addStrategy(new Pillage(unit, unit.pos + d));
}
In fact, this version of "forward" does more: it's implementing some kind of
strolling (dizzy walk), which improves the "BRAAAAIIIINNNSS" - feeling of the
zombies. Beside, it rotates the unit slowly, if its looking in a complete out
of order direction. Units don't have inertia in Nightwatch. This code
compensates a bit for this lack of realism.
It is interesting, that neither "chase" nor "pillage" have to know anything
about "forward". For example, "chase" is also used by human footmen.
However, using an event system for signaling the destruction of resources was
the much simpler concept. When units die, this usually affects strategies
"down in the stack" too. If a unit gets deleted, these strategies have dangling
references.
To test for the deletion of resources with polling, one would have to either
introduce another indirection (cp. std::tr1::weak_ptr) or the resource is
artifactial kept alive and get some flag "isDestroyed". It will be deleted only,
if it is not used by anyone anymore. In fact, this means the resource owns
itself. (The last approach is very common in languages like Java.)
In Nightwatch is the existance of resources strongly managed by the owner
of the resource. I decided to signal destruction of resources by events.
Modeling dependencies between strategies is harder using the stack. Example:
The peon gets the strategy "move to X" and "grab bonus Y". If the bonus vanishes
while the peon is still moving, the "grab" strategy quits nicely (it's
listening to the destruction signal). But the move strategy doesn't get
cancelled. The dependency between "grab" and "move" has to be modelled.
("Move" could listen to the destruction of "grab" or the bonus, but why should
"move" know anything about those? It's used in quite different contexts too.)