11,927,711 members (29,362 online)
Rate this:
See more:
Well, this might sound as a weird algorithm discussion, it's a theoretical one, although I wouldn't mind seeing the abstract implementation. Here it is.

In a 2D game, you have a player and enemies in 2D space. A player has ranged attack as PlayerRange and enemies have their own range(s), but let's say they all have the same range of EnemyRange. What I'm interested in is how to separate a cloud of enemies into groups and circle them to death. here is my solution:

First, acquire range between enemies that will be considered as min-max range to be between each other in a group, and separate cloud of enemies into sub-clouds. Once this is done, create convex hull for each of sub-groups and determine closest sub-group player is to. If player is inside any of those, find closest line of the convex hull and follow in direction of normal to it until player is outside the sub-group.

While outside, construct expanded convex hull using PlayerRange and follow it from point to point until convex hull is no more (i.e. has only 2 enemies left). Once it is so, use simple sphere as path to follow around them until they are destroyed.

Now, all this assumes that sub-group and convex hull calculations are done on a per-frame basis, because enemies do move on their own and may merge from one sub-group to another. This raises a question as to which next point to go to. I think a good solution for this would be to choose next counter- or clockwise point around convex hull and go towards it.

What do you think, is this a good way of doing "circling to death" or are there others?

Posted 31-May-09 17:26pm
Edited 31-Dec-09 1:29am
v2

Rate this:

## Solution 1

Your question isn't very clear, but it appears you want some way to group enemies into clouds to surround them.

One approach is Cluster Analysis. Start with a list of all enemies and a table of the distances among them. Group the two closest enemies into a cluster. The cluster becomes a new "enemy" with a centroid (average X and Y coordinates). Continue grouping enemies until the closest are above some threshold. The clusters of enemies remaining are your compact clouds.

If you have many enemies to group, a KD-tree (http://en.wikipedia.org/wiki/Kd-tree[^]) is efficient for finding nearest neighbors.

Top Experts
Last 24hrsThis month
 OriginalGriff 204 Richard Deeming 175 Tadit Dash (ତଡିତ୍ କୁମାର ଦାଶ) 130 ppolymorphe 94 Jochen Arndt 80
 OriginalGriff 7,740 KrunalRohit 4,723 Sergey Alexandrovich Kryukov 3,658 George Jonsson 2,970 Suvendu Shekhar Giri 2,331