0

So I'm using Unity to do this, but I'm not sure that matters.

I have enemies that are off the visible screen, and I'd like to have indicators on the side of the screen to denote where they are. That's fine, but there's a lot of enemies so I want to group them into blobs. As in, rather than showing 8 indicators on top of each other, I want 1 indicator with an (8) next to it.

So right now, my algorithm is:

  • minimum blog range is a constant that I set
  • loop through all enemies
    • check distance to all enemies already assigned to blobs, if within range, assign to blob
    • if not, check other non-assigned enemies, if any are within blob range, make a blob

I'm doing this every frame, and it feels inefficient. What can I do to improve this as well as save on processing between frames. As in, what could I do with the previous frame's data to make this better (since the likelihood of the blob's members changing is very low, but it'll definitely have an updated position).

Or, should I just stop worrying about it and continue on, because it's just vector math and it isn't really going to cause problems for the engine.

Lex Li
  • 60,503
  • 9
  • 116
  • 147
Brent
  • 23,354
  • 10
  • 44
  • 49
  • I'm not quite clear on your indicators. Are you indicating position or just direction? That is, do you want to have a sort of radar that shows rough location, or an arrow that points to where the enemies are without giving the range? – Michael J. Barber Jul 08 '11 at 07:23
  • Just an arrow on the edge --> that indicates where they are coming from and how many there are. – Brent Jul 08 '11 at 07:30
  • If two enemies are in the same direction, but different ranges, should they be assigned to a group? – Michael J. Barber Jul 08 '11 at 07:39
  • yes, i'd consider those discreet blobs and the user would want to know they were separate waves. That'd be easy enough to change if I felt like it later, just group by angle distance rather than actual distance. – Brent Jul 08 '11 at 08:42

2 Answers2

2

Construct a low-resolution grid that gives a coarse view of the area. Assign each enemy to the appropriate grid location (should be directly calculable). Show an indicator to each occupied grid location; the locations with one enemy get individual enemy indicators, the locations with multiple enemies get group indicators.

In practice, I'd expect a sparse representation to make more sense than actually constructing the whole grid.

Note that essentially the same idea is used in detecting collisions.

ADDENDUM. A minor modification may be appropriate for purely directional indicators. If you have two enemies in the same direction, but at different distances, the grid approach would lead to two indicators in the same direction. If that's undesirable, base the calculations on the bearing to the enemy, splitting the 360 degree circle into coarse wedges, like a pie chart with all areas equal. Group enemies based on which slice of the pie they belong to.

Michael J. Barber
  • 24,518
  • 9
  • 68
  • 88
1

You're probably fine with whatever you have currently as far as processing power in concerned.

There is an interesting approach to the problem of proximity grouping using genetic algoritms: http://www.cbu.edu/engineering/maesc/maesc03/FullPapers/d3-1-doc.pdf

Also, this links here look promising: K-means algorithm variation with equal cluster size

But honestly, I'm good enough at math to actually give a solid answer...

Community
  • 1
  • 1
ElonU Webdev
  • 2,451
  • 14
  • 15