Precisely how is place_meeting calculated?

[NoChill]

Hi!

I will admit I haven't looked intensely, but after a little google searching, I can't seem to find a detailed description of how place_meeting is calculated.

My guess is that for non-precise collisions it's checking if any two adjacent sides of caller's bbox and collision objects bbox are overlapping like such:

caller.bbox_right >= other.bbox_left && (caller.bbox_bottom >= other.bbox_top || caller.bbox_top <= other.bbox_bottom)​

Repeated for all sides.

And for precise collisions, it's basically doing point_meeting for every point defined by the caller's collision mask and checking against the colliding objects collision mask?
And this is why precise is much slower?

Please correct me if I'm wrong!
Thanks.

 

[Simon Gust]

Hi!

I will admit I haven't looked intensely, but after a little google searching, I can't seem to find a detailed description of how place_meeting is calculated.

My guess is that for non-precise collisions it's checking if any two adjacent sides of caller's bbox and collision objects bbox are overlapping like such:

caller.bbox_right >= other.bbox_left && (caller.bbox_bottom >= other.bbox_top || caller.bbox_top <= other.bbox_bottom)​

Repeated for all sides.

And for precise collisions, it's basically doing point_meeting for every point defined by the caller's collision mask and checking against the colliding objects collision mask?
And this is why precise is much slower?

Please correct me if I'm wrong!
Thanks.

precise is only precise after it has done the normal place_meeting with bounding boxes, only then it starts checking every pixel for collision (with the object it has already collided with). So, normal slow until bounding box contact, then very slow.

 

[NoChill]

precise is only precise after it has done the normal place_meeting with bounding boxes, only then it starts checking every pixel for collision (with the object it has already collided with). So, normal slow until bounding box contact, then very slow.

Ah, that makes total sense.
Another thing I thought about. For this to work the calling object has to loop through every object specified in the place_meeting call right?

So essentially let's say, having the player check for collision against 100 hostile projectiles would be equal to having each projectile check for collision with the player?
Since in both cases there are 100 collision checks?

 

[deathzero021]

I'm curious to know this as well. It would be very inefficient to simply for loop through every instance to check for collisions. I'd hope they have a more optimized solution, which I think they do because generally speaking collision checking is pretty fast all things considered.

One interesting solution I've read is in the Doom source code. Carmack created a blockmap system that allowed for super fast collision checking. Basically only instances in the same blockmap would check for collisions with each other. This does introduce some rare bugs but it was a smart compromise back in the early 90's when PC processors were pretty slow. So there are definitely great ways to optimize the collision checking process.

 

[NoChill]

I'm curious to know this as well. It would be very inefficient to simply for loop through every instance to check for collisions. I'd hope they have a more optimized solution, which I think they do because generally speaking collision checking is pretty fast all things considered.

One interesting solution I've read is in the Doom source code. Carmack created a blockmap system that allowed for super fast collision checking. Basically, only instances in the same blockmap would check for collisions with each other. This does introduce some rare bugs but it was a smart compromise back in the early 90's when PC processors were pretty slow. So there are definitely great ways to optimize the collision checking process.

That does sound interesting. I'm guessing then that you would sort all instances running collision checks in a data grid and loop through instances x tiles away from the checker?

I thought of a similar simpler solution where I would do a point_distance based on collision mask radius on collider and checker first and then check potential collisions on instances close enough that way. But then again it needs to do a distance check for every instance we want to check for collision against so I don't know that it would be faster. Might run a test.

Still curious about my original question.

 

[DullShrimp129]

It checks an array between numbers, you can actually calculate collisions without place_meeting and do it manually the way to do so is as follows:
if(x<=Object.x-100) && x >= Object.x+100 //Collision Horizontal
if(y<=Object.y-100) && y >= Object.y+100 //Collision Vertical

Combine them to get full collisions, place_meeting does as the function says, it checks for a meeting of positions between the two object so if the x and y of the object is equal to the collision object it returns true.
For collision check with no place_meeting, do as follows:
if(x<=Object.x-100) && x >= Object.x+100 && y<=Object.y-100 && y >= Object.y+100{//Excute Collision Code}
(The 100 is the size of the object, so if your object is 32x32 set the number to 32, if you want an exact messuring of all objects replace the 100 with sprite_width/2)

 

[Nidoking]

(The 100 is the size of the object, so if your object is 32x32 set the number to 32, if you want an exact messuring of all objects replace the 100 with sprite_width/2)

Pretty sure you're better off just using bbox_left, bbox_right etc. for exact locations of the bounding box rather than calculating it yourself. If the point is to attempt to reinvent the wheel, it's not a good idea to put the corners in from the start.

Not sure what the purpose of the original question is, honestly. The people who know how Game Maker works internally aren't likely to tell you anything that isn't public, and the people who don't can't give you a better answer than what you've already got. If you just want to know why collisions are slower for precise sprites, then yes, it's because it's done pixel by pixel. I don't think you need to know how it works to figure that much out.

 

[chamaeleon]

Seems like it may be possible to use bitwise operators on preprocessed bitmasks representing occupied pixels. 64 bits segments for each sprite could then in theory be used to determine collisions. If (a & b) != 0 then at least one pixel overlap in each sprite out of 64 pixels and there is a collision. Process 64 bit integers until all pixels have been processed or an overlap is found. The aspect of handling rotations is left as an exercise for the interested reader.

 

[NoChill]

Not sure what the purpose of the original question is, honestly.

Not trying to reinvent the wheel nor do I have any issues with how the function works. Just trying to gain a better understanding of what's going on since having full control is what I love about Game Maker.

It checks an array between numbers, you can actually calculate collisions without place_meeting and do it manually the way to do so is as follows:
if(x<=Object.x-100) && x >= Object.x+100 //Collision Horizontal
if(y<=Object.y-100) && y >= Object.y+100 //Collision Vertical

Combine them to get full collisions, place_meeting does as the function says, it checks for a meeting of positions between the two object so if the x and y of the object is equal to the collision object it returns true.
For collision check with no place_meeting, do as follows:
if(x<=Object.x-100) && x >= Object.x+100 && y<=Object.y-100 && y >= Object.y+100{//Excute Collision Code}
(The 100 is the size of the object, so if your object is 32x32 set the number to 32, if you want an exact messuring of all objects replace the 100 with sprite_width/2)

This is helpful, thanks.

Seems like it may be possible to use bitwise operators on preprocessed bitmasks representing occupied pixels. 64 bits segments for each sprite could then in theory be used to determine collisions. If (a & b) != 0 then at least one pixel overlap in each sprite out of 64 pixels and there is a collision. Process 64 bit integers until all pixels have been processed or an overlap is found. The aspect of handling rotations is left as an exercise for the interested reader.

Can't say that I've looked into bitwise operators at all so this is very intriguing. Could this be more efficient than place_meeting? If so why?

 

[chamaeleon]

Could this be more efficient than place_meeting? If so why?

Not more efficient if that is what is done under the hood in the first place (I have no idea if it is or not). It would just be an implementation detail of the function. It is also quite possible that the efficiency of performing bitwise operations representing up to 64 pixels may be eaten up by any required preprocessing to create suitable integers. Especially when it comes to rotations as it is possible the amount of work required to create the integers is equivalent to performing the tests, in which case doing the integer tests is just unnecessary overhead. I'm sure GMS implements the function more or less as efficiently as possible whether it utilizes this or not.

Anyway, assume two 4x4 sprites (I don't feel like making a 64x64 example...), both placed at the same coordinates. Do they collide using precise masks?

Exact bounding box overlap
+----+   +----+
|1111| & |0000| -> 0000 (result zero, proceed to next pair)
|1000| & |0011| -> 0000 (result zero, proceed to next pair)
|1000| & |1111| -> 1000 (result not zero, collision detected)
|1111| & |0011| -> 0011 (not tested because a collision was already detected)
+----+   +----+

One pixel shift difference horizontally, adding a digit
+----+     +----+
|1111|0 & 0|0000| -> 00000 (result zero, proceed to next pair)
|1000|0 & 0|0011| -> 00000 (result zero, proceed to next pair)
|1000|0 & 0|1111| -> 00000 (result zero, proceed to next pair)
|1111|0 & 0|0011| -> 00010 (result not zero, collision detected)
+----+     +----+

Two pixel shift difference horizontally, adding two digits
+----+       +----+
|1111|00 & 00|0000| -> 000000 (result zero, proceed to next pair)
|1000|00 & 00|0011| -> 000000 (result zero, proceed to next pair)
|1000|00 & 00|1111| -> 000000 (result zero, proceed to next pair)
|1111|00 & 00|0011| -> 000000 (result zero, no collision detected)
+----+       +----+

Iterating over 4 pairs of integers *might* be cheaper than iterating over 16 pixel positions if the setup of the integers doesn't outweigh the benefits.