How do scrolling games store their immediate screen status?

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
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

How do scrolling games store their immediate screen status?

Post by DRW »

How do games with regular scrolling (or even four way scrolling) check during gameplay which places in the level are walkable and which places are walls?

In a game like "The Legend of Zelda", it's probably pretty straight forward: Since the game only uses screen-by-screen scrolling, the screen graphics buildup function probably also fills an independent 16 x 11 byte array that has the data of the playfield. And when the characters move, they check their x and y position against this array to check whether they can walk or whether they reach a wall.
So, in this case, it doesn't even matter how the screen data is stored in ROM. The checks during live gameplay go against a small and simple array.

If you had a huge amount of space, the same would also work with scrolling levels: For a level that's 20 screens wide, just declare a 320 x 15 array in ROM and put all the background object IDs there. Use this same array for graphics buildup and for game logic alike: You can use these IDs to check in another array what graphics to load. And in yet another array whether this object is walkable. Divide the character's x and y position by 16 and you get to the exact place in the array where your character is standing.


But what if the level structure is compressed? How is the immediate walkability of a certain point on the screen determined?

Take for example "Castlevania": I doubt that the structure of a level is stored as one huge, uncompressed 1:1 representation.

So, how does the game store its immediate on-screen level status?
Does this game have an 18 x 11 array in RAM, i.e. two blocks wider than the screen? And every time the game scrolls by 16 pixels to the right, then all values in all the rows of the array are shifted to the left, with the last columns being filled with new data from ROM?

Code: Select all

ABCDEFGHIJKLMNOPQR     BCDEFGHIJKLMNOPQRS
ABCDEFGHIJKLMNOPQR --> BCDEFGHIJKLMNOPQRS
ABCDEFGHIJKLMNOPQR     BCDEFGHIJKLMNOPQRS
Or is this done in another way?

And just think of four way scrolling. You would need an array that's slightly bigger than the horizontal and vertical size of the screen. And you would have to shift data horizontally and vertically whenever the player character moves.
That's surely easily possible on a PC game. But is this also the way NES games do this? To me, that's a huge performance eater, having an array that's more than 255 bytes big and also having to constantly shift data around. How do professional games, like "Crystalis", handle this?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: How do scrolling games store their immediate screen status?

Post by tokumaru »

I never understood the appeal of having separate collision maps... To me it makes a lot more sense to have collision information as properties of the blocks used to build the game worlds, so you always access the same map, be it for drawing or collision purposes. If you don't need anything fancy for collisions (e.g. arbitrary slopes, multiple layers, etc.) you can usually pack palette and collision data in a single byte, which is pretty compact.

I generally dislike buffering really small sections of a large map in RAM too. Being able to interact only with things that are visible on screen can cause problems, since enemies near the edges of the screen may need to collide with areas that are a few blocks off screen. If I was buffering parts of a big level in RAM, I'd probably want to have at least a couple of screens worth of data in each axis, but I always prefer to have access to the entire level whenever possible.

Using compression doesn't mean you can't access levels directly in ROM, since there are forms of compression that allow for random access. If you build your levels out of larger blocks, like 64x64 pixels, then each screen can occupy 16 bytes, instead of the 256 or 240 bytes of a screen built out of 16x16-pixel blocks. You still have to encode all those 64x64-pixel blocks, obviously, but you'll still save tons of space if the type of game you're making can reuse those big blocks across a few different maps.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: How do scrolling games store their immediate screen status?

Post by DRW »

If you have a separate collision map, you can check the walkable/solid property directly.
If you use the level map, then you have to get the object ID from the level map. And then you have to take that ID to look up another array to check whether this object is walkable/solid.

Of course you could encode the walkability into the level map itself, as you suggested. But this means you can only have 128 different level objects instead of 256. And if your level object has other properties, like being lava or ice, or even the palette as you said, you're further limited down to 64 or 32 objects.

And all this only works if you actually have your level stored relatively uncompressed to begin with.
Yes, 32x32 meta tiles allow direct access. But in this case, you cannot have small objects on screen, unless you also encode the walkability of each of its four 16x16 subsections into the thing. Which makes access slower again, having to work with bit manipulation. And again, you get limited to fewer meta tiles.
Or if each 32x32 meta tile has properties in yet another external array, then again, you have more stuff to do to get to your desired collision information. While a separate collision map in RAM that stores the data in 16x16 tiles, no matter your actual map compression in ROM, allows more direct access.

So, direct access to the level map for live gameplay only really works if you encode it as 16x16 tiles and if your tile properties plus your level object ID fit into one byte.

And if you use a completely different compression method, you get issues.
For example, in "The Legend of Zelda", a screen is defined by 16 bytes for the 16 horizontal block columns on the screen. Each byte then points to another array that has the 11 vertical block rows.
Sure, you can access these things easily. But it's still faster and shorter to use a straight up 16 x 11 array in RAM.
Or imagine if the screen is RLE encoded: How do you get to the tile at position x=5,y=9?
Or like in "Link's Awakening": Where the floor and walls are drawn globally and then each object is listed with an individual x and y position.


So, yeah. That's why I was asking: How did games with huge scrolling levels did it?
"Gauntlet II" has levels of 2x2 screens, so they can probably spare the RAM data to save an entire level. And "Super Mario Bros. 3" uses its extended cartridge RAM for levels.
But how do games like "Mega Man" or "Castlevania" handle their collision with the background? Are their level maps designed openly enough, so that they can read arbitrary positions directly from ROM? Or do they buffer the collision data of the whole huge level into RAM? Or do they just buffer a subset of the level (the current screen plus some offscreen space) and do massive data shifting every 16 pixels?
Or do they do different approaches?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
Quietust
Posts: 1920
Joined: Sun Sep 19, 2004 10:59 pm
Contact:

Re: How do scrolling games store their immediate screen status?

Post by Quietust »

DRW wrote: Fri Mar 04, 2022 3:35 am Of course you could encode the walkability into the level map itself, as you suggested. But this means you can only have 128 different level objects instead of 256. And if your level object has other properties, like being lava or ice, or even the palette as you said, you're further limited down to 64 or 32 objects.
Not necessarily - you could still have 256 distinct level objects and just restrict them so that 128 are walkable and 128 are non-walkable, using one of the data bits (either D0 or D7) to specify walkability while also being used to specify appearance. You could also use lookup tables indexed by the object ID to determine any of their special properties, assuming that keeping all of the unique property sets contiguous is infeasible.
Quietust, QMT Productions
P.S. If you don't get this note, let me know and I'll write you another.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: How do scrolling games store their immediate screen status?

Post by DRW »

Quietust wrote: Fri Mar 04, 2022 6:11 am Not necessarily - you could still have 256 distinct level objects and just restrict them so that 128 are walkable and 128 are non-walkable
Good point. That might be an option. At least if solid/walkable is the only property.

Quietust wrote: Fri Mar 04, 2022 6:11 am You could also use lookup tables indexed by the object ID to determine any of their special properties
Yeah, that's the primary reason that I meant why a separate map in RAM might be useful: Using the level map requires more steps to get to your data if you don't have the ability to encode literally everything, ID and status, into one byte.

Of course, one could also use two maps in ROM: One for the tiles and one for the properties. With a bit of macro trickery, this wouldn't even require redundancy in the source code file.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: How do scrolling games store their immediate screen status?

Post by tepples »

Super Mario Bros. decompresses each 13-cell-tall column of the level to a 32x13-cell sliding window buffer in RAM. Only interactive elements, not decorations, are actually written back to the sliding window; decorations are written only to the screen.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: How do scrolling games store their immediate screen status?

Post by DRW »

So, SMB indeed saves the entire current playfield to the RAM?
And I assume when Mario walks to the right, they don't shift the values in that array to the left, but simply use some kind of offset value to determine with which entries Mario shall check the collision, right?

I'm surprised that they did this. Because this way, you have an array that is 416 bytes large, i.e. you have to use more complicated logic to access its entries.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: How do scrolling games store their immediate screen status?

Post by tokumaru »

DRW wrote: Sat Mar 05, 2022 2:56 pmAnd I assume when Mario walks to the right, they don't shift the values in that array to the left, but simply use some kind of offset value to determine with which entries Mario shall check the collision, right?
The memory is probably used as a circular buffer, that the game treats as "infinite" but it wraps around because it's not physically infinite.
I'm surprised that they did this. Because this way, you have an array that is 416 bytes large, i.e. you have to use more complicated logic to access its entries.
It's 416 bytes but it's still 32 (a power of 2) cells wide, and since the game only scrolls horizontally, you can have it wrap around with no effort at all.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: How do scrolling games store their immediate screen status?

Post by DRW »

tokumaru wrote: Sat Mar 05, 2022 3:05 pm It's 416 bytes but it's still 32 (a power of 2) cells wide, and since the game only scrolls horizontally, you can have it wrap around with no effort at all.
The wrapping around isn't the thing that surprises me. It's the collision detection: To check whether a character walks against a wall, they have to access an array with a two byte index. This is one of the things that I try to avoid during live gameplay.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: How do scrolling games store their immediate screen status?

Post by tokumaru »

DRW wrote: Sat Mar 05, 2022 4:33 pmThe wrapping around isn't the thing that surprises me. It's the collision detection: To check whether a character walks against a wall, they have to access an array with a two byte index.
The 6502 isn't so underpowered that you have to fit everything in 8 bits... Calculating a 16-bit pointer is hardly an expensive task.

Also, in this particular case, you might not even need to calculate a full-blown pointer all the time... You can think of the 416-byte array as two 208-byte arrays (16 * 13), calculate an 8-bit index as usual and branch on a simple condition to select which table to read from:

Code: Select all

  lda xcoord+1
  lsr
  bcs :+
  lda table0, y
  bcc :++
: lda table1, y
:
Or you could unconditionally modify a bit of a pointer in RAM dedicated to reading from these arrays:

Code: Select all

  lsr pointer+1
  lda xcoord+1
  lsr
  rol pointer+1
  lda (pointer), y
15 or so extra cycles when accessing the level map will NOT break the bank.
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: How do scrolling games store their immediate screen status?

Post by Oziphantom »

sort you tiles into different groups such that you have

0 < death < solid < customTrigger < jumpThrough < background < 256

those 3 values can be defined per level/per area of level if needed. then you can

Code: Select all

lda (charMapPtr)
cmp death
bcc _killPlayer
cmp solid
bcc _hitSomething
cmp customTrigger 
bcc _handleCustomTrigger
cmp jumpThrough
bcc _canPassButLandOn
cmp background
bcc _noCollide



_handleCustomTrigger
sec
sbc customTrigger
tax
lda FuncTable.lo,x
pha
lda FuncTable.hi,x
pha
rts
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

Re: How do scrolling games store their immediate screen status?

Post by DRW »

Yeah, that’s actually a sensible idea. Have the special property be part if the ID number itself. This might be a solution.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Post Reply