# \[Tutorial\] Path Finding Algorithms / AI

**URL:** <https://forum.kirupa.com/t/tutorial-path-finding-algorithms-ai/125369>\
**Category:** Uncategorized\
**Created:** [October 12, 2004, 11:26pm UTC](https://forum.kirupa.com/t/tutorial-path-finding-algorithms-ai/125369 "2004-10-12T23:26:56Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![zylum](https://avatars.discourse-cdn.com/v4/letter/z/d26b3c/32.png) [@zylum](https://forum.kirupa.com/u/zylum)\
**Post date:** [October 12, 2004, 11:26pm UTC](https://forum.kirupa.com/t/tutorial-path-finding-algorithms-ai/125369/1 "2004-10-12T23:26:56Z")

</div>

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.

```auto

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.

```auto

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:

```auto

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.

```auto

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