It is currently Sat Jun 23, 2018 5:23 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 12 posts ] 
Author Message
PostPosted: Fri Feb 16, 2018 11:31 am 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 2092
Location: DIGDUG
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


Top
 Profile  
 
PostPosted: Fri Feb 16, 2018 11:57 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20165
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Fri Feb 16, 2018 12:01 pm 
Offline
User avatar

Joined: Thu Mar 31, 2016 11:15 am
Posts: 308
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.


Top
 Profile  
 
PostPosted: Fri Feb 16, 2018 12:54 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 2092
Location: DIGDUG
A "room" is the amount of data needed to fill 1 nametable.

_________________
nesdoug.com -- blog/tutorial on programming for the NES


Top
 Profile  
 
PostPosted: Fri Feb 16, 2018 1:07 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10523
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Fri Feb 16, 2018 1:34 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20165
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Fri Feb 16, 2018 3:55 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 2092
Location: DIGDUG
Quote:
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


Top
 Profile  
 
PostPosted: Fri Feb 16, 2018 6:02 pm 
Offline
User avatar

Joined: Wed Apr 02, 2008 2:09 pm
Posts: 1149
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: viewtopic.php?f=5&t=14370&start=0
Quote:
;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.

_________________
https://kasumi.itch.io/indivisible


Top
 Profile  
 
PostPosted: Fri Feb 16, 2018 8:37 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10523
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Sun Feb 18, 2018 9:01 pm 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 2092
Location: DIGDUG
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


Top
 Profile  
 
PostPosted: Mon Feb 19, 2018 1:16 am 
Offline

Joined: Thu Nov 24, 2011 7:16 am
Posts: 186
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?

_________________
Projects:
Shadow of the Beast (port)
The Sword of Ianna
The Banketh - The Video Game

My website: RetroNES


Top
 Profile  
 
PostPosted: Mon Feb 19, 2018 8:19 am 
Offline
User avatar

Joined: Fri May 08, 2015 7:17 pm
Posts: 2092
Location: DIGDUG
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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group