I need some ideas.

Unity Engine
1

Hey everyone. I am working on a project that could benefit from what I am trying to accomplish. What I am working on is a method for finding all game objects with a certain tag and find “clumps” of these objects. So far I have just been trying to come up with a good method for doing this. Here is an illustration of what I am talking about.

671101--24076--$Illustration Clumps2.jpg
671101--24076--$Illustration Clumps2.jpg516×516 33.2 KB

Does anyone have any ideas about how this may be accomplished?

2

How often do you want to make this check?

An expensive method would be to use OverlapSphere and check how many objects bear the tag you want. Do this for each object in a group, keep adding new objects to the group until you have done an OverlapSphere on all the items.

Untested code:

var clumps=ArrayList();
var overlapDistance=10.0;

function FindClumps(){
	clumps=new ArrayList();
	var clump=new ArrayList();
	var objs=GameObject.FindGameObjectsWithTag("Ball");
	for(var i=0; i<objs.Length; i++){
		if(clump.IndexOf(objs[i]) == -1){
			var newClump=GetOverlapedItems(objs[i]);
			if(newClump.Count>0){
				newClump=GetClump(newClump);
				clumps.Add(newClump);
				clump=MergeClumps(clump, newClump);
			}
		}
	}
	
	// print out your clumps here.
}

function GetClump(clump : ArrayList){
	for(var i=0; i< clump.Count; i++){
		var newClump=GetOverlapedItems(clump[i]);
		clump=MergeClumps(clump, newClump);
	}
	return clump;
}

function GetOverlapedItems(checkObj : GameObject){
	var objs=Physics.OverlapSphere(checkObj.transform.position, overlapDistance);
	var clump=ArrayList();
	for(var obj : Collider in objs){
		if(obj.gameObject != checkObj  obj.gameObject.tag == checkObj.tag)
			clump.Add(obj.gameObject);
	}
	return clump;
}

function MergeClumps(clumpA : ArrayList, clumpB : ArrayList){
	for(var i=0; i< clumpB.Count; i++){
		if(clumpA.IndexOf(clumpB[i]) == -1) clumpA.Add(clumpB[i]);
	}
	return clumpA;
}

Lots of OverlapSpheres is probably bad for the economy.

3

Well I would like to have it run every frame. I don’t think that would be probable though. If the calculations were performed in portions over the spread of several frames that would be ok. I don’t know how many frames are calculated per second be if the check ran once every second that wouldn’t be too bad.

Your code looks good as far as I can tell. There are some parts I haven’t ever used before though. Also, after the clump is found, is there a way to average all of the positions of the objects in the clump?

4

An easier way would be to create a low resolution grid and update each object to belong to a cell. Then you can just do a count neighbours function in the array to get a rough approximation. You’ll avoid sqrt and all distance checks this way, which will be faster than even a few distance checks, but not as accurate. It depends on your cell size for accuracy.

I’m not sure what its for, so its hard to recommend a solution.

5

I am using this for an AI project of mine. When a certain object detects a large group of enemies it needs to know to avoid them.

Also, what would you use for the grid?

6

I would suggest you investigate the Separating Axis Theorem, it is what hippocoder described and has been used for many years in 2D games to perform very fast collision detection. This was in the days before partitioning trees were even feasible.

Any book on game development that is more than a decade old will have C/C++ solutions to this very problem. Black Art of Java Game Development I recall had one in Java.

7

@JustinLloyd Thanks! I’ll look into this.

8

Another idea might be to just attach a box or sphere collider as a trigger to each of the gameobjects, and then just do a count in OnTriggerEnter/OnTriggerExit