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]

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).

Quote: Original post by jyk
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?

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.

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*

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.

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.

I also recommend the Boids Algorithms.

Oooohhh... good point.

Quote: Original post by EJH
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.

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?

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.