Jump to content
  • Advertisement
Sign in to follow this  
Kid of the neon

Dodging algorithms

This topic is 3001 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!