Scrolling collision methods

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Scrolling collision methods

Post by JoeGtake2 »

Hey all - trying out a handful of things that rock the current boat least. I have lateral scrolling working visually, and I have no problem getting collision data scroll offsets. But...just wondering peoples' methods of updating tile collision data when scrolling (I know there are a few schools of thought on this). Currently, the engine loads 240 bytes worth of collision data into a RAM table, and those table values are read. What would you guys suggest? Get the new-screen table, bump the column, write every value column by column, shifted against scroll direction, then write the new column in the scroll direction? It seems like that would be a lot of values to write at a time, constantly.

Any other good suggestions? Or would this be the most sensible method?
User avatar
dougeff
Posts: 3078
Joined: Fri May 08, 2015 7:17 pm

Re: Scrolling collision methods

Post by dougeff »

For my ninja game, I based it vaguely on SMB, and had 2 full arrays of 16x13=208 (32 pixels at the top for HUD didn't need data)...and collision data doubled as metatiles for updating the PPU as I scrolled.

So 2 arrays, because 2 nametables. And filled as I scrolled.
nesdoug.com -- blog/tutorial on programming for the NES
JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Re: Scrolling collision methods

Post by JoeGtake2 »

Right, but you had to move column 1 values to column 0, then 2 to 1, then 3 to 2...and so on...filling the new column to the right...correct?
User avatar
dougeff
Posts: 3078
Joined: Fri May 08, 2015 7:17 pm

Re: Scrolling collision methods

Post by dougeff »

No.

I didn't shift any values. Once it was in the array it stayed in place.
nesdoug.com -- blog/tutorial on programming for the NES
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Scrolling collision methods

Post by Kasumi »

You need more than a screen's worth of data in RAM or collision gets weird near the edges. I used 32x32 metatiles (made of 16x16 metatiles) to fit 4 screens worth of tiles in a page of RAM. From there you can update the RAM column by column or whatever. It just gives you an offscreen buffer.

If you only scroll in one direction you end up with a HUGE collision buffer relative to the size of the screen. You could just opt for 512 pixels in either direction and then use the other half of the page for something else.
JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Re: Scrolling collision methods

Post by JoeGtake2 »

Kasumi - Yeah, I have a column worth of RAM space for leading offscreen buffering (my intention) and will likely reserve one for *trailing* to for things like monsters moving to edges and whatever.

But this is what you'd suggest knowing my current set up? Effectively shifting the thing column by column once the 16px 'metatile' boundary that I use is reached, and pushing the new column into the new place on the right? Do you recommend splitting this out over frames to make it sort of regulated and dependable, or just firing away? The 16 reads + 16 writes x 16 columns plus new data fetch seems long-ish, but I guess not so bad?
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: Scrolling collision methods

Post by Kasumi »

Suppose you have exactly one screen (256x256 for ease, rather than 256x240) of data that wraps. 16x16 tiles. Edit: I guess we're also assuming the data is stored such that byte 0 is top left, byte 1 is the tile below that rather than to the right of that as well, since that's the code I wrote. 8-) )

Which byte is the tile at the top of the column data for any given position?

Code: Select all

lda posx
and #%11110000
tay
lda tileram,y
The and is effectively a modulus, divide, and subtract of the scroll position all in one.

Suppose you have exactly two screens of data that wrap. Which byte is the tile at the top of the column data for any given position?

Code: Select all

lda posxhigh
ror a;Which screen in RAM is now in the carry
lda posxlow
and #%11110000
tay
bcs screen2
lda tileram1,y
bcc byteloaded;This could be a jmp
screen2
lda tileram2,y
byteloaded:
If you just add one offscreen column in each direction, you can no longer take those shortcuts because there are 18 columns instead of 16 or 32. And obviously with 32x32 metatiles (or some other power of two thing) the math changes slightly, but it'll still remain bitwise in a way that you can't with 18 columns.

This is why dougeff and I don't need to shift data once it's in the array. You should absolutely find a way to not have do that. A lookup table might get you results slightly similar to the above if I'm understand correctly and the plan is a sliding window of 18 columns.

As far as whether to split the update across frames, that's up to you. If you don't have to move the array, you'll only ever need to write 16 bytes every frame, and that's assuming you scroll 16 pixels every frame. (I guess really 15 bytes assuming columns are 240 as is traditional.)

Edit2: I guess the thought to take with you if nothing else is that power of two data has a way of unlocking random access, because of how simple the math is. If your data is screens, you can still only load the next column. It's easy to find which screen (horizontally) because that's a power of two, and then it's easy to find a column within that screen. So you never need 16 reads and 16 writes for 16 columns. Just 15 reads and 15 writes for one column. (Assuming... you only scroll in one direction. Also assuming no compression beyond screens/metatiles.)
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Scrolling collision methods

Post by tokumaru »

You normally don't have to shift the data to implement a sliding window like this, you just treat the structure that holds the data as a ring buffer. This is easier to implement with sizes that are powers of 2, because you can simply mask the upper bits when indexing the data and you're guaranteed to wrap around the ring properly, but it can be done with other sizes too, with look-up tables and/or comparisons.
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Scrolling collision methods

Post by Sumez »

What are your reasons for loading collision data into RAM?

It makes sense for Mario since collision data can be modified by breaking bricks, and the stage layout is loaded using individual structures and algorithms as far as I hear.
But if you store your levels in an easily unpackable format, I find it much easier to just look up collisions directly based on the object's world coordinates. Personally, I store collision data in its own table independently from the level data (allows me to create hidden passages, and invisible platforms etc.), and it doesn't take up a lot of space.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Scrolling collision methods

Post by tokumaru »

Sumez wrote:But if you store your levels in an easily unpackable format, I find it much easier to just look up collisions directly based on the object's world coordinates.
That's my preferred method too. I don't like to impose a hard limit on how far from the screen the action can go (after all, there are certain game mechanics that require objects to be active even when far away from the camera). One problem though is that "easily unpackable formats" tend to not compress as well as other methods, or result in more repetitive game worlds, so not all kinds of games can afford that.
Personally, I store collision data in its own table independently from the level data (allows me to create hidden passages, and invisible platforms etc.), and it doesn't take up a lot of space.
I personally prefer to have the collision data packed with the metatiles. If your collision data is any more complex than solid/empty (i.e. 1 bit per block), then yeah, the data can in fact occupy a lot of space (e.g. water, ice, breakable, hazards, slopes, solidity per side, etc.). I do have 2 sets of collision data per metatile though, so that levels can have 2 layers of solidity, allowing for loops and other crazy structures like those in Sonic games to be implemented using layer switchers. These same switchers could be used to make the same metatile behave differently in different places. I personally find it confusing when games have things that look the same but behave differently, so my games would probably have very little of that stuff, so I think I can afford a few "cloned" metatiles.
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Scrolling collision methods

Post by Sumez »

Yeah, you can basically save the collision data at whatever level of detail is most fitting for your engine. I'm using 2 bits per 16x16 metatile, so it does eat up a bit of data (eg. 1200 bytes for a large stage of 20 full "screens"), but until it becomes a concern, I don't see any reason to change it.
For my purpose it would definitely be more sensible to store collisions with my 32x32 sized tiles in the long run, but most people would just store it along with the 16x16 blocks. Either way it's super fast to look up for the engine.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Scrolling collision methods

Post by tokumaru »

Sumez wrote:1200 bytes for a large stage of 20 full "screens"
Which's not large at all compared to a Sonic level. Even Green Hill Zone act 1, the first level in the first game, is apparently 40x5 "screens" large, or 200 "screens" (many don't have any actual content though, so there's potential for optimization there). Yeah, I tend to compare everything to Sonic, because that's my reference when it comes to platformers, as that's the first one I ever played. :mrgreen:
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

Re: Scrolling collision methods

Post by Sumez »

Sonic's stages are famous for being absurdly large though. :)
I'm talking a game comparable to something like Ninja Gaiden, where every step is a new challenge, and not just scenery that you zoom through :P

Of course this only enforces the obvious conclusion that how you do these kinds of things depends entirely on your game's design.

Curiously the Sonic games famously have a ton of secrets hidden by using tiles with collisions that are different than they appear. How does the game store these? Does it just have duplicates (ie. a wall tile with collision, and a wall tile without it)?

In regards to my own game, storing collisions with the existing 32x32 metatiles is one solution, but it's worth noting that collision maps are even more prone to repeat patterns than the background graphics, and I might just as well end up keeping it stored separately, but compressed on its own. I think that would save a lot more space in the long run.
JoeGtake2
Posts: 333
Joined: Tue Jul 01, 2014 4:02 pm

Re: Scrolling collision methods

Post by JoeGtake2 »

Yeah - this is the method I use with Nametable data (loading next column, based on 64 possible columns...two nametables worth). I get the concept. But...ugh. I don't have the RAM space allocated for two collision tables...or rather, i sort of do, if properly load Collision tables as nibbles rather than full bytes...but that would mean a rewrite of a lot of collision detection, and the ability to use the upper bits as flags for each screen tile (used for various purposes module-pending...again, with this I need to think variable usage which tends to complicate things!). Hm.

And yeah, due to possible changing collision data (destructible terrain, animating tiles, etc) it really has to be loaded into RAM.

Some good things to think about, though, so thanks!
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Scrolling collision methods

Post by tepples »

A game that scrolls only horizontally might use a circular buffer 32 metatiles wide by 12 to 15 metatiles high to cache the map for collision and partial updates. At one byte per 16x16-pixel metatile, this should take just shy of one-fourth of the CPU RAM.
Post Reply