Sign in to follow this  
codex1x

Efficient algorithm to stop enemies from converging

Recommended Posts

codex1x    100
[left][font=Arial,][color=#000000]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 severely slows the program down.[/color][/font][/left]


When my program runs with this function the enemies seem to form a round object I nicknamed a "clump". The clump seems to usually be egg-shaped with the small tip in the direction of the player. I do like the way the clump behaves, however it currently uses a O(n^2) algorithm. Is there a way to calculate the clump all at once, perhaps as a polygon (straight edges are fine it doesn't have to be exactly round) with a O(n) or better algorithm (n being the number of enemies inside).

Currently all enemies move toward the player and then the clump function is used. Here are the two functions for this.

[code]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[/code]

I also posted this question of stack overflow:[url="http://stackoverflow.com/questions/9777882/directing-a-mass-of-enemies-at-once"]http://stackoverflow...enemies-at-once[/url] however no one there knew how to make the algorithm less than O(n^2) which is what is needed for high number of enemies

Share this post


Link to post
Share on other sites
alvaro    21246
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.

Share this post


Link to post
Share on other sites
jefferytitan    2523
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.

Share this post


Link to post
Share on other sites
codex1x    100
[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.
[/quote]
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.

[quote name='jefferytitan' timestamp='1333707373' post='4928728']
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.
[/quote] 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:
[url="http://imageshack.us/photo/my-images/651/elip.png/"]http://imageshack.us/photo/my-images/651/elip.png/[/url]
[url="http://imageshack.us/photo/my-images/836/gamewk.png/"]http://imageshack.us/photo/my-images/836/gamewk.png/[/url]
[url="http://imageshack.us/photo/my-images/832/newfni.png/"]http://imageshack.us/photo/my-images/832/newfni.png/[/url] Edited by codex1x

Share this post


Link to post
Share on other sites
alvaro    21246
Let's imagine you use a k-d tree. The algorithm would go something like this:
[code]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.
}
[/code]

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.

Share this post


Link to post
Share on other sites
jefferytitan    2523
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.

Share this post


Link to post
Share on other sites
alvaro    21246
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.

Share this post


Link to post
Share on other sites
slicer4ever    6760
[quote name='codex1x' timestamp='1333740737' post='4928881']
[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.
[/quote]
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.

[quote name='jefferytitan' timestamp='1333707373' post='4928728']
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.
[/quote] 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:
[url="http://imageshack.us/photo/my-images/651/elip.png/"]http://imageshack.us...s/651/elip.png/[/url]
[url="http://imageshack.us/photo/my-images/836/gamewk.png/"]http://imageshack.us...836/gamewk.png/[/url]
[url="http://imageshack.us/photo/my-images/832/newfni.png/"]http://imageshack.us...832/newfni.png/[/url]
[/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.

Share this post


Link to post
Share on other sites
codex1x    100
[quote name='alvaro' timestamp='1333743046' post='4928892']
Let's imagine you use a k-d tree. The algorithm would go something like this:
[code]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.
}
[/code]

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.
[/quote]

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

[quote name='jefferytitan' timestamp='1333776795' post='4928973']
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.
[/quote]

Quadtrees seem like another good option, are they or k-d trees more often used for nearest neighbor searches?
[quote name='alvaro' timestamp='1333806426' post='4929032']
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]

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.

[quote name='slicer4ever' timestamp='1333818676' post='4929090']
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.
[/quote]
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)

Share this post


Link to post
Share on other sites
jefferytitan    2523
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.

Share this post


Link to post
Share on other sites
jefferytitan    2523
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this