Simple Predator Prey Chase Algorithms

Posted by ljmacphee on July 4, 2007 under game ai, topics in artificial intelligence |

Whether you are writing a game with artificial intelligence or a life form to evolve you have to decide how and when predators catch their prey. Should the predator try to catch the prey? If so what’s the best way? And the predator must watch out for obstacles during the chase, we don’t want any Wiley Coyote type accidents with our predators.

About the simplest method the predator can use to meet up with the prey is to see if the prey’s x & y positions are above or below the predator’s.
Prey ( 3, 6 )
Predator ( 5, 1 )

if ( prey_x > predator_x ) { x++; } else { x–; }
if ( prey_y > predator_y ) { y++; } else { y–; }

So the first pass through the predator moves from ( 5, 1 ) to ( 4, 2 ).

A bit more natural appearing predator chase would be to use line of sight as the path to move towards the prey. Bresenham’s Line Algorithm is usually used for this. While this is not more effective than the previous method it is more natural appearing. It is also more steps to compute.

prey current position ( xp, yp )
predator current position ( xP, yP )

x = x position to move to
y = y position to move to
dx = xp - xP
dy = yp - yP
Adx = AbsoluteValue ( dx )
Ady = AbsoluteValue (dy )

if ( xp > xP ) stepX = 1 else stepX = -1
if ( yp > yP ) stepY = 1 else stepY = -1

if ( Ady > Adx ){ //the y distance from prey is larger than the x distance

fraction = 2*dx - dy;

if (( yP != yp ) && ( fraction > 0 )){
x += stepX
}

y += stepY

}else{

fraction = 2*dy - dx;

if (( xP != xp ) && ( fraction > 0 )){
y += stepY
}

x += stepX
}

Sometimes instead of having the predator chase the prey it is more effective to have the predator intercept the path of the prey. To do this the velocity as well as the position of the prey must be taken into account.

//figure out when we can reach the prey
dvx = vxp - vxP //difference in x direction velocity
dvy = vyp - vxP //difference in y direction velocity

dx = xp - xP //difference in x positions
dy = yp - yP //difference in y positions

dtx = dx/dvx //time away from x intercept position
dty = dy/dvy //time away from y intercept position

//calculate where prey will be at that time
x = xp + vxp*dxt
y = yp + vyp*dxy

//use above Bresenham’s line algorithm to aim for that location ( x, y )

More information:
Line Drawing explained
Bresenham’s line algorithm