ch15.htm

对于程序员来说可以利用JAVA来开发网络游戏！

type of roaming AI where a game object specifically tries to get
away from another object or objects.
<P>
Evading is implemented in a similar manner to chasing, as the
following code shows:
<BLOCKQUOTE>
<TT>if (aX &gt; pX)<BR>
&nbsp;&nbsp;aX++;<BR>
else if (aX &lt; pX)<BR>
&nbsp;&nbsp;aX--;<BR>
if (aY &gt; pY)<BR>
&nbsp;&nbsp;aY++;<BR>
else if (aY &lt; cY)<BR>
&nbsp;&nbsp;aY--;</TT>
</BLOCKQUOTE>
<P>
This is roughly the same code used by the chasing algorithm, with
the only differences being the unary operators (<TT>++</TT>,
<TT>--</TT>) used to change the alien's
position. Like chasing, evading can be softened using randomness
or patterned movement.
<P>
A good example of using the evading algorithm would be a computer-controlled
version of the player's ship. If you think about it, the player
is using the evading algorithm to dodge the aliens; it's just
implemented by hitting keys rather than in a piece of code. If
you want to provide a demo mode in a game like this where the
computer plays itself, you would use an evading algorithm to control
the player's ship.
<H4><B>Patterned</B></H4>
<P>
<I>Patterned </I>movement refers to a type of roaming AI that
uses a predefined set of movements for a game object.
<P>
Good examples of patterned movement are the aliens in the classic
Galaga arcade game, which perform all kinds of neat aerobatics
on their way down the screen. Patterns can include circles, figure
eights, zigzags, or even more complex movements. Another example
of patterned movement is the ghosts in another classic, Pac Man,
who always move toward the player (subject to the constraints
of the walls and, of course, whether you've eaten a power pellet).
<P>
<CENTER><TABLE BORDERCOLOR=#000000 BORDER=1 WIDTH=80%>
<TR><TD><B>Note</B></TD></TR>
<TR><TD>
<BLOCKQUOTE>
In truth, the aliens in Galaga use a combined approach of both patterned and chasing movement; although they certainly follow specific patterns, the aliens still make sure to come after the player whenever possible. Additionally, as the player moves into 
higher levels the roaming AI starts favoring chasing over patterned movement, simply to make the game harder. This is a really neat usage of combined roaming AI. This touches on the concept of behavioral AI, which you learn about in the next 
section.</BLOCKQUOTE>

</TD></TR>
</TABLE></CENTER>
<P>
<P>
Patterns are usually stored as an array of velocity or position
offsets (or multipliers) that are applied to an object whenever
patterned movement is required of it, like this:
<BLOCKQUOTE>
<TT>int[][] zigzag = {{1, 1}, {-1, 1}};<BR>
aX += zigzag[patStep][0];<BR>
aY += zigzag[patStep][1];</TT>
</BLOCKQUOTE>
<P>
This code shows how to implement a very simple vertical zigzag
pattern. The <TT>int</TT> array <TT>zigzag</TT>
contains pairs of XY offsets used to apply the pattern to the
alien. The <TT>patStep</TT> variable
is an integer representing the current step in the pattern. When
this pattern is applied, the alien moves in a vertical direction
while zigzagging back and forth horizontally.
<H3><A NAME="BehavioralAI"><B>Behavioral AI</B></A></H3>
<P>
Although the types of roaming AI strategies are pretty neat in
their own right, a practical gaming scenario often requires a
mixture of all three.
<P>
<I>Behavioral AI</I> is another fundamental type of gaming AI
that often uses a mixture of roaming AI algorithms to give game
objects specific behaviors.
<P>
Using the trusted alien example again, what if you want the alien
to chase some times, evade other times, follow a pattern still
other times, and maybe even act totally randomly every once in
a while? Another good reason for using behavioral AI is to alter
the difficulty of a game. For example, you could favor a chasing
algorithm more than random or patterned movement to make aliens
more aggressive in higher levels of a space game.
<P>
To implement behavioral AI, you need to establish a set of behaviors
for the alien. Giving game objects behaviors is pretty simple,
and usually just involves establishing a ranking system for each
type of behavior present in the system, and then applying it to
each object. For example, in the alien system, you would have
the following behaviors: chase, evade, fly in a pattern, and fly
randomly. For each different type of alien, you would assign different
percentages to the different behaviors, thereby giving them each
different personalities. For example, an aggressive alien might
have the following behavioral breakdown: chase 50% of the time,
evade 10% of the time, fly in a pattern 30% of the time, and fly
randomly 10% of the time. On the other hand, a more passive alien
might act like this: chase 10% of the time, evade 50% of the time,
fly in a pattern 20% of the time, and fly randomly 20% of the
time.
<P>
This behavioral approach works amazingly well and yields surprising
results considering how simple it is to implement. A typical implementation
simply involves a <TT>switch</TT>
statement or nested <TT>if</TT>-<TT>else
</TT>statements to select a particular behavior. A sample
Java implementation for the behavioral aggressive alien would
look like this:
<BLOCKQUOTE>
<TT>int behavior = Math.abs(rand.nextInt()
% 100);<BR>
if (behavior &lt; 50)<BR>
&nbsp;&nbsp;// chase<BR>
else if (behavior &lt; 60)<BR>
&nbsp;&nbsp;// evade<BR>
else if (behavior &lt; 90)<BR>
&nbsp;&nbsp;// fly in a pattern<BR>
else<BR>
&nbsp;&nbsp;// fly randomly</TT>
</BLOCKQUOTE>
<P>
As you can see, creating and assigning behaviors is open to a
wide range of creativity. One of the best sources of ideas for
creating game object behaviors is the primal responses common
in the animal world (and unfortunately all too often in the human
world, too). As a matter of fact, a simple fight or flight behavioral
system can work wonders when applied intelligently to a variety
of game objects. Basically, use your imagination as a guide and
create as many unique behaviors as you can dream up.
<H3><A NAME="StrategicAI"><B>Strategic AI</B></A></H3>
<P>
The final fundamental type of game AI you're going to learn about
is strategic AI.
<P>
<I>Strategic AI</I> is basically any AI that is designed to play
a game with a fixed set of well-defined rules.
<P>
For example, a computer-controlled chess player would use strategic
AI to determine each move based on trying to improve the chances
of winning the game. Strategic AI tends to vary more based on
the nature of the game, because it is so tightly linked to the
rules of the game. Even so, there are established and successful
approaches to applying strategic AI to many general types of games,
such as games played on a rectangular board with pieces. Checkers
and chess immediately come to mind as fitting into this group,
and likewise have a rich history of AI research devoted to them.
<P>
Strategic AI, especially for board games, typically involves some
form of weighted look-ahead approach to determining the best move
to make. The look-ahead is usually used in conjunction with a
fixed table of predetermined moves. For a look-ahead to make sense,
however, there must be a method of looking at the board at any
state and calculating a score. This is known as <I>weighting</I>
and is often the most difficult part of implementing strategic
AI in a board game. As an example of how difficult weighting can
be, watch a game of chess or checkers and try to figure out who
is winning after every single move. Then go a step further and
think about trying to calculate a numeric score for each player
at each point in the game. Obviously, near the end of the game
it gets easier, but early on it is very difficult to tell who
is winning, simply because there are so many different things
that can happen. Attempting to quantify the state of the game
in a numeric score is even more difficult.
<P>
<I>Weighting</I> is a method of looking at a game at any state
and calculating a score for each player.
<P>
Nevertheless, there are ways to successfully calculate a weighted
score for strategic games. Using a look-head approach with scoring,
a strategic AI algorithm can test for every possible move for
each player multiple moves into the future and determine which
move is the best. This move is often referred to as the &quot;least
worst&quot; move rather than the best, because the goal typically
is to make the move that helps the other player the least, rather
than the other way around. Of course, the end result is basically
the same, but it is an interesting way to look at a game, nevertheless.
<P>
Even though look-ahead approaches to implementing strategic AI
are useful in many cases, they do have a fairly significant overhead
if very much depth is required (in other words, if the computer
player needs to be very smart). This is because the look-ahead
depth search approach suffers from a geometric progression of
calculations, meaning that the overhead significantly increases
when the search depth is increased.
<P>
To better understand this, consider the case of a computer Backgammon
player. The computer player has to choose two or four moves from
possibly several dozen, as well as decide whether to double or
resign. A practical Backgammon program might assign weights to
different combinations of positions and calculate the value of
each position reachable from the current position and dice roll.
A scoring system would then be used to evaluate the worth of each
potential position, which gets back to the often difficult proposition
of scoring, even in a game, such as Backgammon, with simple rules.
Now apply this scenario to a hundred-unit war game, with every
unit having unique characteristics, and the terrain and random
factors complicating the issue still further. The optimal system
of scoring simply cannot be determined in a reasonable amount
of time, especially with the limited computing power of a workstation
or pc.
<P>
The solution in these cases is to settle for a &quot;good enough&quot;
move, rather than the &quot;best&quot; move. One of the best ways
to develop the algorithm for finding the &quot;good enough&quot;
move is to set up the computer to play both sides in a game, using
a lot of variation between the algorithms and weights playing
each side. Then sit back and let the two computer players battle
it out and see which one wins the most. This approach typically
involves a lot of tinkering with the AI code, but it can result
in very good computer players.
<H2><A NAME="ImplementingYourOwnAI"><B><FONT SIZE=5 COLOR=#FF0000>Implementing
Your Own AI</FONT></B></A></H2>
<P>
When deciding how to implement AI in a game, you need to do some
preliminary work to assess exactly what type and level of AI you
think is warranted. You need to determine what level of computer
response suits your needs, abilities, resources, and project timeframe.
<P>
If your main concern is developing a game that keeps human players
entertained and challenged, go with the most simple AI possible.
Actually, try to go with the most simple AI regardless of your
goals, because you can always enhance it incrementally. If you
think your game needs a type of AI that doesn't quite fit into
any I've described, do some research and see whether something
out there is closer to what you need. Most importantly, budget
plenty of time for implementing AI, because 99 percent of the
time, it will take longer than you ever anticipated to get it
all working at a level you are happy with.
<P>
What is the best way to get started? Start in small steps, of
course. Let's look at a hypothetical example of implementing AI
for a strategic war game. Many programmers like to write code
as they design, and while that approach might work in some cases,
I recommend at least some degree of preliminary design on paper.
Furthermore, try to keep this design limited to a subset of the
game's AI, such as a single tank. Rather than writing the data
structures and movement rules for an armored division and all
related subordinate units, and then trying to work out how the
lower units will find their way from point A to point B, start
with a small, simple map or grid and simple movement rules. Write
the code to get a single tank from point A to point B. Then add
complications piece by piece, building onto a complete algorithm
at each step. If you are careful to make each piece of the AI
general enough and open enough to connect to other pieces, your
final algorithms should be general enough to handle any conditions
your game might encounter.
<P>
Getting back to more basic terms, a good way to build AI experience
is to write a computer opponent for a simple board game, such
as tic-tac-toe or checkers. Detailed AI solutions exist for many
popular games, so you should be able to find them if you check
out some of the Web sites mentioned later in today's lesson.
<H2><A NAME="AIinCommercialGames"><B><FONT SIZE=5 COLOR=#FF0000>AI
in Commercial Games</FONT></B></A></H2>
<P>
Now that you have a little theory under your belt, it's time to
take a look at how the game industry is using AI. So far, adventure
and strategy games are the only commercial games to have a great
deal of success in implementing complex AI systems. One of the
most notable series of games to implement realistic AI is the
immensely popular Ultima series, by Origin Systems, Inc. The Ultima
series allows the player to explore villages, complete with all
walks of human life, also known as non-player characters (Npcs).
The Npcs in the Ultima series are true to their expected natures,
which makes the game more believable. Even more importantly, however,
is how the computer-controlled humans engage the player in various
circumstances, which makes the games infinitely more interesting.
This degree of interactivity, combined with effective AI, results
in players feeling as though they are part of a virtual world;
this is typically the ultimate goal of AI in games, especially
in adventure games.
<P>
Origin Systems later delivered System Shock, which added an innovative
twist to the interaction between the player and the Npcs. In System
Shock, the player interacts with Npcs via e-mail, which is certainly
a more logical communication medium for games set in the future.
This approach really hits home with those of us who rely on e-mail
for our day-to-day communications.
<P>
With more powerful hardware affording new opportunities for implementing