nesdev.org

Tell me if I'm making any bad ideas here.

Solid block collision should be done in this order:

- move object horizontally
- perform horizontal collision
- move object vertically
- perform vertical collision

In order to do this it should implement object motion within the collision routine, and everything to be moved by velocity regs, without any object being moved "manually."

Collision should only be checked if the edge of an object has moved over a tile from the previous frame, and in the direction it is moving.

So basically, for an object, you could have two registers that count to the width and height of the tile. When the number in the registers is the same as the width or height, you check to see if you bumped into anything and you also set the number in the register back to 0. Off course, if you have 16x16 tiles and one of the registers is at 14 and you want to add 4, you want to make it 2 instead of 18 or 0.

Sorry for this unrelated question, but how do you go to different parts of code that correspond with what action is supposed to be happening, like if you are on the ground or in the air? Do you use jump tables? I had originally used beq and bne, but that is only really useful for if there are only two different things the object can do.

It's an interesting idea and it certainly seams like a simple solution to the which direction did I collide in problem.

Assuming that objects are rectangular, for a 16x24 pixel character and an 8x8 grid you only need to check 3 tiles horizontally and 4 tiles vertically, which is also a plus.

I played around with some graph paper and noticed an issue. Allow me to demonstrate:

Imaging you have a block and an object such as: And the object is moving down/right at -30 degrees (xVel = 1, yVecl = 2)

Then following your algorithm (move horizontal, notice collision, move object out of collision [assumed functionality], move vertically, no collision) then the location of the object would be:
Where as if you calculated X and Y positions together, then checked for a collision, the object should be at:
Maybe your players will not notice, but if your horizontal collision routine removes the objects xVecl then I think they will.

If you do implement this algorithm, I recommend preforming the vertical calculations/checks first. It still has the same issue, but rotated 90 degrees. This case would result with the player standing on the edge of a ledge.

I had some issues with moving both X and Y first, and then doing collision. If I'm walking on pass-through-bottom tiles, it works fine, but when I'm walking on solid tiles I get stuck where the cracks are.

I'm really not sure what's going on with velocity and things. Like I said, I figured that if blocks are 16x16 pixels large, then you only check collision every 16 pixels because there isn't going to be a block halfway in the tile map. You could also still use the x and y collision check, and maybe if both are or over 16, then you could check them both at the same time to make sure there aren't any problems.

Am I even making any sense?

Moving both axis at the same time creates all kinds of trouble. Yes, characters get to go through some corners they woldn't otherwise, but IMO, the worst problem is ejection. Think about it: if you update the two axis at once, and when validating that movement you detect that the object didn't hit a wall, but there was a vertical collision, you'll have to eject the object vertically, and that could invalidate the horizontal motion that you have already considered safe, and the object could get stuck inside a wall.

It's much safer to move and test each axis individually, but there is no universally good order to perform the tests. If you really care about objects being able to land on or jump onto ledges in all extreme cases, you might have to change the order in which you test the axis depending on the direction of the movement.

Espozo wrote:Am I even making any sense?

Not to me. You're talking about pixels and counters while all you need is to scan all blocks that could be touching one edge (top, right, bottom or left) of the character. To test blocks at the right, for example, you'd have to check all blocks between (ObjectRight, ObjectTop) and (O jectRight, ObjectBottom), converting all coordinates from pixel space into block space (i.e. divide pixel coordinates by the size of the block - usually 16). Just get the object coordinates, divide by 16 and use them to look up blocks the level map. You don't ever need to think in terms of pixels unless you have slopes.

Have you had a chance to look over Four-corner collision detection?

tokumaru wrote:Moving both axis at the same time creates all kinds of trouble. Yes, characters get to go through some corners they woldn't otherwise, but IMO, the worst problem is ejection. Think about it: if you update the two axis at once, and when validating that movement you detect that the object didn't hit a wall, but there was a vertical collision, you'll have to eject the object vertically, and that could invalidate the horizontal motion that you have already considered safe, and the object could get stuck inside a wall.

Here's an attempt to illustrate this problem: So, you move both horizontally and vertically at the same time, then test for a horizontal collision and there are none. Then you check for a vertical collision, and you see the object went past the ceiling. To fix this, you eject the object down, effectively sinking it into the floor. To handle the ejection properly here you'd probably have to check the horizontal axis again, and then the logic starts to get weird IMO.

you might have to change the order in which you test the axis depending on the direction of the movement.

Yeah, turns out I was wrong about this. Look: The object is moving in the same direction, but in order to land on ledge A, you'd have to check for vertical collisions first, but to land on ledge B you'd have to check for horizontal collisions first. I can't think of a good solution for this right now, so I'd love to see someone else coming up with something.

tepples wrote:Have you had a chance to look over Four-corner collision detection?

I'll take a look at it now.

EDIT: Looked at your solution. It's pretty interesting, but like you said in the beginning, the object can't be larger than a block, and that's a huge limitation. How would you expand the technique to work with larger objects?

Espozo wrote:I'm really not sure what's going on with velocity and things.

The point about velocity is that if the collision routine knows the direction where the object is travelling, the collision check can be done more efficiently (if the object is travelling right, we know that only its right edge can collide, working from the assumption that the object was free from collisions before movement). Compare that to a situation where you only know the new position of the object, not where it came from. "Velocity" might not be the best word for it though in the context of collisions, it feels too... physichy. "Displacement" might be better.

Figure I might as well add my experience on this, I spent a lot of time on my own collision detection. I started off using the method from Sonic 1 as a base, having two vertical sensor lines on either side and one horizontal one, using this as a reference: http://info.sonicretro.org/SPG:Solid_Tiles

Problem was my character is about half the height of Sonic, so without some really restrictive velocity caps I couldn't check for both upward and downward collisions using their method. So what I did is I split the routine into some different cases for flying up, flying with low Y-velocity, and flying down, with the Horizontal sensor line positioned at the bottom, middle and top respectively. This allows the space to check for upward and downward collisions without triggering the H-sensor. It also works nicely in that if you're pressing against a wall while flying, you won't start to pass through until you're clear of it in either direction. I guess this probably isn't helpful to you if you're trying to build something much bigger than usual, I wouldn't know... But aside from a few cosmetic problems (See the "Bugs Using This Method" section in that link I linked), it seems a very stable system.

Later when trying to do small-projectile collisions I took a slightly different approach. Instead of the earlier method of sensor bars of fixed length, I checked from its new centre backward along each axis only as far as the velocity, starting with Horizontal. They'd keep getting stuck inside a corner as they flew past - clear on the horizontal check but detecting the vertical collision after and sucking it back into the wall.

I ended up building my projectile collision routine to check horizontal first, then vertical, then check horizontal again from the corrected position IFF you had a vertical collision but NOT A horizontal one. Then if the last collision hit was horizontal (ie/ first H pass hit and no vertical hit, or both vertical hit and second H pass hit), it's a horizontal collision, otherwise treat it as a vertical one.

It is not perfectly accurate as projectiles will tend to catch and bounce off a corner they might have just barely scraped past following a real trajectory, but it's the best I could come up with and it looks pretty realistic in practise provided the speed is reasonable. My code also doesn't seem terribly processor-taxing, but it IS almost totally illegible. Writing that was hell for me.

Definitely curious if anyone knows of any fatal flaws with my concepts. It seems to work for me, I haven't had anything skip out of bounds lately.

tokumaru wrote:

tepples wrote:Have you had a chance to look over Four-corner collision detection?

How would you expand the technique to work with larger objects?

Probably by scanning along the leading edge of the sprite. For example, a solid block at center right would be considered solid in top right and bottom right.

Another thing to be careful with is to make sure the bottom of the object is ejected one pixel above the tile instead of the top pixel of the tile, or else it will check horizontal collision within the floor.

So much complexity and we didn't even get to the slopes yet.

tokumaru wrote:So much complexity and we didn't even get to the slopes yet.

I should mention just in case it wasn't obvious that the method I use DOES handle smooth slopes.

What's ironic is that I paid so much attention to getting pass-through-bottom slopes to work properly, I forgot to check if solid blocks worked properly.