�ݺ�ߣ

The Polling Problem

Speaker Name
Dino Dini NHTV University of Applied Sciences

A bit about me
I have been designing and programming video games for
over 30 years.

I am originally from the UK, live in the Netherlands and
now teach Video Game Programming at NHTV in Breda
(IGAD).

I am quite well known in the VG industry outside of the
US for making a series of games concerned with an
obscure sport known as Football, not to be confused with
the US popular sport "Handegg".

The focus of this talk
A = Autonomous
I = Interactive

Computers and their languages are generally good for A
and less good for I.

My focus is solving the problem at the programming
language level, rather than through the creation of
virtual machine architectures (such as Behaviour Trees).

Roman Numbers

The Romans had no symbol for 0.

The result was that it held back their development of
technology and science.

Doing Nothing

Do we lack an appropriate representation in computer
science for doing nothing?

Turing's Vision
Turing was a mathematician, and was interested in
computers as a device for solving problems.

Mathematically, there was no concept of doing nothing.

Data In, Data Out

IMMUTABLE COMPUTER IMMUTABLE
INPUT DATA ALGORITHM OUTPUT DATA

The program runs. The program terminates, all might be well.

The program runs. The program never terminates. Disaster.

If the program terminates before it has finished its job, that's an aberration.

Why on earth should one want to stop the program, apart from being too impatient to wait?

Doing nothing makes no sense; simply do not run the program.

It's a function, Jim
Computers were developed to process data in the manner of a function.

We would like these to execute in zero time.

Is the temporal nature of computation merely an inconvenience?

The interactive world is ongoing
The interactive world does not fit this model well.

Tasks take time and need to pass information between each other
asynchronously.

Computations must contend with mutable input data.

Mutable input data
We normally do not consider the possibility that the input data could change
while we perform computations on it...

What is the square root of 345 ?

OK working on it...

Nearly there...

Wait, sorry I meant 346...

!@@#$@!!

Mutable input data
This is unfortunately common in the real world, and a necessity in effective
game AI.

My GPS loves to say "Recalculating..."

The Polling Problem
Q: What do you get when you try to process unpredictable and time
dependent input with a Turing machine?

The Polling Problem
Q: What do you get when you try to process unpredictable and time
dependent input with a Turing machine?

A: A polling loop

While(!EscapePressed()) { // ugh, there must be a better way
if(pathPlanner->ExecSingleStep()) {
break;
}
}

Say "When"
While(true) {
if(!GlassAcceptablyFull()) {
// erm... do nothing???
yield();
} else {
Say("When!");
break;
}
}

Say "When"
While(true) {
if(!GlassAcceptablyFull() &&
GetGlassStatus() == Normal) {
// erm... do nothing???
yield();
} else {
Say("When!");
break;
}
}

Say "When"
// Pourer
While(true) {
if(!Heard("When!")) {
KeepPouring();
yield();
} else {
StopPouring();
}
}

Say "When"
// Pourer
While(true) {
if(!Heard("When!") && !GlassFull()) {
KeepPouring();
yield();
} else {
StopPouring();
}
}

If and When

If
● A change in state
● Dependent on current state
● When the If is executed
When
● A change in state
● Dependent on resulting state
● When a specified state change occurs

When?
Computers are not really designed for When. They are designed around
procedural logic, effectively a series of ifs executed in a sequence.

When is actually a more natural way to express responses to time
dependent input.

When you have Messages
The typical solution is to use messages, but this does not directly solve the
polling problem.

"When you get the message, do something else"
// pseudocode
function WaitForGlassFill() {
messageHandler = new Handler(OnGlassAcceptablyFull,
delegate(Message m) {
// code executed on message
// Exit from doing nothing
// But how?
});

SetAnimationState("ObserveFilling");
while(true) { // do nothing
Yield();
}
}

You have to keep checking for data changed by
message handlers
// pseudocode
int onMessage=0;
bool stopFlag;
messageHandler = new Handler(eOnGlassAcceptablyFull,
stopFlag = true;
onMessage = eOnGlassAcceptablyFull;
});
while(!stopFlag) { // do nothing
Yield();
}
switch(onMessage) { // ..etc..

You have to keep checking for data changed by
message handlers
// pseudocode
int onMessage=0;
bool stopFlag;
messageHandler = new Handler(eOnGlassAcceptablyFull,
stopFlag = true;
onMessage = eOnGlassAcceptablyFull;
});
SetAnimationState("ObserveFilling"); Hello, Polling
while(!stopFlag) { // do nothing
Yield();
}
switch(onMessage) { // ..etc..

I wish I could simply say...



When(ReceivedMessage(eOnGlassAcceptablyFull)) {
SayWhen();
StartNormalAnimationState();
End; // this will stop this coroutine
}

DoNothing(); // until coroutine terminated

}

I wish I could simply say...



SayWhen();
StartNormalAnimationState(); Here I have a trivial case,
but maybe I want some
End; // this will stop this coroutine
other tasks going on here
} too, like watching out for
a sniper.
DoNothing(); // until coroutine terminated

}

I want reusable behaviours

// anything can pause, it's a substate
// needs to be interruptible!

function Pause(int _count) {

int count=_count;

while(count-- > 0) {
yield;
}

end;

}


SayWhen();
end;
}

while(true) {
Pause(Random(25,50));
GlanceAtRandomPointOfInterest();
yield;
}
}


SayWhen();
end;
} This needs to be
interuptable when
WaitForGlassFill handles a
while(true) { message and switches
Pause(Random(25,50)); task.
yield;
}
}


SayWhen();
end;
}
And what if we want to do
something that is not
while(true) { instantaneous?
yield;
}
}


SayWhen();
Pause(50);
end;
}

while(true) {
yield;
}
}


SayWhen();
Pause(50);
end;
No! Can't do this. It would
}
cause the calling object to
Pause (at best).
while(true) {
yield;
}
}

Messages must change the "program counter"
SwitchTo(GlassFullEnough);
}
State(Normal):
while(true) {
yield;
}
State(GlassFullEnough):
Pause(50); // delay before responding
// etc
}

Messages must change the "program counter"
SwitchTo(GlassFullEnough); This concept is going
} against the grain of most
State(Normal): programming languages
and computer
while(true) {
architecture.
GlanceAtRandomPointOfInterest(); It has to be faked.
yield;
}
State(GlassFullEnough):
Pause(50); // delay before responding
// etc
}

Why Game AI is Difficult - Summary
● No direct language support for multitasking
● Where such support exists, there remains a lack of semantics for
switching execution state synchronously (that is, without polling)
● Polling does not scale well
● Complex time dependent interactions mean that without a proper
methodology behaviours must be kept simple to reduce complexity

Polling would seem to be at the heart of the problem.

Solutions should focus on this problem.

Typical solutions involve the creation of a virtual machine with a separate
domain specific language or encoding of programs in data structures rather
than code.

Virtual machine solutions

Script

Virtual Virtual
Real Domain
Machine Machine:
Machine Specific
(C#) Behaviour
(C++) Language
Trees

Multi-tasking
support
(yield)

Virtual machine solutions

Script

Virtual Virtual
Real Domain
Machine Machine:
Machine Specific
(C#) Behaviour
(C++) Language
Why can't we just
Trees
have a single
language as the
Multi-tasking solution?
support
(yield)

Traditional: A light switch
// With polling
function LightSwitch() {
bool lit=false;
while(true) {
if(Switch.state == "Down" && Switch.previousState == "Up") {
lit = !lit;
SetLightState(lit);
}
yield;
}
}

Traditional: A light switch with delay
Timer startTime; bool lit=false;
while(true) {
if(Switch.state == "Down" && Switch.previousState == "Up") {
if(lit) { lit = false;
SetLightState(lit);
} else { lit = true;
startTime = CurrentTime();
SetLightState(lit);
}
}
if(lit && CurrentTime()-startTime > MaxOnTime) {
lit = false;
SetLightState(false);
}
yield;
}
}

Messages: A light switch
// Oh nice this is now trivial...
// But only because there's no temporal behaviour

bool lit=false;
When(ReceivedMessage(eSwitchPressed)) {
lit != lit;
SetLightState(lit);
}
}

Messages: A light switch with delay
Timer startTime;
bool lit=false;
When(ReceivedMessage(eSwitchPressed)) {
if(lit) { lit = false;
SetLightState(lit);
} else { lit = true;
startTime = CurrentTime();
SetLightState(lit);
}
}
while(true) {
if(lit && CurrentTime()-startTime > MaxOnTime) {
lit = false;
SetLightState(false);
}
yield;
}
}

No Polling: A light switch
// pseudocode of language supporting coroutines, messages
// and state transitions
bool lit=false;
while(true) {
state UnlitState:
when(ReceivedMessage(eSwitchPressed)) { goto state LitState; }
lit=false; SetLightState(lit);
substate(DoNothing());
state LitState:
when(ReceivedMessage(eSwitchPressed)) { goto state UnlitState; }
lit=true; SetLightState(lit);
}
}

No Polling: A light switch with delay
// pseudocode of language supporting coroutines, messages
// and state transitions
bool lit=false;
while(true) {
state UnlitState:
lit=false; SetLightState(lit);
state LitState:
lit=true; SetLightState(lit);
substate(Pause(50)); // That was easy to add!
}
}

PROC system: A light switch with fade
function FadeTo(float to) {
do { float d = (to - light.currentBrightness)*0.1f;
light.currentBrightness += d;
if(d < 0.001f) {
end;
} } }
Timer startTime;
bool lit=false;
while(true) {
state UnlitState:
substate(FadeTo(0));
state LitState:
substate(FadeTo(1));
} }

The PROC system
● Started as coroutine system in 68000 assembler

● Later implemented in C and C++ where messages were added

● Most recently implemented in C# in Unity 3D

The PROC system
● Implements a HFSM with message handling protocols

● Implementation uses nested coroutines

● Has proven very effective at managing complex behaviours

● A solution within the programming language itself

PROC system architecture in C# and Unity 3D
IEnumerator method (a PROC)

Control object with a stop flag

looped switch statement

states Message handlers
Message handlers
states

Straight code

Substate iterators (polling for stop flag)

PROC system message handling
Under Attack
Base

Noise heard
Patrol

Goto next patrol point

Goto position

Under Attack
Base

Noise heard
Patrol

Message manager
Noise heard

Goto position

Under Attack
Base

Noise heard
Patrol

Message manager
Noise heard

Terminate
Goto position

Under Attack
Base

Noise heard
Patrol

Message manager
Terminate Noise heard

Under Attack
Base

Noise heard
Patrol

Message manager

Investigate Noise
Noise heard

Under Attack
Base

Noise heard
Patrol

Message manager

Investigate Noise
Noise heard

…

Implementation in C# / Unity 3D
● Currently uses a pre-processor

● Message handlers are delegates inside methods that can access local
variables of the method

● Termination of a task is implemented using a flag which is polled for

● However, this polling is hidden

Conclusion
● At the heart of the difficulty of robust and rich behaviour in games is the
limitations of popular programming languages
● Many popular solutions create a virtual machine to avoid these problems,
often encoding the behaviours in data structures with domain specific
languages.
● However, with some small additions to existing languages, this problem
could be avoided
● Even without such languages, it is possible to create architectures that
solve the problem directly within the language (albeit inelegantly).

Conclusion
● The core problem is how to manage the response to input data that
changes over time
● This input data is not only from the player, but also between concurrent
tasks
● Polling is inescapable, but can be managed

Conclusion
● To solve these problems, which are connected not only with game AI, but
also with the general problems of scalable multi-tasking programs, you
can use this heuristic:

"Design your architecture to hide the
polling problem as much as possible"

Thank you
Dino Dini

email: dndn1011@gmail.com
Twitter: dndn1011

�ݺ�ߣ

The polling problem

Recommended

More Related Content

Similar to The polling problem (11)

The polling problem