[Tutorial] Path Finding Algorithms / AI

[zylum]

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.

http://members.rogers.com/zylum/angles.jpg

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

[zylum]

Recursive Algorithm (DFS):

I know this is what you've all been waiting for ;)

Recursive algorithms are popular because they are the most powerful
and are used in association with tile based games such as rpgs. The
thing with these set of algorithms is that they require a TON
of computing power. This is because these algorithms generally run in
exponential time which to put simply means that for a small increase
in map size, running time will increase a lot. If you're serious
about making games, i suggest you learn a high level language such as
c++ or java. If you're just here to fool around then i suggest you
stick to small map sizes.

In order to design a recursive path finding algorithm, one must
understand the concept of recursion. Basically a recursive function
is a function which calls itself. To illustrate this concept, lets
look at a simple function which calculates fibonacci numbers.
(fibonacci numbers are a sequence of numbers where each successive
number is the sum of the previous two ie. 1, 1, 2, 3, 5, 8, 13)



function fib (int n) {
if (n == 0) return 0
if (n == 1) return 1
return fib(n-1) + fib(n-2)
}


If we look carefully at the code we see that the function fib() calls
upon itself to calculate the previous two numbers. This process keeps
repeating until it either calculates the value of 0 or 1 which we
already know the value of. Lets go step by step how this function
works:

1) If we try to find the 6th element in the sequence we call fib(6)
2) Since n is not equal to 0 or 1, we must calculate the value
recursively.
3) The value of fib(6) is equal to fib(5)+fib(4) which are the two
previous numbers in the series. So we call the fib function to
calculate these two numbers.
4) This process keeps repeating itself untill it encounters the two
preconditions which return a constant value. If it weren't for these
preconditions, the function would keep calling itself untill your
computer runs out of RAM!!!

This concept may seem difficult to understand at first but keep
trying to analyze it. It will come to you sooner or later.

Ok! Now we know how recursion works... How can we use this knowledge
to develop an algorithm to find a path between two points? Well the
main concept behind DFS is to search through EVERY possible path and
find one that is the shortest.

Lets think about this step by step. We know that our character will
move eigther up, down, left or right. We also need to keep track of
what part of the map has walls or not. To determine which path is the
best, we need to keep track of how many tiles we have travered as
as which ones we already walked on so that we dont end up going in
circles.



map[][]
// load data into the map here. if the tile has a wall, assign a the
//value of 1. otherwise assign a value of 0
trav[][]
//this array will store the cells which we have already traveled upon
//initialize all elements to 0 since we haven't traveled anywhere yet

function findPath (int steps, int x, int y, int fx, int fy) {

}


In the above code snippet, we allocate two, 2d arrays which contain
data about the map and where we have traveled. Also we have a
signature for our path finding function findPath(). As arguments for
the function we need to keep track of how many steps we have taken at
a certain path aswell as the current coordinates and the coordinates
of what we want to find.

Now we need to think about preconditions which cause our function to
end and return a value. So when do we return a value? We return a
value when we encounter a wall, when we encounter a tile we have
already traversed or when we find what we are looking for.



function findPath (int steps, int x, int y, int fx, int fy) {
if (x == fx && y = fy) return steps
if (map[x][y] == 1 || trav[x][y] == 1) return MAX_VALUE

}


In the above snippet, we see that if we encounter our destination, we
will return the amount of steps we took, and if we encounter a wall
or a place we have already visited, then we return a really big value
so that we dont choose that path.

Ok so we have the basic outline of the function, what now? We need to
decide which direction we want to go in. So what we do find the best
path if we go left first, the best path if we go right, and so on.
Once we initially push the algorithm into motion we search all
possible moves in all directions and keep track of where we have
traveled as well as how many steps we took at this particular path.
Once all paths are check we check whether any of the paths have
successfully found the destination, if so we return true, otherwise
we return false. This allows us to know what to do once the function
has finished.



int LD, RD, UP, DD
sight = 8

function findPath (int steps, int x, int y, int fx, int fy) {
//once function is started, we can search all paths in every direction
// we know the function started because we took a step.
if (steps > 0) {
//record that we traveled here
trav[x][y] = 1

//preconditions
if (x == fx && y = fy) return steps
if (map[x][y] == 1 || trav[x][y] == 1 || steps > sight) return MAX_VALUE

//look in each direction and update the value of bestPath
bestPath = findPath (int steps+1, int x+1, int y, int fx, int fy)
bestPath = min(bestPath, (findPath (int steps+1, int x-1, int y, int fx, int fy))
bestPath = min(bestPath, (findPath (int steps+1, int x, int y+1, int fx, int fy))
bestPath = min(bestPath, (findPath (int steps+1, int x, int y-1, int fx, int fy))
return bestPath

//remove this element from the traveled array since we have finished
//looking at this particular path
trav[x][y] = 0
}

//this is where we initially start the recursion and keep track
//of the best direction to go in
if (steps == 0) {
//find the best path for each of the directions
LD = findPath (int steps+1, int x-1, int y, int fx, int fy)
RD = findPath (int steps+1, int x+1, int y, int fx, int fy)
UD = findPath (int steps+1, int x, int y+1, int fx, int fy)
DD = findPath (int steps+1, int x, int y-1, int fx, int fy)
}

//if atleast one of the directions has a value less than MAX_VALUE then
//that means we have successfully found a path and we return true
if (LD < MAX_VALUE || RD < MAX_VALUE || UD < MAX_VALUE || DD < MAX_VALUE) return 1

//if all directions return a value equal to MAX_VALUE then no paths
// were found and we return false
return 0
}

//now that we know which direction is best to go, we move the
//charater accordingly
if (findPath(0, this.x, this.y, enemy.x, enemy.y)) {
if (LD = min(min(LD, RD), min(UP, DD))) {
this.goLeft()
} else if (RD = min(min(LD, RD), min(UP, DD))) {
this.goRight()
} else if (UD = min(min(LD, RD), min(UP, DD))) {
this.goUp()
} else if (DD = min(min(LD, RD), min(UP, DD))) {
this.goDown()
}
} else {
//move randomly or whatever else you want to do if you cant find
//a path
}


The above code is a simple implementation of a pathfinding algorithm.
It may seem confusing at first but keep working at it until you
understand it. I know i didn't explain things very well at the end of
this tutorial but i have been writing for hours... If you have any
questions, ask away and I'll try to clear things up tomorrow.

The algorithm that I have provided above is by no means efficient. In
fact it is horribly inefficient but it gets the job done in a
resonably straightforward manner. If you want to look into faster
algorithsm i suggest researching about the algorithms I have omitted
in this tutorial.



Well that's it... My first contribution to kirupaforums in a long
while. I hope it helps some of you otherwise these finger cramps were
all int vain!!!

-zylum :s:

[Dr Warm]

whoa! that's a mouthfull, thanks man, i'll try and convert it to actionscript (from ur psuedo) when i have some time, but its pretty close anyway

[Dr Warm]

theres an interesting use of the Recursive Algorithm in solving mazes, ie if u can't do it the computer will do it for you. This is an example i got from ultrashock.com (i had to post the fla, because u can't give the url! sorry about that, not sure if its illegal) but i can't remember which method it uses, probably the A* (a star) that's a 'faster' way but uses more CPU, as u can see when u get to the later stages, also the creation of the maze also uses a similar method

[signifer123]

Wow thtas is an insanley fast autosolver thats awesome