From Retrosoftware

Revision as of 18:39, 17 December 2010

SAGA Rework Diary

Background

I've often wondered why the BBC never got graphical versions of the Scott Adams and Mysterious Adventures games. Yes, the BBC was short of memory and only had a limited colour palette; but it still should've been possible to supply some graphics; even mode 7 ones!

So, I've decided that I'm going to add some graphics to the games on a BBC. My target platform is to fit on a BBC B with standard PAGE &1900 DFS to allow full saving.

How To Start

There are a couple of ways this can be done:

1. Hack the current engines to add graphics on a new room.
2. Write a new interpreter.

I've decided to go for the second route, even though it would take the most amount of effort. There's many reasons for this, some due to laziness (both mine and Brian Howarth - the original author of the engine), others due to technical constraints.

The most important reason is that there doesn't seem to be just one engine, with each new game that came out, the engines got updated and twiddled.

The second is that the engines do some quite nasty stuff. The original engine (for the Golden Baton on the BBC Micro) relocates all code to &D00 - so messing up any NMIs and anything to do with discs.

Step One: Compress Incoming Data

The Scott Adams database format (will be referred to as 'SAGA' from now on). Is well documented and publicised, since it was documented in a 1980 issue of Byte magazine by Scott Adams. An interpreter, ScottFree, written by Alan Cox of Adventuresoft and Linux kernel fame; is available for modern machines. The default format of the data is as an ASCII file, including comments, which makes the files vary between 12 and 32 KB (depending on the game).

Obviously this is of no real use to us. So we need to compress it into a more BBC friendly size. The original drivers for the BBC compressed all integers into 16 bits. reducing the size to around 6 - 10 KB. That's still not enough!

So, the logical decision is to compress the files using a modern machine to be as small as possible without altering the data. Whilst we're at it, we may as well make some tunings to make the engine code size smaller.

The data file falls into several sections as detailed below:

Header

This consists of 13 16-bit numbers to refer to number of words, actions etc. The easy choice here is to reduced them all to 8-bit numbers. We can pretty much ensure that this is safe by checking the format files, where most things are restricted to 150.

There's one exception: the number of actions. These don't seem to have an upper limit. But, the largest number I've seen is for Seas of Blood, being 347. We can squeeze this number into 9-bits, and we have a header item (word length, which is usually between 3 and 5) which we can be sure will never use the top bit (word length). So we can munge the extra bit in there.

Some more amendments are needed though. We can drop number 0 and 12 as they're not used by the engine. But, to make things quicker on the engine we need to add a field: by default there is one number to cover both verbs and nouns, with the smaller list being padded out to match the larger list. This is wasteful, so I'm going to have separate byte counts for both verbs and nouns.

I'm also going to add some 16-bit numbers at the start of the header to give an easy to use offset for the start of each section, just to make things easier for the engine. I can technically work this out programatically at game initialisation, but for now I'm going to keep the table.

Actions

Actions in SAGA are a group of 8 16-bit numbers, these consist of:

• verb and noun
• 5 counts of condition
• 2 counts of actions

For some reason, verb/noun and the actions are in multiples of 150. So I'm going to change this multiple to 256 to make it easier for the engine. The conditions are in multiples of 20, again I'm going to change this to 256 to make it easier. Net gain in size = 0.

But, as there's a static number of conditions and actions, several of them end up unused. So we can remove empty conditions and actions and add a byte to list the number of conditions and actions in a nibble each. So the end result will be (in bytes):

• verb
• noun
• count of conditions<<4 + count of actions
• up to 5 of
  • condition
  • argument
• up to 4 of
  • action

This looks like it doesn't save us much space, but trying this over a range of games reduces the size of the actions segment to around 60%!

Verbs and Nouns

The SAGA format allows a collection of verbs and nouns of which must be up to wlen (as defined in the header). In practice wlen has always been 3, 4 or 5. In traditional engines, these have been stored as a list of words with verbs and nouns interleaved with a divider character between each word.

The two ways to save memory here are to make a separate count of verbs and nouns to remove excess padding and to remove the separator character, by setting bit 8 of the last character.

One other feature is that synonyms can be made by adding a * to the start of the synonym, for example:

LIGH *BURN *IGNI

Rather than waste a whole byte to indicate this. We can set bit 8 of the first character to indicate that this word is a synonym of the previous one.

Finally, to make life easier, I'm going to separate the lists so that verbs and nouns are stored in separate locations.

Rooms

Rooms are defined as 6 bytes to give the room pointers for each exit (in the order north, south, east, west, up and down) followed by a description string to give the room description.

There's not much we can do here to compress this data. One potential may be to allow the number of exits to be variable, but this needs further experimentation.

I am going to compress the text in the room description, this will be described later.

Messages

The messages section just contains a list of messages. This is going to be text compressed (qv).

Objects

Objects are listed as a string to defined the name of the object as seen in the game, which may have an optional noun attached; followed by a byte for starting location.

An example of an object with an attached noun is:

Jewelled Knife/KNIF/

We will try and squash these by:

• Compressing the text
• Separating out the noun and storing the value as a byte (listing the noun number), or a 0 if no noun
• Storing the room as a byte

Text Compression

Text compression was often used in text adventures to ensure maximum space. When trying to choose the best algorithm several things need to be taken into account:

• Size of text (as lots of text can give a much better dictionary for compression)
• Size of dictionary
• Complexity of encoding
• Complexity of text
• Complexity of decoding

If we look at other text adventures we can see a variety of schemes being used:

• Robico used Midge, which was a dictionary compression scheme, which worked well due to the large amount of text.
• The Quill used a dual byte token scheme, where two letters where replaced by a token
• Infocom uses ZSCII, essentially a 3:2 encoding scheme where 3 characters are mangled into 2 bytes.

I did some messing with dictionaries, 2 character tokens, 3 character tokens etc and came to the conclusion that the compression that is easiest to decode, encode and got the best compression ratio is, similar to the Quill, to replace common repeated characters with a single byte token. The problem with this scheme is that the maximum compression ratio is 2:1; and we don't get anywhere near that!

My table of different tests:

I decided that the best results across a selection of games came from unnormalised letters, i.e. I don't mess around with them first. The algorithm for encoding is simple:

• Go through all strings 2 letters at a time
• Enter letters into a dictionary and count the number of occurrences
• Sort the dictionary by largest counts
• Take the top 127 entries; this is our final dictionary
• Go through the strings again, this time by dictionary entries
• Replace any matched characters with the token from the dictionary with bit 8 set

This also makes the decoding algorithm easy:

• Go through the string
• If bit 8 is set insert token
• If bit 8 not set insert character

The other advantage is that the dictionary size is less than a page, so we can use an index register to find the tokens!

Finally we need to store the dictionary at the end of the file. As the dictionary entries are a known size, we can just place it as a stream with no separators.

14/11/2010: Coding Starts

With a bit of free time (child and wife having a nap), it's time to try and warm up skills that haven't been used for over 20 years. I'm writing the message decoding routine in 6502 assembler.

It amazes me how much you remember and how much you forget. Lots of messing around with both indexed and indirect registers; then further messing around with the BeebEm debugger (there are so many ways it ought to be improved) and finally I get a working version, which will take a message number in A% and will then print the decoded string.

Things learnt:

• INC is not the same as ADC (Zero flag, not Carry dammit)
• Lines in the BBC BASIC interpreter are tokenised (i.e. don't chose .PRINT as a label)

After a suggestion from Samwise, I decided to move the code I'd written to my PC and continue under the SWIFT IDE. This require a bit of further hacking, and to change the code so it writes the decoded message to a memory location (so I can easily changed the publishing code later).

I also added some basic init code to move and mess around with pointers. It's a small start, but a major one.

The only problem is that if we run it from BASIC I get strange line feeds, and sometimes repeated words of OSCLI. I'm not too worried about this as the final code won't be run from BASIC, but I'm curious as why there any output at all (is it my zero page locations)?

15/11/2010: More Coding

Not as much time for code, things like work get in the way!

I've decided to drop SWIFT as a development IDE; it's only really well integrated with Ophis, which is a tad too commodorey for my liking. Instead I've gone to BeebASM and notepad++. One of the advantages is that I can edit my code, reassemble it and then tab across to beebem and just test it.

I did a bit of a redesign, deciding to abstract output routines (in case I want to window them, or give them a half-size mode 5 font). I've also been writing search routines, so for important things I can just set A to the number and do a simple JSR.

To get an output, I hacked together the room outputting code. Whilst the description is relatively sorted, the exits were hacked just so I could have something to display - I'll need a better way to display system messages in future. in the screen shot I manually set A and called the routine, as my initalisation routine also does a mode 7; so this really wouldn't have made a good screen shot!

What the attached screen shot also shows is something I'd forgotten from the specification: rooms are normally preceded with a system message (either You are in a or I am in a), but they may also start with an "*", which tells the engine not to display the system message nor the "*". This resulted in a bit of code I'm not particularly proud of:

               lda workbuffer
               cmp #'*'
               beq skipone
               ldx #youare MOD 256
               ldy #youare DIV 256
               jsr printbuf
.skipone   ldx #workbuffer MOD 256
               ldy #workbuffer DIV 256
               lda workbuffer
               cmp #'*'
               bne printit
               inx
               bne printit
               iny
.printit      jsr printbuf

I'm sure that the second lda workbuffer:cmp #0 is superfluous, but I couldn't think of an easier route for the moment.

16/11/2010: Objects and Engine State

First up: I realised that the extra lda workbuffer above is superfluous (though not the cmp). I could have saved the flags register to stack, but I gain nothing by doing this.

This time I've been doing the code to manage objects. This is a bit more complicated than just searching through for present objects. As objects can be moved during the lifetime of the adventure they need to be stored in the save area, along with other data used by the engine (e.g. flags, counters, current room etc). So, I've reserved a page to keep this information in and set it up at gameinit. The routine's quite simple: blank out the main area, then copy object locations and information from the game header (player start room, light length).

The advantage of keeping this contiguous is that when I implement SAVE GAME and LOAD GAME, all I need to do is save and load to this page of memory!

Finally I added the code to print out present objects. As the text is in the standard tokenised format, this was easy enough (code reuse is really useful).

One potential problem that I'm seeing is the amount of 16 bit updates I'm doing. This is leading to a lot of code of the style:

{.objectloop   lda objectlocs,x
               cmp currentroom
               beq printobject
.nextobject inx
               cpx nitems
               bne objectloop
               jmp leave
.printobject stx xstore
               txa
               jsr findobject
               lda foundptr
               clc
               adc #2
               sta foundptr
               bcc prtobj
               inc foundptr+1
.prtobj      jsr copymessage
               ldx #workbuffer MOD 256
               ldy #workbuffer DIV 256
               jsr printbuf
               ldx xstore
               jmp nextobject
}

There must be an easier way to manage a 16-bit number than just doing inc loc(or adc); bne (or bcc); inc loc+1. I'm starting to wish I was doing this on a Z80 now!

A quick update ere the day ends. To test the exits code I added a very quick way of navigating around the adventure (i.e. a hack - I just read N, S, E, W, U, D from the keyboard and move in that direction).

19/11/2010: More Compression

Three days and I'm back to where I was on the 16th. Well, not quite, I've updated the compression routines which required quite a bit of a rewrite. There's also been a bit of tuning for handling messages.

First off, the compression. The ScottFree format of rooms is:

byte northexit
byte southexit
byte eastexit
byte westexit
byte upexit
byte downexit
string description

Which is generally wasteful as very few locations have all six cardinal directions open. The easiest way to compress this is a have an exit count, followed by only those exits that are open. Of course we need a way of the direction of each exit. It'd be great if we had enough spare bits to munge this into a single exit byte; but there are 6 directions (so 3 bits required) and the SAGA engine allows up to 150 rooms (8 bits), so this won't work. What we can have is an exit status byte (similar to that used by the Robico engine), which uses a bit for each direction, e.g. bit 0 = north, bit 1 = south etc. This gives us a count and the order of exits in one byte.

It does mean that we have to be a tad more complex on using the exits. Fortunately, RichTW came to my aid with the difficult bit of how to map a given exit (e.g. North) to its location.

The other compression step was on conditions, I fixed a bug in my compression code, which may have lost some conditions. Whilst doing this I notice a potential for another saving: the most common condition is 0 (push), which pushes a parameter onto a stack for the actions to use later. The parameters could be a counter (up to 8), a flag (up to 16) or a room or object (up to 150) and there are up to 20 conditions. As we only have 20 conditions, we have 3 spare bits that we can use. If we make a special condition where if the condition is 0 and the parameter is less that 127, we store this in a byte with bit 8 set. Most condition 0's I've seen are less than 127, so it will save us quite a few bytes.

One side effect of this is that it will be better to change the count of conditions/actions to be a count of bytes representing conditions/actions, so any find functions don't have to try to parse them. We also have 2 spare bits that we could use to compress other conditions similarly!

On to the big change: until now I'd been using zero terminated strings (I'm too used to C programming). The problem with this technique is that if you need to search for a message you have to touch every byte from the string start to the string end. If we change this slightly so each string is preceded by a count to the next bit of information, we have a net byte difference of 0, but our loops to locate a string are quicker and require less code! The only disadvantage to this is I had to roll back a change to the objects, which used the terminator byte to store information to make some minor shrinkages in object data. Below is the same code as used above, now simplified:

.objectloop    lda objectlocs,x
                   cmp astore
                   beq printobject
.nextobject   inx
                   cpx nitems
                   bne objectloop
                   jmp leave
.printobject   stx xstore
                   txa
                   jsr findobject
.prtobj          jsr copymessage
                   ldx #workbuffer MOD 256
                   ldy #workbuffer DIV 256
                   jsr printbuf
                   ldx xstore
                   jmp nextobject

Finally, I've moved the system messages to a table at the end of the code. As the messages change for different games, this makes it easier to allow template loads. To save code I made a second entry point in my currently existing findmessage routine, so it could just use that!

22/11/2010: Parsing Input

Had a weekend too busy to put any real effort in, but I did the parsing routine. This was one of the routines I was dreading as I had to think around a couple of loops with at least 3 different counters (one for offsets in the input, one for offset within the table and a counter for the real word - so as to match synonyms). But, it's done now, it could do with some clean up, but it's in, it works, it handles erroneous messages (with errors) and handles multiple spaces.

The next task is a large one: starting work on conditions and actions - the meat of the interpreter! As there's multiple condition and action codes, I think the best way will to have a table set up so the I can jmp (addr). I just need to make sure I get the stack right for the rts, as there's no indirect jsr instruction.

At the moment I think I'm going to have something similar to:

                         jsr handlecondition ; set up rts return in the stack
                         .... ; handle next instruction
.handlecondition  lda conditionaddrl,x
                         sta bufptr                        
                         lda conditionaddrh,x
                         sta bufptr+1
                         jmp (bufptr)
...
.conditionaddrl equb cond0L,cond1L ...
.conditionaddrh equb cond0H,cond1H ...

I'll also need to implement a random number generator for 0 (AUTO) conditions.

26/11/2010: Conditions

Just a quick update as I haven't had much time to work on it at the moment. I've set up the conditions routine (all except for the flags, as I'm lazy). Initially this was set up so each conditions jmp'd to either condfailed or condsuccess. To minimise the size of code I'd set up a couple of branches in the middle of the condition code, so each return would only be 2 bytes as opposed to 3. The reason why the branches were in the middle was due to the branch limit of 127 bytes either way.

The resultant code came out to &F6 bytes - so close to the page limit that a branch can cover! Some code reduction tuning was required. First off, the values to the registers were altered to match most conditions better (i.e. parameter in X and condition code in A; leaving Y reserved). This reduced the size of the code to &E3 bytes.

I can reduce it even more, by using RTS instead of a branch - but I need to think how this can be handled properly. There's also a possibility that I can munge several condtions together (most are very similar in code, e.g. "item present" and "item not present"). Again these need more thought.

The code to handle message responses was also added. The screenshot above is a mocked up one where I added only the code to move an object to the responses code.

So in theory I only have to write the responses handling code now and we should be able to play through the adventure from start to finish. For convenience I need to fix a few bugs in the parsing code (single verbs don't work properly and we sometimes loose the noun if it's unknown) and add the known shortcuts (N, S, E, W, U, D, I). Then there's the graphics code.

Update I've cleaned up the code now; the code for the conditions stands at &B5 bytes - thats a saving of 65 bytes! How did I do this, following on from the above tunings I also:

• Changed A to contain the location of the object parameter (this is the most common use of parameter), so I could set it before I made the jump.
• Changed to use an RTS in 60% of cases with a single return point.

The code to do the calling is:

                   lda objectlocs,x         ; as a shortcut
                   jmp setcondret          ; set up stack properly
.jumptable    jmp (bufptr)
.setcondret    jsr jumptable
.condret        beq condloop            ; condition succeeded
                   lda #0
                   sta exitnum              ; otherwise leave

So we use the zero flag to hold the status of the test - if it is set, then the test was successful. The problem here is I had to use a couple of branches for testing the "not" conditions (there maybe a better way, but it's late and I can't think). The branches just set A to 0 or 1, which'll set the zero flag for me:

.failit           lda #1
                  rts
.succeed      lda #0
                  rts

I still need to write the flag code, this may take it back up to a full page :-(

01/12/2010: Responses

It's been a while since I've updated; having been busy on other things. Anyway, I've implemented most of the responses and have been playing through The Golden Baton to try and find bugs.

There's still stuff to be done, but I guess I've implemented about 90% of the interpreter and it plays through most of The Golden Baton, my bug list looks something like:

• GET ROPE (when hanging) requires repeating (continued)
• No "Don't understand if nothing actioned"
• LOOK over-ride
• Unimplemented:
  • continue
  • put item
  • print counter
  • swaploc1
  • sel counter
  • refill lamp
  • light and dark flags
  • light lifetime
  • quit
  • load
• Tune and clean up source

In terms of file sizes, my code stands at &B03 bytes, which include the system messages, which I'm playing to load externally. This added to the size of the compressed game file for TGB (&11E8) is &1CEB. Comparing this against the original size that was released (&3148) and I've reduced the size to about 55%.

But, there's always a sting in the tail: my dreams of getting some games to work with MODE 0/1/2 is turning out to be a pipedream. With PAGE at &1900, this means that the code plus the game will go up to &35EB, which is quite scary as TGB is one of the smallest games. I have some space below &E00 that I can use (pages 4, 7, 8, 9, A, B - I've already allocated 5, 6 and C) and I could potentially lower PAGE to &1400 if I'm careful about the use of disc, but this has to cover the code I haven't yet written (including graphics code) and only for small games.

So it's time to make the design decision: I'm going to go for mode 4 or 5 for graphics. I could possible make an exception if I'm know the game is running on a Master/B+/E00 DFS which would give me an extra 10 pages; or, if I was running from ROM. More to think about!

I should be happy though - I've implemented a SAGA interpreted in a tad under 3K in a machine code that I haven't used for 20 years, and even then I only used it to write cheats for games!

Lessons over the past few days:

• Check out your zero page allocations carefully; I nearly came to a halt as I was trying to squeeze too much into 10 bytes of zero page, when I actually over half of it unused!
• Set up your OSFILE/OSWORD blocks in advance instead of creating them on the fly - it takes up a lot less memory.
• Don't set up your wireless encryption key with lots of swearing in it as it'll be embarrassing when your better half asks for it!

05/12/2010: Play through!

Unfortunately a lack of time left me little chance to work on the engine so I've only have a few minor additions. What I have done is to add support for:

• Light and dark rooms
• Continued actions
• Fixing several bugs, including a nasty one where flag 8 wouldn't set

The light and dark routines I was dreading as I wasn't 100% certain of how they would work, from examine of ScottFree and the games themselves, then the logic for saying whether a room is dark is:

• If the dark flag (flag 15) is set
• If object 9 (lit lamp) is not in the room
• If object 9 (lit lamp) is not in the inventory
• Light length is not 0

Fortunately as I'd written all the condition codes as miniature functions, so all the final code is:

.isdark
{
               ldx #15           ; dark bit
               jsr flagset
               bne quit
               ; now check for a light
               ldx #9            ; object 9 - lit lamp
               lda objectlocs,x
               jsr itemcarriedroom
               ; swap over z flags states
               bne setzero
               ; Check whether it has fuel
               lda lighttime
               beq quit
.setzero    lda #0               
.quit         rts
}

The darkness status is checked at several places:

• When the room details are displayed
• If a move is made
• If an object is got

For most of these it will print a "Too dark to see message", the only difference is when a move is made, then if the move is successful the move will be made and a message printed "Dangerous to move in the dark!", if the move fails, then the message "I fell down and broke my neck" is displayed and the player is killed. This boils down to a simple jsr isdark and a beq to print the message if necessary.

The end result is that I have managed to play through The Golden Baton from start to finish successfully. Of course I haven't checked whether every condition has worked and I need to spend time on edge conditions (oh fun, oh joy).

My current bug list stands at:

• No "Don't understand if nothing actioned"
• LOOK over-ride
• Code needs tuning and reducing
• Unimplemented:
  • put item
  • print counter
  • swaploc1
  • sel counter
  • quit
  • load
  • Fighting Fantasy combat mode

Most of these only affect specific games (The Sorcerer of Claymorgue Castle and Seas of Blood) or are relatively easy. So I think I can put the interpreter on one side for a bit and attempt to do some graphics work!

For those interested, the code size now stands at &B8E bytes, of these &95b is actual code; the other bytes are the system messages and the OSWORD/OSFILE definition templates.

05/12/2010: A Quick Mock-up

I started messing with translating the original Mysterious Adventures graphics across to the BBC. This is relatively simple, the format has already been described by me at Adventure International Memorial. It is basically a selection of moves, draws and flood fills. This is almost trivial to implement on a Master (as there's a built in flood fill in MOS). There may be a tad more fun on the BBC.

Normally to convert from the Spectrum graphics to the BBC plot co-ordinates we'd multiply the co-ordinates by 4, which'd fill half the screen with the graphic. I wondered whether it'd be easier to multiply by 2 and have a smaller image and use this as a header. The image attached is a mockup, written in BASIC which plots the first screen, then uses text windows to place the text in appropriate places to maximise use of the screen. The screen is mode 1 and the BASIC program will only work on the Master (due to the aforementioned flood fill), but I thought it'd show how much better we can be than the other computers!

12/12/2010: Tidying up

Unfortunately I didn't have as much time over the weekend as I'd wanted. I'd wanted to rewrite the system message code to allow insertable parameters, using the spare ASCII codes 1 - 31 but after some basic testing I had to go back to rethink what I was doing. The plan is to allow the message to control the semantics of the content, rather than the positioning, so the output code can then place it, or colour it appropriately to its meaning. I will need some codes to include contents from the game, e.g. current noun, current verb, counter state etc. Also I'll need some to mark an object, room description etc.

What I did manage to do was to do some code reduction and clean up the start and end code. The code reduction has mainly being about code reuse and altering loops so that they count down, which usually saves 2 bytes.

One advantage of code reuse has been in my osfile call for save and load, even though the procedure only does:

ldx #osfileblock MOD 256
ldy #osfileblock DIV 256
jmp osfile

This saves me one byte for the two places it's called; but, I found out on testing that OSFILE uses the block as working area, meaning I ought to form it properly each time, which means more bytes saved on creating the block.

Anyway, new code has been to handle LOADs (I'd already implemented SAVEs) and QUITs and to make sure it exits semi-gracefully on a QUIT or end of game - this is done by simply saving the stack pointer at engineinit and then retrieving it at the end!

17/12/2010: More additions and code reduction

This covers the past few days where I've being doing dribs and drabs when I have had time. First off, some new stuff. I added a pseudo-random number generator as just grabbing a value from &FE44 didn't turn out to be random (interestingly enough Brian Howarth's code just gets the low byte of the system clock for this). I also added the print counter routine, one vital step on getting SCORE working properly.

The other area of work was code reduction, which I saved some notes on byte reductions. The first step was turning JSR xyz:RTS into JMP xyz; this saved about 5 bytes. Next I added a couple of functions to perform 16-bit addition to the most commonly used pointers. Some moving pointers around so I could could use common code also saved some bytes. Finally I found a whole chunk of code that I had duplicated, so this went.

The final savings were around 56 bytes, with details shown below:

Because I'm using two pointers (bufptr and foundptr) I have a duplication of code which I should probably try and remove:

.skipstringbp
{
               ldy #0
               lda (bufptr),y
               jmp addtobufptr
}

; simple routine to add A to bufptr and save a few bytes
.addtobufptr
{
               clc
               adc bufptr
               sta bufptr
               bcc nooverflow
               inc bufptr+1
.nooverflow    rts
}

This could save another 17 bytes; I need to think it out better though...