Preventing entities from stacking on top of eachother in an overhead shooter

Question

I'm working on an overhead shooter and what happens is, over time, as I move in circles around the arena, the enemies will begin to stack on top of each other until they're one giant stack of units. It ends up looking pretty silly.

The AI is pretty simple and basic: Find the player, move towards him, and attack him if he's in range.

What's the best way to push them away from each other so that they don't all end up on the same spot? I think flocking is a bit overkill (and probably too intensive since I'll have 100-200 enemies on the screen at a time).

Ideas?

Thanks!

Answer 1

Here are a few different approaches you could take to solving this problem:

1. You could define a potential field for each unit that associates a "height" or "badness" to each location on the map. Each unit moves in a way that tries to minimize its potential, perhaps by taking a step in the direction that moves it to the lowest potential that it can in one step. You could define the potential function so that it slopes toward the player, causing all units to try to move to the player, but also be very high around existing units, causing units to avoid bumping into one another. This is a very powerful framework that is exploited all the time in AI; one famous example is its use in the Berkeley Overmind AI for StarCraft, which ended up winning an AI StarCraft competition. If you do adopt this sort of approach, you could probably then tweak the potential function to get the AI to behave in many other interesting ways, and could easily support flocking. I personally think that this is the best approach to take, as it's the most flexible. It also would be a great starting point for more advanced pathfinding models. For a very good and practical introduction to potential fields for AI, check out this website. For a rigorous mathematical introduction to potential fields and their applications, you might want to check out this paper surveying different AI methods using potential fields.

2. If you define a bounding circle for each enemy, you could just explicitly disallow the units from stacking on top of each other by preventing any two units from being within two radii's distance of one another. Any time two units got too close, you could either stop one of them from moving, or could have them exert forces on one another to spread them apart. When two units bump into each other, you could just pick a random force vector to apply to each unit to try to spread them apart. This is a much hackier and less elegant solution than potential fields, but if you need to get something up and running it's definitely a viable option.

3. You could choose a set of points around the player that the units try to move toward, then have each unit randomly choose one of those target points to move to. This would cause the units to spread more thinly in a ring (or whatever shape you'd like) around the player, avoiding the huge masses that you've seen so far. Again, this is way less elegant than using potential fields, but it's another quick hack you could experiment with if your goal is to get something working quickly.

Hope this helps!