DonNews #21 27 марта 2005

Программирование

THEORY AI - The arguments about the construction of artificial intelligence in games.

__________________________________________

Theory of AI



(C) SpoozE / oHg / XXL

 Good morning everyone!
 Once the main thing. In this article I will
You about the implementation of artificial intelligence
(Hereinafter - AI), the scale of our with you
SPECCY. To begin to outline what
AI is and what we should strive for it
writing.

  By developing AI must be approached very
carefully, because each task requires
highly specialized and "fitted"
algorithm for solving it. In this regard, I
I will describe step by step creation of AI for
widely known game "BATTLE CITY". Thus,
the very first step is to estimate the required actions of 
AI-objects (hereinafter - paper). In our case, requires that 
the tanks: went just like that, guarding the base, attacked the 
enemy base, were wrong. Hmm maybe some confused the last 
paragraph, but errors in the actions of bots are very important,

because we want to create a realistic model
behavior. If in a game situation all
tanks rush to the enemy base, it
will look to put it mildly is not very
realistically, and gameplay of this change is not for the 
better, so that leave until a complete search path and talk

of chaotic motion.
 The most simple - of course just randomly choose a direction
some period of time, but look
this is not exactly what we want.
Me at the time of development seemed appropriate to introduce 
for each tank counter the change of direction and type of 
motion.  About changing the type of motion tell a little

later, and now about a change of direction. As
does it work? At the counter we put random
- the number of moves to change direction (Range depends on the 
scale map, but you can enter depending on the model behavior). 
Then each tick (interval time for which handled play

situation), we decrease the counter by one,
and if it is zero, then update again
direction and a counter. Also, the counter should be reset 
during an unsuccessful attempt to make a move (such as a tank 
collided with another tank or a wall). Thus

we have achieved quite realistic motion "at random". But, alas, 
in this case the probability of achieving certain tank

position depends on the spatial configuration blocks and can be 
very small. As seen in Figure




Is the probability that the tank will be in the hole
in the wall close to zero. In such cases,
save hardware resources, instead of laborious calculations is 
advantageous to use so-called checkpoint (from English.

Checkpoint - point inspection). In my implementation of the 
checkpoint are the array of the same block as the level, only 
blocks have the value change of direction and more properties. 
Thus, each tick is a check tanks at Checkpoint, if the tank is 
in the position with Checkpoint, we are a few additional tests 
(such as checkpoint may be only for the red tanks), and in the 
case success of the tank takes a direction that

corresponds to the checkpoint. Anticipating a little bit
forward, I want to mention the fact that, in accordance with 
the target we have should be several models of behavior

tanks. I outlined the two - attacking and defending. Attackers 
tend to base the enemy, using wave algorithm

search path (on which below), and the defending simply touring 
the map. In connection this checkpoint vary by model

behavior of the tanks which will be on these
Checkpoint ride. For example checkpoint can
be only for teams of red and only
for attacking tanks (you can make up their own
criteria of differentiation). So we
need to implement a full search algorithm
way. The easiest way - the wave
algorithm. Realized it is elementary to
following algorithm:

  1. The starting point - destination
bot, in our case - the base of the enemy.

  2. Splitting a field on the conditional squares
advisable to break into the same size as the blocks and 
Checkpoint. 

  3. Hammered cells "impassable" units such as # FF

  4. Assigning a cell with coordinates
target value of zero.

  5. All empty, "a passing" cells
around assigning a value per unit
more.

  6. Treat each of the labeled
cells is similar.
 In the case of tanks, we formed two
field of AI - the red and blue base.
Now to get the shortest path to
object, you just have to move in that
cell where the value is less.



  It is easiest to identify the movement of
this algorithm, as fifth direction and
choose it as well as up, down,
left and right, but only for the attackers
tanks. That is, the zero-counter, at
forward of the tank is a choice
traffic along the shortest path to the enemy
database. But as soon as the counter becomes
is zero, the tank can go and normal direction, which leads to 
realism. It is also worth considering that the motion of the 
wave algorithm priority than traffic to checkpoint and 
"offensive" to checkpoint to check whether the tank is not 
moving on fifth direction.

Fuh. Today I probably finished, but
did not even expect rid;)


                              2 b cont ...