# Predictive Rectangle Collision Resolution Corner Snagging

I've written two main functions who's purpose is to detect and resolve collisions between a moving rectangle and a non-moving rectangle. I have a decent understanding of how the algorithm works, and in practice it works very nicely... except for of course the classic tiny bug that drives everyone insane!

Overall, the functionality goes like this. You have a rectangle with a velocity, and one that doesn't. Using the velocity of one rectangle, you determine if and when (along the velocity vector) a collision occurs with the other rectangle. Then using the time of the collision, you adjust the velocity component to avoid collision.

This works pretty great, in 99% of cases! Moving the player rectangle towards the target rectangle yields the right results at most angles, however like 8 specific (and relatively common) cases mess the whole thing up.

For example, when I move the player rectangle until it's collided with the top side of the target rectangle, that lines it up so the bottom of the player is touching the top of the target. Then if I move the player directly to either side, and try to move back, the player gets snagged on the corner of the target and cannot proceed. At this point, only the corners of each rectangle are barely touching.

Of course, for an added layer of "what's going on?" this only applies to the top, bottom and right sides of the target rectangle. When I've tried the same thing on the left side of the target, the player still experiences effects but it's not a full stop; it's merely just a slowing down.

In order to figure out what it could be, it's necessary to look directly at how the code works. The function rayVsRect is responsible for checking the velocity against a rectangle, and finding the time of the collision (alongside returning other useful stuff like a contact point and a normal vector). rectVsRect is responsible for carrying out collision detection between the two rectangles. It expands the target rectangle by the dimensions of the other rectangle. That way we can simply use the rayVsRect function to get the same values we want. The language is lua by the way, just in case that makes a difference to know, maybe perhaps in knowing the subtleties of how data is stored or other fun stuff like that. Who knows? (Hopefully it's not that)

function rayVsRect(ray, rectangle)
local invDir = {vx = 1 / ray.vx, vy = 1 / ray.vy}

local nearX = (rectangle.x - ray.x) * invDir.vx
local nearY = (rectangle.y - ray.y) * invDir.vy
local farX = (rectangle.x + rectangle.width - ray.x) * invDir.vx
local farY = (rectangle.y + rectangle.height - ray.y) * invDir.vy

--Turn nan values into "infinity"
if nearX ~= nearX then
nearX = 4294967296 * math.sign(rectangle.x - ray.x)
farX = 4294967296 * math.sign(rectangle.x + rectangle.width - ray.x)
end
if nearY ~= nearY then
nearY = 4294967296 * math.sign(rectangle.y - ray.y)
farY = 4294967296 * math.sign(rectangle.y + rectangle.height - ray.y)
end

if farX < nearX then farX, nearX = nearX, farX end
if farY < nearY then farY, nearY = nearY, farY end

if (nearX > farY) or (nearY > farX) then return 0 end

local contactTime = math.max(nearX, nearY)
local farContactTime = math.min(farX, farY)

if farContactTime < 0 then return 0 end

local contactPoint = {x = ray.x + contactTime * ray.vx, y = ray.y + contactTime * ray.vy}

local contactNormal = {x = 0, y = 0}
if nearX < nearY then
if ray.vy > 0 then
contactNormal.y = -1
else
contactNormal.y = 1
end
else
if ray.vx > 0 then
contactNormal.x = -1
else
contactNormal.x = 1
end
end

return {contactTime = contactTime, contactPoint = contactPoint, contactNormal = contactNormal}
end

function rectVsRect(velocity, rectangleOne, rectangleTwo, dt)
if velocity.vx == 0 and velocity.vy == 0 then return 0 end

local expandedRectangle = {
x = rectangleTwo.x - rectangleOne.width / 2,
y = rectangleTwo.y - rectangleOne.height / 2,
width = rectangleTwo.width + rectangleOne.width,
height = rectangleTwo.height + rectangleOne.height
}
local ray = {
x = rectangleOne.x + rectangleOne.width / 2,
y = rectangleOne.y + rectangleOne.height / 2,
vx = velocity.vx * dt,
vy = velocity.vy * dt
}

local collision = rayVsRect(ray, expandedRectangle)

return collision
end


The way velocity is adjusted is handled by the hitbox component in my whole system. I don't need to include the whole thing, but an excerpt of how the velocity is adjusted will probably be helpful to think about as well.

  local collision = {}
collision = rectVsRect(velocity, rectangleOne, rectangleTwo, dt)

if type(collision) ~= "table" then return end
if (collision.contactTime < 0) or (collision.contactTime >= 1) then return end

velocity.vx = velocity.vx + collision.contactNormal.x * math.abs(velocity.vx) * (1 - collision.contactTime)
velocity.vy = velocity.vy + collision.contactNormal.y * math.abs(velocity.vy) * (1 - collision.contactTime)


There are lots of things that could be the problem, and I'm having trouble narrowing it down and coming up with the right tests to figure it out. I feel like this sort of error, where there's nothing wrong syntactically but it doesn't behave quite how you want it to, is the hardest sort of error to figure out, but likely the most important to get good at solving.

These are the things that come to my mind of what it could be:

• Some slight problem in the rayVsRect maths/logic, perhaps related to the "infinity" that comes about when dividing by 0. Now that I think about it, in this case the expanded rectangle's position might be the same as the ray's position in whatever direction it is, which would make math.sign(rectangle.x - ray.x) equal to 0. Maybe the subtlety is there? I'll investigate that pretty soon, but for now I don't know.

• Something to do with expanding the rectangle in rectVsRect, maybe I did the math or logic slightly wrong? Compared to other's versions that I've learned this technique from though, it looks almost exactly the same as far as I can tell, and their versions work very nicely

• Something to do with the resolution technique, although I really can't think of anything it could be

In summary, I'm not entirely sure what the problem is. The strongest lead seems to be my first bullet point, but I think I need help navigating this. I'm not really sure how to test it in either case. I like to think I'm good at coding/math, but things like this really make me feel small, and in ways that's a good thing. I'd like to overcome it, and learn how to be better at this, but I would also really appreciate help!

EDIT: So update after digging into the divide by zero thing. My suspicions lead me to investigate how the math worked out. I originally had to add a little if statement after calculating the near and far times in rayVsRect because a divide by zero would turn the values to nan. This caused the player rectangle to disappear because its transform wasn't a pair of numbers anymore. Normally I don't think this is a problem in a language like C++ (I learned this way of detection/resolution from someone who coded in C++), but it was a problem here in lua.

I was very suspicious of what happened when I used 'math.sign(). I had to code in this function for this purpose and others, and it simply looks like this:

function math.sign(x)
if x < 0 then
return -1
elseif x > 0 then
return 1
else
return x
end
end


This seems fine and all, and it really is, but it was causing issues in the bit of code that turned nans into really large numbers. In any language that would produce an infinity instead of nan, that would be fine for rayVsRect because the comparison below would still yield the wanted results.

if (nearX > farY) or (nearY > farX) then return 0 end


My extra bit of code was supposed to turn the nans into a large number to simulate this same sort of math that works. However, the fact that math.sign() returns 0 when the input is 0 kind of messes things up.

When the ray's velocity and rectangle's side perfectly line up in any way, that creates one of these situations where 0 is returned from math.sign(). For example, if the velocity vector perfectly passes through the top side of the rectangle, math.sign(rectangle.y - ray.y) would give us 0. Then the snagging would occur, because 0 is undoubtedly less than whatever farX is (it's probably well over 1 at my player's speed).

I don't really know the most efficient way to adjust my code, and could perhaps use some help with that. I've thought about changing math.sign() but I think the way it works is fine, and I use it for other functions too. I've also thought about making a new math.sign() specifically for this, but I'm not sure how it would work. This is because each different situation needs either a positive 1 or negative 1, and there's no way math.signNewAndImproved() would be able to tell without clunkily passing it in.

I tried a slightly clunky solution by adding a couple of if statements. My code went from this:

--Turn nan values into "infinity"
if nearX ~= nearX then
nearX = 4294967296 * math.sign(rectangle.x - ray.x)
farX = 4294967296 * math.sign(rectangle.x + rectangle.width - ray.x)
end
if nearY ~= nearY then
nearY = 4294967296 * math.sign(rectangle.y - ray.y)
farY = 4294967296 * math.sign(rectangle.y + rectangle.height - ray.y)
end


To this:

--Turn nan values into "infinity"
if nearX ~= nearX then
nearX = 4294967296 * math.sign(rectangle.x - ray.x)
farX = 4294967296 * math.sign(rectangle.x + rectangle.width - ray.x)

if rectangle.x == ray.x then nearX = 4294967296 end
if (rectangle.x + rectangle.width) == ray.x then farX = -4294967296 end
end
if nearY ~= nearY then
nearY = 4294967296 * math.sign(rectangle.y - ray.y)
farY = 4294967296 * math.sign(rectangle.y + rectangle.height - ray.y)

if rectangle.y == ray.y then error(tostring(farY)) nearY = 4294967296 end
if (rectangle.y + rectangle.height) == ray.y then farY = -4294967296 end
end


However, I've run into a slightly different dilemma. This actually solved the problem for the top and left sides of the target rectangle, however it did pretty much nothing for the bottom and right sides of the rectangle. Why could this be? It must be a math error, I guess I'll have to figure it out!

New contributor
Vonkswalgo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Logically, your task is pretty simple; particulary when there is no rotation. During each frame, based on velocity, current position and angle, you can predict where you will wind up by the end of the frame. Each rectangle has 4 (corner) points. Anytime one of these points is "contained" in the others rectangle, it's a collision; and you either deal with it or avoid it if "predicting". One has to be aware of course if the interval "travel" will take you "beyond" the point of collision, so you adjust "duration" accordingly (impact distance / total frame travel) * frame time. Commented yesterday

So here was the problem: When the player rectangle moves directly to the side, it calculates the nearY and farY as nan because they end up dividing by zero. Other languages would calculate this as infinity, and with the maths that would be okay, however lua unfortunately isn't like that. So, I had a block of code that turned nearY into infinity if it was nan. This is where the issue was.

The maths would work out because it would be either positive or negative infinity, and that would cause the actual collision check to work anyway. I needed to make the really large number either positive or negative depending on the context, and to do that I initially used a math.sign() function I wrote. The problems emerged when math.sign() returned zero, because the input was zero. Funnily enough, the only instance where this was the case (and was problematic) was when the ray's position was equal to the (expanded) rectangle's position or its position plus size. That's only when you're sliding along the sides of the block; that was causing the corner snagging.

In the end, the solution wasn't too crazy. Maybe slightly clunky, but I just used an if statement to check if the ray's position was equal to the rectangle's position, and adjusted accordingly. No more snagging. The end. Hopefully. I'm done with rectangles.

The final code block for resolving nans looks like this:

if nearX ~= nearX then
nearX = 65536 * math.sign(rectangle.x - ray.x)

if rectangle.x == ray.x then nearX = 65536 end
end

if farX ~= farX then
farX = 65536 * math.sign((rectangle.x + rectangle.width) - ray.x)

if (rectangle.x + rectangle.width) == ray.x then farX = -65536 end
end

if nearY ~= nearY then
nearY = 65536 * math.sign(rectangle.y - ray.y)

if rectangle.y == ray.y then nearY = 65536 end
end

if farY ~= farY then
farY = 65536 * math.sign((rectangle.y + rectangle.height) - ray.y)

if (rectangle.y + rectangle.height) == ray.y then farY = -65536 end
end
`

It could probably be modified to be less clunky and more readable, but this does what I need it to and it works well!

New contributor
Vonkswalgo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.