Click here to Skip to main content
13,091,248 members (53,646 online)
Rate this:
Please Sign up or sign in to vote.
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 16:26pm
Updated 31-Dec-09 0:29am

1 solution

Rate this: bad
Please Sign up or sign in to vote.

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 ([^]) is efficient for finding nearest neighbors.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month

Advertise | Privacy |
Web02 | 2.8.170813.1 | Last Updated 31 Dec 2009
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100