Adjusting my point of reference, and all becomes clear.

I have been scratching my head over the logic implemented in the routines that calculate object intersection for some time now, and it is the reason they remained unnamed until now, despite the fact that I knew their purpose. I had assumed all along, for no good reason and without giving it further thought, that an object's (x,y) position in 3D space was defined by the location of the corner closest to the origin, and the width and depth were the dimensions along the X and Y axis respectively. It occurred to me today however (whilst not even at the computer), that the position could instead be the center of the object, with the width and depth being the X and Y radii respectively. Looking at the aforementioned routines in a new light, the logic became obvious. Doh!

All variables and bit fields (flags) have been decoded and documented. All routines (with the exception of Z-ordering) have been documented. I now have stubs for all of the audio routines in the C port, but have not implemented any audio logic as of yet. IOW the entire program, again with the exception of Z-ordering, has now been reverse-engineered!

I do know of one bug in my C port that causes special objects to re-appear after you've picked them up whenever you re-enter the room. I'm hoping that's the same bug that I saw last week when picking up a special object that caused Sabreman to fall through the floor indefinitely!?!

Next task though is to reverse-engineer the Z-order algorithm and port it to C. I suspect the maths will be quite simple, it'll be the recursion that will be trickier to unravel and port to C.

Speaking of which, the code lends itself to a C implementation remarkably well. In fact there are only two (2) cases when stacks are adjusted and JP is used to jump to code elsewhere - exiting a screen and ending the game. As it stands I've used setjmp/longjmp in an attempt to preserve the implementation, but I have 2 issues with this. Whilst the exit screen case works fine, for some reason I can't fathom the end game case crashes. But more significantly, some development platforms (eg. Neo Geo) don't actually have implementations of setjmp/longjmp. So I'll need to find a work-around soon.

MUST. IGNORE. TRS-80. GRAFYX. SOLUTION. PORT...

Only a few 'bits' remain unknown

Not surprisingly, given the time of year I haven't had much time in the last week or so to work on this project.

That said, I've managed to make a little headway. I've been focused on getting the remainder of the unknown variables (bit flags) decoded and am happy to say that only a handful of bits from a single byte in the object table remains.

The object table contains 3 bytes of flags/counters; the first mostly defined in hard-coded object data and partially documented on the Icemark Knight Lore Data Format site. The 2nd I've now fully decoded, and comprises a counter in the top nibble and flags in the bottom nibble. The 3rd I've partially decoded, but the byte itself is used for different purposes for each of the objects. For some objects it's a counter, others it denotes direction, and others again different bits for different flags. At last count I still have at least 7 uses of flags to decode. I do have clues for 3 of those (all related), which incidentally appear to be consistent for all objects. So that leaves around 4.

For those of you wondering how I have reverse-engineered (and ported) pretty much the entire code base, yet don't understand the purpose of a handful of flags - in most instances the flags are tested and routines simply conditionally exited prematurely, sometimes on the basis of multiple criteria. So it's not always clear what individual flags mean, until you've examined all uses of a flag together. And in some cases, I just haven't gotten around to doing exactly that just yet.

I know of one bug in my C port that occurs in some cases when you pick up a special item, though it is admittedly difficult to play the trickier screens without proper Z-order. For this reason, and the relative lack of bugs, I've concluded that once all bit flags are decoded, there's no escaping attacking the Z-order algorithm. Only then will I be able to properly play-test the game.

It may surprise some of you that I'd never- and I mean never - played the game when I started this port. In fact, even now I've played this far longer on my C port than on any ZX Spectrum emulator. I was so impressed by the praise this game received in Retro Gamer magazines, the screenshots I saw in the same, and the YouTube video I watched briefly, that I didn't need to play the game. In fact, I actually didn't want to; I wanted to experience it for the first time on my own port. It will certainly be the case for the first game I finally play all the way through and win.

Anyway, time will continue to be fleeting in the short term and so I'll hack away at the remainder of the flags and then when the silly season winds down I'll tackle the Z-order algorithm, then hopefully spend most of my time playing the game in order to eliminate the last niggly bugs from my port.

That might be a few weeks off yet as I'll be heading up the coast for a week in the new year and have resolved to leave the laptop at home, the idea being to spend my time after the kids are in bed watching the cricket, reading books on my tablet and if I absolutely must, conversing with my wife. ;)

And I've been thinking about prospective ports again, and the TRS-80 Model 4 is always in the back of my mind. I only just realised in the last day or so that, aside from keyboard input which is trivial, I really only need to re-code two rather straightforward routines to get it running on the Model 4. This is because all rendering is done on a screen buffer in normal memory, with just two blit routines that transfer it to the actual screen. Now I'm sure it'll run into bandwidth issues on the TRS-80's Grafyx Solution hires board, and it may perhaps not been particularly playable because of the slow-down, but at least it'll run and it will look damn impressive - unquestionably worth the exercise given the relatively trivial effort required. It'll probably be my first port after the PC since I've effectively got fully relocatable Z80 source code now.

All over bar the Z-ordering

By my reckoning, the C port is complete except for a single routine - the Z-ordering algorithm.

Although the exact purpose of a handful of routines and flags are still unknown, I do understand the gist of them (i.e. what they are trying to achieve) and it is of course still possible to complete the (rest of the) port; which is exactly what I've done. Naturally a few more mysteries were uncovered during the process. As it stands, all bytes in the graphic object structure are known (interestingly 4 of them are unused, and another 4 have dual-purpose), although some bit flags are still to be decoded. All but five (5) global variables are known, and having a quick look at those just now it looks like they've simply escaped my attention, rather than being difficult to deduce.

UPDATE: All global variables have been named

So the game is playable in the sense that you can move around, interact with objects, move from screen to screen, drop/pickup special objects and be killed. There were, however, one or more bugs introduced when I added the object interaction routines that have affected the object movements; guards spin on their heels, balls don't bounce, gates don't move up/down. Whilst not easy to find in 4,200 lines of code, they'll likely be simple typo's.

UPDATE: The bug that prevents objects from moving correctly has been fixed. The game is pretty much playable now, with perhaps a couple of minor bugs that occur infrequently.

[Oh, there's no audio yet either. There's a surprising number of audio routines, some of which have quite a lot of code in them to produce what appear to be semi-random sounds.]

I'm going to stick to the plan of completing the game (fixing the bugs) before tackling the Z-order code. Having done some analysis of the Z-order routine, it doesn't appear to have any effect outside rendering, so it should be possible to have a fully playable game without it. I'll endeavour to decode the last remaining bit flags during the process.

It's exciting to be so close to having a fully-commented disassembly and a fully functional direct C port of the game. It's been a lot of work, but the subsequent porting to 16-bit platforms should be almost trivial in comparison. The Amiga will probably be the best candidate, although I'm still very keen to attempt a Neo Geo port, if only for the challenge! I don't dare think of the work involved in a 6809 port at this point...

I'm hoping my next post will be to announce a fully-functional game, sans Z-ordering.

Man or beast?

A week since my last post and I'm happy to say that I've made very good progress in that time. So much so, that you can control Sabreman turning, walking and jumping; he looks around randomly and at midnight he transforms into Sabre Wulf.

I was hoping to be able to post a short video of  Sabreman walking around, and perhaps other objects moving as well, but trying to find any sort of free video screen/window recording software without the risk of installing all manner of malware on your machine is simply too great. So until I get a recommendation from a trusted source, a few still frames will have to suffice.

Sabreman looking around

At night time you transform into Sabre Wulf

In fact, the game isn't that far off being playable - the sun and moon move across the frame and the days tick over - and there's not a huge amount of code left to reverse-engineer or port to C. I've gone about as far as I can now without tackling at least one of the two most technical aspects of the program - object interaction - which is little more than 3D collision-detection.

So late last night with only about 30 mins free I decided on a small fun diversion and instead worked on getting a raw dump of the loader screen displayed properly on my port. I'm yet to actually see how the screen is rendered during loading from tape, but I'm thinking of ultimately emulating that on my port, which will be a challenge on the Neo Geo.

Displayed from a raw dump of Spectrum video and attribute memory

The object interaction is required to move from screen to screen, where the object handler routine for the arches plays a key role. Once the generic interaction routine is done, the other objects shouldn't pass through one-another and aside from aesthetics, the game should be all-but-done. I'm even feeling less daunted by the Z-order rendering algorithm now.

Definitely getting to the business end of the whole process now!

ADDENDUM: I should add that the bug I thought I'd found was not, in fact, a bug.

It's interesting the obscure - but extremely helpful - stuff you find when you search the internet hard enough. I think I found a bug in the wipe routine tonight, so I went searching for reports of graphics glitches in the game; I haven't found any (yet) but did come across this blog entry right here on blogspot.com.au! Talk about perfect timing! ;)

That aside, I'm really down to the nuts and bolts of the code now. In fact, most of the rendering of all objects, both static and dynamic, is complete, excepting for sprites concerned with the player (of which there are quite a few) and interactions between objects. So it's time to roll up my sleeves and properly analyse the routines I've - temporarily - stashed in the too hard basket.

Actually the routine to wipe the old sprite was a bit of a diversion; I've been working on completing the high level game loop code (finished) and am about to turn my attention to having the keyboard inputs actually control the player. That will allow me to test all the player-related sprite handler routines before diving into the object interactions.

So if you smell something burning...

Cross-platform ports

I've been cranking the handle and have finished at least templates for each of the sprite update/handler routines. About half of them are completely implemented, so each room is now lively animated with moving blocks, balls, ghosts etc. The core engine is now 2,500 lines of C code.

Needing a break from translating Z80 assembler into C, and inspired by a query from a friend as to why I was using Allegro rather than SDL, I decided to take a step back and re-architect the code for cross-platform building as I did for Lode Runner.

As for Allegro vs SDL, it is simply a case of what I know. Allegro is simple to use but has some annoying kinks, so I was up for trying something new. After poring over tutorials and the API reference for at least 10 minutes, I had the Knight Lore menu screen rendering in a window! Unfortunately I then spent the next few hours trying to get keyboard input working, and have still yet to do so. Whilst I currently have both Allegro and SDL projects, the jury is out on SDL atm.

PC platform library issues aside, I now have template projects that build - and run - on Amiga, Sega Genesis and Neo Geo targets. The core code runs, but there's no graphical output yet. The Amiga and Sega Genesis projects at least display some text to show it's running. I should stress that this does not necessarily mean that I will be completing ports for all of these platforms. The Amiga is probable, I'd certainly like to do the Neo Geo if I can overcome a technical issue, but the Sega Genesis is probably unlikely.

With that out of the way, I should resist further work on the Amiga and/or Neo Geo ports and return to the C core implementation itself. There are probably a few more sprites that I can knock over quickly - such as the guards - but then I'll have to have a full implementation of the game loop and all its subtleties before going any further, as a lot of the remaining handler routines rely on that framework to be in place.

During this process I've had more of an insight into the mechanics of the code and I must admit it's not bad at all. For example, some of the game's state is implicit in the sprite number of particular objects, and the entire game logic is implemented within the object handler routines.

So from here-on in, the game will soon become playable. The player's character already appears at the start of the game from a cloud of sparkles, he just can't move yet.

UPDATE: One of the guard types and the wizard are fully animated and walk around the room now!
 

Don't believe everything you see!

Whilst things are progressing, it hasn't perhaps been as quickly as I'd like because I've been chasing down a couple of 'bugs' in my C implementation. I won't bore you with too many details, but I was testing the animation of the moving blocks when I came across room #29.

Whilst I hadn't noticed any issues with the room rendering prior to this, room #29 was obviously completely wrong...

This can't be right!?!

Spectrum Original

After spending a few hours chasing down this issue, including painstakingly comparing the graphics object table between the original (memory dump in MESS) and my C code, I couldn't see any differences at all.  And then it hit me...

Because I haven't implemented the Z-order logic yet, the rendering of objects is done in arbitrary order (more correctly, the order in which they are defined in the location table). Of course I realised this - what I didn't realise though, is that it could create the type of optical illusion you see above! If you follow the outline of the block structure with your eyes, it is actually correct.

Lesson learned, I'm continuing to work my way through the object handler routines. In fact, player, guards and wizard aside, I've finished most of the simpler objects. What I haven't done, though, is the low-level object collision/interaction routine, so atm (movable) objects fall through other objects to the floor, and pass through them when moving around. But they do move in the manner intended and are confined by the physical boundaries of the room.

Fun fact #34: spiked balls don't drop immediately in rooms with odd-numbered location ID!

There was movement at the station...

I've made some pretty decent progress today at lunchtime and this evening, deducing the purpose of no less than three more bytes in the object table, identifying another two as flags (leaving just 6!) - and the purpose of 3 of those bits - and a handful of global variables.

I thought I'd choose an object with the simplest movement - the portcullis that moves only up and down (i.e. along the Z axis) - and try to reverse engineer the handler for that object. It was quite successful, so much so that I now have a fully animated portcullis! Not unexpectedly this involved some generic low-level movement routines which are used by all the moving objects, such as bounds checking on the object which, of course, are also now implemented in C.

I guess I'll stick with the objects with the simplest movement logic, and work my way through to more complex object behaviour. Somewhere along the line the rest of the object table bytes should fall into place. Note that there is quite a lot of code to get through, and the next update of any significance may be a while away yet.

No more candy, back to meat and potatoes.

I've got all the static objects rendered in their correct locations now; the only objects remaining are those relating to the player and/or are dynamically generated and/or move. Because I can't really test any of those though, I'll leave them until I have implemented the code to allow me to do so. In summary, most of the objects are rendered and it's time to proceed to the next stage.

The choice I have now is to either analyse in minute detail and then implement the sprite priority (Z order) code, or continue with reverse-engineering the rest of the code.

I've chosen to go with the latter - I'm on a roll and I don't want to risk getting bogged down in the detail of one particular routine which is, ultimately, purely cosmetic (albeit important). I figure I can tackle that right at the end whilst I can see the light at the end of the tunnel.

The key data structure in the game is an array of objects that is constructed before you enter each room (screen), and contains an entry for each sprite including the player, special objects, and foreground & background objects. Each entry is 32 bytes and contains not only 3D location & 2D rendering information, but also state information for objects for example, that move.

Last night I deduced the purpose of another two of those 32 bytes, now leaving 11 (plus a few flag bits) still remaining unknown. And whilst trying to get to sleep shortly after it occurred to me what one of the unknown flags could be - but I'm yet to test that theory.

Besides those 11 bytes, there's around 30 other 'global' variables whose purpose also remains unknown. A few of those are simple flags accessed in only a few places in the code (which shouldn't be difficult to deduce) and at least a few others are temporary storage for the recursive Z order routine. Most of the game state is stored in the aforementioned object table.

EDIT: In one fell swoop I've confirmed my theory about the flag and also crossed another three global variables off the list!

And finally, it's clear that the sprite adjustment routines are actually the object handler/update routines (and to give you an idea of the work involved, whilst there are 188 sprites defined, there are 'only' 50 distinct handler routines), so I've got a bit of renaming to do in the disassembly and my C code. I am confident now though that I have full understanding of all the code and data structures and there should be no surprises from hereon-in; the puzzle is starting to come together.

I've got a fair bit of code to implement now as I need to flesh out the main loops and the routines I've already reverse-engineered but haven't yet bothered to port to C (as they don't play an important part in the rendering) and then start to implement the bulk of the handler routines as I reverse engineer them. There's a bit of code re-use so the C port might get a little messy at the lower levels and it won't be easy to keep track of what has and hasn't been fully implemented.

The next bit of eye candy probably won't be for a while, though it'll likely be a video.

What a difference a line makes!

I realised this morning that adding masking should be trivial - and it was basically a single line.

So here's the difference:

No masking

With masking

Note that the Z-order (sprite priority) has still not been implemented, hence the issue with the arch on the right hand side of the screen. But you can now clearly see the gargoyles sitting on the blocks.

Unmasked

I've worked my way through all the rooms now, adding the sprite adjustment routines for each of the foreground and background objects and implementing within each the logic that is strictly concerned with the sprite adjustment. As a result, the initial state of all rooms are now rendered 'correctly'; at least as far as pixel placement is concerned. What remains are a handful of adjustment routines for the player and the special objects that need to be collected and placed in the cauldron.

I suspect the 'sprite adjustment' routines are actually responsible for handling all the object interactions, so when I confirm that I'll update my nomenclature accordingly.

In the mean time, once I have finished the remaining sprite adjustments I'll implement the sprite masking, which I've thus far ignored. That will produce more pleasing results but the sprite priority (Z order) is still yet to be done.

No sprite masking as yet

You can see in the rendering above that the gargoyles sitting on the blocks are 'lost' in the blocks and the bricks on the walls, as is the arch on the western (front, right) wall. They're actually rendered last in the scene, but without the masking, which produces a black outline, they blend into the objects behind them.

From there I face another choice on how to proceed, but I'll discuss that next post.

I've also been thinking about potential target platforms for a port. The C code will allow me to port to the Amiga at least (I should also take the opportunity to do an Atari ST port while I'm at it), and the Neo Geo (hopefully) with some effort. The Sega Genesis will be more difficult than I first thought, and perhaps not even viable, as it will require use of the rather bandwidth-limited pseudo-bitmap graphics mode. I'll produce a PC port of course but I doubt anyone will be interested enough to look at it. Maybe a mobile platform will be a possibility?

As for assembler ports, the Coco3 was always the original target. But I've also been considering the TRS-80 (Grafyx Solution) - the results won't be stellar without double-buffering but perhaps still impressive enough to warrant a play through? Any other Z80-based bitmapped systems I've neglected?

Foreground objects

Another quick session, added and debugged logic to render the foreground objects.

Room ID=46

Like the background objects, there's plenty of per-sprite code to wade through, including what I believe is code to move the objects around. So basically, the bulk of the program. After rendering's done, there's very little code left to reverse-engineer!

In my PC port, I can move from room to room by simply pressing N, S, E or W keys.

From here-on in there's a lot of handle-cranking...