Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Imagine a very simple shoot-em-up, something we all know:

shoot-em-up 1

You're the player (green). Your movement is restricted to the X axis. Our enemy (or enemies) is at the top of the screen, his movement is also restricted to the X axis. The player fires bullets (yellow) at the enemy.

I'd like to implement an A.I. for the enemy that should be really good at avoiding the players bullets. My first idea was to divide the screen into discrete sections and assign weights to them:

weighted shoot-em-up

There are two weights: The "bullet-weight" (grey) is the danger imposed by a bullet. The closer the bullet is to the enemy, the higher the "bullet-weight" (0..1, where 1 is highest danger). Lanes without a bullet have a weight of 0. The second weight is the "distance-weight" (lime-green). For every lane I add 0.2 movement cost (this value is kinda arbitrary now and could be tweaked).

Then I simply add the weights (white) and go to the lane with the lowest weight (red). But this approach has an obvious flaw, because it can easily miss local minima as the optimal place to go would be simply between two incoming bullets (as denoted with the white arrow).

So here's what I'm looking for:

shoot-em-up total destruction

  • Should find a way through bullet-storm, even when there's no place that doesn't impose a threat of a bullet.
  • Enemy can reliably dodge bullets by picking an optimal (or almost optimal) solution.
  • Algorithm should be able to factor in bullet movement speed (as they might move with different velocities).
  • Ways to tweak the algorithm so that different levels of difficulty can be applied (dumb to super-intelligent enemies).
  • Algorithm should allow different goals, as the enemy doesn't only want to evade bullets, he should also be able to shoot the player. That means that positions where the enemy can fire at the player should be preferred when dodging bullets.

So how would you tackle this? Contrary to other games of this genre, I'd like to have only a few, but very "skilled" enemies instead of masses of dumb enemies.

share|improve this question
2  
Have you considered using something like steering behaviors? There's one for obstacle avoidance specifically: red3d.com/cwr/steer/Obstacle.html –  Tetrad Nov 11 '11 at 15:08
    
@Tetrad I have thought about steering behaviors.. also because they can nicely be switched, like "try to shoot player" and when danger is ahead switch to "evade". I fear that a 1D (that's what I'm basically dealing with) version of evade will be way too dumb to make good decisions. I might be wrong though. –  bummzack Nov 11 '11 at 17:38
add comment

2 Answers 2

up vote 7 down vote accepted

I think your basic idea is sound, but it is not analogue. You need an analogue field of value that runs across the screen. So, 1D diffusion gradient, from which you can derive a value at an exact point on that line, on the fly. Diffusion gradients are cheap and can be used by multiple enemies at once, as they describe the environment, and not the entity's view of it (a bit like radiosity lighting) -- probably why you've opted for the approach you have in your question. This gradient should be relatively smooth, so as to evoke organic movement from the enemy, and obviously updates as your gamestate does. Perhaps moving average?

The gradient should combine:

  • Proximity
  • Velocity
  • Breadth of bullet
  • (optionally) Position of targets (players)

For dodging, we have to be able to find a solution accurately whenever a solution exists. Such is the case whenever there is a gap small enough for the enemy to dodge through. That is, you can only do what you can do, so the gradient approach will work no worse than any other approach in this sense, I'd say.

The diffusion gradient should push the enemy towards local optima (being the peaks in the graph) with less imperative to move, the closer we are to a local minimum, hence a diminishing returns effect on dodging. This opens the door to more intelligent decision-making as to when the enemy has a good opening to fire.

If the need to fire is greater than the need to move, then do so; your code may also determine this by how much they differ. You can implement this as part of the base graph, in which case the player position reduces the surrounding values in the graph (assuming enemies gravitate to the lowest point), which combines all decision-making into one graph, or you can keep the "desire to fire" graph separate from the main "desire to dodge" graph, which will offer you more direct control.

IRL, I wouldn't bother dodging a projectile until it's within a distance which I know, at my top dodging speed, is starting to become difficult to avoid. First hand experience from throwing stones as a lad. A bullet at x distance travelling at velocity y has the same danger rating as a bullet at 2x distance travelling at 2y. So this needs to be factored in correctly.

Ways to tweak the algorithm for enemy difficulty include

  • introducing a latency on updates to the graph (Born Too Slow)
  • introducing random, localised innaccuracies into the graph
  • simply not having enemies obey what the graph tells them, over a sequence of updates (say 1 to 10 frames) due to sheer AI laziness.

Again, you can either implement all the factors into one graph (less control, and less useful for multiple enemies), or into several graphs which you look at together to get the results (more modular, probably works better for multiple enemies). It's hard to be more specific, as there are a lot of directions you can take this approach.

share|improve this answer
1  
Dear Nick. I went ahead an implemented a small test-version of that behavior in flash and I'm very pleased by the result (bullets are spawned randomly). I'm currently using 3 gradients, one for threat, movement cost and a static one for the edges (so that edges of the screen are less desirable). They are visualized in the flash application. I feel that with some tweaking I can achieve very good results and also factor in other weights like shooting positions. Thanks a lot mate. –  bummzack Nov 12 '11 at 9:39
1  
Hey @bummzack, it's a pleasure mate, that's a cool little demo! Your view of the problem was new to me and looked interesting -- I'm glad to see it works! Glad to help with it, and thanks for sharing. –  Nick Wiggill Nov 12 '11 at 11:36
add comment

This can be looked at as a pathing problem. Instead of thinking how the baddy avoids the bullets, imaging the bullets are static and the baddy must travel through them to the bottom of the screen.

    E    
B  B**B
  B***B  B
 B***B   B
B**B** B 
 B**B**BB
B*****B B
      P

E = enemy
B = bullet
P = player
* = path options to bottom of screen

Once the baddy has plotted a successful path it just needs to take the next step each time. There are probably already some good algorithms around for path finding such as this. If the baddy moves at the same speed as the bullets one example algorithm might be;

Start at the baddy and mark safe positions in empty spaces to the below left, directly below and below right. Then consider each safe space you have just created and repeat. If at any time you find there are no safe spaces below then mark the space as not safe and backtrack.

share|improve this answer
1  
Interesting approach. I fear that this is kinda expensive though as the environment changes so fast and it's hard to use common path-finding algorithms as they work best with discrete "maps". –  bummzack Nov 11 '11 at 10:48
    
It shouldn't be too expensive, don't forget that you only have to calculate the bottom row each turn, you don't have to recalculate the whole thing. –  Qwerky Nov 11 '11 at 10:59
    
@bummzack Environment is not "fast", at least, in terms of computer. For game developer, you should understand, that almost every game is step based, it is just about size of that step. But, at each step, calculations can be made, so Qwerky soltuion is the thing you need. –  Deele Nov 11 '11 at 11:26
    
Actually, I agree with @bummzack. While this approach is logically solid, it will be more expensive than the 1D approach proposed in the question. May be premature optimisation, but I find that approach to be far more elegant. See my answer for an elaboration on that. –  Nick Wiggill Nov 11 '11 at 12:00
2  
This is probably the proper answer, but not exactly a realistic one. In the time it takes the enemy to work out a path, the field can have another set of bullets invalidating the path completely, meaning that recalculating the path would be a must. And recalculation is a bitch. Furthermore, your idea of backpropagating to a point where it was safe makes it even more expensive! @Nick Wiggill I don't think it's premature optimisation, just good foresight to ensure you don't kick yourself in the crotch. –  Ray Dey Nov 12 '11 at 18:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.