Game versions, file systems, and the next step

The first day of the coding period starts tomorrow, so it’s time for an update!

There are two important things to go over since the last post. The first is about the version of the game being used, and the second is following up from that.

Game Version

My original assumption with the project was that I would be continuing the partial engine that JoeFish had been working on, using the IBM version of the game. However, after a better examination of the source code and discussion with my mentor, I am instead working on an engine for the Apple IIGS version of the game, and using the JoeFish code as reference where it is relevant. The reasons for this decision are twofold. First, the JoeFish code is largely already refactored compared to the source assembly, and I would instead prefer to start from a more direct port of the source, before refactoring it once it is functional. The second factor is the source code itself. The Apple IIGS version is written in 65816 assembly, which is the architecture that I am most comfortable with already (it is the same processor architecture used in the Super Nintendo, so I am used to reading and writing assembly for it). When looking through the source code of each version, it stood out as the one that I could get a handle on most quickly.
In terms of game version differences, The Immortal is an interesting case. There are many differences between every version of the game (with the NES version being distinct even in the screen rendering itself), but the largest mechanical difference has to be the combat system. The original version of the game on the Apple IIGS uses a top down combat system which takes place on the same game screen as the rest of the gameplay. However, this was not the case for many other versions, such as the IBM DOS, the NES, or the Genesis, as they used a separate combat screen with large sprites of the wizard and goblin. It raises an interesting question for the unified engine, that being how much of the combat system is shared between the two implementations, and whether it might be possible to make overhead combat an option in other versions. This is not relevant for now, but examining the different versions brings up many questions about how the unified engine should handle them in the long term.

The ProDos File System

The first challenge in working on the Apple IIGS version of the game is the file type itself. The game primarily exists as disk image files (boot.dsk and graphics.dsk) like many other Apple II games, but unlike any already supported by ScummVM, The Immortal uses the ProDos file system. This was a later revision of the Apple DOS file system, and came with many fundamental changes. The Apple IIGS, using the much more powerful 16bit 65816 chip as compared to the 8bit 6502 on the Apple II, demanded a more powerful file system (there were many other reasons to move away from DOS3.3 as well), and what we got was ProDos. However, the file structure of ProDos is somewhat complex in comparison. It could support very large file sizes, and the file system was abstracted away from the physical tracks and sectors in DOS3.3, but it did come with extra complexity and slower read speed. The important thing about this, is that with the file format not having a backend implementation in ScummVM, I will need to make my own for the engine to be able to extract and work with the data files of the game.
After spending some time reading about the file system and looking at the raw byte data of the disks, I have written code to follow the file structure and list files from directories.

However, in the interest of ensuring the source code retain its own structure with regard to data loading, the next step is to implement a virtualization of the file system in the engine. This would allow  a call to ProDos (a program on the apple IIGS could retrieve data from the disk with a JSR to a special address in memory, followed by the command it wants ProDos to perform, and the arguments for that command) to be translated to a call to the ProDos file system object instead, retaining the structure of the call in the engine. This is taking some time to implement, so the result will be in the next blogpost. Another benefit to mention about this virtual file system, is that it can eventually be converted into an implementation of the Common::Archive system in ScummVM, allowing engines for other games that use ProDos to avoid implementing their own ProDos handling code. This makes sense as the ProDos interface code is already distinct from the game source code, so instead of having multiple implementations of loading game data for different game engines, the different game engines can retain more of their source structure.

Okay, now that we know why we’re working on ProDos, I should explain how the file structure actually works.
It looks complicated when interpreting any individual bit of data from the disk, but the structure is actually pretty straightforward.

As mentioned earlier, ProDos abstracts away from the physics tracks and sectors of disks, with the device driver itself translating between ProDos commands and where the data is physically located. Instead, a ProDos disk is divided into a series of Blocks, containing 512 bytes each. The first two blocks are always the ‘Loader’ program, which gets run immediately and allows programs to interface with the disk. After that, the rest of the disk is made up of a few things:

  • Directories
  • The Volume Bitmap
  • File data

The Directories are comprised of a Header, and a list of File Entries. The Header contains various bits of information required to traverse the file system, such as a pointer to which block contains the remaining entries in the directory if there is not enough room in the current block. Since each block only has 512 bytes of data, and the blocks are in functionally random positions within the disk, there need to be pointers that link relevant blocks together. The Volume Bitmap is a sequence of bits that represent how space in blocks is used or unused in the disk, and is located after the directory blocks, but before the file data. One other thing to note is the term KeyBlock which just refers to the first block of any directory, if the directory requires more than one block.

A ProDos disk can be described in terms of blocks (any given directory can take more than one block, but for the purpose of this post I will assume only one) like this:

Block 0: Loader 1
Block 1: Loader2
Block 2: Volume Directory (the main directory)
Block 3: Subdirectory
Block 4: Volume Bitmap
Block 5+: File Data

The header and general file system traversal is fairly straightforward, but there is one big complication to note about this. Files can be very small, or very large, and the file system has to have a way to handle this in terms of small, 512 byte blocks. The way it does this is pretty interesting, and although I will go into further detail in the next post when the virtual file system is implemented, for now I will just mention the basics.

Files in ProDos can be classified as either inactive (deleted etc.), some type of tree file, or a subdirectory file. The subdirectory file of course just directs you to the subdirectory keyblock, and an inactive file is self explanatory. The tree file is what regular files are stored as, and in a nutshell it defines the size of the file.
ProDos would ideally like to have files always be small enough to fit in single blocks, as you would expect. But if a file gets too big for a single block, it needs a way to link multiple blocks together to save and load that file. To do this, it defines them as a seed, a sapling, or a tree. These definitions are functional, as a seed only needs a directory entry pointing to the data block in the disk. Whereas a sapling (bigger than one block, but not bigger than 256 blocks) requires another step (it has to ‘grow’ from a seed to sapling as the data size grows). In that case ProDos will dedicate a new block as an index for up to 256 data blocks, and the directory entry will then link to the index block instead of the data block, which is used to find and link all the data blocks across the disk. Lastly, a tree file is for the biggest files, and adds another step, linking together the index files of a sapling with a Master Index block, allowing for massive files of non-contiguous blocks of data. This makes virtualizing the file system somewhat complicated, but it is also a pretty neat way to handle files.

The Next Step

Alright, to close out this post I will briefly mention the next steps. The coding period begins tomorrow and the first step will be to ensure the virtual file system is usable, and get all the data from the disk organized and extracted by the engine. If there is time, hopefully I can implement the compression/decompression functions and maybe even get an image from the graphics data.
I have been revising my week by week plan to fit the new game version, and will continue to do so as I get a better idea of how the new engine will progress.

Okay, thanks for reading if you made it this far, I’ll have another update next week!



Leave a comment

Your email address will not be published. Required fields are marked *