Question about collision detection with other objects

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

User avatar
SusiKette
Posts: 138
Joined: Fri Mar 16, 2018 1:52 pm
Location: Finland

Question about collision detection with other objects

Post by SusiKette » Sat Nov 14, 2020 3:35 am

I have been looking into collision detection and found one method where rather than using hitboxes, the code uses a distance to measure if a hit has occurred. The required distance seems to be calculated something like this:

Code: Select all

pw = width of player's hitbox
ow = width of object's hitbox
dist_x = ((pw/2) + (ow/2))

*the camera relative coordinate has to be at the center of the object for the hit to occur equally on both sides
Here is an example of the code:

Code: Select all

Test_Object_Collision:
		LDA player_x_rel		; player x position relative camera
		SEC
		SBC obj_00_x_rel,X		; current object's x position relative camera
		BCS ResultPlusX			; X reg has current object slot
		
		EOR #$FF				; reverse sign if result was negative
		CLC
		ADC #$01
		
ResultPlusX:
		CMP Hit_Distance_X,Y	; compare result to required distance for collision
		BCS NoCollision			; Y reg has the index to the desired hit distance
		
		LDA player_y_rel		; player y position relative camera
		SEC
		SBC obj_00_y_rel,X		; current object's y position relative camera
		BCS ResultPlusY			; X reg has current object slot
		
		EOR #$FF				; reverse sign if result was negative
		CLC
		ADC #$01
		
ResultPlusY:
		CMP Hit_Distance_Y,Y	; compare result to required distance for collision
						; Y reg has the index to the desired hit distance 
NoCollision:
		RTS ; ------------------------------------------------
So my question is; Is this a common way of handling collision between objects and are there other types? Once you have collision, how would one go about making a code for solid enemy (like frozen enemies in Metroid)? I tried to write some code in a more modern game engine and it always seemed to have some bug especially when moving diagonally. Although I'm not sure if that was due to something in the engine itself or if it was in my code.
Avatar is pixel art of Noah Prime from Astral Chain

Oziphantom
Posts: 1080
Joined: Tue Feb 07, 2017 2:03 am

Re: Question about collision detection with other objects

Post by Oziphantom » Sat Nov 14, 2020 6:52 am

you are forgetting that distance is sqrt((X1-x2)^2+(Y1+Y2)^2) in your case you are adding X and Y which is not the distance.
So you check X delta against X distance and Y delta against Y distance, and if they are both in range you hit. This gives you Axis Aligned Bounding Box Detection. If one fails you can exit early.

The other technique is to shrink one to a point and expand the other to compensate, this is call Minkowski collision.

User avatar
SusiKette
Posts: 138
Joined: Fri Mar 16, 2018 1:52 pm
Location: Finland

Re: Question about collision detection with other objects

Post by SusiKette » Sun Nov 15, 2020 6:35 am

Do these two detection methods have any differences? Like speed or some advantages?
Avatar is pixel art of Noah Prime from Astral Chain

Oziphantom
Posts: 1080
Joined: Tue Feb 07, 2017 2:03 am

Re: Question about collision detection with other objects

Post by Oziphantom » Sun Nov 15, 2020 6:44 am

Multiply is very expensive, SQRT very very very expensive ( but you can easily avoid the SQRT ). Expensive to the point of, never do it unless you truly must.

AABB vs AABB needs more checks than Minkowski Shape vs point.

to detect if two boxes overlap between two boxes A and B

if (A.left > B.left && A.left < B.right) || (A.right > B.left && A.right < B.right) &&
(A.top> B.top && A.top < B.bottom) || (A.bottom > B.top && A.bottom < B.bottom)

vs Minkowski Shape ( which is an expanded AABB ) vs point

if (point.x > A.left && point.x < A.right && point.y > A.top && point.y < A.bottom)

it is a lot faster. But you have to store point offsets and expanded shapes over just shapes so it uses more storage.

User avatar
tokumaru
Posts: 12000
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Question about collision detection with other objects

Post by tokumaru » Sun Nov 15, 2020 7:54 am

What I've been doing lately is this:

1- Subtract the X of one object from the X of the other one to find the horizontal distance between them. To keep things fast (8-bit math), I ignore distances larger than 255 (there are no hitboxes large enough to cause collisions between objects that far from each other).

2- Subtract half of the width of each object from the distance (assuming the hotspots are at the center of the hitboxes, otherwise use the appropriate offsets defined some other way). If the result is negative (distance is smaller than the partial hitboxes combined), this means that there's a horizontal overlap.

3- Repeat steps 1 and 2 for the vertical axis. If there's a vertical overlap as well, the objects are colliding.

This is very similar to the idea presented in the fist post, and it works very well.

As for objects being solid, you'll have to detect the direction of the collision (based on the velocities of the objects) and react accordingly. Collisions from the sides or from below should act like collisions against the background, where the solid object will eject the invading object by the necessary number of pixels.

Walking on solid objects is more complicated, since one object has to essentially be carried by another. In this case, it helps to implement a "standing on" field in each object's RAM, where you can reference another active object that needs to be followed. If an object is marked as "standing on" another, every frame you adjust its vertical position according to the hitbox of the solid object, and also apply the same horizontal displacement, so that the solid object effectively carries any objects that are standing on it.

User avatar
SusiKette
Posts: 138
Joined: Fri Mar 16, 2018 1:52 pm
Location: Finland

Re: Question about collision detection with other objects

Post by SusiKette » Mon Nov 16, 2020 1:47 am

I'm assuming you can also use the distance required for collision to calculate how much the other object needs to be pushed back to not be inside the other object. Since you are checking X and Y separately, does it matter which one you check first? Especially if moving into another object diagonally.

I guess if you want to have the hotspot at the bottom of the object you can use the full height of the object that is below the other object.
Avatar is pixel art of Noah Prime from Astral Chain

Oziphantom
Posts: 1080
Joined: Tue Feb 07, 2017 2:03 am

Re: Question about collision detection with other objects

Post by Oziphantom » Mon Nov 16, 2020 2:17 am

you would pick which case is more likely to be not true more often. So in a horizontal scrolling game you would choose X first, in a vertical scrolling game you would choose Y first. This way you "exit faster" from the test and hence save the extra test and hence clocks.

User avatar
SusiKette
Posts: 138
Joined: Fri Mar 16, 2018 1:52 pm
Location: Finland

Re: Question about collision detection with other objects

Post by SusiKette » Mon Nov 16, 2020 2:29 am

I mean if object moves diagonally into another object and you want to push the object out, whether you should push the object out in X or Y axis first? If it depends, how do I figure out in which case X is first and when Y? I think having the order wrong can cause incorrect behavior when the code attempts to push the object out.
Avatar is pixel art of Noah Prime from Astral Chain

Oziphantom
Posts: 1080
Joined: Tue Feb 07, 2017 2:03 am

Re: Question about collision detection with other objects

Post by Oziphantom » Mon Nov 16, 2020 3:05 am

shouldn't matter. As you will push in both directions either way in a single "update".

User avatar
SusiKette
Posts: 138
Joined: Fri Mar 16, 2018 1:52 pm
Location: Finland

Re: Question about collision detection with other objects

Post by SusiKette » Mon Nov 16, 2020 3:34 am

Here are few examples:

1. Player jumps while moving left/right and hits the bottom of solid object. You would need to push the player down here. But if you push player on X axis first the player would zip to the side of the solid object.

2. Similar case if player falls while moving left/right and hits the side of the solid object. You would need to push player sideways, but if you push on Y axis first the player would zip on top of the object.

This is what I mean by the incorrect behavior I mentioned in my previous post. And it also is the reason I wasn't able to make a functioning collision code in a modern game engine like I mentioned in original post.
Avatar is pixel art of Noah Prime from Astral Chain

Oziphantom
Posts: 1080
Joined: Tue Feb 07, 2017 2:03 am

Re: Question about collision detection with other objects

Post by Oziphantom » Mon Nov 16, 2020 3:50 am

1.) the player penetrates the object from below. So you have a +y push out vector. They are still moving on the X.

So get position
x += xDelta
y += yPushOut
..next frame
or
y += yPushOut
x += xDelta
..next frame

result either way before the next collision result they are no longer inside the object above them are still moving a long the x

2.)
the player penetrates the object from the side. So you have -x push out vector. They are still moving on the Y.

So get position
x -= xPushOut
y += yDelta
..next frame
or
y += yDelta
x -= xPushOut
..next frame

result either way before the next collision result they are no longer inside the object above them are still moving a long the y

User avatar
SusiKette
Posts: 138
Joined: Fri Mar 16, 2018 1:52 pm
Location: Finland

Re: Question about collision detection with other objects

Post by SusiKette » Mon Nov 16, 2020 4:40 am

How do you then detect from which side the player "penetrates" the solid object? Do you need a special case if the player penetrates the object exactly from a corner?
Avatar is pixel art of Noah Prime from Astral Chain

Oziphantom
Posts: 1080
Joined: Tue Feb 07, 2017 2:03 am

Re: Question about collision detection with other objects

Post by Oziphantom » Mon Nov 16, 2020 5:27 am

when you collide A against B. you will do a A.x - B.x and the sign of this tells you which way you need to move. If negative then B.x is to the right of A.x and you want to move A.x -penetration. If positive then B.x is to the left and you want to move A.x + penetration.

Exactly on a corner will give you a penetration in both X and Y but you will probably want them to "still make it" rather then get pushed back out completely. So you might want to add a special case.

Typically for backgrounds, you don't check AABB against the world but instead check multiple points around the person. This way you check middle "in front", diagonally down and below middle. Then with these 3 points of information and your state or heading. You can choose what it is best to do.
Here is a 16K game that has collision system in it. https://github.com/oziphantom/Qwack64/b ... r/qwak.asm Its not the best, and it does have the "get stuck in corners" problem, but I left it as it was a real life saver on the harder levels and I was up against the 16K limit.
newCollision is sprite to sprite and then checkSpriteToCharCollision is sprite to background.

User avatar
tokumaru
Posts: 12000
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Question about collision detection with other objects

Post by tokumaru » Mon Nov 16, 2020 7:24 am

SusiKette wrote:
Mon Nov 16, 2020 1:47 am
I'm assuming you can also use the distance required for collision to calculate how much the other object needs to be pushed back to not be inside the other object.
Yeah, the negative result after you subtract the partial hitboxes from the distance should tell you the amount of overlap between the hitboxes.
Since you are checking X and Y separately, does it matter which one you check first? Especially if moving into another object diagonally.
In my experience, the order in which you check each axis when detecting collisions only makes a significant difference when you need objects to land on platforms... If an object is falling and moving horizontally towards a platform, you may want to update the X position first, so the object stays above the platform, and then Y, making the object land on it. If you moved in the Y axis first, the object would possibly go below the top of the platform, and hit its side after the horizontal movement, causing it to miss the platform, which can be frustrating for players.
I guess if you want to have the hotspot at the bottom of the object you can use the full height of the object that is below the other object.
That's generally how I set up my hitboxes, with the hotspot at the bottom, horizontally centered, but since I don't like to hardcode this kind of stuff (certain objects may attach to walls or ceilings, in which case I'd like to put their hotspots near the surfaces they attach to, or they might have extensible limbs, causing the left and right parts of the hitbox to be uneven), I actually define each hitbox as a set of 4 offsets relative to the hotspot. This way I can easily pick any side I need, and I can also freely resize and rotate the hitboxes to match the current state of each object.

User avatar
SusiKette
Posts: 138
Joined: Fri Mar 16, 2018 1:52 pm
Location: Finland

Re: Question about collision detection with other objects

Post by SusiKette » Wed Nov 25, 2020 12:21 pm

I think I have a good idea on how the solid collision should be made. Not sure if it was mentioned here, but I heard of technique where you compare how much the hitboxes overlap on X and Y axis and push out the axis that has least overlap. If they are equal you could implement special cases on which axis to prioritize. Now I just need to start thinking how to write that code efficiently.
Avatar is pixel art of Noah Prime from Astral Chain

Post Reply