This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

4-Way scroll compression?

4-Way scroll compression?
by on (#67832)
Well just thinking about the development of a 4-way scrolling game...since the data goes to the RAM horizontally, and is probably compressed, when you player goes to the left....how the heck does it get that without taking a billion clocks to do the math to find out what tiles are where?


And also another qucik question....8K of WRAM, 2K of that could be used for 4-screen "mirroring", right?



It's magical how even after reading it, playing a game that does this really bring a light onto how complex these "old" games are. It's amazing.

by on (#67833)
I used big metatiles of 16x16 tiles to pull it off easily.

by on (#67834)
So you just looked up a meta lookup table so you then didn't have to compress it to get it to fit? Hmm....

by on (#67835)
This is the problem of compression of a 2D data set with random access. Make a map of the first level in a paint program and I might be able to offer suggestions as to how to store the level or how to move things around to make it easier to compress.
Re: 4-Way scroll compression?
by on (#67836)
65024U wrote:
since the data goes to the RAM horizontally

There is your problem, you are assuming that the data is encoded/stored in a certain way that prevents you from doing what you want with it rather than designing the encoding method based on what you want to do with the data in the first place. Good design is the key.

The obvious solution would be to use lots of RAM and decompress the whole map to it. I'm not too fond of that solution because not only it requires extra hardware but even 8KB can't hold really big levels if your metatiles are small.

The ideal solution in my opinion is to not compress the whole map as a single entity, but divide it into entities of fixed dimensions (such as "screens") that you can have random access to and compress those individually using your method of choice. Of course there is a hit in compression efficiency, but nothing is free in this world.

For platformers, big metatiles are great, since they allow you to make huge levels that don't occupy a lot of memory. For RPG they are not so good, because maps aren't as repetitive. Another solution that helps reduce the size of level maps and allows for reasonably quick random access is using several layers of metatiles. If your map is made of big metatiles, those metatiles can be made of smaller metatiles, and so on. The more layers you have the more compact (and more repetitive) the maps will be.

by on (#67837)
Hmmm that way of doing it in sections of a fixed is a clever thing!


And as to the map, I don't really have anything in mind but just how to access and set it up and move it around, thats what I am trying to wrap my head around. And yeah I guess your right but yet....thats just how it goes, the data would be stored horizontally, row for row....Why not plan for it?



And yeah doing it screen-by screen would enable dumping maps to RAM in sections a lot easier I guess and quicker to be able to decompress the map on the fly, so that seems like a good idea. I was thinking of just the compression scheme that was talked about where it is just the TILE# byte then the REPEAT byte.


Also, if you were making an RPG game, how would you know when to decompress the map and change something before it enters the screen? So many difficulties to this! XD Maybe a adventure scrolling game isn't a good idea. :/

by on (#67840)
Dragon Quest 2 (with no cartridge RAM) did maps by using up to 676 bytes of RAM for the map. The overworld was different, it was RLE, and you can do sequential access to RLE in a reasonable amount of time, provided you have row pointers. Dragon Warrior 4 needed more CPU time for the overworld, so it divided the map in half down the middle so it could seek to the right half of the map.

by on (#67843)
Dwedit wrote:
you can do sequential access to RLE in a reasonable amount of time, provided you have row pointers.

That's an example of "dividing the map into entities of fixed dimensions", the rows being such entities, because you have random access through them via those pointers.

I don't think row RLE is a good choice for free scrolling though, unless the length of the rows was small enough for you to not have to process a lot of data you don't need when scrolling horizontally.

65024U wrote:
And yeah doing it screen-by screen would enable dumping maps to RAM in sections a lot easier I guess and quicker to be able to decompress the map on the fly, so that seems like a good idea.

Yeah, if your largest metatiles are between 256 and 64 pixels wide/tall, keeping a good number of them in RAM is not such a big deal. You just have to update that RAM as the camera scrolls, by progressively decompressing the map.

Quote:
I was thinking of just the compression scheme that was talked about where it is just the TILE# byte then the REPEAT byte.

That's RLE.

Quote:
Also, if you were making an RPG game, how would you know when to decompress the map and change something before it enters the screen?

Look at the camera's coordinates. When they move a certain number of pixels (usually the dimension of the blocks you keep in RAM) you have to update a row/column of data.

For example, say I'm using 32x32-pixel metatiles to build my map. I then decided to set aside 256 bytes of RAM to represent an area of 16x16 of those blocks, covering a total area of 512x512 pixels. That's an area much larger than the screen, so it should be enough for the "active" map.

Now, to keep my "active map" always updated, I have to change it as the camera moves. To detect if I need a new column of metatiles, I have to detect when the camera completes 32 pixels of movement to the left or to the right. The easiest way to do that is to save its old X coordinate, move it, and EOR both coordinates. Then check bit 5 (since 32 in binary is %100000), if it's 1, the camera crossed a 32-pixel boundary and you need to decode a new column. Check the direction in which the camera moved to know if the new column is at the left or at the right. It works the same way for vertical movements.

It's not mandatory that you update the "active map" every metatile though... Depending on your compression scheme you could update it every 2, 4 or even a whole screen of metatiles, as long as you have at least a screen worth of valid data and enough CPU time to decode larger portions of data.

You'd use the same basic technique for rendering tiles to the name tables. You can detect when the camera has moved 8 or 16 pixels (depends on how fast you scroll and how many tiles you are able to update every frame - 8 pixels is OK for most games, but Sonic for example needs 16) and read the metatiles from your "active map" to get tiles out of it, tiles that you will write to the name tables during VBlank. The source and destination coordinates are always calculated based on the camera coordinates.

Quote:
Maybe a adventure scrolling game isn't a good idea. :/

That's up to you. If the idea isn't clear in your head, you probably shouldn't do it. You shouldn't take my word for it, when I explain solutions like I just did I do it hoping that it will give you ideas, and not that you will try to follow my explanation like some sort of guide, believing that it will work just because I said so.

So if what people here are telling you makes sense, and gives you better ideas on how to implement scrolling, go ahead. If not, go with something simpler, like horizontal scrolling only, which is infinitely simpler than horizontal+vertical.

by on (#67844)
Yeah, I know firsthand if you don't have a good idea of how you do something, you might as well know nothing, and this has really helped. I usually think of the screen just that, a screen, but thinking of it as a map with a camera is a hard thing to understand, but is so helpful to wrapping your head around everything. Such a big help bringing all of these details to light guys! This has to be the most concentrated game programming information site ever, not only for NES.


And as for updating the screen as it scrolls, I understand the 1 column move tell the game to update the row is it has to be modified because of progress in the game, but yet......It seems like there's nothing that can be done to store that easy. XD Oh well. Somethings gotta take up a lot of room.


Well I need to get back on my old project, but creating a scrolling demo is deffinently something I am doing next, and then just expand on the engine from there and maybe get something playable. Maybe if I take it slow enough, it'll come together better? I hope so.


Wow....yet again, thanks guys. You guys are the biggest help ever! :)

by on (#67874)
Wow, scrolling on the NES sure takes a lot of planning. It makes the SNES look good.

My "Project SNES" engine does scrolling in a way that would be impossible on the NES. The whole level is copied in the RAM stored with a 16x16 tile per byte. Every frame it processes an entire screen of tiles (2 if in dual collision mode) using a LUT to convert the bytes into the attribute words. During forced blank, it uploads the entire screen (2 if in dual collision mode) to v-ram, using 16x16 tile mode.

It might sound like a waste of hardware, but if you want to make 50 blocks explode at one time, it becomes useful.

This would never work on the NES because:
1) smaller amount of RAM
2) slower CPU
3) lack of 16x16 tile mode
4) lack of DMA

Reasons 1 & 3 also apply to the Sega Genesis.

by on (#67875)
psycopathicteen wrote:
The whole level is copied in the RAM stored with a 16x16 tile per byte.

Some NES games do that, but AFAIK they all have 8KB of extra RAM.

Quote:
Every frame it processes an entire screen of tiles (2 if in dual collision mode) using a LUT to convert the bytes into the attribute words. During forced blank, it uploads the entire screen (2 if in dual collision mode) to v-ram, using 16x16 tile mode.

Yeah, drawing a full screen every frame is out of the question on the NES.

Quote:
It might sound like a waste of hardware, but if you want to make 50 blocks explode at one time, it becomes useful.

Another advantage I can think of is that you can easily animate tiles without having to update patterns, which are typically slower to update than tile maps. On the NES, background tile animation can of course be done with CHR-ROM bankswitching at no CPU cost whatsoever, but this depends on mapper features, obviously.

Quote:
Wow, scrolling on the NES sure takes a lot of planning. It makes the SNES look good.

Things are not that bad on the NES. Most of the games out there would work well with the NES-friendly "update only the edges of the tile map as you scroll" technique. Background animations are done through bankswitching or CHR-RAM updates, although the latter is much more limited. My engine has special functions to handle the modification of tiles that are in the middle of the screen, so it's possible to update a decent amount of blocks every frame (surely not 50 though... maybe 10).

And there are several ways to compress level maps that allow for random access of the data, so you can simply access them directly from ROM. In my game, not a single byte of RAM contains level map data. The only RAM I use that's related to that are pointers used to read the maps/blocks, which stay exclusively in ROM.

by on (#67883)
Crystalis used a different approach. If you have played the game then you will notice that many areas have identical looking "screens" (even though the game implements 8-way scrolling).

The game world is composed of 100+ disjoint "areas". Special areas on each map are "warps" that cause the game to load a new area when the player steps on this spot.

The "areas" are defined in a largish table at 0x14310 to 0x17D09.

At the beginning of the ROM are 256 "screens" of meta-tiles. Each meta-tile is 2x2 NES tiles (so 16x16 pixels). Each area is a rectangular grid of screens.

There is no RLE compression. The game engine can determine if a tile is passable/not passable but doing a simple look up (and bank switching the screen data as appropriate). The game only decompresses what is visible on the screen, as off-screen enemies don't move (so no need to do collision detection, so no need to store off-screen map tiles in a readily accessible format). Personally, I think that off-screen enemies _should_ move around, but I didn't design the game.

http://datacrystal.romhacking.net/wiki/ ... is:ROM_map

All of the game maps can be viewed here:

http://www.vgmaps.com/Atlas/NES/index.htm#Crystalis


Disclaimer: Crystalis is one of my most favorite NES games. Back in 2001 I reverse engineered about 30% of the ROM, creating a commented disassembly, and wrote a tool to extract the maps. I was going to write a full game editor but ran out of steam and moved on to other projects. I still have my map decompresser code, but lost the commented disassembly. :(

by on (#67884)
clueless wrote:
Personally, I think that off-screen enemies _should_ move around, but I didn't design the game.

The designers/programmers probably thought they should move too, but since CPU time is very limited not moving them was probably a practical decision.

by on (#67887)
clueless wrote:
Crystalis used a different approach. If you have played the game then you will notice that many areas have identical looking "screens"

Super Mario Land for Game Boy uses this as well. It's so repetitive that the first time I played it, I thought 1-1 was a trap level like SMB1's 4-4 and 7-4.

by on (#67900)
Crystalis is my favorite game too! I have played it....alot! But truthfully with it I have never noticed how repetitive it it. I just never have. And a commented disassembly? 0_o Thats insane! Too bad it is lost :'(


As for it not being compressed thats pretty hardcore, and the special areas like villages and other places like bosses. I was looking at the pattern tables as since it had 4-way scrolling but watching how it did the MMC3 interrupts and did some funky stuff to scroll the screen, I was impressed and confused to hell and back of how it did it. XD


Well now after thinking of this really hard, I think that it'd be better just to use single-screen mirroring to scroll all 4 ways, and just do it a battle-kid sytle and just have one screen at the time where the "characters" travels along the screen the whole time and it scroll when he hits a certain point and then it puts the nametable in one of the 4 slots then scrolls the required way to the next screen. But yet, I still really would want to scroll 4-ways because.....I don't know. It seems like the challenge is worth it, and doing such a thing would give so much more to a game and you could add alot with it..... hmm :/ I really wish this was easier. :/

by on (#67901)
I would not say that Crystalis did not use any compression. Just that they did not use RLE for converting areas to meta-tiles.

This is all that I have left of my Crystalis hacking tools. I had posted them to Zophar's domain years ago, but they garnered little interest. The C code compiles into several tools. One is a map dumper. Another tool is a disassembler that disassembles the rom, merging it with comments stored in text files. I lost most of those files. Another tool fixes the checksum in a saved game file, making it easier to hack saved games. I don't remember what the other tools do.

At the time my goal in disassembling Crystalis was to create a map and/or full-game editor, not understand how it implemented scrolling or player physics. I gave up when I discovered that most event trigger in the game are custom code and not table driven. It is fairly easy to modify the map. Tedious but easy. However, changing the story looked to be much more complicated than I was willing to deal with.

[1] http://www.ecoligames.com/~djenkins/gam ... ols.tar.gz

[2] https://www.ecoligames.com/svn/Crystalis/
"svn co https://www.ecoligames.com/svn/Crystalis/ crystalis"

[3] http://www.zophar.net/wwwthreads/showfl ... 5&o=0&vc=1

by on (#67902)
Ahh, okay. It used some, but just not that. Okay.


Yeah, I was considering that too. A subroutine for special stuff that happens and it is all custom code, that might be how it runs too. Just JSR's to a text-updater, JSR's to button inputt and cursor movement, if not answer 1, close text box and increment special stuff counter or else give sword or something like that. I don't know any other way that could be done so yeah... :P


I am not much into hacking or reverse engineering, but I will probably give these tools a whirl some time. Crystalis is so amazing. Its hard to believe you got mostly through the code....phew! That makes me tired. XD

by on (#67925)
Personally I'm very opposed to screen re-use. I find it completely lame and cheap, and make games much less enjoyable.
In some cases when it is done on purpose (for mazes) it is ok, but games that uses it all the time are indecent.

I belive a good way to make any compression sheme pseudo-random is to compress every line/column of metatiles or screens (whathever you like the best) separately and have pointers at each of them. Note that you can have a pointer to each "screen" for compression purpose, without re-using screens at all (or not much). I do this in my game which obviously does screen-based scrolling, but it would work in a game that does random scrolling and that has memory for 4 screens (however, it would have to load them while scrolling which might be terribly slow and/or complex).