__________________________________________
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 ...
