This page is a mirror of Tepples' nesdev forum mirror (URL TBD).

Collision question

I'm rebuilding my game's collision system manually so that I can make it follow the NES more accurately. (Friendly reminder, I'm not actually building this for the NES, I'm just trying to emulate the NES.)
So far, it is going good. I have successfully made a falling object properly get blocked from falling through a floor.

I have never done something this close to a game's foundation before, so I'm going to describe it here in case someone knows a better way. The method I used was simple. Especially since I'm forcing the object to move in whole unit increments, It's really easy to predict movements and make sure that an object never moves too far. So I directly set the object's position to be that same position plus velocity. Then I have it check three points on the bottom to see if there is anything there that could be collided with. If so, the object is then moved to be directly on top of the ground. This is checked in the same frame so the object will never appear part-way through the ground. This would duplicate features I've seen in some games where if you jump up through a platform and are just barely near the top, you will instantly warp to the top.

I was about to basically duplicate the exact same method for collision on the sides, but then I realized wouldn't be able to properly duplicate some features I have seen.

Observe this sample from Castlevania.
Attachment:

castlevania3-0.png [ 5.88 KiB | Viewed 2351 times ]

Because of a valid reason, the player wound up partway in a wall. If the player moves away from the wall, they move freely and normally. If they move toward the wall, they can move no further. On the surface, that sounds easy enough. I only check the collision when they are moving, and in the direction they move. But the method I used to collide with the ground, if used here, would cause the player to instantly pop out the side of the block, instead of simply denying them from walking further into the wall.
If I have the side collision simply stop the player if it detects an object there, then it will be possibly to partially embed the player in any wall.
So the only way I can think to properly duplicate this design is to plug in special checks to see exactly how a player wound up in a wall, and then change the collision pattern according to that.
But that is really convoluted and is stacking the system to explicitly produce this result. I doubt that's how the collision in Castlevania was designed; I suspect that it was made in a straight-forward method and the fact that this happens is a byproduct of that method.

So... How is this game handling collision? How is this game actually keeping the player from walking into walls, such that if they happen to be in a wall they can walk through it?
If I had to guess, I'd say that Castlevania's collision routine only checks for Simon's feet. If he is under a block there isn't any collision because the feet only intersect with the bottom 8 pixels. It still works when colliding with tall walls because the feet would hit the side of the wall and stop Simon from moving.
heardtheword wrote:
If I had to guess, I'd say that Castlevania's collision routine only checks for Simon's feet. If he is under a block there isn't any collision because the feet only intersect with the bottom 8 pixels. It still works when colliding with tall walls because the feet would hit the side of the wall and stop Simon from moving.

Hmm, that won't completely account for everything, because you can still get stopped by blocks that are at face-level but don't go all the way to the ground.

For a moment I thought I could have the check in the feet actually push the player back, but have a check in the upper-body only keep the player from moving forward. But then the player would still be capable of walking part-way into a wall if it does not go all the way down to the ground.
Marscaleb wrote:
you can still get stopped by blocks that are at face-level but don't go all the way to the ground.

Are you saying it's impossible to go down those stairs in the screenshot you posted?
You seem to be over-complicating the concept. Any X/Y collision checks should be done separately.

Now, I'm not going to go into too much detail, but I will attempt to break down the basic logic for you, below.

First, check the Object's Jumping/Falling Status.

By Default, or if Falling, check the Object's Feet.
If Negative, check the bottom-left, and bottom-right positions, if Positive, the Object is on a platform.

If Jumping, omit the Feet check, and check the Head position instead, mirroring the corners.

Once this operation is complete, check if the Object is moving.
check the middle-left, or middle right positions (case-sensitive), to check collision points.
if Negative, check the corners as before, checking the upper/lower points for a solid tile.

There! Rock solid 8-point collision detection. I do hope my notes make sense.
This method prevents clipping into blocks, and supports the implementation of slanted surfaces.

For jump-through platforms, you just omit checking for them if the player is jumping, but not when falling/standing. It's a simple matter of adding that to the tile's attribute data.
tokumaru wrote:
Marscaleb wrote:
you can still get stopped by blocks that are at face-level but don't go all the way to the ground.

Are you saying it's impossible to go down those stairs in the screenshot you posted?

Oh right, the stairs. No, the stairs work, but they are triggered by pressing down. They are really a separate element and not part of the normal collision. If you just walk forward, not trying to trigger the change to walking on the stairs, you just bump into the block.

At that spot in the screenshot, you can actually jump straight up and then be partially embedded in the block above it, and that will be the same situation. You can walk out into the open area, but walking into the brick will stop you.

Alp wrote:
You seem to be over-complicating the concept. Any X/Y collision checks should be done separately.

Yes; and I am doing that.
Also, I think the X movement should be handled first, so if you are trying to land on a corner, you are more likely to make it.
(Edit, whoops, I said Y instead of X.)

Alp wrote:
There! Rock solid 8-point collision detection. I do hope my notes make sense.

Yes, it does make sense, but it is not quite what I am needing help with.
Checking points is easy, the problem is how to actually handle the process of blocking a player from moving through an object.

I was just using a system that basically teleports the player to the outside edge of what they are hitting, but that won't allow me to duplicate the situation I described above.
Quote:
I was just using a system that basically teleports the player to the outside edge of what they are hitting, but that won't allow me to duplicate the situation I described above.

First check if point was in a wall before movement. If yes, don't eject from that point that frame.

The stairs seem like a special case that allowed points to get inside a wall. (i.e. if(instairstate)then ignore collision) .) And since you can't jump off stairs while you're on them (if I remember correctly), they probably figured it was safe to do that because they could just make stairs start and end where it wouldn't be a problem. (Not that that's necessarily safe thinking.)

There are even ways to make jumping off the stairs work. Don't allow jumping when any of the corners is in a wall, maybe.

Edit: And if just allowing the player to walk through a wall once all their corner points (for example) are in it at the start of the frame, you can choose to only ignore collision for each point on the tile it's already in. (So if the movement would move a point that's in a wall into another tile that point is not currently in, that would eject.)

Programming is figuring out how to distinguish the case you want a thing to happen from the case where you don't want it to happen. Once you've figured it out, you make an if for that and do the thing based on it. (Simplified)

Checking if the player is in a wall from the start is one way to distinguish between this and a more standard ejection case.
I was thinking about it on my to work tonight, and effectively what Castlevania is doing is letting you walk the distance between you and the wall. I could set up the collision in my game to use raycasting to find the distance between the player and the wall, and then move the player no more than that distance.

It would produce the same result, but I am still curious how Castlevania did it. Raycasting seems like a bit to much for the NES to run several times per frame. And even if you try to simplify it, the best I can think is that it would effectively check for collision on each individual pixel the player could traverse that frame. That may be possible, but doesn't sound very efficient. Grant can move I think like three pixels per frame, and to check at least between two blocks, that could be up to six collision checks. Possible, but inefficient.
Quote:
Raycasting seems like a bit to much for the NES to run several times per frame.

Not with a fixed square tile size that's a power of two. You can use bitwise AND, (a bitwise exclusive or,) and an addition/subtraction to get the starting position of the next tile. Unless your character is moving very, very fast (faster than your fixed tilesize in a frame), you only ever need to check two points per "ray".

Basically if you know where a point is, you can find out VERY quickly how far into it you are and how far away the next tile is.

Edit: However, the reason these games usually move you into a wall, and then eject you is you don't need a raycast. Say you're not in a wall. The tile next to you could be a wall or it could not be one. So I have to get the distance to the next tile, and then check that one to get the distance I can move. If I just move, then I only have to check the point I moved to. If it's a wall, I just eject (again assuming the player can't move faster than the tile width. If it's not a wall, I don't eject. (And as stated, it's very fast to find out how far to eject.) And I've only checked one point. But checking two points isn't really... slow (unless the collision info is extremely compressed or something). It's just less fast.

You don't need to check every pixel. Just the corners, and maybe a point or two in between the corners depending on how tall the character is in relation to the fixed square tile size. Slopes make lots of things more complicated, of course. (Well... if the game only has 45 degree slopes that's not so bad.) That's probably part of why you straight up can't collide with stairs (you fall instantly through them) unless you enter the stair state. And that's probably why you can't jump off them. (I'm on stairs. I accidentally press A. Now I will fall through the stairs.) Though actually
I once did something similar to this by limiting the eject distance to the object speed. If an object moved three pixels, but the distance required to move the object out of the wall was four pixels, then the object was only ejected by three pixels, resulting in no movement for that frame.