Just another question about objects overlapping

Hi everyone, I can't reply in the old post made by R0J0hound with a great example

So, the question is what if I have a rectangle object instead of square, and can we avoid relying on layout size or its angle and work just with the necessary sprite?

The code from this example:

	const SIZE=150, radius=150, layoutW=runtime.layout.width, layoutH=runtime.layout.height,
	 COUNT=Math.ceil(layoutW/SIZE)*Math.ceil(layoutH/SIZE);
let grid=[];
for(let i=0; i<COUNT; i++) 
	grid.push([]); //init
function hash(x,y){
	return ((Math.floor(x/SIZE) + Math.floor(y/SIZE)*Math.ceil(layoutW/SIZE))%COUNT+COUNT)%COUNT;
}
function add2grid(obj,i){
	if(grid[i].length==0 || grid[i][grid[i].length-1]!==obj) 
		grid[i].push(obj);
}
globalThis.spatialGrid=function(){
	for(let i=0; i<COUNT; i++) 
		grid[i].length=0; //clear
	let objs = runtime.objects.sprite.getAllInstances();
	for(let i=0; i<objs.length; i++){
		let obj = objs[i];
		add2grid(obj, hash(obj.x-radius/2, obj.y-radius/2));
		add2grid(obj, hash(obj.x+radius/2, obj.y-radius/2));
		add2grid(obj, hash(obj.x-radius/2, obj.y+radius/2));
		add2grid(obj, hash(obj.x+radius/2, obj.y+radius/2));
	}
	for(let i=0; i<objs.length; i++){
		let obj1 = objs[i], h=hash(obj1.x, obj1.y);
		for(let j=0; j<grid[h].length; j++){
			let obj2 = grid[h][j];
			if(obj1===obj2) {
				grid[h][j]=null;
				continue;
			}
			if(obj2===null) 
				continue;
			let dist=Math.sqrt((obj2.x-obj1.x)**2+(obj2.y-obj1.y)**2);
			dist=Math.max(0, radius-dist)/10;
			//dist=(radius*(Math.max(0, radius-dist)/radius)**0.5)/5;
			//dist=radius/(dist/dist/10;
			if(dist>0){
				let ang=Math.atan2(obj2.y-obj1.y, obj2.x-obj1.x);
				obj1.offsetPosition(-dist*Math.cos(ang), -dist*Math.sin(ang));
				obj2.offsetPosition(dist*Math.cos(ang), dist*Math.sin(ang));
			}
		}
	}
};

That bit of code just resolves overlaps between a bunch of circles that are the same size. Then to make it faster all the circles are first added to a grid spatial hash.

So roughly it creates the grid spacial hash, adds the circles to all the grids their bounding box overlaps, then loops over the circles and uses the spacial hash to get other nearby circles, and finally it detects collision and pushes them apart.

I don’t understand the question to have a rectangle instead of a square. You can make the grid of any size but it just needs to be the same size or smaller than the circle size.

The layout size is used to have something to divide into grids. It could be made to reuse the same grids when objects are outside the layout. Probably by using x%layoutWidth or something.

The angle is used for the push out logic for circles. Circles are the simplest to do that for. Using object bounding boxes instead are a bit more complex. Beyond that the push out logic would require some fancier algorithm such as SAT,GJK/EPA, MPR, SDFs,…etc to do the collision detection and resolving.

If all you want to do is detect if two objects overlap it’s easiest to just use construct's js api overlapping function.

That example was just tailored to a specific thing. It’s not really general purpose without a fair amount of modification.

I don’t understand the question to have a rectangle instead of a square.

Hi R0J0hound, thanks for your reply and contribution to the community of course!

I managed to break all ties with the layout size, but I can't realize how to do the same spatial grid but not for circles or squares, but for rectangle sprites instead, which can change their angle during the gameplay? Now my rectangle sprites have like an "invisible field" on its longer sides that pushing out other similar sprites even before collision, but I'd like to keep it within the sprite rectangle. Is my explanation clear enough?

const SIZE = 144, radius = 144;
let grid = [];
let objs = runtime.objects.sprite.getAllInstances();

function calculateDistance(obj1, obj2) {
 return Math.sqrt((obj2.x - obj1.x) ** 2 + (obj2.y - obj1.y) ** 2);
}

function applyForce(obj1, obj2, dist) {
 let separation = Math.max(0, radius - dist);
 if (separation > 0) {
 let ang = Math.atan2(obj2.y - obj1.y, obj2.x - obj1.x);
 let force = separation / 12.5;
 obj1.offsetPosition(-force * Math.cos(ang), -force * Math.sin(ang));
 obj2.offsetPosition(force * Math.cos(ang), force * Math.sin(ang));
 }
}

globalThis.spatialGrid = function() {
 objs = runtime.objects.sprite.getAllInstances();

 for (let i = 0; i < objs.length; i++) {
 for (let j = i + 1; j < objs.length; j++) {
 let obj1 = objs[i];
 let obj2 = objs[j];
 let dist = calculateDistance(obj1, obj2);
 applyForce(obj1, obj2, dist);
 }
 }
};

So, the Separating Axis Theorem (SAT) is probably the easiest algorithm to use to implement collision detection and response between rotated rectangles. Here's one possible implementation in events:

dropbox.com/scl/fi/buz1axwu4pv9p16m2qos9/sat_test2.capx

I don't have a js version of that.