I took a break from this site over a year ago. A few days ago I
remembered about it and thought I’d come back and visit. Well
needless to say it brought back a lot of memories of when I first
started programming. Now that I’m back with a new wealth of
knowledge, I thought I’d write a tutorial on a more advanced topic
of game AI…
P.S. since i haven’t used flash in ages and don’t have it currently
installed on the machine, i will have to use actionscriptesque pseudo
code to illustrate how you would implement the code. If anyone feels
like converting the code, feel free to do so 
PATH FINDING TUTORIAL:
There are many situations in a game where you might want the
enemy to walk or run towards a certain location ie. towards you.
In these types of situations you have a few possibilities to
which path finding AI you might want to use.
The two main types of path finding techniques are:
Decision Based:
- nonrotational
- rotational
Recursive:
- DFS (depth-first search)
- BFS (breadth-first search)
- Dijkstra’s Algorithm
- A* Path Finding Algorithm
The algorithsm we shall discuss in this tutorial are the decision
based algorithms as well as the simplest of the recursive type
algorithms. This is because they are easy to comprehend as well as
easy to implement. We will ignore BFS, Dijkstra and A* since these
are very complex algorithms which may require special data structures
and are harder to implement.
Simple Non-Rotational Path Finding Algorithm:
When dealing with simple games or early levels of a game where the AI
doesn’t have to be so intense, this is the algorithm to go with.
Another one of this algorithms benefits is that it requires very
little processing power.
The main idea of this algorithm is to move in the direction of where
the enemy is. It’s as simple as that. If the opponent is to the right
of you, then move right. If it’s ahead of you, then move forward.
if (this.x < enemy.x) this.x ++
else if (this.x > enemy.x) this.x --
else if (this.y < enemy.y) this.y ++
else if (this.y > enemy.y) this.y --
When implemented the enemy moves very predictably and unrealisticaly.
With the code above, the enemy will first line up with your x
position and then it will try to line up the y position. To improve
the way the enemy moves you might want to add an element of
randomness. So instead of first lining up a certain axis, choose at
random which axis you want to line up at a given time.
if (this.x != enemy.x && this.y != enemy.y) {
if (randomInt(1,2) == 1) {
if (this.x < enemy.x) this.x ++
else if (this.x > enemy.x) this.x --
else
if (this.y < enemy.y) this.y ++
else if (this.y > enemy.y) this.y --
}
} else {
if (this.x < enemy.x) this.x ++
else if (this.x > enemy.x) this.x --
else if (this.y < enemy.y) this.y ++
else if (this.y > enemy.y) this.y --
}
As you can see the enemy moves much more realisticaly (if you can
call it that! lol). You can play around with the values in the
random integer method to control the prefered axis of the enemy. that
is to say that if the range is greater, ‘1’ will be returned less
often therefore making the enemy tend to move along the y axis
more often than on the x axis.
Simple Rotational Path Finding Algorithm:
If you have created a simple game in which your charaters rotate when
moving around then this is the algorithm for you! This algorithm has
two disadvantages when comparing it to the nonrotational algorithm.
First, it requires triginometry and second it requires more
computational power due to the use of the Sine, Cosine and Tangent
functions.
The basic idea to this algorithm is to turn towards the enemy in a
direction which will require the few amount of degress of rotation.
Then move forward in the direction you are facing. So the first thing
we need is a function which calculates the between the enemy and you.
Then we need to determine which direction it is best to turn towards.
After we have determined those two peices of information the rest is
fairly straight forward.
First to find the angle between the two objects. Consider the above
image… Find the angle between B and G, we use the inverse of
tangent. There is no use explaining what tangent does here since you
will learn it sooner or later at school. So angle A would be equal to
tan^-1(rise/run)
Great we now know the angle between G and B. Or do we? Normally in
most programming languages, zero degrees is located on the positive
branch of the x axis. Now with this in mind, we need to determine the
angle relative to this ‘zero’ degrees. The two possibilities are
angle B which is positive or angle C which is negative which is also
equal to 360 + angle C which will result in a positive angle which is
equal to angle B. Since you don’t know which angle will be returned
by your program, it is safe to check before assuming you have the
correct angle:
function findAngle () {
run = this.x - enemy.x
rise = this.y - enemy.y
angle = tan^-1(rise/run)
if (angle < 0) angle = 360 + angle
return angle
}
Finally! We have a function which determines the angle between the
two objects. Now we just need to determine whether to turn clockwise
or counter-clockwise. This task is fairly simple. If the angle
between the two objects is less than 180, then check if the angle at
which the enemy is facing is within the range of TABTTO - TABTTO+180.
If it is, turn counter, otherwise clockwise. If TABTTO is greater
than 180, then check is the angle at which the enemy is facing is in
the range of TABTTO-180 - TABTTO. if it is, turn clockwise, otherwise
turn counter. All these conditional statements are to prevent
checking within a range which is greater than 360 degrees. Now that
we have all the necessary information, we can put everything
together.
function findAngle() {
run = this.x - enemy.x
rise = this.y - enemy.y
angle = tan^-1(rise/run)
if (angle < 0) angle = 360 + angle
return angle
}
if (findAngle() < 180) {
if (this.angle > findAngle() && this.angle < findAngle() + 180) {
this.angle --
} else {
this.angle ++
}
} else {
if (this.angle > findAngle() - 180 && this.angle < findAngle()) {
this.angle ++
} else {
this.angle --
}
}
this.angle = (this.angle + 360) % 360 // this prevents the angle from
//exceding 360 or going below 0
this.moveForward()
Note: when using the tan^-1 function, make sure you use the correct
syntax for the language you are using. Make sure that you are using
the degree version if you keep track of angles with degrees and use
radian version when keeping track of angles in radians. I beleive the
correct function in Actionscript would be ‘atan(rise,run)’ but im not
sure so check that up…
next installment coming right up…
-zylum
