Need a better way to check for background collision

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
Roth
Posts: 401
Joined: Wed Aug 03, 2005 3:15 pm
Contact:

Need a better way to check for background collision

Post by Roth »

Up to this point, I have been able to do background collision in a fairly simple way, which in turn actually simplifies the game itself, but lends to it too many restrictions. Here is how I have handled background collision for games that have more than one screen of gameplay:

1.) Have four corners of player, each with its own X and Y (define these before gameplay)
2.) Have an X and Y fine movement
3.) If player moves left or right, decrement or increment the X fine movement respectively. The same goes with moving up or down, except it's the Y fine movement.

Now assume that the player has been moving left (at one pixel per frame). Also assume the collision table is in 16x16 tile representation.

4.) If the X fine movement hits 0, look up the tile that is NEXT to the top left corner on the left, and if it is solid, do not allow them to move. If that is clear, check the bottom left corner. If that is also clear, allow them to move and set the X fine movement to #$0f (if moving to the right, instead of checking for 0, you would check for #$0f before checking the tiles to the right).

If you want the player to move at a speed of 2, then it still would work, decrementing and incrementing the X and Y fine by 2 each time.

So, this method works fine for standard, basic games and purposes, but is not at all suited for variable speeds of the player. If I want the player to move at a speed of 1.5 pixels per frame, then I have to come up with another variable of something like... x_fine_extra and y_fine_extra or something. And then the code just starts getting carried away and almost illegible to even myself, the one who wrote it! haha

I have been looking at the page where tepples describes pushing a sprite out of solid walls, but can't for the life of me figure out how that is actually employed. I understand the concept of letting the player move, then after the fact, and before the frame is done, check if they are in a wall, and then push them out if they are. What I don't get is how to know how much to push them out, especially if you are using 16bit movement. And also, if you don't know what direction they were coming from, how to know what direction to push them out.

This feels like the biggest obstacle for me to being able to make slightly more complex games, but I just can't wrap my head around it.
DoNotWant
Posts: 83
Joined: Sun Sep 30, 2012 3:44 am

Re: Need a better way to check for background collision

Post by DoNotWant »

Roth wrote: And also, if you don't know what direction they were coming from, how to know what direction to push them out.
Well, you would have to keep track of which direction your active objects are moving in some way, like having left/right and up/down flags, or use negative/positive velocities.

I haven't grasped the part about how much to push them either, so I can't answer that, sorry. :(
User avatar
Broke Studio
Formerly glutock
Posts: 181
Joined: Sat Aug 15, 2015 3:42 pm
Location: France
Contact:

Re: Need a better way to check for background collision

Post by Broke Studio »

Hi,

have you checked this topic ?

It's full of great informations on the subject.
My first game : Twin Dragons available at Broke Studio.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Need a better way to check for background collision

Post by tepples »

Roth wrote:I have been looking at the page where tepples describes pushing a sprite out of solid walls, but can't for the life of me figure out how that is actually employed. I understand the concept of letting the player move, then after the fact, and before the frame is done, check if they are in a wall, and then push them out if they are. What I don't get is how to know how much to push them out, especially if you are using 16bit movement. And also, if you don't know what direction they were coming from, how to know what direction to push them out.
When you push something to the right (cases 5, 7, and D on that page), you push it by far enough to make the left edge coincide with a tile grid line. For example, if the left edge is at x=13, and the next grid line to the right is x=16, push it to the right by three pixels.
User avatar
OmegaMax
Posts: 80
Joined: Wed Sep 21, 2016 8:55 am
Location: Calgary.Alberta,Canada

Re: Need a better way to check for background collision

Post by OmegaMax »

Use a variable describing which direction your actor/object is facing.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Need a better way to check for background collision

Post by tepples »

Facing isn't as important to collision as velocity. A lot of walk-through-wall quirks in Super Mario Bros., such as the one leading to the minus world, happen when the facing direction is the opposite of the sign of velocity.
User avatar
OmegaMax
Posts: 80
Joined: Wed Sep 21, 2016 8:55 am
Location: Calgary.Alberta,Canada

Re: Need a better way to check for background collision

Post by OmegaMax »

While that's true you should still be keeping track of which direction your actor is facing.Just test the sign of the the integer velocity.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Need a better way to check for background collision

Post by tokumaru »

glutock wrote:have you checked this topic ?
Yes, this covers the basics of ejecting objects, including figuring out how many pixels to push the objects out and in which direction.
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Need a better way to check for background collision

Post by Kasumi »

If the tilesize is a power of 2 (like 16), and if your characters cannot move more than tilesize pixels per frame, and you do not have finer collision than the tiles (like slopes):
The "andvalue" = tilesize-1
So the andvalue for a tile of 16 is 15.

First move the character.

And the pixel position with the andvalue. You only need the byte directly related with pixel position. (Subpixel, high byte doesn't matter) What this does is tell you where in the tile you are. (0-15)

If you're moving right, and have just moved into the first pixel of a collision enabled tile, AND andvalue would give you zero. But you want to eject one to the left.
Basically just add one to the anded position, and that's how much you want to subtract from XPOS to eject.

If you're moving left, and have just moved into the first pixel of a collision enabled tile AND andvalue would give you fifteen. But you still want to eject one. Just to the right.

So you XOR andvalue, then add one, and that's how much you want to add to XPOS to eject.

Code: Select all

ejectleft:;Can be optimized a touch, but written for understanding
lda xlow
and #%00001111
clc
adc #1
sta temp

lda xlow
sec
sbc temp
sta xlow

lda xhigh
sbc #0
sta xhigh
rts

ejectright:
lda xlow
and #%00001111
eor #%00001111
clc
adc #1
adc xlow
sta xlow

lda xhigh
adc #0
sta xhigh

rts
The text above says "moves into the first pixel of a tile", but that's just to make clear how it works (with the easy values of ejecting one). You could move right 8 pixels into a tile and the equation still does the right thing.
Roth
Posts: 401
Joined: Wed Aug 03, 2005 3:15 pm
Contact:

Re: Need a better way to check for background collision

Post by Roth »

Thanks for the feedback everybody. I generally have had a byte that defines what direction the player is moving, but wasn't sure if it was something that I actually needed or not. I wasn't sure if people generally just checked each corner and then pushed through some sort of crazy math formula : P

@kasumi:
In your example, is xlow a counter of sorts that goes from 0-f and uses an xlow_fine in the 16bit movement? And when xlow passes #$0f, wrap back to zero and xhigh is changed when xlow is wrapped?

I think my main confusion right now comes from also wondering if there is a standard kind of way that you can tie the actual sprite to the main X and Y positions, or if these are separate operations. Do people tend to have the user manipulate the X,Y and the sprites are coded to go with them, or do people tend to have the user manipulate both the X, Y and at the same time manipulate the sprites in a separate routine?
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Need a better way to check for background collision

Post by tokumaru »

Roth wrote:I generally have had a byte that defines what direction the player is moving, but wasn't sure if it was something that I actually needed or not.
If you're gonna implement more complex physics and use acceleration and velocity, it's better to not have any redundancy and deduce the direction of the movement by looking at the sign of the velocity variable.
Do people tend to have the user manipulate the X,Y and the sprites are coded to go with them, or do people tend to have the user manipulate both the X, Y and at the same time manipulate the sprites in a separate routine?
I can't speak for everyone, but as I matured as a programmer, one of the most important things I learned was to separate the model from the view. The model is your simulated world, which should be able to exist and function even if nobody is looking at it or controlling it. The view is just a representation of the game world, for players to be able to see what's going on. The more you can keep these things separate, the more maintainable and portable your games will be.

What I do is give each object a hot spot (X and Y coordinates specifying where in the level map the object is) and a bounding box (4 values specifying how far from the hot spot each side of the collision box is). These are exclusively for the model, and have nothing to do with sprites. Objects are moved using these properties, and they collide against the level map and each other using these properties. Drawing sprites is a completely separate step, performed later by a routine that processes sprite definitions. This routine first calculates where in the screen an object's hot spot is, taking the position of the camera into consideration, and then uses that point as an anchor and generates the individual OAM entries based on it.
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Need a better way to check for background collision

Post by Kasumi »

"16bit movement" isn't specific. Two bytes with a range of 0-65535 pixels is 16 bit. Two bytes with a range of 0-255 is 16bit.

As the post says, you only need whatever the byte directly related with pixel position.

If you have
byte1 (every time this goes up by one it effectively adds 256 to the pixel position)
byte2 (every time this goes up by one it effectively adds 1 to the pixel position)
byte3 (every time this goes up by one it effectively adds 1/256 to the pixel position)

You want byte 2. You don't need an extra byte, that's what the AND is for. If you AND anything with 15, you will get a result that is 0-15. So given any pixel's position, an and of that position will tell you where in the tile you are. And if you know you're one pixel into the tile (position zero), you know you want to eject one. If you know you're in the second pixel of the tile (position one), you know you want to eject two.

The XOR (for left travel) and add is what gets how far to move out, the AND gets you where where you are in.

As far as sprites, there's absolutely not a standard. For me the X, Y position represent where the top left of the object is. Then I have a height and width. To eject right/down, I use the X, Y position of the object directly. To eject left/up I have to add the width or height to the position. (I need to know how far the edge is in the tile, and the left edge doesn't help me do that for the right edge unless the object is a very specific width.)

I move the object, then eject it, then do whatever else to it. (Say moving its position relative to another object because it got grabbed). When its position is final, I draw the sprites that make it up relative to that position (or don't, if they end up offscreen after adding the offset).
Post Reply