How to compress multi-direction scrolling?

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
User avatar
dougeff
Posts: 3078
Joined: Fri May 08, 2015 7:17 pm

How to compress multi-direction scrolling?

Post by dougeff »

I was reviewing my ninja game's scrolling engine. I figure with some minor tweaks I could scroll both left and right. (I have it working with uncompressed data).

But I'm scratching my head at compressing the room data. When I was only scrolling right, I had a pointer to each room, and decompressed as I scrolled through the room, one vertical column of metatiles at a time, adjusting the pointer after 13 metatiles.

(On a side note, I was never happy with my hand edited compression system, either)

Now, if I scrolled both directions, a pointer to a room wouldn't work unless I uncompressed the entire room into a 208 byte (16x13 game area, HUD at top) RAM space first, which would use up more RAM than I'd prefer.

Another idea I had was to compress half (left vs right) a room, and only have to use 104 bytes. I would need a pointer to each half-room, which isn't too crazy.

Or I could decompress into the unused part of the stack, maybe. 208 bytes there should be ok.

Thoughts?
nesdoug.com -- blog/tutorial on programming for the NES
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: How to compress multi-direction scrolling?

Post by tepples »

Assuming you don't want to just decompress an entire map to WRAM the way Super Mario Bros. 3 does, you could still randomly access columns in a data format similar to that of Super Mario Bros. Each object consists of two bytes:
  1. Position of object within screen (4 bits Y, 4 bits X)
  2. Object type
You'd maintain pointers to the start of objects within each page (256-pixel-wide area). Every time you draw a column, you'd scan the objects on the previous page and the current page to calculate the distance from the left side of the object to the column being drawn. If this distance is 0 to 15 metatiles, call each object's column drawing procedure, passing these arguments:
  • X position within the object, that is, the distance between the left side of the object and the current column (0-15)
  • Y position of the object
  • Object type
Each column drawing routine overwrites part of a 12- to 15-entry array of metatiles representing the current column. You may have one routine for each four object types, reserving the lower bytes for an "object size" argument.

Once all column drawing routines in range have finished, copy the metatile column to a 32-metatile-wide by 12- to 15-metatile-tall sliding window buffer used for collision detection, and prepare VRAM update packets based on each metatile's shape.

If you want, I can dig up President, a tech demo I made in 2009 that implements this algorithm. Both Super Mario Bros. and the President demo implement additional layers of scenery behind the objects, such as the iconic hills and cloudbushes.
User avatar
pubby
Posts: 583
Joined: Thu Mar 31, 2016 11:15 am

Re: How to compress multi-direction scrolling?

Post by pubby »

What do you mean by "room"?

For 2-way scrolling along the X axis, data is almost always stored in a column-major order. For compression, nowadays you can get away with only using metatiles. The larger metatiles you use, the better it will compress. If you insist on using RLE then it's easiest to compress each column individually and store each column's compressed size somewhere so that you can traverse backwards.

Anyway, I've developed a pretty cynical view on level compression. Most of the times it is a trap that limits you more than it helps. If you want to make your life easier, your levels prettier, and you RAM more spacious, ignore all compression beyond 16x16 metatiles. Flash memory is cheap; developer time is not.
User avatar
dougeff
Posts: 3078
Joined: Fri May 08, 2015 7:17 pm

Re: How to compress multi-direction scrolling?

Post by dougeff »

A "room" is the amount of data needed to fill 1 nametable.
nesdoug.com -- blog/tutorial on programming for the NES
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: How to compress multi-direction scrolling?

Post by tokumaru »

And then there's always multi-level metatile encoding, where metatiles are composed of other metatiles, if you're willing to go through a bit of indirection. It's pretty compact and allows random access, since the amount of memory used per room is constant.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: How to compress multi-direction scrolling?

Post by tepples »

Mega Man series for NES and Sonic the Hedgehog series for Game Gear use two levels (through 32x32), and Blaster Master uses three (through 64x64). Sonic the Hedgehog 2 and Sonic 3 & Knuckles for Genesis have a 128x128 scale. At that scale, it introduces another level of griddiness into your architecture. Sonic Advance series has 96x96-pixel metatiles, which appears to be an adaptation of the 128x128-pixel grid rhythm of later Sonic games for Genesis to the Game Boy Advance's smaller screen.

An even bigger metatile scale is reuse of a whole room: Sonic the Hedgehog for Genesis and Sonic CD use 256x256, and Super Mario Land uses 160x128. One problem here is that if you reuse rooms too obviously in early levels, new players will end up wondering whether the level is like the "maze" levels of the first Super Mario Bros. (4-4 and 7-4), where you get seamlessly kicked back four rooms if you don't pass through the right invisible rings.
User avatar
dougeff
Posts: 3078
Joined: Fri May 08, 2015 7:17 pm

Re: How to compress multi-direction scrolling?

Post by dougeff »

And then there's always multi-level metatile encoding, where metatiles are composed of other metatiles, if you're willing to go through a bit of indirection. It's pretty compact and allows random access, since the amount of memory used per room is constant.
I think I like this best. Instead of a 16x13 set of metatiles, a 8x7 set of metatiles to metatiles. I only need to fetch 7 bytes, and then decompress twice, buffer of 13, 2 buffers of 26. 26+26+13+7=72 total, plus 7 for a column of attributes (skipping the top for HUD) = 79.

That seems a manageable size of RAM for constructing the background on the fly.
nesdoug.com -- blog/tutorial on programming for the NES
User avatar
Kasumi
Posts: 1293
Joined: Wed Apr 02, 2008 2:09 pm

Re: How to compress multi-direction scrolling?

Post by Kasumi »

My "secret" slope game decompressed levels of 256x256 screens of 128x128 metatiles of 32x32 metatiles into RAM. (The 32x32 metatiles were further divided into 16x16 metatiles.)

With a page of RAM, you can fit 4 screens of 32x32 metatiles. All objects read from this RAM for collision. There was an RLE step for the 32x32 metatiles in the 128x128 metatiles. I think there were two streams. One for tile number, one for repeats. You could fit two strings of repeats in every byte since 16 was the guaranteed max. (XXXXYYYY)

I also did an overlay compression thing: https://forums.nesdev.com/viewtopic.php ... 70&start=0
;Basically:

tiles00:
.db 0, 0, 0, 0, 1, 0
tiles01:
.db 0, 1, 0, 2, 4, 5

becomes:

tiles00:
.db 0, 0, 0
tiles01:
.db 0, 1, 0, 2, 4, 5


;The address for tiles01 is put in the middle of tile00's data, but it doesn't matter. Because in either case, reading tiles0X,y will get the same value for both the top and bottom, so long as Y is in range. (If Y is out of range, that'd be... a bug.)
(I actually always recommend this. No changes to the underlying code that loads it are needed, even. Indivisible used only that overlay compression.)
I fit quite a lot in 16KB with all these techniques: https://youtu.be/2bJW64G_tHY
There are object definitions included in that, but they don't show up in the video. As well, I'm not limited much as far as what I can put in a level, even if all these test maps look pretty basic. Granted, if they got less basic I would also get less savings. But like... all of these maps fit in less space than the like... two in Indivisible.
The decompression was somewhat expensive, I guess? But only happened for 1 frame at 128 pixel boundaries.

And it's not hard, except for the RLE, somewhat. AND #% a given bit gives you which "half" of the metatile you're on for each dimension if it's a power of two.

Edit: But to be honest, I feel like just overlaying the data for the columns of metatiles would get you really decent savings. I only did all the rest for bidirectional random access.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: How to compress multi-direction scrolling?

Post by tokumaru »

I did try this kind of overlay compression once, where each screen was divided into rows or columns of metatiles, and all the rows and columns would be packed as tightly as possible as a single 1D array, so that each screen was just made of a constant number of pointers to this array. The results weren't so good though, so I scrapped the idea. I can see this working better when combined with other techniques, though.
User avatar
dougeff
Posts: 3078
Joined: Fri May 08, 2015 7:17 pm

Re: How to compress multi-direction scrolling?

Post by dougeff »

Here, I got it working. meta-tiles to meta-tiles. 2 way scrolling with a sprite zero hit.

https://youtu.be/wWrZ8Pn0t58
nesdoug.com -- blog/tutorial on programming for the NES
User avatar
Diskover
Posts: 219
Joined: Thu Nov 24, 2011 7:16 am
Contact:

Re: How to compress multi-direction scrolling?

Post by Diskover »

dougeff wrote:Here, I got it working. meta-tiles to meta-tiles. 2 way scrolling with a sprite zero hit.

https://youtu.be/wWrZ8Pn0t58
I love.

Will you share?
User avatar
dougeff
Posts: 3078
Joined: Fri May 08, 2015 7:17 pm

Re: How to compress multi-direction scrolling?

Post by dougeff »

Well, this is for asm6. not cc65. The ninja game was written in asm, and this is a slight modification of that code.

I'm not sure yet, but maybe I will make this open source one day.
nesdoug.com -- blog/tutorial on programming for the NES
Post Reply