VB:Tutorials:Seeking and Fleeing

From GPWiki
Jump to: navigation, search

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.

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.