I am testing out making a powder-based physics engine, and I have quickly run into a problem: there are too many collision checks for my computer to load after about 150 particles. I need a physics engine that will be able to load many more collisions than that, possibly in the thousands, and some of these particles will do multiple collision checks. All the particles are being checked for a collision with all the other particles at once, and they are all 2x2 squares. Any suggestions for a better collision system?
var ctx = document.getElementById("c").getContext("2d");
var powder = {};
var mouseX = 0;
var mouseY = 0;
var click = false;
var select = 0;
var types = {
0: "green",
1: "blue",
2: "brown",
3: "grey"
}
document.onmousemove = function(mouse) {
mouseX = mouse.clientX - document.getElementById('c').getBoundingClientRect().left;
mouseY = mouse.clientY - document.getElementById('c').getBoundingClientRect().top;
};
function newPowder(x, y, type, id) {
var temp = {
x: x,
y: y,
type: type,
checked: false,
};
powder[id] = temp;
};
function choose(a, b) {
if (Math.random() > 0.5) {
return a
} else {
return b
}
}
document.onkeydown = function(event) {
if (event.keyCode === 40) { //Down
select--;
} else if (event.keyCode === 38) { //Up
select++;
} else if (event.keyCode === 32) { //space
click = true;
};
if (select > 3) {
select = 3;
} else
if (select < 1) {
select = 0
};
}
document.onkeyup = function(event) {
if (event.keyCode === 32) {
click = false
};
};
var interval = setInterval(function() {
ctx.clearRect(0, 0, 500, 500);
if (click) {
newPowder(Math.round(mouseX / 2) * 2, Math.round(mouseY / 2) * 2, select, Math.random() * 50);
};
for (var key in powder) {
var toContinue = false;
drawDot(powder[key].x, powder[key].y, types[powder[key].type])
if (powder[key].type == 3) {
continue
}
if (powder[key].onGround == false) {
for (var key2 in powder) {
if (getDistanceBetweenEntity(powder[key], powder[key2]) < 3) {
if (collisionCheck(powder[key2].x, powder[key2].y, 2, 2, powder[key].x, powder[key].y + 2, 2, 2)) {
powder[key].onGround = true
if (powder[key2].type == 2 && !powder[key].checked) {
powder[key].checked = true;
powder[key].x += choose(choose(2, -2), 0);
};
};
};
};
};
if (toContinue) {
continue;
}
if (powder[key].x > 500 || powder[key].y > 500) {
delete powder[key];
continue;
}
if (!powder[key].onGround) {
powder[key].y += 2;
checked = false;
} else if (powder[key].type == 1) {
powder[key].x += choose(2, -2);
}
powder[key].onGround = false;
};
}, 0);
function rectangleContainsPoint(x1, y1, width, height, x, y) {
if (width <= 0 || height <= 0) {
return false;
}
return (x >= x1 && x <= x1 + width && y >= y1 && y <= y1 + height);
};
function drawDot(x, y, color) {
ctx.save();
ctx.fillStyle = color;
ctx.fillRect(x, y, 2, 2);
ctx.restore();
}
function collisionCheck(x1, y1, width1, height1, x2, y2, width2, height2) {
if (x1 < x2 + width2 && x1 + width1 > x2 && y1 < y2 + height2 && height1 + y1 > y2) {
return true;
};
};
getDistanceBetweenEntity = function(entity1, entity2) {
var vx = entity1.x - entity2.x;
var vy = entity1.y - entity2.y;
return Math.sqrt(vx * vx + vy * vy);
};<!DOCTYPE html>
<html>
<head>
</head>
<body>
<canvas id="c" width="500px" height="500px" style="border:1px solid #000" onclick="click = true"></canvas>
</body>
<script src="script.js" type="text/javascript"></script>
</html>Up and Down arrows to change particle type. Space to spawn particles.
Naturally a quadratic complexity algorithm isn't going to scale very well with more particles where you check for collision of every particle against every other particle. You want to reduce the search time per particle from linear to logarithmic or better.
Acceleration structures useful here could be a fixed grid or a quad tree or K-d tree.
Instead of checking for a particle collision against every other particle, put your particles into a grid structure or hierarchy (quad tree).
For the grid, simply check the particles residing in the same grid cell(s) as the particle you are testing for collision (there could be multiple if the particle has a non-zero size).
The quad tree is simply an extension of this concept with an "adaptive" grid that forms a hierarchy. The K-d tree is similar, except it's a binary tree instead of a 4-ary tree which cycles between X/Y partitions of the search space, and doesn't have to subdivide evenly (however, it is typically the most expensive to construct among these three).
The tricky part here is that when your data is very dynamic, as in this case, you have to be able to build and update the structure fast enough. So sometimes a simpler structure like the fixed grid can work better here than the quad tree since it's easier to build that more quickly even though it provides lower-quality spatial queries.
In any case, any kind of accelerator here should make your algorithm scale a whole lot better, and I would suggest the fixed grid for starters, and the quad tree if you need even faster collision queries in exchange for increased time building and updating the accelerator.
Also given the nature of your program so far where the particles are only affected by gravity in a straight downward fashion, an even simpler way than the above methods is to sort your particles by their X position (can use radix sort to do this in linear time). Then you can do a binary search to find which particles are first in the X proximity to narrow the number of tests you are performing to logarithmic. This is potentially even worse than the fixed grid in terms of search query since it has pathological cases where all particles could be in the same X position (a fixed grid would account for both X and Y), but it's a quick way to do it.