LoginLogin

Possible Reasons For Snagging Corners

Root / Programming Questions / [.]

randoCreated:
rando#1
Hey friends! I’m very confused! I’ve been laying the foundations for a game, and part of that foundation is collision. I know, we all struggle when it comes to collision! It’s for some reason like the hardest thing ever. I’ve got a solid AABB Swept algorithm down, meaning I’m fairly sure I’m happy where that’s it, however at this point in my confusion I wouldn’t be totally surprised if the problem is there, only a little surprised. I’d expect it to be more likely in the other part of the process, which is when we’re dealing with a tilemap. The main part of the process when dealing with a tilemap is sorting the tiles by distance from the player. At first I thought this was suspect for snagging, because usually the culprit is not sorting the tiles properly. However, I’ve inspected this process meticulously and am driving myself crazy. There could very well be something wrong, but I can’t figure out what it is. The issue is apparent whenever you have tiles arranged next to each other, forming a continuous flat surface. The player should be able to glide along this surface smoothly, and at high frame rates it might appear that they are. However, when the speed drops or specifically when the player attempts to jump up against a wall, they very clearly snag. It’s especially clear jumping, because it cancels all vertical velocity and the player falls like a rock. This happens at any speed horizontally too, it’s just much more apparent at slower speeds. Usually this happens because the tiles are checked in a bad order. Checking a far away tile before checking a closer tile can lead to making an unnecessary adjustment to either component of the player’s velocity. That of course leads to the snagging effect. However, I was under the impression that I did sort the tiles properly. Here’s what code I used: 
’Sorting all nearby possible tiles
DEF PROX_TILES(RX,RY,BX,BY,EX,EY)’RX/RY are player coordinates (tiles), BX/BY/EX/EY are the box of tiles to check

DIM PXM[0]
DIM DIST[0]

VAR I,J
FOR I=BX TO EX STEP SGN(EX-BX)
FOR J=BY TO EY STEP SGN(EY-BY)

PUSH PXM,I+J*MAP_WIDTH%’Turns coordinates into single number
PUSH DIST,POW(I-RX,2)+POW(J-RY,2)’Distance FROM PLAYER (no sqrt)

NEXT
NEXT

SORT DIST,PXM
RETURN PXM
END

‘Checking collisions with sorted table 
PXM=PROX_TILES(RX,RY,BX,BY,EX,EY)’Sort tiles

VAR I
VAR X,Y
DIM R2[0]
FOR I=0 TO LEN(PXM)-1

Y=FLOOR(PXM[I]/MAP_WIDTH%)’Y tile coordinate
X=PXM[I]-Y*MAP_WIDTH%’X tile coordinate

IF X<0 || Y<0 || X>MAP_WIDTH%-1 || Y>MAP_HEIGHT%-1 THEN CONTINUE
IF RTB[X,Y,0]==-1 THEN CONTINUE’If there is no tile there

R2=PULL_RECT(RTB,X,Y)’Pull single tiles from array
IF LEN(R2)==0 THEN CONTINUE
R1=STD_RECT_VS_RECT(R1,R2)’Resolve collision

NEXT
I’m really not sure what it could be, if the problem isn’t with that code. It seems to still want to adjust for the other tiles anyway, like maybe it does check in the right order but it still makes unnecessary adjustments for the other tiles. I’m not sure why it would do that, because I think in my code I adjust the R1 velocity before it’s used again for the check, but something is clearly not quite right. An interesting quirk that’s probably related is that it still snags when for example the player jumps straight up with no horizontal velocity. I’m not 100% sure why that could be, but it might drag us back to the collision algorithm itself? Any thoughts or input would be greatly appreciated! I hope I’m not going crazy!
TheV360#2
oh, quick thing -- wrap your code in an [​code​][​/code​] block to avoid BBCode triggering from array usage! the parser accidentally made a part of your code invalid, as it saw an [​i​] tag, erased it, and made text after it italic. unfortunately though, you might need to give up your em-dash comments. 
OPTION STRICT

?"like so"

' blah blah

—Y tile coordinate
rando#3
Thank you for telling me. I’ve grown to love em-dash comments thanks to lua ;) Another kind of update: it didn’t really change the results too much in terms of snagging, but now instead of using POW to calculate tile distances, I literally just use the RECT_VS_RECT function to get the collision time without resolving the collision (if collision time is 0.5, collision occurs at the point halfway across the velocity vector, 0.25 is a quarter across and etc.). That way, we get the distance in terms of the player’s velocity which is better in this situation because we want to check tiles that fall in the path and we want to check closer tiles that are on the path before further ones. This really should fix the snagging, but the cause must be something else and I have no idea what it could be beyond the vaguely developed idea of something to do with width. EDIT: As an additional update, I’ve done some experimenting and took the tilemap out of the equation, and it looks like the problem does lie somewhere either in RECT_VS_RECT or RAY_VS_RECT. I’m not sure exactly what the problem is though. Here’s the code for each: 
DEF RECT_VS_RECT(R1,R2)

DIM R[0]

DIM SR[0]’expanded rectangle
PUSH SR,R2[0]-R1[2]/2’0 and 1 are x/y, 2 and 3 are w/h
PUSH SR,R2[1]-R1[3]/2’(Position 2) - (half height 1)
PUSH SR,R2[2]+R1[2]’(width 2) + (width 1)
PUSH SR,R2[3]+R1[3]’(height 2) + (height 1)

DIM RV[0]’velocity vector
PUSH RV,R1[0]+R1[2]/2’Center of R1
PUSH RV,R1[1]+R1[3]/2
PUSH RV,R1[4]’R1 velocity
PUSH RV,R1[5]

R=RAY_VS_RECT(RV,SR)

RETURN R

END

DEF RAY_VS_RECT(RAY,RECT)

DIM R[0]

VAR RX,RY
IF RAY[2]==0 THEN RX=POW(10,-8) ELSE RX=RAY[2] ENDIF
IF RAY[3]==0 THEN RY=POW(10,-8) ELSE RY=RAY[3] ENDIF

VAR TNEAR_X,TNEAR_Y
VAR TFAR_X,TFAR_Y

TNEAR_X=(RECT[0]-RAY[0])/RX
TNEAR_Y=(RECT[1]-RAY[1])/RY

TFAR_X=(RECT[0]+RECT[2]-RAY[0])/RX
TFAR_Y=(RECT[1]+RECT[3]-RAY[1])/RY

IF TFAR_X<TNEAR_X THEN SWAP TFAR_X,TNEAR_X
IF TFAR_Y<TNEAR_Y THEN SWAP TFAR_Y,TNEAR_Y

IF TFAR_X<TNEAR_Y || TFAR_Y<TNEAR_X THEN RETURN R

VAR THITNEAR=MAX(TNEAR_X,TNEAR_Y)
VAR THITFAR=MIN(TFAR_X,TFAR_Y)

VAR NX,NY

IF TNEAR_X>TNEAR_Y THEN
 NX=-1*SGN(RAY[2])
 NY=0
ELSEIF TNEAR_Y>TNEAR_X THEN
 NX=0
 NY=-1*SGN(RAY[3])
ENDIF

PUSH R,THITNEAR
PUSH R,THITNEAR*RAY[2]+RAY[0]
PUSH R,THITNEAR*RAY[3]+RAY[1]
PUSH R,NX
PUSH R,NY
RETURN R

END
rando#4
I am still going crazy, even though now I’m not tired. I’ve tried everything I’ve thought of so far, the biggest thing being a possible rounding problem. The square’s width is 13 pixels, so I thought perhaps in the rectangle function where we expand the target rectangle’s size, it might get confused by the decimal and expand the rectangle an extra pixel. However, if that were the case, the horizontal velocity should theoretically be stopped a pixel sooner and the vertical velocity should never be impacted. On top of that, experimentation shows that even if the width were 14 or 16 pixels, the problem persists. What the heck is going on? I even like double checked my ray algorithm with the javidx9 video I learned this concept from (https://m.youtube.com/watch?v=8JJ-4JgR7Dg) and made tiny revisions here and there just so they’re mathematically the exact same, and the problem still isn’t solved. Why is the computer detecting and resolving a collision that doesn’t exist?
rando#5
Another update: I believe the problem might lie in my RAY_VS_RECT function. At this point I’ve isolated that function by making a small program where I can control a ray, and there’s a rectangle to test if the ray intersects with it. Here’s what I discovered: If the ray passes directly through one of the sides of the rectangle in such a way that they look like the same line (parallel and overlapping), an intersection is discovered. However, if the ray just barely hits one of the sides (not parallel), no intersection is detected. An intersection will be detected however once the ray is at least 1 pixel inside the rectangle. Perhaps an important note: an intersection is technically detected in the perpendicular case but the time to the collision is 1 so in practice the player’s velocity would not be changed and borders would still end up overlapping. Whereas, in the parallel case the time to the collision is always less than one and the overlapping borders will always cause an abrupt velocity change. I think this might be the culprit. If the ray represented the player’s velocity (which in practice, it does), the center of the player would end up exactly on the border of the expanded rectangle targets. This seems fine, they’ve stopped and their hitbox border exactly overlaps the target not expanded rectangle’s border. However, once the player jumps and the velocity is parallel to the tiled wall, the velocity now crosses the higher rectangle as in the first situation where an intersection was detected, thanks to the second situation putting us in this position. The player hits a ceiling that doesn’t exist. As for the solution? I’m not totally sure… yet. I’m not exactly sure which case is more problematic—the parallel lines or the perpendicular lines. But perpendicular lets the player’s box mesh with the target and parallel doesn’t, and I’m not exactly sure what in the maths leads to that but it’s causing issues.
MZ952#6
This is not an answer to your problem but I remember getting so frustrated with this stuff (I watched that exact same video) that I completely reverted to a simplistic but expensive collision engine I hope you figure this out because I experienced similar "snagging" problems that I guess I just couldn't resolve lol
rando#7
Well and it’s so weird because I’ve done the same thing on Lua for example, and it works fine. I wonder if it’s my error or some subtle thing with SmileBASIC. Either way, I hope I can figure it out because if I can’t I might have to resort to normal AABB which I don’t really want to do.
rando#8
So as a new development, I’ve now removed the tiles because this seems like such a rough fix and I want to move on to other stuff. Now collision is based on larger rectangle units, however this could still cause potential problems like if you have a 1-block high horizontal tunnel the player can jump against. In this oddly specific scenario, this issue could still be painfully visible. In short, I’d still like to resolve this issue if possible, only now I’m trying to get other stuff done because I don’t want to be hung up on this forever. As for the nature of the bug, I just discovered something super strange. When the horizontal velocity is exactly at zero, the bug doesn’t happen. As in, when my stick is in the “neutral” position, the bug occurs, but when I multiply the player’s horizontal velocity by zero in the code, it stops occurring and works the way I want it to. Could the bug literally just be my circle pad being funky, giving the player a minuscule amount of horizontal velocity that ultimately shouldn’t matter but still ends up changing the collision? Maybe in the ray function I’ll round velocity to the nearest tenth or something, and hopefully that might help? We’ll see. UPDATE: So this is kind of interesting. Rounding in the ray function did not really solve the problem in the main program, but it did solve the problem in the rectangle demo. What I observed is that moving straight up and down in the rectangle program 9/10 times moves smoothly, however 10/10 times still snags in the main program. I don’t really think it’s because of some subtle difference in the code, although it might be. More likely I think is just that the problem is somewhere else. I don’t know where it could be though. Perhaps related to gravity vs controlling vy via stick input, I’m really not sure. I’m really just tired right now so I’ll think about it more tomorrow.