After a bit of research, I came out with some minimum specs for the game. It should be able to run on a BBC Model B with the default 32K of RAM, and a 40-track floppy disc drive.So the questions I need to answer are:
The challenge I've set myself isn't to write a roguelike from scratch within 7 days; it's to see exactly how much can be squeezed into a BBC Micro
- What restrictions does the game need to work against?
- What data does a roguelike need to store?
- How can I fit all that data into the machine?
As previously stated, I'll be writing the game in BBC BASIC II, for a 2MHz BBC Micro with 32K of RAM and a 40 track floppy disc drive (giving around 80K of space once formatted). But it's a little more complex than that.
Firstly, we've got to take into account the BBC's memory map. The BBC used a unified memory architecture - code and data can (and will) both be stored in RAM. The screen memory is also stored in RAM. This means that as each memory pool gets larger (code, data, screen memory), the others will get smaller. Code size is one thing that I can't predict at this stage, but the others - data and screen memory - can be controlled quite easily. If you cast your minds back, you'll remember that the BBC supports 8 screen modes:
|Mode||Type||Text resolution||Memory used|
|0||2-colour, full graphics||80x32||20KB|
|1||4-colour, full graphics||40x32||20KB|
|2||8-colour, full graphics||20x32||20KB|
|3||2-colour, full graphics||80x25||16KB|
|4||2-colour, full graphics||40x32||10KB|
|5||4-colour, full graphics||20x32||10KB|
|6||2-colour, full graphics||40x25||8KB|
By looking at the table, it becomes clear that I only had 4 real options available:
- An 80-column mode.
This is the norm for a roguelike, but the BBC doesn't have any 80-column modes that also have colour. Colour is a useful feature to enable players to quickly identify items and monsters. Also, 80 column modes use upwards of 16KB of RAM - leaving very little (at most 9.5KB) for the game and data (The remaining 6.5KB of RAM is used by the OS, filing system, and BASIC interpreter).
- A 40-column mode.
The black and white versions use less memory than the 80-column modes, but the colour version uses 20KB.
- A 20-column mode.
These are only available in colour; the 8 colour version uses a whopping 20KB, but the 4 colour version uses only 10KB. But with only 20 columns of text to work with, the visible map area would be rather small, and I'd almost certainly need to add support for a scrolling map (something that could probably be done without in 40 or 80 column modes).
This has 40 columns of colour text, but as it's a text-only mode it only needs 1KB of RAM. As I'm not interested in graphics, this makes it appear far superiour to the 40-column graphics modes. But in reality that memory superiority comes at a cost - every time I want to change text colour, I need to sacrifice a space on screen. In other words, I can't place two objects of differing colours next to each other.
The only other major factor restriction-wise is that of the floppy drive. I've already stated that a single-density, single-side floppy will give around 80KB of space once formatted; but I've also got to take into account the fact that Acorn DFS has a limit of 31 files per disc, and 7 character filenames. I'm intending to use the disc drive to store savegames, bones files, and a high-scores list (along with the game code and data). On the surface this doesn't seem like much of a problem, but it will force me to use a more complex save file system (see below).
Data to store
What data does a roguelike need to store? Briefly:
- Static game data.
This contains all the base stats of the items and monsters in the dungeon, including their names, appearance (a single ASCII character), and what class of item they are (weapon, food, monster, tool, etc.) This data will remain the same for every single game (Although the names of items may be randomized to add an investigative, discovery element to the gameplay).
- The current dungeon level.
This is the architecture of the dungeon, containing elements such as walls, doors, and stairs leading to the levels above and below. For the most part the dungeon is non-interactive, but most roguelikes support destructible terrain (typically the ability to carve passages through rock using a pick-axe). Although there is unlikely to be a pick-axe in my game, I do want to add support for destructible terrain, so it's important for the game to allow me to modify the map during play.
- The items in the current dungeon level.
This includes the player, the monsters, and all the other objects (food, weapons, etc.). It will also include all the objects the player and the monsters are holding. For each object, the minimal amount of data needed will be its type (player, laserdisc, cemtex mouse, pot noodle, etc.) and its location (either a coordinate in the dungeon or the ID of the player/monster that it is 'inside'). However I'm also hoping to store much more information - most notably the current health of a monster, the quality of a particular weapon or piece of armour, whether some food is poisoned or mouldy, etc.
- The players' map.
A traditional feature of roguelikes is that they employ line-of-sight - i.e. when you enter a level you only know about your immediate surroundings, and you cannot see anything that is behind a wall. As you explore the level your character creates a map of the level (either mentally or on a piece of paper), thus more and more of its structure is made visible to the player on-screen. So for each map cell I'll need two extra bits of information - whether the player can see it now, and whether he has seen it before. It is possible to store more information (e.g. the last known location of monsters, or the location of invisible monsters), but basic visibility information will do for now.
- Other state variables.
This includes the current game time (i.e. turn number), the player's score, experience level, dungeon level, etc. These variables will be added to the game as and when needed, since it's impossible to predict all of them beforehand.
- Previous levels.
I'm a big fan of persistent levels, so naturally I'll want the game to save the layout and contents of previous levels, so it will all still be there if the player needs to return at some point. This will basically involve storing the dungeon map, dungeon items, and the player's map. If needed I could cut this feature, but in my opinion it's a big part of what makes a roguelike a roguelike.
- Bones files.
These are stored on disc, and have a random chance of being loaded into memory when the player travels to a new level. A bones file is basically the dungeon map and dungeon contents for a level on which the player died. Typically games modify the item list slightly before writing it to a bones file - e.g. to transform the deceased player into a ghost, and to curse all his items.
- High scores.
This is basically a text file listing the name and score for each player who has played. They typically also contain other information, e.g. the length of the game, the maximum dungeon level reached, and the reason for ending the game (e.g. the players cause of death, or whether he won the game by defeating his nemesis and escaping alive).
You wanted to fit that into how much RAM?
Yes, it does sound like quite a bit, and it's possible that I may have to start cutting back. But after a fair amount of planning and head-scratching, I'm confident that I can get everything down to a manageable size:
- Static game data.
During the design process, I've made a list of around 120 dungeon items and their stats. I then grouped those items into types, and those types into classes. This gave me a list of exactly what information needs to be stored for each dungeon item, both in terms of its active and static data. Initially, I was considering using DATA keywords to store the static data. BASIC II supports RESTORE by-line-number, so by storing data for each item on a seperate line I could have fast access to it without requiring the entire DATA segment to be read or extracted and stored elsewhere.
Unfortunately some simple maths shows that DATA statements would take too much space. To store a one-digit number, two bytes would be required - one for the number, and one for the comma seperating it from the next field. A raw CSV export of the spreadsheet I was designing everything in came to 14K (A bit of an unfair test, but indicitative of how many items I'm hoping to include in the game). So, I set about designing a better solution (which will be discussed in detail tomorrow). Current tests suggest that it can squeeze the static data into about 4K of memory - half of which is the names of all the items.
- The current dungeon level.
For simplicity, I won't be having a scrolling map. This means that the largest level possible would be 40 by 25 tiles; in reality I'll only be using 40x22, as 3 rows will be required for displaying the players' status and game messages. And since the dungeon is fairly simple in design, I'll only need at most 1 byte per tile - so a full map of the current dungeon level will require 880 bytes of memory.
- The items in the current dungeon level.
To allow for one-byte object IDs, I'll be limiting the game to 256 items per level. Furthermore, one of those will always be the player, 52 will be reserved for his inventory (to allow the inventory items to be referenced with upper and lowercase A-Z, ala NetHack), and one will be reserved for the 'no object' ID. This will leave 202 items for the rest of the dungeon. This number sounds perfectly reasonable to me, considering the small size of the levels, and that only the items in the current dungeon level will be kept in memory. Following on from my design of the static dungeon data, I was able to work out exactly how much memory is required per item - a mere 7 bytes. This contains the 1 byte type ID, a 2 byte location, and 4 bytes of data (The interpretation of which changes depending on what class the object belongs to). Therefore 255*7=1785 bytes of memory will be required to store all the dungeon items, and storing the items on a particular level into a savefile or bones file will require 202*7=1414 bytes.
I've decided against using dynamic memory allocation for two reasons - firstly, BASIC doesn't really support it, and secondly, it would open the game up to running out of memory and crashing if there isn't enough memory spare for all 255 objects. Of course, it can still run out of available object slots, but that's a lot easier to detect and handle than running out of memory outright.
Similarly, I could write more advanced savefile code that strips out empty object slots, to reduce disc space. But that would require some form of advanced save format that either compacts the savefile or reuses empty space; a save format that would take time to develop and increase the code size further. The simple solution to this problem would be to store each level in a seperate file, but with only 31 files per disc it could quickly run out of allocations.
Having said that, the practicality of storing the game code, static data, high scores, bones files *and* save files on one 80KB floppy with a 31 file limit is questionable - once the game is finished I may advise authentic floppy users to store each savegame on a seperate floppy.
- The players' map
To store this, I only need two bits per map cell. One bit to flag if it's currently visible, and one bit to flag if it's been visible in the past. Rather than allocate a seperate buffer for this information, I'm going to make use of some unused bits in the dungeon map. There are only 31 different dungeon tiles, so the current map structure is only using 5 of the 8 bits per byte. Adding the players' map to that will leave one bit spare, which I can use for temporary calculations, such as checking which tiles should be blasted by an explosion.
- Other state variables
As stated it's a bit hard to tell how many of these there will be, so it's also impossible to state how much memory they would require. At the most, I'd expect them to use 1K of memory, but hopefully their requirements are so small that I don't need to factor them into any calculations.
- Previous levels
I've already revealed some of my plans for this - each savefile will be made up of fixed-size blocks (for ease of rewriting the data). The first block will be the header, containing the 'other state variables' and the player state (most notably the player object and his 52 private inventory slots). This will take around 400 bytes of space. Then for each level there will be the dungeon map (squeezed into 660 bytes, as we only need to store 6 bits from each byte), and the 202 dungeon items (1414 bytes), totalling 2074 bytes per level. Assuming I have an entire 80KB floppy at my disposal, that means I can fit 39 levels worth of data. As the game progresses I will decide on how deep the dungeon is, to hopefully ensure that the game code, data, high scores, and a full save file can fit on one floppy.
- Bones files
These are basically a stripped-down savefile, containing only the data for one level - so will be around 1964 bytes in size.
- High scores file
Unless I strip out old scores, the high scores file has the potential to grow uncontrolably. I may just leave this as a problem for the player to tackle, however.
My RAM usage looks to be the following:
- 6.5KB used by the OS
- 1KB used for screen memory
- 4KB used for static data
- 880 bytes used for the current dungeon level and player map
- 1785 bytes used for the object list
Luckily some help is at hand, in the form of BasCompress and StrongBS, which can strip out all unnecessary space from a BASIC program and rename variables to get the code as small as physically possible. I will only be using these programs as a last resort, however - although the BASIC code they produce should run without problems on a BBC, the compressor itself only runs on RISC OS. If the BBC code relies on a compressor, then it would prevent anyone without a RISC OS machine from modifying the (readable) version of the code, because they wouldn't be able to recompress it to run on the BBC. The only cruncher I'm planning on using extensively is BASIC's own builtin CRUNCH command - but even that is only avaialble on BASIC V and above, and at present isn't supported by Brandy.