How to implement an intelligent enemy in a shoot-em-up?

Question

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

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:

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:

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

Answer 1

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.

Answer 2

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.