[President] Remembering collected items without extra RAM?

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

What would you want to ROM-hack?

Poll ended at Wed Jan 14, 2009 6:26 pm

SMB1 clone without PRG RAM
2
20%
SMB3 clone with PRG RAM
8
80%
 
Total votes: 10

tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

[President] Remembering collected items without extra RAM?

Post by tepples »

I've run into a problem: I'm sick of remaking Tetris.

Now I want to make a platformer similar to the Super Mario series, intended to be ROM-hacker-friendly. The player can pick up coins and power-ups from levels, but I don't want the player to be able to grab an item, move the camera two screens away, and then come back and grab the same item again.

But is this feasible without PRG RAM? Eventually I (or a ROM-hacker using my engine under license) might want to put a game on a cart to sell, and I'd imagine that the parts for SNROM-clone (MMC1 CPLD, extra 6264) are a lot more expensive than the parts for UNROM-clone (74HC161, 74HC32). Or should I just bite the bullet and spring for PRG RAM?

Several platformers for NES that have backtracking (Zelda II, Metroid, Kid Icarus, SMB2, SMB3) have 8 KiB of PRG RAM on the cart to remember what coins have been collected, which ? blocks have been opened, which bricks have been broken, etc. Games without PRG RAM either have a tiny level (Lode Runner, Crystal Mines), or lack backtracking (e.g. Super Mario Bros., Contra, Rainbow Islands, Battletoads), or have the vast majority of items comd from defeated enemies (e.g. Mega Man series). Gregg Iz-Tavares and Dan Chang recognized this in the the M.C. Kids post-mortem: "Without the extra RAM, we would have most likely have been forced to redesign the game either so levels didn't have to be modifed or so that it only scrolled in one direction."

Here's what the memory map looks like so far:
  • 0000-00FF: zero page, including state of level decoder
  • 0100-019F: VRAM transfer buffer
  • 01A0-01FF: stack
  • 0200-02FF: OAM buffer
  • 0300-03FF: unknown, much of it to be occupied by the music engine
  • 0400-05FF: state of 16 active objects
  • 0600-07FF: 32x12 metatile decoded section of map centered on player
I guess my internal debate is whether to make something like SMB1 (which has no backtracking) or to make something more flexible like SMB3 (which would pretty much need the entire map decoded to RAM first).
Celius
Posts: 2158
Joined: Sun Jun 05, 2005 2:04 pm
Location: Minneapolis, Minnesota, United States
Contact:

Post by Celius »

Honestly, what I'd do is organize all items/powerups in the level in a list of some sort. This list holds their coordinates, and information about the power up. This is in ROM. Then you make an array of flags in RAM which hold answers true or false to indicate whether an item has been taken. Say the player takes the 3rd item in the list. The third bit from the left in the first byte of the taken-status flags would be set. Since it's one bit per power up, that saves you RAM. If you plan on having 2048 power ups or coins, then that'll be 256 bytes.

I think if you're closer to being able to get away without using WRAM than not, you should try and avoid WRAM. The only reason I use it is because my game is a new Castlevania style game where there are lots of RPG aspects and you save your game. Since I basically had to use it to save games, I allowed for 3 save files, 1k each, leaving me 5k of RAM to work with. But if you're not planning on saving your game, I think you can get away without it.
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Post by Bregalad »

I've run into a problem: I'm sick of remaking Tetris
Honnestly, it's about time.

I think it should be possible to have backtracking and flags for items without extra cartridge RAM. In my game engine, the levels are separed into screen and each screen can hold up to 8 objects. There is a 64-byte table in the system RAM that holds one flag for eacah possible object in a 64 screen level, so that when the player opens a chest in the level it remains open until the player either gets a game over condition and have to do the level again, or beats the level. If he just loose a life but not game over yet, the flags aren't touched so that he cannot collect items more than once.

If you look carefully at Mega Man games, there is often extra life or energy capsules in levels that are not dropped by enemies, and those don't reapear when you exit the screen and come back if you picked them. Yet no Mega Man game ever used extra RAM.

The reason SMB3 needed extra RAM is because there is many coins and bricks that can be picked/destroyed, much more than 8 per screen. In that case yes extra RAM can be needed.
Useless, lumbering half-wits don't scare us.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Post by tokumaru »

I don't remember much of the memory map I was planning on using, but I'm pretty sure my Sonic engine could almost work with just 2KB of RAM. When I decided to add 8KB of RAM I indeed moved the object states there, but just because it made the object definitions easier to read (which can be hard when scrolling in both directions, shouldn't be a problem for side scrollers). The other things that reside in PRG-RAM now are the complete level map (it could be in ROM instead) and the currently active objects (I did this to increase the number of those from 16 to 32).

The bottom line is that the PRG-RAM I'm currently using isn't really necessary, it just made things a bit easier and more flexible. This means that the basic idea could probably be realized with just 2KB. If you have a bit for each object in the level just to tell if they're dead or alive, you could track 512 objects with just 64 bytes (I'm sure you can fit that in your memory map). Since 1 bit might not be enough for some objects (that need to remember more than alive/dead), I made some extra memory available (128 or 256 bytes, can't remember), and the object definitions of these objects contained a pointer to the byte to be used for this purpose (since there are few bytes, the pointer is only 8 or 7 bits). Technically you could even use a few consecutive bytes if the object is really complex and really needs them, there is no 1 byte per object limit.

That's it, I think you can keep track of a lot of things with 1 bit per object in the level and a few extra bytes for more complex objects.
UncleSporky
Posts: 388
Joined: Sat Nov 17, 2007 8:44 pm

Post by UncleSporky »

I think this is one of those things that gets weeded out in design - how big and complex do your levels need to be? Once you've got an average level figured out, you can see how much data you'll need to store.

I would tend to think similarly to the others here, you should be able to track one level's worth of objects with individual bits. Of course I don't know how commercial games did it at the time, perhaps there's something about that approach that just won't be enough.

You could also do something in between: make levels that are non-backtrackable after a certain point. You go through a door and there's no door to take you back, or you jump off a high ledge into the next screen below and there's no going back. These would be the halfway points of the levels, the checkpoints. A simple one way door would be easiest to explain to the people making their own levels.
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg »

Zelda used a lossy scheme for storing enemies; you could defeat some of the weaker ones in a room, exit, and re-enter to find the stronger ones converted to weaker ones. I think a lossy scheme could usefully work to reduce storage space below one bit per item. You could divide the level into sub-sections, group objects and enemies into classes, and keep track of the number of objects for each class in each sub-section. I think there are some creative things that can be done in approximating what things were left. Of course such a scheme could only be used for common things like coins or filler enemies; special items and bosses must be remembered precisely.
UncleSporky
Posts: 388
Joined: Sat Nov 17, 2007 8:44 pm

Post by UncleSporky »

blargg wrote:Zelda used a lossy scheme for storing enemies; you could defeat some of the weaker ones in a room, exit, and re-enter to find the stronger ones converted to weaker ones. I think a lossy scheme could usefully work to reduce storage space below one bit per item. You could divide the level into sub-sections, group objects and enemies into classes, and keep track of the number of objects for each class in each sub-section. I think there are some creative things that can be done in approximating what things were left. Of course such a scheme could only be used for common things like coins or filler enemies; special items and bosses must be remembered precisely.
I think such a system would work fine for enemies, which are alive and their positions can change, but I know I would hate to pick up a few coins out of a big square of them and come back to find the remaining coins rearranged. I can understand a system like that from a programming perspective but not a gaming one.

Also to address earlier points about how much object data needs to be stored, I think Mario needed extra RAM for situations like this:

Image

Big piles of interactive objects that have changing states. If your engine doesn't need that, you could do fine with less RAM. Admittedly it is more fun knowing you can break down that whole pile and there might be something hidden in the middle.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples »

UncleSporky wrote:Big piles of interactive objects that have changing states.
You're right about that. In fact, there's an even more pathological case of deformability that I want my engine to be able to handle: WORLD 1-2 from the original Super Mario Bros. Think of the amount of data that one would need to store for all the brick blocks in that map.
UncleSporky
Posts: 388
Joined: Sat Nov 17, 2007 8:44 pm

Post by UncleSporky »

tepples wrote:
UncleSporky wrote:Big piles of interactive objects that have changing states.
You're right about that. In fact, there's an even more pathological case of deformability that I want my engine to be able to handle: WORLD 1-2 from the original Super Mario Bros. Think of the amount of data that one would need to store for all the brick blocks in that map.
I just counted because I am bored. There are 263 breakable blocks in 1-2. 135 more brick tiles are not breakable due to being grounded but I imagine they are stored the same way (and if it were Mario 3 you could use a shell or your tail). There are 11 tiles that are ? blocks, hidden powerups and such. 21 enemies and 17 loose floating coins.

That's 447 things in the level that are interactive and would need at least 1 bit to indicate whether they still exist in their original state. (The multi coin blocks would require more.) If all you needed was 1 bit each that's 56 bytes for the whole level not including the pipe detour, ending staircase, or anything else I might've missed.

I think that's doable, especially if you used a one way door and split it in half, but at the same time you could build a much more robust and flexible engine with more RAM. It sounds like if you were going to make a nice Mario 3-esque game you would personally go for more RAM, and you should do it however you want. Personally, I have more fun trying to do more with less. :)
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Post by tokumaru »

Why can't I vote "SMB3 clone without PRG RAM"? Seriously, I think that's very possible. Of course you'd have to look away from the obvious and give up on decoding large sections of level maps to RAM, coming up with a decent scheme for reading maps from ROM instead.
Celius
Posts: 2158
Joined: Sun Jun 05, 2005 2:04 pm
Location: Minneapolis, Minnesota, United States
Contact:

Post by Celius »

tokumaru wrote:Why can't I vote "SMB3 clone without PRG RAM"? Seriously, I think that's very possible. Of course you'd have to look away from the obvious and give up on decoding large sections of level maps to RAM, coming up with a decent scheme for reading maps from ROM instead.
I was wondering the same thing. I would've voted for SMB3 without WRAM too.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Post by tokumaru »

Celius wrote:I was wondering the same thing. I would've voted for SMB3 without WRAM too.
Yeah, I just voted wrong because I though the first option said "SMB3" (kinda assumed that from reading the post, instead of actually paying attention to it). I just realized what was actually written when my vote was already being sent. Yeah, that one vote is from me and it's wrong. Sorry. =P
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples »

tokumaru wrote:Of course you'd have to look away from the obvious and give up on decoding large sections of level maps to RAM
By "large sections" do you mean bigger than the 32x12 metatile buffer that I already envision?
UncleSporky
Posts: 388
Joined: Sat Nov 17, 2007 8:44 pm

Post by UncleSporky »

I just voted for SMB3 because I'd prefer to see a more fully-realized game, whatever you have to do with RAM.

It can be difficult in cases like this. It's a lot of trouble to try to squeeze a good game in with less space, and you may not be satisfied in the end. But you're already going to the trouble of making a NES game which is enough of a headache by itself! What are you thinking, making a NES game, you crazy person?!
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Post by tokumaru »

tepples wrote:By "large sections" do you mean bigger than the 32x12 metatile buffer that I already envision?
I'm still not sure. 32x12 = 384 bytes does seem like quite a waste to me, and enough to remember the states of a lot of objects! I'd probably prefer compressing the level maps using a scheme that is not so slow to decode in real time but still compresses fairly well.
Post Reply