Monday, February 12, 2018

How many did I say? Sorry, I meant half that.

As I begin development of the yet unnamed hack, my first order of business is to free up as much space on the ROM as possible. We saw before how the Mega Drive has a 32 megabit, or 4 MB ROM address space, and when Sonic 3 is locked on to Sonic & Knuckles, they take up the entirety of this space.

However, as I also mentioned, the public disassembly contains a special build flag, the Sonic3_Complete flag, which according to the disassembly's README file...
[...] will change the assembly process, incorporating all necessary Sonic 3 data split from the original rom to create a complete Sonic 3 and Knuckles rom without filler.
Indeed, setting this flag causes all Sonic 3 data that isn't referenced by Sonic & Knuckles to be trimmed off, producing a lean, 3.23 MB ROM. Can we get it even smaller, though?

As an initial approach, I tried repacking all of the compressed assets in the game using flamewing's optimized suite of compressors. These are able to output smaller versions of the same files, but which the game's Kosinski and Nemesis decompressors can unpack all the same. Doing so brings the ROM size down to 3.16 MB.

We can do better, though. As you may recall, the Sonic 3 cartridge contains a small subset of Knuckles' sprites that are used during his cutscene appearances. In Sonic 3 & Knuckles, these sprites are still used for the cutscenes which take place in Sonic 3 stages, so the Sonic3_Complete flag includes the cutscene art block in the ROM.

Much like the player object, cutscene Knuckles uses DPLCs to ensure that only one of its sprites needs to be loaded to VRAM at a time. This requires that all of his sprites be stored uncompressed in the ROM, which takes up a significant amount of space. All told, Knuckles takes up about 19.7 KB of the Sonic 3 cartridge.

However, since player sprites are also uncompressed, this presents an opportunity. If we take a close look at the above sprites, we can see that most of them are identical to sprites which can be found in the main Knuckles art block. In fact, only nine sprites along the bottom row are unique to the cutscene art block.

Once isolated, these sprites only take up about 4.3 KB. If we add them to the main Knuckles art block, and then simply edit cutscene Knuckles' DPLC scripts to point at the identical sprites in the main art block, we can lose the cutscene art block entirely and save about 15.4 KB.

The main art block is exactly 130,944 bytes. Adding the sprites above makes it 135,360 bytes. That's just over 132 KB.


To understand why this is a problem, let's look at the documentation for the DPLC format over at the Sonic Retro wiki:
Sonic 3 & Knuckles uses the same DPLC format as Sonic 2 for the main characters: the first word is the number of DPLC requests to make, and each successive word (up to the value of the first word) is split up so that the first nybble is the number of tiles to load minus one, and the last three nybbles are the offset (in tiles, i.e. multiples of $20 bytes) of the art to load from the beginning of the object's specified art offset in ROM.
To put it differently, each DPLC entry is a word in the format $NAAA, in which N is the number of tiles to copy to VRAM (minus one), and AAA is the the number of the tile to start copying from. So for instance, if we wanted to queue up tiles $3E2 through $3E7, that's six tiles starting from $3E2, so we would write down $53E2.

This format can only index up to $1000 tiles, and because each tile is $20 bytes long, that means the art block can't be larger than $1000 × $20 = $20000 bytes, or 128 KB.

So now we have to go into the art block and somehow save up 4 KB of tiles in order to add in the 4.3 KB of sprites from the cutscene block. Thankfully, there are a lot of poorly optimized sprites to aid us in our task.

For instance, in the teetering sprites above, there's a lot of empty space, and the shoe on the floor appears three times despite being identical in each frame. By nudging Knuckles around slightly, we can reduce the size of the sprite pieces and reuse the shoe for every frame, saving about a dozen tiles. Rinse and repeat for all 252 of Knuckles' frames.

You do the impossible and fit everything into 128 KB. That should work, right? Just build the ROM and-- oh, bloody hell.

Assuming you actually followed that link to the Sonic Retro wiki, you may have noticed that the DPLC format is different between Player Characters and Other Objects. Here's what it says in the latter case:
For other objects, the first word is the number of DPLC requests to make minus one, and each successive word (up to the value of the first word plus one) is split up so that the last nybble is the number of tiles to load minus one, and the first three nybbles are the offset (in tiles, i.e. multiples of $20 bytes) of the art to load from the beginning of the object's specified art offset in ROM.
Cutscene Knuckles isn't a player character, so by exclusion, he must be an "other object". So what, that just means the DPLC entry format is $AAAN rather than $NAAA, right?

Not so fast. In order to calculate the ROM offset for the DMA transfer, the DPLC code must take the starting tile number AAA and multiply it by $20, the size of each tile. Let's look at how the code in Knuckles_Load_PLC does it:
                andi.w  #$FFF,d1
                lsl.l   #5,d1
Pretty straightforward. The bottom 24 bits are isolated, and then promoted to a longword as the value is shifted left five times, multiplying it by $20. Now let's look at the general purpose code in Perform_DPLC:
                andi.w  #$FFF0,d1               ; Isolate all but lower 4 bits
                add.w   d1,d1
This time around, the tile number is in the top 24 bits, so it is already multiplied by $10 and only needs to be multiplied by two in order to calculate the offset. This is done by adding by adding the contents of the d1 register back onto itself, without promoting the value to a longword.

There are two consequences to this. One is that the d1 register does not have to be cleared before loading each new DPLC entry. The other is that tiles past the 64 KB boundary are inaccessible: since the topmost bit is always truncated, a request for tile $9B9 results in tile $1B9 being loaded instead.

At this point I just shrugged, moved all the cutscene sprites to the first half of the art block, and called it a day.

Friday, February 2, 2018

End of part one

On this day 24 years ago, Sonic the Hedgehog 3 was released for the Sega Genesis in North America. Happy birthday!

Coincidentally, today also marks my 200th post on this blog. Holy goodness, I swear I did not plan this far ahead when I started the blog nine months ago. It's been a lot of work writing a post every weekday, but also a lot of fun, especially when I was able to answer your questions. Doing so has made me learn a lot of things I previously did not know.

To all of my readers, especially those who have contributed to the discussion in the comments: thank you so much.

I would like to take this opportunity to make a couple of announcements. At various times, people have approached me on Twitter, YouTube, and even the Sonic Retro forums, asking me to work on a new version of Sonic 3 Complete, or to release my work in some other form. I'm not really interested in the former, because if I had my way, half of the stuff in that ROM hack would be thrown out, which would be a tremendous disservice to everyone who's ever contributed to it, as well as everyone who had played the previous versions.

I've also been reluctant on pursuing the latter, because "Sonic 3 Complete except with a lot less features" is a hard sell, both to the developer and the consumer. However, over the past few months I've been doing a lot of brainstorming, and I feel that I now have enough original ideas and a sufficiently unique direction to warrant pursuing them.

I'm excited to announce that starting today, I will begin development of my own Sonic 3 hack.

Which brings me to my second announcement. Like I've said, writing this blog has been very fun, but it has also been a challenge, and I have learned the hard way that I am not good with deadlines, even when it's doing something which I enjoy. Combined with the time I'll need to work on the hack, I am hereby suspending regular updates to this blog.

Let me make that perfectly clear: the blog isn't going anywhere. I still have more than 100 potential blog posts in my bag, and they will materialize sooner or later. Plus, working on a hack is bound to give me even more subject matter to work with. I just won't be posting regularly for the time being, that's all.

To that effect, I would advise you to follow me on Twitter, since I'll tweet out each new blog post. I'll probably also post some hack updates on there, and I promise I'll try to cut down on the memes.

I've gone back and tidied up the formatting on the older blog posts, and over the coming weeks I'd like to make the tags more helpful, as well as optimize the first animated GIFs I made, because they weigh a ton. Next thing I'll probably do however is write an updated about page to reflect the current nature of the blog, as well as the hack.

Again, thank you so much for reading this far, and I hope you'll stick around -- this ride ain't over by a long shot.

Thursday, February 1, 2018

Trouble at the border

A while ago, we saw how in Sonic 3, Knuckles' boss area in Launch Base Zone 1 was originally a bit different, and that Sonic 3 & Knuckles modifies it by altering the level layout directly in RAM. Logically, the same changes are also applied to the matching area at the start of act 2, except that this time, the twin boxes are already open.

Interestingly, in Sonic 3 the checkered tube is still present in the act 2 layout, despite normally being removed when the boss is defeated. It's possible that the act transition was originally planned to happen up there, and the tube would only explode at the start of act 2.

However, this theory is challenged by the presence of hidden monitors, buried in the floor at the bottom of the room, as early as the Sonic 3 object layout.

On the other hand, assuming the tube was meant to explode in act 1, it would then suddenly reappear upon loading the act 2 layout, which wcould lead to this curious scenario.

This isn't the only level layout adjustment performed in Launch Base Zone 2, though: directly after Knuckles' act 2 boss area, the Sonic 3 layout cuts off rather abruptly. In Sonic 3 & Knuckles, a couple of extra chunks were added to end the pipe floor more naturally.

This change is purely cosmetic however, because Knuckles' end of level cutscene forces him to jump at the exact point where the floor would cut off, regardless.

If it's weird you're looking for, though, look no further than Angel Island Zone 2. For whatever reason, there are actually hidden monitors buried in the floor of Knuckles' boss area. In act 2.

What on earth could the developers have been planning here?