Detecting area with high amount of other objects

The title is not clear enough as I struggled to word it. However, I’ll try my best to explain here.

I am trying to make a rally behaviour in which a bot will seek all of its “teammates” in range, finds the area where most of them are, and goes there.

For example(Given image):
edit: in my drawing forgot to make the arrow towards the: “Largest group in range”, this is where I’d like the bot to go to"

I want my bot to detect the location of the biggest group of teammates within its range and go there.

Assume that I know:
-Know all of my teammates(list of teammates)
-Know which ones are in-range
-Know their position(and other attributes, as I have their instances)

Appreciating your comments! :slight_smile:

You need to make clear for yourself what a “group” is. For example, the group of 5 in your image may aswell be a group of 3 and a grou of 2, or a 5 groups of 1, depending on your definition of what a group is. Create some example images for yourself and define rules for what a group is. Would a line of dots be a group? Or only things clustered together? Also what happens when a 4-group is fully in range, but only 3 dots of a 10-group are in range; which is the larger group you drive to? And so on. After you have your logical rules down for what makes things a group, you can start figuring out what groups there are.

You could now attempt an easy approach for finding groups. Get one of the dots in your range, check the group-rules for it, add all dots that come up to its group, check the group-rules for them as well, and continue until you found all dots in that group. However, this can get expensive. For one bot that’s fine. Assuming you intend to do these calculations for all the dots in the image separately, there is no way it would run in realtime.

So under that assumption you will need to heavily cut down on the calculation costs. For this you should calculate the existing groups once and then keep track to changes to them (dots entering or leaving the group) over time. To further cut down on costs you could implement an Quadtree.

Either way, i hope this gives you some ideas for how to continue.

1 Like

I was hoping not to relay on groups at all…
I thought of somehow adding up all the vectors to all of the teammates in range(and normalizing), which would give a general direction towards the place with the largest amount of teammates, however, it is not nessicarily their location, meaning the bot might just end up not near those teammates, I’d like to find a way to find a more accurate way

What a fascinating problem! In your diagram, you have labeled a set of five teammates as “Largest in range.” What I notice first about that set of five is that, visually, I can easily see two sets of teammates: a set of three, to the upper-left of the area occupied by the whole set of five, and another set of two, to the lower-right. Further, that set of two is standing a bit apart from each other, so one could say they are not really a set, but two individuals.

This has me thinking we might want to define a multiplier for a given teammate that applies when that teammate is within a certain distance of another. That is, every teammate counts as one point for purposes of how big a group they are in. Then, for each teammate, add another point for every teammate within a certain distance (that distance being much smaller than your “range” circle). After that, you would move towards the teammate which had acquired the highest score.

That might be a start.

Yup, that’s not going to work, and you can already see why. A small group of three or four, all near each other, would be swamped by a dozen in another direction, all standing spread out along a line. I think what Yoreki and I have suggested is a better approach, though the computation is going to suffer from a combinatorial explosion if you have a lot of teammates.

I think what you are doing has a lot in common with Craig Reynolds’s “Boids” research. He dealt with flocks of birds and came up with some practical ways to divide space so that you don’t have to test every bird in a big flock against every single other bird. Have a look at his Web site. It might give you some good ideas.

1 Like

This is a good start indeed, combining with what Yoreki has said, it can give a good start. If you rely on the idea of groups. It’s not something I wanna strike down, however, I’d like to try vector calculations first, I mentioned my problem above, hopefully, there’s a way to make the calculation more accurate. like in the following image.

In there, I just quickly drew an arrow to each teammate representing the vector direction to them, and a red arrow representing the approximate (quickly just used my eyes no calculation there) normalized vector of all of them.
In there, you can see, working in such a method will yield an approximate direction towards the largest group, however not quite next to them, which could result in the bot not reaching the group as expected. It’s a much cheaper method so if there is a way to properly implement it I’d love to hear :slight_smile:

6454580--723173--Map.png

I agree, it will indeed swamp it a lot in the other direction in the given example, however, due to teammates in the larger group, I assume, the normalized direction should point to them(approximately) and all that’s left for me to figure out is how to make it more accurate from there.

However, if this method is destined to fail, I agree that yours and Yoreki’s method should work best. But due to this solution’s cheap cost, I’d like to at least try it first.

I believe the vector method is doomed. Your last image shows why, and you could easily create a more convincing version: Just put two groups at about a 170-degree angle from each other. Your summed vector is going to point 85 degrees away from each of them, into an unoccupied area.

Please do have a look at Reynolds’s Web page. You are going to find out that you are not the first person ever to have wanted to work on this. A lot of very good stuff has been published on it that I believe you will find helpful and that will save you a lot of time and wasted effort.

Soo… I made a quick experiment on Unity… the center cube is the bot, and the rest are teammates, the red line is the normalized vector…

As expected… it is not quite accurate…
Is there any for it to be better? Or do I have to take to second one?

6454637--723197--Map.png

Alright, I’ll take a look at it, I’ll update later on

Get vector of stronger group, rather than sum of all teammates, or groups.
You could also consider distance to groups.

Mentioned Boids concept, is something you may want to investigate.

I managed to do that, I used Stevens’ method for it.
Made groups based on the centroid of members and group distance.
If you’re interested in the way the code is:

private readonly List<RallyAI> group;
private Vector3 centroid;


public void Add(RallyAI ai) { group.Add(ai); centroid = Entity.Centroid(group); }
public float GroupRadius => 2 + 0.5f * group.Count;
private bool InRange(Entity entity) => Vector3.Distance(centroid, entity.transform.position) <= GroupRadius;


public static IEnumerable<RallyGroup> GroupUp(IEnumerable<RallyAI> teammates)
        {
            List<RallyGroup> groups = new List<RallyGroup>();

            foreach (var ai in teammates)
            {
                if (groups.Count == 0)
                {
                    var fg = new RallyGroup();
                    fg.Add(ai);
                    groups.Add(fg);
                    continue;
                }

                foreach (var g in groups)
                {
                    if (g.InRange(ai))
                    {
                        g.Add(ai);
                        continue;
                    }
                }

                var ng = new RallyGroup();
                ng.Add(ai);
                groups.Add(ng);
                continue;
            }

            return groups;
        }

It’s not quite the entire thing, but it’s the major part of it so I think it will do for this question, thank you all so much for helping me! :smile:

1 Like