How to go about implementing background collision

So I've been looking into this for a couple days now, and after some trial and error I think I've got the basic idea down. I could probably make the data part of this smaller, and probably should, but for now I just have 1 table of 208 bytes of collision data for 1 test screen. My status bar takes up 48 metatiles, so I don't have to worry about collision with that.

Each byte in the table represents one 16 by 16 pixel block, where 0 equals not solid and any other value equals solid.

The one thing that I don't understand though, and that I can't find a clear-cut answer for, is how exactly do I go about comparing the sprites' positon to this data? The game I'm working on isn't a platformer, so I don't have to worry about gravity or anything like that.

An idea that I tried out is, have 4 variables, above_solid, below_solid, left_solid, and right_solid. Each frame, before the controllers are read, I calculated which byte from the collision table to read from by throwing away the low nibble of the player's Y position, and adding the player's x position divided by 16. Then I subtracted 48 to account for the status bar, and stored the value in another variable, bgcol_index. I'd find out the solidity of the surrounding 4 "blocks" by checking the bytes of the background collision index plus 1, minus 1, plus 16, and minus 16. Then when each d-pad direction was read, I'd check its respective variable (i.e below_solid when down was being read), and branch past moving the player if it wasn't zero. But because my player's metasprite has some weird dimensions (16x24 pixels), I couldn't get it to work quite right.

So I guess what I'm saying is I know how collision data works, but I don't know what to do with it in the actual code.

I find collisions with background significantly more complicated than sprite vs Sprite collisions. I would comment further, but since I had so many bugs implementing this in my games, I shall not be giving advice, except to say you will be moving, then ejecting (if collision), in the opposite direction of motion.

Just because the sprite/character is 16x24 doesn't mean that its collision box needs to be that. I know there are atleast some games that use a 16x16 collision box even though the character is taller but I can't name an example at the moment.

It sounds to me like your problems might be related to your compensation for the status bar. You may want to refer to the playfield as starting at Zero for simplicity and instead just add the offset when drawing sprites so they appear lined up with the playfield.

For collision with a static background you have the right idea. You need to divide the object's Y position by the tile height and then multiply that by the number of tiles in a row. Then you need to take the X position and divide that by the tile width. Then you'll have a single number that tells you where in the physics map you are located with the X/Y you have given.

If you start scrolling it's going to become a bit more complicated. But for single screen action like Zelda it isn't too difficult to deal with background collision.

I usually define a few constants that dictate points for collision relative to an object's coordinates.

If we consider a 16x16 box, with its origin in the center, and I want it to have a 16x16 collision rectangle, I might define the following:



The advantage of this is that I can very easily change these constants later to alter my collision area. To get the sides of the box, I might do:



Assuming I have a large array containing the collision map in 8x8 tiles, and I'm not concerned with slopes, I can check collision like this:



To do a better job, in that example above you'd want to check both corners of the box. If the box was bigger, you'd need multiple test points spaced <= your tile size, otherwise a small piece of ground might go through the box.

Also, in NES land, you will be working in assembly (I should hope) so you'll have to do the pointer math manually, rather than have a 2D array like in my example. To get the offset in your map data array, you need to compute it with some more work. My example is still C-esque, but the intent should be clear.

One of them is PyFHBG.

To find the ejection direction, you need to read the collision map four times to find the solidity at all four corners of a sprite. Then there's an algorithm that calculates which direction to push.

One tip I'll give you is to move only ONE axis, then check for collisions on that axis, then move the other axis and check for collisions on that axis. Do NOT move in both directions and then check for collisions. I don't know if you planned to do it that way, but I wasted about a day or so trying to figure out how to determine whether I've landed on the top of a corner or hit the side. It doesn't work.


This will work if all of your objects have the same hitbox size, but if your objects vary, and you want them to use the same routine, you're going to need variables for each object to define the size of it's hitbox. I have a hitbox width and height variable for each object, and with that, I can find any side, any corner, even divide them by half to find the center.

So what I do is a little like this:

First you're going to have to save a few variables. Save your X position and Y position before movement is applied. You'll need this for a few things. You don't need one of these variables for every object though because you only need it for the object being processed, so one temp variable for all objects will suffice.

Next we need to apply Xspeed to Xpos. Depending on your engine, how this is implemented will vary, but if you're going to scroll, and you want smooth acceleration, jump arcs, etc, you'll probably want a 16-bit speed and 24-bit position.

Just to save a little bit of unnecessary work, I check to see if the Xposition has changed, and if not, I skip over the collision detection. It's not feasible to do this for the Y axis in my game because of gravity, but that's neither here nor there. I also have to do this check to change my sprite's direction too if that matters for your game.

Now, we've confirmed X axis movement, so let's see if we need to check the right or left side. Subtract your last X position from the current X position. You don't need to do this with your full 16 or 24 bit position value, just the one that corresponds to a pixel. Like, I have xPosHi, which corresponds to how many screens the object has moved over, xPosLo, which corresponds to pixels, and xPosSub which corresponds to sub-pixel positions. I just use xPosLo for this check. If the result of that subtraction is positive, your object has moved right, so check the right side. If negative, you've moved left so check the left side.

Edit: I was thinking for a minute that this wouldn't work and was going to change but I think I was wrong about that. 0 - $FF = 1 which is positive which means you moved right. $FF - 0 = $FF is negative which means you moved left. I'm still editing this though because I checked my code and realized what I did was actually a little different. I subtract the xPos to see if the object has moved, like I said, but in that instance, I BEQ, meaning, jump over collision code if my X pixel position hasn't changed. When I get into the collision routine, I'm actually using an object's speed to see if they're moving left or right. So I just wanted to note that there are options to use speed for some checks too. I believe I used speed in my collision check since it's a separate routine, it's quicker to do just one LDA and get the answer. However, I can't go by speed to see if an object has moved due to subpixel movements.

Second Edit: After typing this I went back over my code and realized there is a mistake in the way I'm doing it. Checking X speed for knowing which side to check won't work. I've never actually seen any errors with the program, however, an object could have an X speed of 0 and still be moving left, and I can't do a secondary check on subpixel speed because that can be negative and still moving right. So, I hope I didn't confuse you with the edits. Basically, ignore the edits asides from seeing what not to do, because I'm pretty sure the original method I described of checking current X position against last X position is the only way to reliably do this. I've got to change mine now.

Now, there are different ways to do the actual check. I'll just kind of give you a general idea.

Some people like to check multiple points on their object. Mine calculates how many tiles need to be checked for the hitbox height. I don't believe the way that I did this is very standard, however I've tested it and it saves cycles on reading from the metatiles.

So, you know now you want to check the right side, calculate the right side position using hitbox size variables or constants, now you're going to have to math it up to find where those pixels fall on the map. This varies greatly depending on your engine, but if you said 16x16, then you've basically got to divide your positions by 16 to find the tile they occupy. This becomes a bit more complicated in an actual game situation though.

Have you done metatiles yet? This part will be almost exactly the same as the math to locate your metatiles.

Here's what I do. I don't expect that you'll be able to copy this but I'm hoping it gives you an idea. My map is arranged in columns, so first it finds the map column then uses the Y position to find how deep into that column to go.



Y axis part, for me, is:



That LDA from MetatileCollisionHiYOffset references this table:



This part is very specific to my engine, since I use SMB3 style scrolling which limits me to two screens vertically, so an object Y position high byte will never been anything other than a 0 or 1.



Danmaku SHMUPs use a hitbox significantly smaller than the player's ship to allow for complicated bullet dodging.

daryl.revok ninja'd me while I was ponderously typing out my answer, but I'll post it anyway in case it's of use:

The approach I use is to test individual points. Take your player's position, add an offset for the point you're testing, and use the high bits of the result to determine which tile of the map that point falls inside.

If the tile is solid, you can then use the low bits (the ones you threw away when looking up the tile) as an offset to move the player out of the block: for points on the right side of the player, subtract one more than the low bits of the point's X position from the player's X position; for points on the left, add one tile-width minus the low bits.

(I haven't actually implemented this system on the NES yet, but using 16x16 metatiles with 4 bits of subpixel position would seperate the high and low bits on a byte boundary, saving you some work shifting and masking.)

To make it easier to determine which axis to push along, I update the player's position in two steps. First I move the player horizontally, and test points on the forward side for collision. Then I update the vertical coordinate and repeat for the top or bottom points, depending on if the player is moving up or down.

As for which points to use, that depends on which parts of you character you want to be 'solid'. If the collision box is no larger than a tile you can simply use the corners. Don't forget that each corner must be tested in two directions, one horizontal and one vertical. That works out to four tests per frame, just like tepples' approach.

If your character is larger than a tile then using the corners may miss small obstacles; you'll need to add points to the longer edges so that the gaps are smaller than one tile in size. If you want more complex shapes, you may need to test points even when the player's not moving in their direction.

I'm not very good at explaining things clearly. I can draw some diagrams if that would help.

So I got it to work...kind of. I've run into the problem that I'm sure many before me have experienced. The collision only works if the object is perfectly aligned to the grid. So if it's halfway between a solid section and an empty section, it'll go through.

My current code is as follows:


and here's what I'm getting:




If you guys want I can post a simplified example rom/source that isn't bogged down by the rest of my code. (Tomorrow. I'll also look at your guys' previous suggestions (Thanks, by the way) more closely.)

I'm about to head out for the night but I'll check it out tomorrow if someone else hasn't fixed it. When you review what I wrote, just note I made two edits which pretty much negate one another. What I said the first time was correct. What I said on the first edit was wrong, and the second edit redacted the first edit. I'm going to leave it though because that kind of thought process may help in finding errors.

I'm not yet fluent in 6502 assembly, so the only thing I can spot is that you're only testing one tile per direction of movement, and your character is more than one tile in size. Or are you pre-enlarging obstacles in your collision map?

Does the behaviour differ in different directions? I can't quite tell what your images are pointing out.

What I do now is look at all the tiles/blocks/metatiles from one end of the edge to the other, instead of adding more collision points. I mean, the idea behind adding more collision points is to make sure you don't miss any solid tile/block/metatile, so what could be safer than checking all of them in a "for" loop? It can even be faster in some cases, like when an object with a 16x16 hitbox is perfectly aligned to the 8x8 grid (something that would happen very often when not on slopes): if you check all tiles from the top to the bottom, that will be only 2 checks, but if you went with the "more points" approach you'd always need 3 checks.

Yeah, that's exactly what my PC code does in practice - I just glossed over it as I was simplifying the description. Sorry about that.

It looks like I was not quite clear in my post - the definitions for the collision points was just for one object, not all objects. Indeed, each object type needs to have its own definitions.

After tinkering with it some more, I seem to have solved my one problem, but have now run into yet another one. When my player collides with a wall, it can only move in the direction opposite of where it was moving. (i.e if you collide with a wall while moving right, you can't keep moving right, but you also can't move up or down. Just left.)

Here's a demo, I tried to make the code as concise as possible

From your description, it sounds like you are checking for the condition "am I stuck in a wall on the right?" but aren't consequently pushing the player out of the wall. If you know the wall will be aligned on an 8x8 boundary, you can simply "snap" the player's X coordinate appropriately.

You're adjusting the player's position in Read(Up|Down|Left|Right), but using the old position from player_x(1|2)y(1|2) for collision detection. That means that your collisions are being detected a frame late, after the player is already in the wall.

Move the code above ReadUp into a function, and jsr to it after adjusting player_(x|y), so that the values of player_x(1|2)y(1|2) properly reflect the new position.

Sorry I didn't get to this yesterday, but I'm going through and making some changes now.


This is the biggest problem with the logic. You are supposed to allow the player to move, and then correct it's movements if necessary, however, you need to test the player position AFTER the move.

Some thoughts:

Only testing on the corners will allow an object to pass through a collision tile if it hits in the middle. Someone else might be able to help you with the corner method; I did something more like what tokumaru suggested. I think people who do the corner method though generally have three points along each side.

The way you read controllers disallowed diagonal movement, so I fixed this.

Your player was able to overlap one pixel on the bottom, because the sprite draw position is one pixel lower than the value in OAM data for Y position, so I added one more to your hitbox Y value.

I did very minimal optimization. You probably shouldn't worry about optimization at this point, but there were some really simple things I wanted to do. You had some duplicate multiplication, so I just transferred those values to X and Y to save quite a few steps. Optimization is definitely not the thing to focus on in the beginning, but getting in the habit of using the X and Y registers when you can is a good habit, I think. There was also a little unnecessary branching I commented out.

I would suggest to start spending a little bit of time formatting. Your program is getting long enough that it would help. You may want to put some of your subroutines into includes. Some more comments might help too. Some things may seem self explanatory now while you're working on them, but as your program grows and you go back and forth between certain parts of your engine, you're not going to be as familiar with them. I don't know about other people but I like to put lines between sub routines if they're going in the same file.

A lot of stuff is set up to be very specific for a particular set of data, for example, the UpdatePlayerMetaSprite routine. This is writing to set memory locations for the OAM data. Granted, this is the fastest way to perform the simple set up that you have, but I think most people probably set up a routine to update the sprites for all of their objects. I understand this is a demo though.

So here's the program with a few minor changes, and no wall stick. Your engine would have problems with any block that is smaller than 24 pixels though, because of the point issue I mentioned previously. I think testing three points on each side, for your player hitbox size, would fix this, but since your current level design prevents this from happening anyway, I'll let you figure out how you want to tackle that.

May I ask how you did this? I'm curious because I did the same sort of thing and I wonder if I went about it in a particularly logical way. This is what I did:

TLDR: Starting from the object's hitbox height, subtract the number of pixels object overlaps top collision tile, then subtract the number of pixels object overlaps bottom collision tile. Divide remaining number by 16.

Alright, it looks like turning the process of finding the player's position relative to the collision data into a subroutine and calling it for each button was all I needed to do. It seems to be working correctly now.

On a side note, I was disallowing diagonal movement of the player on purpose, (in both the demo and my actual engine) but I guess if people think it feels better to have it I can change it.

Anyway, I'll go ahead and add 2 more collision points in the center of the player's height so he won't be able to move through single metatile spaces. I really appreciate your guys's help, as background collision was something I'd been dreading. I can finally scratch that off the list. On to the next thing! I really hope this project I'm working on can see the light of day.

This is a simplified way to do it, and you'll probably want to change some things as you go on. Some things to consider:

Your enemies also need to do background collision checks, so eventually you'll want your routine to be able to handle more objects than just the player.

The way the collision map is being checked works if your objects are moving no faster or slower than a single pixel per frame. The way I think this is typically handled is that pressing a button will alter your object's speed, and then speed is used to adjust position.



This is personal preference, but I feel like it would be a better play experience to allow it. I know Link can't move diagonally in Zelda 1, but he can in LTTP, and not being able to do so in the first one just feels like a hindrance to me. I can't see how at any point not being able to move diagonally would actually benefit gameplay. Granted, it's your game of course and I'm just trying to help you move forward with making what you want to, so please do what you feel is better.



I'm pretty sure one point in the center of the 24 pixel height will prevent this. I didn't do the point method myself though so you may want to double check the math, but I do believe it's impossible to hit a tile which won't be caught by a point in the middle or corners with a 24 pixel hitbox height.

24/2 = 12, which is smaller than the 16-pixel tile size, so yes, it will work.

But as tokumaru pointed out, it would be better to iterate over the tiles. I'd simply start at the top corner and step down a row at a time, fetching the collision map bytes and ORing them together, until I reach the bottom corner.

Didn't read the whole thread, but an interesting trick I used for slopes was to use "under-slope tiles." Give the tiles underneath the slopes collision data to pop up to the slope above it while walking left or right.