# Dodging algorithms

## Recommended Posts

There is a 2D shooting game with AI opponents. We have a collection of projectiles, existing at current moment on board with all known parameters: speed, position, direction, damage. Also there is a AI player with known position and shape. Let's suppose that AI player's shape is square, and projectiles are dots. Player is hit when he collides a projectile. I need an algorithm which takes information above and chooses direction where AI player should go to minimize damage from projectiles. Now I came to next algorithm: 1. Detect that AI player will be hit by some projectile (shown by gray line on image); 2. Calculate damage D0 cause by this projectile; 3. Calculate damage D1 if AI player will go away from line of fire to perpendicular direction, if he has enough time (position AI 1); 4. If D1 > 0 calculate damage D2 caused by moving to AI 2; 5. Choose min(D0,D1,D2) and go to appropriate direction. Then, if AI player again under line of fire, repeat algorithm from beginning. [Edited by - Kid of the neon on April 26, 2010 12:30:58 PM]

##### Share on other sites
jyk    2094
You can use HTML tags to link or embed images in posts.

Anyway, what was your question exactly? You said you needed a 'dodging' algorithm, but it sounds like you have one. Does it work the way you want it to?

I didn't quite understand the part about damage, but other than that this seems pretty similar to the way I've handled projectile evasion for AI agents in the past (which always seemed to work well).

##### Share on other sites
Quote:
 Original post by jykYou can use HTML tags to link or embed images in posts.Anyway, what was your question exactly? You said you needed a 'dodging' algorithm, but it sounds like you have one. Does it work the way you want it to?

thanks for help! Are there any general purpose algorithms for dodging?

About damage: if there was projectile moving under player, AI would take damage wherever player moves, so AI should go to projectile causing minimal damage.

##### Share on other sites
Best bet is to project forward a time step or a few time steps. For each step, determine the location of the agent and then extend your projectile momentum to see if there would be a collision. You can repeat for a few time steps if necessary. Then, assemble that information and decide what the best course of action would be (i.e. the least amount of damage).

This is a quick and dirty solution and would be a bit expensive because of the increased ray casts. *shrug*

##### Share on other sites
Emergent    982
I'm not aware of any general-purpose "dodging algorithms" that are robust (though certainly potential-based approaches seem reasonable). Here's one way to think about it as a planning problem though:

Your world is 2d; adding time as a third dimension, your projectile trajectories are lines in 3d. Computing the Minkowski sum of these lines with your agent's shape, you get the free configuration space for your agent (all the points where its center can be). You start at some point (x,y,0) in spacetime and want to get to any point on the t=T plane (for some fixed lookahead T) while minimizing accumulated damage. In principle, this is just a pathfinding problem in 3d, with the one restriction that you cannot move backwards in the 't' direction.

##### Share on other sites
EJH    315
Another suggestion, on a game I did we used a modified boids for NPC steering:

http://www.red3d.com/cwr/boids/

and just made projectiles as repulsors and gave them high weight. If you are using some other general obstacle avoidance algorithm just consider projectiles as another obstacle with high repellence. This is very nice because the dodging is built-in and no need to do manual ray-casting or projectile prediction every update.

##### Share on other sites
hiigara    108
I also recommend the Boids Algorithms.

##### Share on other sites
Oooohhh... good point.

##### Share on other sites
Quote:
 Original post by EJHAnother suggestion, on a game I did we used a modified boids for NPC steering:http://www.red3d.com/cwr/boids/and just made projectiles as repulsors and gave them high weight. If you are using some other general obstacle avoidance algorithm just consider projectiles as another obstacle with high repellence. This is very nice because the dodging is built-in and no need to do manual ray-casting or projectile prediction every update.

EJH,

I've read about boids and algorithm implementation (http://www.vergenet.net/~conrad/boids/pseudocode.html), but I don't understand how to apply this algorithm to my problem. As from algorithm overview, there are 3 corrections to velocity of boids: to center of mass, away from nearby boids and matching velocity. From this, how NPC agent velocity should be changed?

##### Share on other sites
Use one of these instead. From the same site:

Steering Behaviors

Specifically if you use a hybrid of the techniques in "seek and evade" and "obstacle avoidance" you should be good to go.

##### Share on other sites
EJH    315
Quote:
 Original post by Kid of the neonI've read about boids and algorithm implementation (http://www.vergenet.net/~conrad/boids/pseudocode.html), but I don't understand how to apply this algorithm to my problem. As from algorithm overview, there are 3 corrections to velocity of boids: to center of mass, away from nearby boids and matching velocity. From this, how NPC agent velocity should be changed?

That article is very good.

You can change "away from nearby boids" to "away from X" where X is anything you want, such as enemies or projectiles. You can change "move to center of mass" to moving to wherever, such as toward the target or some other desired position.

##### Share on other sites
Extrarius    1412
I'd probably use potential fields. Create a grid over the playing area, put a large value at the point of each projectile based on the amount of damage it does, then draw a line of decreasing values along the projectile's path (with how much each step decreases in 'badness' based on the speed of the projectile - slower projectiles decrease in value faster). If the paths of multiple projectiles cross, add the values together. Then make a new field based on the sum of values close together in the original field (so if the AI is 10 units in radius, each square in the new field is the sum of all squares in a 10 unit radius). Finally, move towards the lowest values you can reach this frame.

If you have many AIs with identical characteristics, you can calculate the field only once and use it for all of them.

Also, you don't have to calculate the entire field, only the field around the AI based on its movement capabilities and size. If the AI is 10 units in radius and can move 20 units, you only need to calculate the field in a 30 unit circle around the agent. To do this, just project projectiles until they collide with the area of interest, then use that distance to decide how much to reduce the field impact of the projectile (just as if you had filled in the grid all the way from the projectile to the area of interest).

This has the benefit of taking global projectile distribution, time, and agent statistics into account. The steering or boids approach will typically only take local projectile distribution into account, and it takes more work to incorporate the fact that you only need to avoid the front of projectiles (using distance to a line or something like that).

##### Share on other sites
Emergent    982
Quote:
 Original post by ExtrariusI'd probably use potential fields. Create a grid over the playing area[...]

Short of trying to do something optimal (which is hard and likely not worth it), I'd likely just use a potential-based approach as well. But why a grid? Just choose some reasonable function that you can evaluate analytically and move down its gradient; computing that should be much faster than iterating over a grid...

I'd only use a grid if I wanted to compute something like the brushfire algorithm or solve the heat equation (or some other PDE) over it numerically; sometimes this gives nice potential fields with particular global properties (e.g., no local minima). But if we're just doing locally-optimal stuff, heck, just build a potential out of elementary functions and differentiate.

##### Share on other sites
nigo    156
Take a normal vector to each 2D (ground plane) projectile velocity vector (90 degree turn) and accumulate them. This is very cheap as only requires swapping their x and y and changing sign of new x. If this normal vector is on the opposite side of their velocity vector than the agent is, invert it. You want the normal vector to point into agent subspace (the projectile striaght path is a 2D BSP splitting plane).

The accumulated vector is your desired direction.

Rationale: You dont want to cross projectile paths and you will preferably avoid running in the same direction projectiles go, as they sort of catch up.

You can weight the vectors according to their speed and intersection distance (distance from agent position to projectile straight path) if you want.

##### Share on other sites
Extrarius    1412
Quote:
 Original post by Emergent[...]But why a grid? Just choose some reasonable function that you can evaluate analytically and move down its gradient;[...]
Because it's easier to iterate over projectiles and draw lines from them than try to figure out an equivalent formula, and I'm not sure you could create an equivalent formula that didn't involve the same calculations as a grid. The influence of a projectile is conditional upon its eventual collision with a point, so you're still going to have to project them all forward in time to test for collision, then, if it would collide with a given position, calculate some value based on the distance into the future when it would collide combined with its damage.

The grid acts a very simple cache that allows evaluating each projectile only a single time regardless of the number of movement choices (or agents that need to make choices). You could use something more complicated (a fancy partitioning tree or graph) to cache collision information but I don't think it buys enough to be worth the extra work.

For example, if your movement choices are stay, right 1-10 units, or left 1-10 units, you'll need to know collisions for 21 possible locations. If you make a grid and fill it, you'll calculate each projectile's path once over a 21-square grid (since you only need to know the info for the places you can move) or, if you calculate each choice's weight independently, you might end up examining each projectile 21 times.

##### Share on other sites
Emergent    982
Quote:
 Original post by ExtrariusThe grid acts a very simple cache that allows evaluating each projectile only a single time regardless of the number of movement choices (or agents that need to make choices).

I like that the complexity is basically constant w.r.t. the number of agents, but generally I'd expect many more grid cells than agents, which means that iterating over agents should be faster...

Quote:
 For example, if your movement choices are stay, right 1-10 units, or left 1-10 units, you'll need to know collisions for 21 possible locations.

Oh! So you're not just talking about moving down a gradient (which is what I always think of when I hear "potential field"); you actually want a global minimum. Is that right? In that case, I understand gridding, since basically all methods to find global minima boil down to exhaustive search...

##### Share on other sites
Storyyeller    215
In my game, the way I did it was to have the ai project forward the trajectories of bullets, and also project forward the trajectories of itself following possible inputs.

It starts by testing the trajectory it would follow if it does nothing. If that results in a collision, it then starts testing more complicated patterns such as accelerate 50, wait 50 or wait 50, accelerate 50.

If there are no paths with fewer then N input changes, then it just gives up and resigns itself to taking damage.

Of course, my game has factors that may make it not applicable to your situation. For example, I have a strong gravity well, meaning that simply projecting straight lines doesn't work. It also makes it impossible to find a closed form solution for the equations of motion. So that pretty much forces a trial and error approach involving projecting the simulation forward in time.

Other factors in my game that make it a more viable approach are the fact that all bullets do the same damage (so that I just do a boolean test instead of trying to minimize total damage), and there are a small number of them at any given time.