I've been writing a few blog entries with semi-technical notes about the innards of my WIP Ultima-style game. In this one, I talk about keeping track of state in dungeons with extremely limited RAM.
I've been working on implementing dungeons in Penult, starting with original data from Ultima 3 for testing purposes. Dungeons in Ultima 3 consist of 8 levels each, and each level is a 16x16 square of tiles. Since there are less than 16 unique tiles, two tiles can be stored in 1 byte of ROM, so a full dungeon takes up 1024 bytes of ROM space.
Due to extremely limited RAM (256 bytes for a SuperChip cartridge), only the currently visible portion of a level is loaded into RAM. The problem with this approach is that there are treasure chests distributed throughout the dungeon. If the player loots one, it should either vanish, or show an open chest, and not give the option to loot that chest again.
I could keep track of which chests have or haven't been looted throughout the dungeon, and override the chest information loaded from ROM with the current state of the chests. With the dungeon having 8 levels, and each level being 16x16, there are 2048 tiles in the dungeon, so 2048 possible places a chest could reside. Even if the chest state (looted or not) is stored as a single bit, this would take 256 bytes of RAM - which is all the available RAM, which obviously not feasible.
(dungeon view and treasure chests in Ultima 3 (left) vs Penult (right))
On the plus side, due to the smaller visible range while in a dungeon, much of the RAM used for the visible tiles during the rest of the game is not used here. Specifically, I use 84 bytes for the 12x7 screen, but only 30 bytes for the max 6x5 screen while in a dungeon, so this leaves me with 54 free bytes. How can these be used short of storing the state of every single tile in the dungeon?
First, I can at least track the state of the tiles on the current level. Each level has 16x16 = 256 tiles, so if the state of each is stored as one bit, then this will take 32 bytes. How to deal with the remaining levels, though? If I only tracked the current level, then the player could go to a different level, then immediately return to the previous level to loot the same chests again.
The solution I came up with involves tracking the state of previously-visited levels in sections. I divide the levels into 16 4x4 sections, and if any chests in that section have been looted, the whole section is marked as looted. When a level is revisited, the chest information is loaded into RAM, and then the section information is used to mark any chests as looted on the level in sections that have been marked as looted. While this method isn't exact, it should be close enough that the difference would not usually be noticed by players.
It is coincidence that the chests from the 37-year-old dungeon data that I'm using seems to align neatly with the sections I defined, but I can do that intentionally when creating my own content.
The section data for each level takes up 2 bytes using this method, or 16 total bytes for all levels, plus 32 bytes for the chest data for the current level which comes to 48 bytes total, out of the 54 extra available in dungeon mode.
This approach does have a few downsides. The main one is that using all of the variables that aren't used by the smaller display means that I can't switch back to the regular display while in the dungeon. Cases where I would normally do so would be when displaying the stats screen, or when in combat. This means that I'll need to come up with dungeon view specific versions of each of those screens. In the case of combat at least, I think this will end up being more of a positive than a negative, since it will lend a different feeling to dungeon battles vs outdoor battles.
(Current stats screen)