Seeking and Fleeing AI Algorithms

Level:
Level3

Chicken with its head cut off, or laser guided missile? Your choice. The seeking and fleeing algorithms used in your game will make a huge difference in the gameplay, don't doubt it. Your enemies can have all kinds of cool moves and abilities, but if they can't intelligently locate the player (for seeking AND for fleeing purposes), they won't inspire fear or impart the neccessary sense of realism.

If you would like to follow along download the source code for this tutorial. 

Bring on the math! Determining the distance between an enemy and the player is of primary importance. If the player is far away, enemies should exhibit a certain set of behaviours (or "states"). If the player is nearby, the set of behaviours should be noticeably different. I've written a function that will quickly determine the distance between two points on an X,Y grid:

Private Function GetDist(intX1 As Single, intY1 As Single, _
   intX2 As Single, intY2 As Single) As Single
   GetDist = Sqr((intX1 - intX2) ^ 2 + (intY1 - intY2) ^ 2)
End Function 

Ok, so we know how far away the player is, but in which direction? We need a function for this as well!

Private Function FindAngle(intX1 As Single, intY1 As Single, intX2 As Single, _
   intY2 As Single) As Single
   
   Dim sngXComp As Single
   Dim sngYComp As Single
   
   sngXComp = intX2 - intX1
   sngYComp = intY1 - intY2
   If sngYComp > 0 Then FindAngle = Atn(sngXComp / sngYComp)
   If sngYComp < 0 Then FindAngle = Atn(sngXComp / sngYComp) + PI 
End Function

This will return the angle (in radians) between the two points given. Note, the Y value has been inverted since (in computer land) Y increases as we move down the screen.

For many types of games, these two functions are all you'll need. You know where the player is, and how to get to him, so simply move your enemies in that direction (or in the opposite direction for fleeing). In situations where the player and enemy entities are controled by velocity vectors (as opposed to incremental movement styles), we need a little more...

Private Sub AddVectors(sngMag1 As Single, sngDir1 As Single, _
   sngMag2 As Single, sngDir2 As Single, Optional ByRef sngMagResult As Single, _
   Optional ByRef sngDirResult As Single)
   
   Dim sngXComp As Single
   Dim sngYComp As Single
   
   sngXComp = sngMag1 * Sin(sngDir1) + sngMag2 * Sin(sngDir2)
   sngYComp = sngMag1 * Cos(sngDir1) + sngMag2 * Cos(sngDir2)
   
   sngMagResult = Sqr(sngXComp ^ 2 + sngYComp ^ 2)
   
   If Sgn(sngYComp) > 0 Then sngDirResult = _
      Atn(sngXComp / sngYComp)
   If Sgn(sngYComp) < 0 Then sngDirResult = _
      Atn(sngXComp / sngYComp) + PI
End Sub

I love this function! For those of you who don't know how to handle vectors, worry not! This function will add them together for you.. no need to think. Simply pass the magnitude and direction of the two vectors you wish to add, and it will spit out the magnitude and direction of the resultant vector (sngMagResult and sngDirResult)!

What do we need this for, you ask? Well, let us ponder our problem for a moment. Suppose that our player and enemy are spaceships (yay!). In order for our enemy to seek the player, he must first calculate the angle between them, and thrust in that direction, right? Yes, but then he'll simply overshoot the player (since objects in space do not simply stop moving when you stop thrusting!), and have to turn around and try again. We need some sort of braking mechanism.

Also, what if the player is moving? The enemy may be able to seek the player's CURRENT position, but anticipating his FUTURE position would obviously be advantageous (not to mention more realistic).

To accomplish all of these things, we need two new values:

  • The difference between the velocities of the enemy and player
  • The velocity required to intercept the player

In order to avoid overshooting the player, we need to match velocities with him at some point, hence the need for the first velocity value. Also, in order to anticipate the player's movement, we need to calculate the velocity required to intercept; giving rise to the second velocity value above.

To calculate the velocity difference, we simply subtract the player and enemy velocity vectors! This is easily accomplished by adding π to either of the vector's "directions" (thus inverting its value), and then using our AddVectors function.

To calculate the intercept vector is a tad trickier. The direction of this vector can be calculated using the FindAngle function; just pass the coordinates of the player and enemy. To determine the magnitude, we must first determine the distance between the enemy and player (GetDist function), divide it by the magnitude of the velocity difference, and multiply by the acceleration of the enemy.

HUH? Why? Finding the distance and dividing by the velocity gives us the "time" to intercept (how long until the enemy catches up with the player given the current velocity set). Multiplying this "time" by the accel gives us the velocity to intercept. Isn't physics fun?

Now, we add these vectors together (AddVectors function) to determine the direction in which our enemy should thrust. Here's some code from the sample source:

AddVectors msngSpeed, msngHeading, msngEnemySpeed, _
   msngEnemyHeading + PI, sngMagDiff, sngDirDiff
   
If sngMagDiff <> 0 Then
   AddVectors ENEMY_ACCEL * GetDist(msngX, msngY, msngEnemyX, _
      msngEnemyY) / sngMagDiff, FindAngle(msngEnemyX, msngEnemyY, _
      msngX, msngY), sngMagDiff, sngDirDiff, , msngEnemyFacing
Else
   msngEnemyFacing = FindAngle(msngEnemyX, msngEnemyY, msngX, msngY)
End If 

The first line gets the velocity difference. The If statement ensures we don't divide by zero. The second AddVectors call accepts the intercept velocity and the velocity difference and returns the "facing" value for the enemy.

Anyone ever watch that old TV show, "The Prisoner"? Check out the source code for this tutorial, it's just like ROVER from "The Prisoner"! Geek factor + 1. I hope this visual basic 6 tutorial was helpful please post any questions or comments below.

This tutorial is released under the GNU Free Documentation License 1.2. The original can be found here.

If you enjoyed this post, subscribe for updates (it's free)

i used timer to move

i used timer to move shapes

naming shape as ball

I just right ball.top = ball.top + 50 under timer

How to make objects move

I agree with Roda, it would be good to have that tutorial first.

I agree also - Maybe one of

I agree also - Maybe one of you would be willing to write on? :-)

I'll post it on here if you do.

>>

This would be good if you had a tutorial on how to make objects move in the first place...

LINK DOESNT WORK

The link to the source code does not work "Page not found"

Sorry about that it is fixed

Sorry about that it is fixed now!

looks like it needs fixin'

looks like it needs fixin' again.

Link still not fixed

Link is: http://www.vb6.us/tutorials/]/source-code/seeking-and-fleeing-algorithms-source-code-sample
should by: http://www.vb6.us/source-code/seeking-and-fleeing-algorithms-source-code-sample

Thanks - fixed it now

Thanks - fixed it now