Jittering in Platformer when falling onto map tiles...

[SeanSeanston]

I'm making a platformer with Slick, so I've got a level made up of tiles that the player (currently a green rectangle) can collide into and walk on etc.

I've based my collision detection largely on the JNRDev tutorial here:
http://wiki.allegro.cc/index.php?title=Pixelate:Issue_13/jnrdev

I also have gravity working, where when the player is in the air, a gravity float value is added to the player's y velocity (and multiplied by Slick's delta value, keeping track of time since the last frame and making values consistent regardless of frame rate) and when the player falls into a platform, the player stops, is repositioned in line with the platform etc.

However, I've noticed some jittering behaviour... especially when I let the player's fall speed get higher. I suspect that's probably just making it more obvious and it's happening regardless of that, but w/e. Also of note is that even with the terminal velocity set relatively high, I don't always notice any jitter, though sometimes it's very noticeable. I imagine it depends on the exact velocity values at impact and where the colliding tiles are in relation to the player etc.

I've drawn a diagram to explain it clearly:



As you can see, what happens is that the player is moving downwards and to the left (or right) at the same time. On colliding with the platform, the player often sharply snaps to the right a few pixels as well as properly landing on the platform surface.
Presumably, since colliding tiles to the left are checked when the player is moving in that direction and repositioned appropriately, and horizontal collisions are checked first... what must be happening is that a collision with the tile below is detected while moving to the left, and as a result the player is undesirably being repositioned to that tile's right side... which is what the code is meant to do. It's just of course that it looks terrible and would also potentially interfere with gameplay somewhat.
Like I said though, it doesn't always appear to happen, and I'm not sure why that is... it could just be that the positioning is very small and unnoticeable, even when it seems as though the player's side edge is colliding with the center or so of a tile... but that's probably not important.

Knowing what's wrong pretty clearly... how do I actually fix it?
Horizontal collisions need to be addressed, and depending on the layout of the map and the collision, I may want the player's horizontal movement to be altered rather than the vertical in some cases. I can't simply avoid checking the player's sides when moving up/down or going at a certain speed.
I can see roughly what I want to do... but I'm finding it hard to properly define what should be done in an exact methodical way that would work in all situations

Granted, something like this doesn't need to be a pixel perfect representation of the real world. For instance, in the case of landing on that platform, ignoring the x repositioning altogether and simply raising the player up above the platform would like fine, though realistically part of that leftward movement would have been achieved by traveling through solid rock but no one would notice or care.
Even still, given the various circumstances that might crop up... do I have to alter my collision detection almost entirely and use some sort of gradual pixel-by-pixel testing of at what point the collision occurs when traveling in each axis, and reposition to the point just before colliding? Which is also complicated by my use of floats to store position, but I guess that could be got around...

Any thoughts? This must be a common problem, and I think I had a similar one with a top-down shooter I made in C++.

[65K]

Not sure if I understand all this... but.. about repositioning:
You dont do the collision check before you actually move player with intended new positions ?
Or, is your movement time based, thus in case of too long time deltas, you get stuck in tiles ?

[SeanSeanston]

You dont do the collision check before you actually move player with intended new positions ?

What I do every frame is:
1. Figure out the x and y velocities.
2. Test if applying the x velocity to the player would result in a collision, and position the player to the edge of that tile and zero its velocity if that would occur.
3. Test the y velocity and handle that similarly.
4. Add gravity to the y velocity.
5. Add the x and y velocities to the player's position (which will be 0 by now if colliding) after multiplying by delta.

Or, is your movement time based, thus in case of too long time deltas, you get stuck in tiles ?

The movement is a speed value assigned to the velocity, which is then multiplied by delta before being added to the player position. Of course, y velocity is a bit different but jumping works that way too.

As for delta, I just had a look by printing out the delta value whenever the player lands on a platform.

It seemed to hover around either 4 or 5 no matter what. I made a few normal landings and at least 1 jittery one, but they were all either 4 or 5 (apart from the first which was 7 but I assume that was some kind of startup lag).

So I imagine it's not to do with delta being too big or so it would seem.

What does confuse me though is why this isn't happening more often... does the JNRDev tutorial's way of doing it seem to anyone else like this would be a glaring problem with it? Seems like it would have to happen with diagonal movement, which is going to occur a lot in a platformer.

As an aside too, I'm wondering if the program should be altered to run game logic a fixed amount of times per second and have rendering work independent of that, like in this article:
http://gafferongames.com/game-physics/fix-your-timestep/
Or if that's even possible with Slick...
I just saw there's a way of setting VSync and smoothing deltas... trying that now. Also you can set the maximum and minimum times between updating, so that's cool.

Still, I'm pretty sure it's the algorithm that's flawed here.
Got thinking a while ago about behaving differently depending on the direction the player came from, but that would require dealing with the x and y velocities together, so I think that might be what's needed either way... which would require some reworking. Had a horrible time trying to implement something like this before in my aforementioned top down shooter. Slowly stepping through the velocities didn't work at all for whatever reason.

Games published by our own members! Check 'em out!

[65K]

What I do every frame is:
1. Figure out the x and y velocities.
2. Test if applying the x velocity to the player would result in a collision, and position the player to the edge of that tile and zero its velocity if that would occur.
3. Test the y velocity and handle that similarly.
4. Add gravity to the y velocity.
5. Add the x and y velocities to the player's position (which will be 0 by now if colliding) after multiplying by delta.

Why position the player in case of collision at all ? If you do a look-ahead check that shouldn't be necessary.
Why are 3. and 4. two separate steps ?

[UprightPath]

Well, you just answered your question as to why it's happening.

If you're checking collision at the goal you'll find, in step 2, that you'll be 'colliding' with that block and your repositioning code puts you to the right of it (Since that's the rules).


How to fix that? Ah, that becomes the fun of it. You can always write code that when you're confront by a collision, you find out which face your player's going to impact with first then react in that way instead of what you have right now.

IE- Distance from important character edge X to important block edge X, divided by the current velocity. Then distance from the character edge Y to block edge Y, divided by the current velocity. Since in both cases the distance will be less than your velocity, you will have a value between [0,1]. Compare the two. The lower one is the direction in which collision with that block will first happen. If they're the same, it's a going to be a perfect corner collision, and you should decide how that works.

Why position the player in case of collision at all ? If you do a look-ahead check that shouldn't be necessary.
Why are 3. and 4. two separate steps ?

Because it sounds like collisions can happen in the middle of a trajectory motion. Think falling where it isn't an issue of preventing a player from making a motion, but more reacting to the engine's repositioning. Unless you meant something different about look-ahead check (That is, I'm assuming you mean you check if there's a collision and prevent the motion in that direction.)

[65K]

Why position the player in case of collision at all ? If you do a look-ahead check that shouldn't be necessary.
Why are 3. and 4. two separate steps ?

Because it sounds like collisions can happen in the middle of a trajectory motion. Think falling where it isn't an issue of preventing a player from making a motion, but more reacting to the engine's repositioning. Unless you meant something different about look-ahead check (That is, I'm assuming you mean you check if there's a collision and prevent the motion in that direction.)

I still don't see the need for repositioning. For a trajectory movement you could still check the next player location for validity before you move him there (for each single pixel step).

[Eli Delventhal]

Yes, you don't need to reposition as long as you don't move unless the area is open. If you want to move 10 pixels and the obstacle is 5 pixels away, for example, then you move exactly 5 pixels. You need to make sure to be consistent with whether you want the two objects to overlap by exactly one pixel (constantly be colliding) or never actually touch (be directly next to each other). In some cases I've had the movement check separate from the gravity and one expected touching and the other expected adjacency, which causes twitching like you've described.

Either approach can make sense depending on your situation but you must be consistent or problems will arise.

[SeanSeanston]

Hmm... I later spent ages trying to figure out why something else was happening: every so often, the player would appear to move below the surface of the tile it was supposed to stop on, then flick back to its proper position.
After much printing out and comparing values and repetitive testing, I found the collision function wasn't always testing against the right tiles. Specifically, in the case above, it was testing against the tile just above where it was supposed to and I wasn't sure why for a while...
Turned out, I wasn't factor in the delta when I was determining the end point for tiles to check against. I was adding the y velocity, say, instead of yvel * delta, so the collision detection function wasn't checking far enough.
So I changed it to:

1	float colBoxEnd = x + ( xvel * delta ) + w;

and the other 3 cases similarly (the other directions, that one is for moving right).

Now, after some testing last night and today, it seems that all of my collision problems are gone. I haven't been able to replicate that jittering ever since factoring in the delta.
I guess it must have been checking against the wrong tiles all along 

Why position the player in case of collision at all ? If you do a look-ahead check that shouldn't be necessary.

Seemed like snapping to the closest valid position was a reasonable way of doing it.

Do you mean I should calculate the velocity required to put the player in that position instead?

I did try that before in a C++ game... I'm not sure what I went with in the end exactly. It took me ages to try a lot of different ways of getting the player to collide properly with moving enemies and in the end I just abandoned it and did things another way that was equally good or better gameplay-wise...

Why are 3. and 4. two separate steps ?

I did change that a bit... I put the gravity before the y collision checking because I realized that the new extra gravity of a frame wasn't being taken into account for collisions since it was being added after the collision checking

Well, you just answered your question as to why it's happening.

If you're checking collision at the goal you'll find, in step 2, that you'll be 'colliding' with that block and your repositioning code puts you to the right of it (Since that's the rules).

Except now I'm really quite confused as to why it seems to be working perfectly...

Hmmm... looking at the exact code now I think I might see why... the separate axis testing doesn't take into account the other axis' velocity. I think that would result in what I'm seeing... yeah, I think so.

IE- Distance from important character edge X to important block edge X, divided by the current velocity. Then distance from the character edge Y to block edge Y, divided by the current velocity. Since in both cases the distance will be less than your velocity, you will have a value between [0,1]. Compare the two. The lower one is the direction in which collision with that block will first happen. If they're the same, it's a going to be a perfect corner collision, and you should decide how that works.

Interesting... I'll try to remember how that works. I've had similar problems before.

After messing around trying all I can though... I'm pretty sure it's finally working now. Have to get used to Slick and remember to always put delta in appropriate places