directing a mass of enemies at once

Question

I am working on a simple 2d game where many enemies continually spawn and chase the player or players in python + pygame. A problem I ran into, and one many people that have programmed this type of game have run into is that the enemies converge very quickly. I have made a temporary solution to this problem with a function that pushes any two enemies randomly apart if they are too close to each other. This works well but is about an O(n^2) algorithm which is run every frame and at high enemies the program starts to slow down.

When my program runs with this function the enemies seem to form round object I nicknamed a "clump". The clump seems to usually ecliptic but may actually be more complex (not symmetrical) because as the player moves the enemies are being pulled in different directions. I do like the way this clump behaves, however I am wondering if there is a more efficient way to calculate it. Currently every enemy in the clump (often >100) is first moved in the direction of the player, and then pushed apart. If there was instead a way to calculate the figure that the clump creates, and how it moves it would save a lot of computation.

I am not exactly sure how to approach the problem. It may be possible to calculate where the border of the figure moves, and then expand it to make sure the area stays the same.

Also my two functions currently being used to move enemies:

def moveEnemy(enemy, player, speed):
    a = player.left-enemy.left
    b = player.top-enemy.top
    r = speed/math.hypot(a,b)
    return enemy.move(r*a, r*b)

def clump(enemys):
    for p in range(len(enemys)):
        for q in range(len(enemys)-p-1):
            a = enemys[p]
            b = enemys[p+q+1]
            if abs(a.left-b.left)+abs(a.top-b.top)<CLUMP:
                xChange = (random.random()-.5)*CLUMP
                yChange = ((CLUMP/2)**2-xChange**2)**.5
                enemys[p] = enemys[p].move(int(xChange+.5), int(yChange + .5))
                enemys[p+q+1] = enemys[p+q+1].move(-int(xChange+.5),-int(yChange+.5))
    return enemys

Edit: some screen shots of how the clump looks: http://imageshack.us/photo/my-images/651/elip.png/ http://imageshack.us/photo/my-images/832/newfni.png/

http://imageshack.us/photo/my-images/836/gamewk.png/

The clump seems to be mostly a round object just stretched (like an eclipse but may be stretched in multiple directions), however it currently has straight edges due to the rectangular enemies.

Answer 1

There are several ways to go about this, depending on your game. Here are some ideas for improving the performance:

1. Allow for some overlap.
2. Reduce your distance checking to be done after a fixed number of frames.
3. Improve your distance checking formula. If you are using the standard distance formula, this can be optimized in many ways. For one, get rid of the square root. Precision doesn't matter, only the relative distance.
4. Each unit can keep track of a list of nearby units. Only perform your calculations between the units in that list. Every so often, update that list by checking against all units.
5. Depending on how your game is setup, you can split the field up into areas, such as quadrants or cells. Units only get tested against other units in that cell.

EDIT: When the units get close to their target, it might not behave correctly. I would suggest rather than having them home-in on the exact target from far away, that they actually seek a randomized nearby target. Like an offset from their real target.

I'm sure there are many other ways to improve this, it is pretty open ended after all. I should also point out Boids and flocking which could be of interest.