log in | register | forums
Show:
Go:
Forums
Username:

Password:

User accounts
Register new account
Forgot password
Forum stats
List of members
Search the forums

Advanced search
Recent discussions
- Elesar brings back Font Directory Pro for modern machines (News:9)
- AMCS free versions are live! (Gen:9)
- Elesar updates Font Directory Pro to 3.21 (News:)
- Disappearing websites (News:)
- What development tools do we need ported to RISC OS (News:6)
- Help getting RPCEmu working on a MacBook (Gen:9)
- What software updates would like to see at the next show? (News:6)
- RC15 bring RISC OS to any Raspberry Pi (News:3)
- Latest Drag'n'Drop magazine reviewed (News:)
- Wakefield 2017 Show Report (News:4)
Related articles
- Bob and Trev: Resurrection: Just in time
- Monster AI
- Combat
- Visibility and pathfinding
- The level generator
- Static game data
- Bob and Trev: Resurrection
- Wakefield 2003 - the preview
- Newsround
- Games news
Latest postings RSS Feeds
RSS 2.0 | 1.0 | 0.9
Atom 0.3
Misc RDF | CDF
Site Search
 
Article archives
Acorn Arcade forums: News and features: How to fit a roguelike in 32k
 

How to fit a roguelike in 32k

Posted by Jeffrey Lee on 00:00, 11/3/2007 | , , , , , , , ,
 
Previously, on Bob and Trev: Resurrection...
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.
 
...
 
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
So the questions I need to answer are:
  1. What restrictions does the game need to work against?
  2. What data does a roguelike need to store?
  3. How can I fit all that data into the machine?

Restrictions

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:
 

ModeTypeText resolutionMemory used
02-colour, full graphics80x3220KB
14-colour, full graphics40x3220KB
28-colour, full graphics20x3220KB
32-colour, full graphics80x2516KB
42-colour, full graphics40x3210KB
54-colour, full graphics20x3210KB
62-colour, full graphics40x258KB
7Teletext40x251KB

 
By looking at the table, it becomes clear that I only had 4 real options available:
  1. 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).
  2. A 40-column mode.
    The black and white versions use less memory than the 80-column modes, but the colour version uses 20KB.
  3. 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).
  4. Teletext.
    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.
In the end, it was memory requirements that won me over. Using only 1KB of RAM, Mode 7 was the obvious choice, leaving just over 24.5KB of RAM to store my BASIC program and its data. And although I wouldn't be able to provide any significant colour support for the target machine, there is scope for machines with more memory (e.g. 64KB) to use the 4-colour Mode 1.
 
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.

Summary

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
Totalled up, that's about 15465 bytes - leaving about 16.5KB for me to fit the BASIC code into. This doesn't sound like much, and considering some of my plans for the game, I don't fully expect to be able to support all the features I want.
 
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.
 
  How to fit a roguelike in 32k
  Phlamethrower (11:55 11/3/2007)
  Phlamethrower (12:50 11/3/2007)
    fwibbler (17:55 11/3/2007)
      monkeyson2 (18:10 11/3/2007)
        Phlamethrower (18:23 11/3/2007)
          monkeyson2 (18:25 11/3/2007)
            Phlamethrower (18:28 11/3/2007)
        fwibbler (21:13 12/3/2007)
          Lampi (11:05 17/3/2007)
            Phlamethrower (11:52 17/3/2007)
 
Jeffrey Lee Message #99755, posted by Phlamethrower at 11:55, 11/3/2007
PhlamethrowerHot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff

Posts: 15054
A progress update, then.

The load/save system, dungeon generator, time system, and simple player input/movement code is done. You can happily wander around levels opening and closing doors, looking at the pretty line-of-sight.

The code is currently hovering around the 10K mark, which is a bit worrying since the limit is 16K.

But more worrying is that it's all hideously slow when run on a BBC emulator. This is perhaps something that I should have seen coming, but I think focusing on the memory constraints first was the right thing to do. I'm now in the process of rewriting the code for speed, which unfortunately means removing some of the fancy features (Like proper line-of-sight).

Compared to the speed, the memory limits aren't so much of an issue at the moment. I can even squeeze about 4K more space out of the code by moving the level generator to a seperate program.
batr1.png 652x598 12.5KB
batr1.png
652x598
12.5KB

  ^[ Log in to reply ]
 
Jeffrey Lee Message #99758, posted by Phlamethrower at 12:50, 11/3/2007, in reply to message #99755
PhlamethrowerHot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff

Posts: 15054
</rewrite>

It now runs at a decent speed. Hurrah!

It does take about 6 seconds to change room, but as long as you stay in the same room (and there aren't any monsters about) you can move about 3 squares per second. And even the room change time can be sped up further - maybe to 2 or 3 seconds.
  ^[ Log in to reply ]
 
fwibbler Message #99772, posted by fwibbler at 17:55, 11/3/2007, in reply to message #99758
fwibbler

Posts: 318
Have you tried setting PAGE=&1200?
  ^[ Log in to reply ]
 
Phil Mellor Message #99777, posted by monkeyson2 at 18:10, 11/3/2007, in reply to message #99772
monkeyson2Please don't let them make me be a monkey butler

Posts: 12380
Have you tried setting PAGE=&1200?
Will that affect DFS?
  ^[ Log in to reply ]
 
Jeffrey Lee Message #99782, posted by Phlamethrower at 18:23, 11/3/2007, in reply to message #99777
PhlamethrowerHot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff

Posts: 15054
^ what he said.

But if it did work, it'd get me around another 1.5k to play with.

Also, are BeebIt and 6502Em both Wrong, or didn't the BBC have a cursor in mode 7? RISC OS machines and 65Host have a cursor, and I'm 99% certain the teletext chip supports it, but BeebIt and 6502Em don't show it (And yes, I do have the 'cursor' options turned on )

[Edited by Phlamethrower at 18:25, 11/3/2007]
  ^[ Log in to reply ]
 
Phil Mellor Message #99783, posted by monkeyson2 at 18:25, 11/3/2007, in reply to message #99782
monkeyson2Please don't let them make me be a monkey butler

Posts: 12380
Also, are BeebIt and 6502Em both Wrong, or didn't the BBC have a cursor in mode 7? RISC OS machines and 65Host have a cursor, and I'm 99% certain the teletext chip supports it, but BeebIt and 6502Em don't show it
I'm fairly sure it did have a cursor, but it possibly looked different to the ones in other modes.
  ^[ Log in to reply ]
 
Jeffrey Lee Message #99785, posted by Phlamethrower at 18:28, 11/3/2007, in reply to message #99783
PhlamethrowerHot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff

Posts: 15054
Ah, upgrading from BeebIt 0.42.1 might help

Version 0.50 (12 Apr 2003)
...
- Added a cursor to teletext mode.
  ^[ Log in to reply ]
 
fwibbler Message #99856, posted by fwibbler at 21:13, 12/3/2007, in reply to message #99777
fwibbler

Posts: 318
As I recall, unless you're planning to do something fancy with DFS then it shouldn't affect it.
It should still work for basic operating procedures.
Cheers!
  ^[ Log in to reply ]
 
James Lampard Message #100153, posted by Lampi at 11:05, 17/3/2007, in reply to message #99856
Lampi

Posts: 190
I've already stated that a single-density, single-side floppy will give around 80KB of space once formatted
I'm pretty sure it's actually 100K (-512 bytes for the catalogue)

I work it out as (40*10 *256) /1024 =100.
i.e. it's 10 sectors per track.
It's ADFS that uses multiples of 8 sectors.
  ^[ Log in to reply ]
 
Jeffrey Lee Message #100156, posted by Phlamethrower at 11:52, 17/3/2007, in reply to message #100153
PhlamethrowerHot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff

Posts: 15054
I can't seem to find the website I got the information from, but I was rather uncertain myself whether it really was 80K.
  ^[ Log in to reply ]
 

Acorn Arcade forums: News and features: How to fit a roguelike in 32k