Efficient algorithm to stop enemies from converging

At the very least, you could use a partition algorithm (look up quadtrees and k-d trees) and reduce the complexity to O(n*log(n)). That would probably be good enough.

It depends what look/feel you want. For example, you could do it martial arts style, e.g. no more than x enemies attack at once, the rest stay back. Or you could do it patrol style, e.g. each enemy has an allocated area they won't step outside unless actively fighting the player. If you want to be a bit more AI Director like, you could have a varying "pressure function", e.g. you want to have varying amount of difficulty over time, and the pressure function determines how many enemies will be spawned, what proportion of enemies will actively pursue, how aggressive they are, etc.

At the very least, you could use a partition algorithm (look up quadtrees and k-d trees) and reduce the complexity to O(n*log(n)). That would probably be good enough.

Could you explain a bit. I looked into the Wikipedia articles on quadtrees and k-d trees and couldn't find how it would help my example. I am fairly new to these sort of things.

It depends what look/feel you want. For example, you could do it martial arts style, e.g. no more than x enemies attack at once, the rest stay back. Or you could do it patrol style, e.g. each enemy has an allocated area they won't step outside unless actively fighting the player. If you want to be a bit more AI Director like, you could have a varying "pressure function", e.g. you want to have varying amount of difficulty over time, and the pressure function determines how many enemies will be spawned, what proportion of enemies will actively pursue, how aggressive they are, etc.

The way I would like my game to behave, and the way it currently does, is that all enemies pursue the player. The problem is finding an efficient algorithm so that they do not converge on each other. My algorithm currently checks each enemy against every other enemy and if they are too close pushes them a little apart but this is O(n^2) which is too slow for >500 enemies.

What I'm really looking for if possible is a way to calculate the whole "clump" at once, possibly as a polygon. Since the game is moving at 40FPS it doesn't have to be perfectly accurate and the "clump" currently isn't smooth anyways. Its made up of many rectangles forming a almost round shape.
Here are some screen shots of how the clump now behaves:
http://imageshack.us/photo/my-images/651/elip.png/
http://imageshack.us/photo/my-images/836/gamewk.png/
http://imageshack.us/photo/my-images/832/newfni.png/

Let's imagine you use a k-d tree. The algorithm would go something like this:
Start with an empty k-d tree.
For each particle P {
Query the k-d tree to obtain a list of particles that are closer than some threshold.
For each particle Q in that list {
Compute a force or a displacement to be applied both to P and [its opposite] to Q.
}
Add P to the k-d tree.
}


For each particle P {
Move P a bit in the direction accumulated in the previous loop.
}


The trick is that inserting a particle in a k-d tree only takes time O(log(N)), and querying for particles that are very close to a particular location also costs O(log(N)). Because you do this for every particle, the resulting algorithm is O(N*log(N)), which is much faster than O(N^2) for large values of N.

This is how you find nearby neighbors is done in a k-d tree: As you descend through the tree in depth-first order, you can prune large branches if you know that the whole volume represented by a node in the tree is farther away than the threshold to the particle you are looking at.

Possibly quadtrees may be easier to start with. Break the area into 4 quadrants. If there's more than x enemies in any quadrant (you pick x, where x > 1) you break it up into 4 more quadrants, etc.

Actually, the easiest way to get started would be to use a fixed-size grid. Say you want your agents to push away from each other when they are 1m away or less. Divide your scene into square cells of side 2m and store the list of agents in each cell. When you want to find the list of agents that are 1m away or less from any other agent, you just need to look at its cell and 3 neighboring cells. This is both faster and simpler than using a k-d tree or a quadtree, but it might use more memory.

[quote name='alvaro' timestamp='1333685472' post='4928671']
At the very least, you could use a partition algorithm (look up quadtrees and k-d trees) and reduce the complexity to O(n*log(n)). That would probably be good enough.

Could you explain a bit. I looked into the Wikipedia articles on quadtrees and k-d trees and couldn't find how it would help my example. I am fairly new to these sort of things.

It depends what look/feel you want. For example, you could do it martial arts style, e.g. no more than x enemies attack at once, the rest stay back. Or you could do it patrol style, e.g. each enemy has an allocated area they won't step outside unless actively fighting the player. If you want to be a bit more AI Director like, you could have a varying "pressure function", e.g. you want to have varying amount of difficulty over time, and the pressure function determines how many enemies will be spawned, what proportion of enemies will actively pursue, how aggressive they are, etc.

The way I would like my game to behave, and the way it currently does, is that all enemies pursue the player. The problem is finding an efficient algorithm so that they do not converge on each other. My algorithm currently checks each enemy against every other enemy and if they are too close pushes them a little apart but this is O(n^2) which is too slow for >500 enemies.

What I'm really looking for if possible is a way to calculate the whole "clump" at once, possibly as a polygon. Since the game is moving at 40FPS it doesn't have to be perfectly accurate and the "clump" currently isn't smooth anyways. Its made up of many rectangles forming a almost round shape.
Here are some screen shots of how the clump now behaves:
http://imageshack.us...s/651/elip.png/
http://imageshack.us...836/gamewk.png/
http://imageshack.us...832/newfni.png/
[/quote]

may i also suggesting spreading your clump calculations over several frames. essentially, store the currently working enemy variable, and then, after each player has been checked against another player, see if the allocated function time has been met, and if so, continue with the rest of the game logic, until you get back to the function, and continue executing your clump function.

Let's imagine you use a k-d tree. The algorithm would go something like this:
Start with an empty k-d tree.
For each particle P {
Query the k-d tree to obtain a list of particles that are closer than some threshold.
For each particle Q in that list {
Compute a force or a displacement to be applied both to P and [its opposite] to Q.
}
Add P to the k-d tree.
}


For each particle P {
Move P a bit in the direction accumulated in the previous loop.
}


The trick is that inserting a particle in a k-d tree only takes time O(log(N)), and querying for particles that are very close to a particular location also costs O(log(N)). Because you do this for every particle, the resulting algorithm is O(N*log(N)), which is much faster than O(N^2) for large values of N.

This is how you find nearby neighbors is done in a k-d tree: As you descend through the tree in depth-first order, you can prune large branches if you know that the whole volume represented by a node in the tree is farther away than the threshold to the particle you are looking at.

Ok, also about how balanced should the K-D tree be if it is the form I decide to implement. The Wikipedia page suggests taking a random sampling of points and then finding the median of them to use each time a node is added. For this should I just take a random sample of a constant like 10 or should it vary with the amount of points (like 10*log(n)).

Possibly quadtrees may be easier to start with. Break the area into 4 quadrants. If there's more than x enemies in any quadrant (you pick x, where x > 1) you break it up into 4 more quadrants, etc.

Quadtrees seem like another good option, are they or k-d trees more often used for nearest neighbor searches?

Actually, the easiest way to get started would be to use a fixed-size grid. Say you want your agents to push away from each other when they are 1m away or less. Divide your scene into square cells of side 2m and store the list of agents in each cell. When you want to find the list of agents that are 1m away or less from any other agent, you just need to look at its cell and 3 neighboring cells. This is both faster and simpler than using a k-d tree or a quadtree, but it might use more memory.

In the end I may do something like this. One big factor with all this is that it doesn't need to be perfect. I may do what you described but not even check distance. If two enemies are in the same section just push them apart. It wouldn't be perfect but it should do the job and enemies won't converge.

may i also suggesting spreading your clump calculations over several frames. essentially, store the currently working enemy variable, and then, after each player has been checked against another player, see if the allocated function time has been met, and if so, continue with the rest of the game logic, until you get back to the function, and continue executing your clump function.

I will probably do something like this once I have a working implementation, but right now i think I need a better than O(n^2) algorithm for a high number of enemies to even work.

Thanks for all the reply's. Are there particular advantages to quadtrees vs k-d trees that make one or the other more common. Also with dividing the screen into a preset grid: I'm currently using fullscreen at 1400*1050 pixels, and checking if enemies are within 10 pixels of each other. With sections at 20*20 I would need 3675 sections. Would using this much memory impact performance?

I also had another idea but I'm not sure if it would work:
1. Compute each enemies distance to the player; O(n)
2. Sort these distances; O(n log n) I believe
3. The hard step which I'm not sure could be implemented in O(n log n) or better: In order based on distance, closest enemies first, attempt to move each enemy straight at the target. However if another enemy already moved is within a distance (say 5 pixels) the enemy will move differently. It will try to find the closest point to the target, within however many pixels it can move at once, from its current location (10-20 usually), that is not within 5 pixels of any enemy.

This is probably the "perfect" solution in how enemies would behave, but can it be done in O(n log n)

With approximation I think O(n) or better may be possible. For example, break enemies into various zones based on distance from the player. The ones closest to the player need to check for collisions every frame. Further away zones not every frame. If two enemies are very far away from the player they will travel in almost the same direction as each other, so have almost no chance of colliding, therefore less checks required. Plus the player may not see them collide even if they do.

Just to clarify, on re-reading the thing about O(n) or better sounded a little optimistic. I didn't do the math per se, but it's based on the idea that the more enemies there are, the further they must be away on average, and therefore the more liberties you can afford to take with approximation. You could also form ad-hoc squads in formation and only check for collisions between squads. If enemies frequently change squads it won't look too formation-based even if it is.