4 ms·
Actually a collision is an overlap with only one initial event. So collision = overlapping + state. That is an object collides initially but will perhaps contin
by aliswe 7y ago
Actually a collision is an overlap with only one initial event. So collision = overlapping + state. That is an object collides initially but will perhaps continue to overlap the other object.
In 2D games programming, at least in the old days, the detection effectively consisted of detecting whether NOT two objects were overlapping.
Consider this pseudocode formula:
function isOverlapping(a, b){
return a.x < b.x + b.w // a's left is to the left of b's right
&& // And
a.x + a.w > b.x // a's right is to the right of b's left
... And the same for vertical.
Compare with this :
function isOverlapping(a, b){
if(a.x > b.x + b.w) return false; // was to the right
if(a.x + a.w < b.x) return false; // was to the left
if(a.y > b.y + b.w) return false; // was below
if(a.y + a.h < b.y) return false; // was above
return true; // not not overlapping, so must be overlapping
}
Additionally, these constant additions were unnecessary for each permutation of the detection matrix, so you would store left and right sides whenever you moved an object:
function move(a, x, y){
a.left = x;
a.top = y;
a.right = a.x + a.w;
a.bottom = a.y + a.h;
}
Then the isOverlapping guard statements would be changed to:
if(a.left < b.right) return false;
Etc. Which is a cpu-over-memory optimization. But also makes the code easier to read ...
- vardump 7y agoIf you need to optimize this, on modern CPUs, you'd probably want to always run all tests and have just one exit, instead of multiple possible paths. That's easier said than done, because "&&" typically does generate a branch. In other words, doing significantly more computational work but less conditional branching can run significantly faster, because modern CPUs are built for this kind of code. Once you achieve completely branchless collision test, you've completely eliminated branch misprediction penalties inside it. I've sped up existing code too many times simply by removing if-statement checking if the work needs to be done... :-) That said, I find it highly unlikely 2D collision testing optimization running on modern CPU yields any measurable performance improvement.
- peterwoerner 7y agoA nice trick I have used for similar problems (although finite element related) is (x + abs(x))/2 returns x if x>0 and 0 if x<0.