Transcript Chapter_12-Actor Behaviorx

Chapter 12:
Implementing Actor
Behavior (“AI”)
Initial Questions
What is Artificial Intelligence?
What is the purpose of Artificial Intelligence
in games?
Concerning Terminology:
This Chapter will deal with an aspect of game
design that is commonly called “Artificial
Intelligence”. As this term is inherently vague
and frequently misused, we will instead be using
a more Greenfoot-specific term:
Actor Behavior
For the purposes of this Chapter, Actor Behavior
will refer to any algorithmically generated (i.e.
Non-Player) Behavior exhibited by an Actor
within a scenario.
Importance of Actor Behavior
Any game that implements moving (or otherwise
non-static) Actors needs to find a way to
actually create that Behavior. Greenfoot is not
providing any kind of “default” or “dummy”
Behavior.
The specific implementation of Actor Behavior
can have a significant influence on how well a
game is able to achieve its goals.
Implementing Actor Behavior
We will examine 4 kinds of Actor Behavior:
A)
B)
C)
D)
Deterministic Behavior
“Optimal” or Greedy Behavior
Random Behavior
Constrained Random Behavior
Implementing Actor Behavior
We will be using a
modified version of the
classroomScrolling
scenario for this
chapter.
Specifically, we will
focus on the Boss-class
and how we can
implement its behavior.
Implementing Actor Behavior
What is the goal of the Boss “Character”?
What is our goal when designing the Boss
Behavior?
Deterministic Behavior
Deterministic Behavior refers to a class of
Behavior where every individual action (and thus
the observed Behavior in general) is
predetermined and can be predicted.
Strictly Deterministic Behavior is not influenced
by context (such as the movement or presence
of other Actor objects) or randomness.
Examples of Deterministic
Behavior
Do not take any actions
Examples of Deterministic
Behavior
Move in a straight line
Examples of Deterministic
Behavior
Move one cell up, then one cell forward, then
one cell forward, then one cell down
Implementing Deterministic Behavior
Design a non-trivial
Deterministic Behavior for
the Boss class. You can
take the following actions:
a) Fire a Bullet
b) Change the Boss´s xCoordinate
Implementing Deterministic Behavior
Deterministic Behavior
for the Boss class:
Constantly move left or
right.
If you reach the end of
the screen turn the
other way.
Fire every 20 act cycles.
Implementing Deterministic Behavior
public void behavior() {
if (fireDelay == 20) {
fire();
fireDelay = 0;
}
fireDelay++;
if(getX() == 5) {
direction = 1;
}
if(getX() == getWorld().getWidth()-5) {
direction = -1;
}
setLocation(getX()+direction, getY());
}
Deterministic Behavior
(Strictly) Deterministic Behavior is relatively
easy to implement and can be useful for certain
tasks (such as obstacle avoidance).
However, it can also appear predictable,
insufficiently dynamic, non-reactive and
“lifeless”.
Note: Sufficiently complex deterministic
behavior can appear to be random (or at least
non-predictable).
Deterministic Behavior
While the initial placement is random, this (too)
is Deterministic Behavior
Greedy Behavior
Greedy Behavior refers to a class of Behavior
where every action is “locally optimal”.
I.e. during each “action-cycle” (usually one call
to the act() method) the Actor always takes the
action that most directly advances its goal.
Unless the scenario itself is static, Greedy
Behavior is necessarily influenced by context
(such as the movement of other Actor objects).
Examples of Greedy Behavior
Shortest Path (“Travelling Salesman”):
What would be a “locally optimal” move?
Examples of Greedy Behavior
Always travel to the next closest unvisited
point:
Implementing Greedy Behavior
Design a possible Greedy
Behavior for the Boss
class.
What is the goal the Boss
is trying to achieve?
Considering this goal,
what would be an
“optimal” action?
Implementing Greedy Behavior
Greedy Behavior for the
Boss class:
Move to the same xcoordinate as the
Rocket.
Fire every act cycle.
Implementing Greedy Behavior
public void behavior() {
fire();
List<Rocket> rockets = getWorld().getObjects(Rocket.class);
for(Rocket a: rockets)
setLocation(a.getX(), getY());
}
The Boss fires constantly.
Implementing Greedy Behavior
public void behavior() {
fire();
List<Rocket> rockets = getWorld().getObjects(Rocket.class);
for(Rocket a: rockets)
setLocation(a.getX(), getY());
}
The Boss tracks the
movement of the Rocket.
Greedy Behavior
Greedy Behavior is comparatively easy to
implement, assuming a clear goal can be
identified and the number of possible
actions is relatively limited.
However, Greedy Behavior can be
simplistic, frustrating for the player and
generally not “fun” to compete against.
Also note that Greedy Behavior does not
necessarily result in the most efficient
Behavior.
Random Behavior
Random Behavior refers to a class of Behavior
where actions are executed or not executed
depending exclusively on the result of a random
operation.
The exact nature of the random operation is
irrelevant, assuming it is sufficiently random.
Implementing Random Behavior
Random Behavior for
the Boss class:
Move left with 50%
probability. If you are
not moving left, move
right.
Fire with 50%
probability each act
cycle.
?
?
?
Implementing Random Behavior
public void behavior() {
int random = Greenfoot.getRandomNumber(2);
if (random == 0) {
setLocation(getX()+2, getY());
}
else {
setLocation(getX()-2, getY());
}
random = Greenfoot.getRandomNumber(2);
if(random == 0) {
fire();
}
}
Movement is random and not constrainted
by previous actions. Every act cycle can
change where the Boss is moving.
Random Behavior
Unconstrained random behavior can appear to
be either exceedingly erratic or insufficiently
dynamic. Especially unmodified random
movement (“coin-flip”) is problematic.
While including an element of randomness in
Actor Behavior is usually desirable, it needs to
be “constrained”.
Constrained Random Behavior
Constrained Random Behavior is still based on a
“Seed” of randomness, meaning it is generally
non-deterministic.
However, the randomness is modified by various
constraints that impose restrictions on how
random the Actor behaves.
We can think of Constrained Random Behavior as
“unpredictable behavior within predictable
parameters”.
Examples of Constrained
Random Behavior
Start at a random position
(within a fixed quadrant)
Examples of Constrained
Random Behavior
Spawn with a
randomized
movement Vector
(with a direction
component
between 75 and
104 degrees)
Implementing Constrained Random
Behavior
What Constraints could we impose
on the Boss character
to improve his behavior?
Implementing Constrained Random
Behavior
We will impose the following constraints on our
Boss Behavior:
- There is a high chance that no Bullet is fired
each turn (no “coin-flip”)
- If the Boss is within 50 pixels of a border, it
move in the opposite direction
- Once the Boss has started moving in a certain
direction, it stays committed to that
movement for at least 20 act cycles
Implementing Constrained Random
Behavior
private int movementTimeDelay = 20;
private int movementTime = 0;
private int direction = 0;
public void behavior() {
int random = Greenfoot.getRandomNumber(20);
A Bullet is only
fired 5% of the
time.
if(random == 9) {
Bullet bullet = new Bullet (new Vector(0,0), 90);
getWorld().addObject (bullet, getX(), getY()+40);
bullet.move ();
}
movementTime++;
setLocation(getX()+direction, getY());
Implementing Constrained Random
Behavior if(movementTime > movementTimeDelay) {
if (getX() > 350) {
direction = -1;
movementTime = 0;
}
else if (getX() < 50) {
direction = +1;
movementTime = 0;
}
else if (random < 5) {
direction = -1;
movementTime = 0;
}
else if (random > 14) {
direction = +1;
movementTime = 0;
}
Movement stays
consistent for at least
20 act cycles.
}
}
Implementing Constrained Random
Behavior if(movementTime > movementTimeDelay) {
if (getX() > 350) {
direction = -1;
movementTime = 0;
}
else if (getX() < 50) {
direction = +1;
movementTime = 0;
}
else if (random < 5) {
direction = -1;
movementTime = 0;
}
else if (random > 14) {
direction = +1;
movementTime = 0;
}
Evading borders is
prioritized over
general movement.
}
}
Constrained Random Behavior
Constrained Random Behavior allows us to
implement Behavior that is both relatively
unpredictable for the player and “designed”.
This means that we can influence difficulty,
style of challenge, and other factors.
It can be considered a combination of
Deterministic Behavior and Random Behavior.
In fact, any complex Actor Behavior will most
likely contain elements of all 4 Behavior classes.
The PacMan Game
The PacMan Game
There are 4 Non-Player Actors in this game:
Ghosts of different colors that move around
the board.
While each Ghost has the same goal in theory
(Eat PacMan), they all exhibit unique Behavior.
The Orange Ghost
The Orange Ghost exhibits
Deterministic Behavior.
It moves around the central Box
on a fixed path, ignoring PacMan
and only eating him if their paths
happen to cross.
The Orange Ghost
The Orange Ghost
public void ghostBehavior() {
if (direction == WEST)
{
setLocation(getX()-3,getY());
if (null != getOneIntersectingObject(Boundary.class))
{
setLocation(getX()+3,getY());
setDirection(SOUTH);
The Ghost changes
}
direction whenever a
}
Boundary is hit.
else if (direction == EAST)
{
setLocation(getX()+3,getY());
if (null != getOneIntersectingObject(Boundary.class))
{
setLocation(getX()-3,getY());
setDirection(NORTH);
}
}
….
The Orange Ghost
public void ghostBehavior() {
if (direction == WEST)
{
setLocation(getX()-3,getY());
if (null != getOneIntersectingObject(Boundary.class))
{
setLocation(getX()+3,getY());
The direction it
setDirection(SOUTH);
}
chooses is fixed and
}
depends entirely on its
else if (direction == EAST)
previous direction.
{
setLocation(getX()+3,getY());
if (null != getOneIntersectingObject(Boundary.class))
{
setLocation(getX()-3,getY());
setDirection(NORTH);
}
}
….
The Pink Ghost
The Pink Ghost exhibits (Heavily)
Constrained Random Behavior.
He moves on predetermined paths
between the "teleport" points on
the left/right side of the level. If it
has reached one of the "teleport"
points, it starts to move towards a
"teleport" point on the other side of
the board. The decision between
the two possible points is made at
random.
The Pink Ghost
The Pink Ghost
The Pink Ghost
The predetermined paths are stored in a twodimensional array as a sequence of direction-changes:
int[][] sequence = {
{WEST, SOUTH, WEST, NORTH, WEST, NORTH, WEST, NORTH, WEST},
{WEST, SOUTH, WEST, NORTH, WEST, NORTH, EAST, NORTH,
WEST, SOUTH, WEST},
{EAST, SOUTH, EAST, NORTH, EAST},
{EAST, NORTH, WEST, NORTH, EAST, NORTH, EAST, NORTH,
EAST, SOUTH, WEST, SOUTH, EAST, SOUTH, EAST}, …
int path = 2;
int index = 0;
This path connects the
Right-Down teleport
point to the Left-Down
teleport point.
The Pink Ghost
The predetermined paths are stored in a twodimensional array as a sequence of direction-changes:
int[][] sequence = {
{WEST, SOUTH, WEST, NORTH, WEST, NORTH, WEST, NORTH, WEST},
{WEST, SOUTH, WEST, NORTH, WEST, NORTH, EAST, NORTH,
WEST, SOUTH, WEST},
{EAST, SOUTH, EAST, NORTH, EAST},
{EAST, NORTH, WEST, NORTH, EAST, NORTH, EAST, NORTH,
EAST, SOUTH, WEST, SOUTH, EAST, SOUTH, EAST}, …
int path = 2;
int index = 0;
The path the Ghost is
currently on, as well as
the position within this
path, are stored in two
integer variables.
The Pink Ghost
public void ghostBehavior() {
getNewPath();
if (direction == WEST)
{
setLocation(getX()-movement,getY());
if (null != getOneIntersectingObject(Boundary.class))
{
setLocation(getX()+movement,getY());
setDirection(sequence[path][index]);
index++;
}
}
….
If the Ghost collides with a
Boundary, it changes direction.
The new direction is
determined by the next value
stored in the array.
The Pink Ghost
public void getNewPath() {
if(getX() < 5) {
index = 0;
int random = Greenfoot.getRandomNumber(2);
if(getY() < 298)
path = 4+random;
else
path = 2+random;
setDirection(sequence[path][index]); If a screen border has been
reached, the Ghost chooses
}
between the two possible new
paths via „coin-flip“.
if(getX() > getWorld().getWidth()-5) {
index = 0;
int random = Greenfoot.getRandomNumber(2);
if(getY() < 298)
path = 6+random;
else
path = 0+random;
setDirection(sequence[path][index]);
}
}
The Blue Ghost
The Blue Ghost exhibits Greedy
Behavior.
It tries to get to PacMan on the
shortest path possible. However,
this means that he is unable to
get around Boundaries.
The Blue Ghost
The Blue Ghost
The Red Ghost
The Red Ghost exhibits (Lightly)
Constrained Random Behavior.
He continues on his current path
until he hits a Boundary and then
chooses a new direction at
random.
However, he is made more
dangerous by his ability to use
teleport points.