U4 Formats: LZW

LZW stands for the brilliant guys who invented this file compression algorithm. If you goole, you will be able to find lots of articles and lecture notes about LZW format. It is a little difficult to figure out the details, but since it’s such a important algorithm, it’s worth to study about it.

The short description of LZW is that, when this LZW thing compresses an original file, it generates a kind of look-up table, and it stores the index of the look-up table. However, LZW encoder doesn’t save the look-up table itself – in only saves the index data (which is now the compressed data) that refer to the table. With clever thought, when the LZW decoder reads the index data, it can regenerate the look-up table while decompressing the data.

There’s one thing to note though. After decoding the Ultima IV’s LZW compressed pictures, the resulting data becomes the Raw data. For some reason, I thought the uncompressed data should be RLE data, and so I wasted hours before I realize it was not RLE data but Raw data.

For the look-up table, LZW algorithm uses hash table. You can google about hash table, and you can study about it if you really want, and actually I do encourage you to do that, but studying hash table doesn’t guide you anywhere when we talk about Ultima IV format. Why? Because Ultima IV uses a very unique and peculiar kind of hash table. Among others, Marc Winterrowd is the guy who figured out Ultima IV’s LZW algorithm. Even the xu4 project uses his code directly. I’m not 100% sure, but I think he dived into the source code, if not the compiled executalble file itself. Otherwise, it won’t be possible to reverse engineer the algorithm – it is so much strange algorithm the Origin Systems (the company that made Ultima IV) used.

Anyway, this is the end of the post. No python code today, because Ultima IV’s LZW is, again, way too complicated to explain with a few words.

U4 Formats: Raw and RLE

Ultima IV internal formats fall into three catagories: Raw, RLE, and LZW. Those formats are thoroughly investigate by many hackers and presented on internet, and ultima codex wiki is one of them. I also got help from the site, and so there aren’t many things for me to tell, but I do have something to comment on.

Raw format is very basic one. It’s uncompressed format, and it has just color information from the first pixel to the last pixel, in specific order. If you know the width and the height of the original picture, you can draw the picture on your canvas. You need to do some experiments maybe, but it’s not too hard to do.

import pygame
from pygame.locals import *

EGA2RGB = [
    (0x00, 0x00, 0x00),  # BLACK
    (0x00, 0x00, 0xAA),  # NAVYBLUE
    (0x00, 0xAA, 0x00),  # GREEN
    (0x00, 0xAA, 0xAA),  # TEAL
    (0xAA, 0x00, 0x00),  # MAROON
    (0xAA, 0x00, 0xAA),  # MAGENTA
    (0xAA, 0x55, 0x00),  # BROWN
    (0xAA, 0xAA, 0xAA),  # SILVER
    (0x55, 0x55, 0x55),  # MATTERHORN
    (0x55, 0x55, 0xFF),  # BLUE
    (0x55, 0xFF, 0x55),  # LIGHT GREEN
    (0x55, 0xFF, 0xFF),  # AQUA
    (0xFF, 0x55, 0x55),  # SUNSET ORANGE
    (0xFF, 0x55, 0xFF),  # FUCHSIA
    (0xFF, 0xFF, 0x55),  # YELLOW
    (0xFF, 0xFF, 0xFF),  # WHITE
]

def raw(decompressed):
    if decompressed == None:
        return None

    pixels = []
    for d in decompressed:
        a, b = divmod(d, 16)
        pixels.append(EGA2RGB[a])
        pixels.append(EGA2RGB[b])
          
    return pixels


if __name__ == '__main__':
    pygame.init()

    displaysurf = pygame.display.set_mode((128, 64))
    pygame.display.set_caption('File Formats')

    with open("../ULTIMA4/CHARSET.EGA", "rb") as file:
        bytes = file.read()

    pixels = raw(bytes)
    pixObj = pygame.PixelArray(displaysurf)
    for i in range(16):
        for j in range(8):
            for k in range(8):
                for l in range(8):
                    pixObj[i * 8 + k][j * 8 + l] = pixels[i * 64 + j * 64 * 16 + k + l * 8]
    del pixObj

    loop = True
    while loop:

        for event in pygame.event.get():
            if event.type == QUIT:
                loop = False
                break

        pygame.display.update()

    pygame.quit()

Selecting a featured image is recommended for an optimal user experience

RLE format, or Run-Length Encoding format uses a simple and easy-to-understand compress algorithm. There are many variants in RLE format: some of them are simple and not too effective, and some of them are very sophisticated and carefully designed for the compress performance. Ultima IV’s RLE version is, I would say, the simpler one. It doesn’t give you very high compression ratio, especially when your picture is complicated, but if your original image uses single pixel color reapeatedly and continually, the compression ratio can be very good.

Ultima IV’s RLE starts from “normal mode”, and the normal mode is just like the raw format. But if you encounter the magic number 0x02, your state becomes “run-length mode”. The number after 0x02 tells you the repeat number, and the 3rd number tells you the color pixel value you should repeat. After the Run-Length Encoding, the state goes back to the “normal mode”.

.....

STATE_NORMAL        = 0
STATE_GET_RUNLENGTH = 1
STATE_GET_RUNCOLOR  = 2

def rle(bytes):
    pixels = []
    state = STATE_NORMAL
    for d in bytes:
        if state == STATE_NORMAL:
            if d == 0x02:
                state = STATE_GET_RUNLENGTH
            else:
                a, b = divmod(d, 16)
                pixels.append(EGA2RGB[a])
                pixels.append(EGA2RGB[b])
        elif state == STATE_GET_RUNLENGTH:
            run = d
            state = STATE_GET_RUNCOLOR
        elif state == STATE_GET_RUNCOLOR:
            for i in range(run):
                a, b = divmod(d, 16)
                pixels.append(EGA2RGB[a])
                pixels.append(EGA2RGB[b])
            state = STATE_NORMAL
    return pixels

if __name__ == '__main__':
    pygame.init()
    displaysurf = pygame.display.set_mode((320, 200))
    pygame.display.set_caption('File Formats')
    with open("../ULTIMA4/START.EGA", "rb") as file:
        bytes = file.read()

    pixels = rle(bytes)
    pixObj = pygame.PixelArray(displaysurf)
    for i in range(320):
        for j in range(200):
            pixObj[i][j] = pixels[i + j * 320]
    del pixObj

    loop = True
    while loop:

        for event in pygame.event.get():
            if event.type == QUIT:
                loop = False
                break

        pygame.display.update()

    pygame.quit()

Please note that the above codes are NOT my own. It is actually James Tauber‘s work, and I borrowed his code almost without any modification.

The post is getting longer, so I will describe about the LZW format in the next post.

Ultima IV Intro: Logo Appearing

The next thing I always wondered about the intro sequence of Ulitma IV was the appearing of the logo “Ultima IV”. To me it looked kind of unique, and I didn’t think of the logic until very recently.

The closest algorithm I could think of was, ramdomize x and y coordinate and put a pixel there, and repeat.

# Radomized appearing of logo, a reproduction of Ultima IV's introductory sequence
# program by Dr. Roach (https://drroach.game.blog/), 2020-02-25

import pygame
import random

color = (128, 128, 255)
black = (0, 0, 0)

pygame.init()
pygame.display.set_caption("Logo Demo")

screen = pygame.display.set_mode((320, 200))
screen.fill(black)

font = pygame.font.SysFont("comicsansms", 54)
text = font.render("Dr. Roach", True, color)

w = text.get_width()
h = text.get_height()
x0 = 160 - w // 2
y0 = 80 - h // 2

clock = pygame.time.Clock()

running = True
while running:
	for event in pygame.event.get():
		if event.type == pygame.QUIT:
			running = False

	x = random.randint(0, w // 2) * 2
	y = random.randint(0, h)
	screen.blit(text, (x0 + x, y0 + y), (x, y, 2, 1))

	pygame.display.update()
	clock.tick(250)

pygame.quit()

If you run the code above, it would show our logo in an randomized way. However, it’s very different from what we see in Ultima IV intro.

Then what? Well, it just came up in my mind all of a sudden, and the result was below.

# Radomized appearing of logo, a reproduction of Ultima IV's introductory sequence
# program by Dr. Roach (https://drroach.game.blog/), 2020-02-25

import pygame
import random

color = (128, 128, 255)
black = (0, 0, 0)

pygame.init()
pygame.display.set_caption("Logo Demo")

screen = pygame.display.set_mode((320, 200))
screen.fill(black)

font = pygame.font.SysFont("comicsansms", 54)
text = font.render("Dr. Roach", True, color)

w = text.get_width()
h = text.get_height()
x0 = 160 - w // 2
y0 = 80 - h // 2

clock = pygame.time.Clock()
r = 0.0

running = True
while running:
	for event in pygame.event.get():
		if event.type == pygame.QUIT:
			running = False

	for x in range(w // 2):
		for y in range(h):
			if random.random() < r:
				screen.blit(text, (x0 + x * 2, y0 + y), (x * 2, y, 2, 1))
			else:
				pygame.draw.line(screen, black, (x0 + x * 2, y0 + y), (x0 + x * 2 + 1, y0 + y))

	if r < 1.0:
		r += 0.0025

	pygame.display.update()
	clock.tick(50)

pygame.quit()

To explain the algorithm, it starts from a number you pick, and let’s call the number “r”. For each and every pixel of the logo, you roll a dice. If the resulting number is smaller than the number “r”, you draw the pixel. If the number on your dice is bigger than “r”, you draw backgrould color black for the pixel instead.

After you are done with all the pixels of the logo, repeat from the first pixel, except that now we increase the number “r” a little bit. As our “r” grows, the chance of showing the logo gets higher, and the chance of showing black backgound gets lower.

I hope my explanation is clear enough. To me, the result seems quite close to the Ultima IV’s logo appearing scene.

Logo appearing in Action

Ultima IV Intro: LB’s handwriting

When I ran Ultima, I had lots of questions regarding how could Lord British make the game, and this one was the first question. How to program such a nice handwriting at the very beginning of Ultima IV intro sequence. I could only guess, but I didn’t have a clue.

But things have changed. Now we have internet, and many smart guys out there who tried to reverse engineer the wonderful game uploaded their findings on the internet for you to see. If you look into the ergonomy-joe’s decompiled source, you can find how things worked inside of the game. But still, even though there are lots of information available, if you don’t have enough time and energy, it’s not easy to dig down the gold mine and actually get the gold out. If your coding skill is not good enough and/or you are not familier with C language, that is out of question. So, I will try to explain how it works behind the surface.

In the ergonomy-joe’s decompiled source, take look at the SRC-TITLE/DATA.C. In the file, our ergonomy-joe was kind enough to comment the portion where the Lord British’s handwriting is, and that is the unsigned character array D_346E. It contains the x, y coordinate of the handwriting.

So, to make a long story short, the program has the x, y points data inside. When right time comes, it just draws the points sequencially, that’s all.

Now here’s a python source that draws the handwriting. The python version is 3.x, and the pygame version I use is 1.9.6.

# Lord British's handwritings, a reproduction of Ultima IV's introductory sequence
# the data is from ergonomy-joe's decomiled source
# program by Dr. Roach (https://drroach.game.blog/), 2020-02-23

data = [
	0x54,0xBD,0x55,0xBC,0x57,0xBC,0x59,0xBC,0x5B,0xBC,0x5C,0xBD,0x5C,0xBE,0x5B,0xBF,
	0x59,0xBF,0x58,0xBE,0x58,0xBD,0x57,0xBB,0x56,0xBA,0x56,0xB9,0x55,0xB8,0x55,0xB7,
	0x54,0xB6,0x54,0xB5,0x53,0xB4,0x53,0xB3,0x52,0xB2,0x52,0xB1,0x51,0xB0,0x4F,0xB0,
	0x4E,0xB0,0x4D,0xB1,0x4D,0xB2,0x4E,0xB3,0x50,0xB3,0x51,0xB2,0x54,0xB2,0x55,0xB1,
	0x56,0xB1,0x57,0xB0,0x59,0xB0,0x5B,0xB0,0x5D,0xB0,0x5F,0xB0,0x61,0xB0,0x63,0xB0,
	0x65,0xB0,0x67,0xB0,0x69,0xB0,0x6B,0xB0,0x6D,0xB0,0x6F,0xB0,0x71,0xB0,0x73,0xB0,
	0x75,0xB0,0x77,0xB0,0x79,0xB0,0x7B,0xB0,0x7D,0xB0,0x7F,0xB0,0x81,0xB0,0x83,0xB0,
	0x85,0xB0,0x87,0xB0,0x89,0xB0,0x8B,0xB0,0x8D,0xB0,0x8F,0xB0,0x91,0xB0,0x93,0xB0,
	0x95,0xB0,0x97,0xB0,0x99,0xB0,0x9B,0xB0,0x9D,0xB0,0x9F,0xB0,0xA1,0xB0,0xA3,0xB0,
	0xA5,0xB0,0xA7,0xB0,0xA9,0xB0,0xAB,0xB0,0xAD,0xB0,0xAF,0xB0,0xB1,0xB0,0xB3,0xB0,
	0xB5,0xB0,0xB7,0xB0,0xB9,0xB0,0xBB,0xB0,0xBD,0xB0,0xBF,0xB0,0xC1,0xB0,0xC3,0xB0,
	0xC5,0xB0,0xC7,0xB0,0xC9,0xB0,0xCA,0xB0,0xCB,0xB1,0xCC,0xB1,0xCD,0xB2,0x5E,0xB8,
	0x5E,0xB7,0x5D,0xB6,0x5D,0xB5,0x5C,0xB4,0x5C,0xB3,0x5D,0xB2,0x5F,0xB2,0x60,0xB2,
	0x61,0xB3,0x61,0xB4,0x62,0xB5,0x62,0xB6,0x63,0xB7,0x63,0xB8,0x62,0xB9,0x60,0xB9,
	0x5F,0xB9,0x69,0xB9,0x6A,0xB8,0x6A,0xB7,0x69,0xB6,0x69,0xB5,0x68,0xB4,0x68,0xB3,
	0x67,0xB2,0x6B,0xB8,0x6C,0xB9,0x6E,0xB9,0x77,0xB9,0x75,0xB9,0x74,0xB9,0x73,0xB8,
	0x73,0xB7,0x72,0xB6,0x72,0xB5,0x71,0xB4,0x71,0xB3,0x72,0xB2,0x74,0xB2,0x75,0xB3,
	0x76,0xB4,0x77,0xB5,0x77,0xB6,0x78,0xB7,0x78,0xB8,0x79,0xB9,0x79,0xBA,0x7A,0xBB,
	0x7A,0xBC,0x7B,0xBD,0x7B,0xBE,0x76,0xB3,0x77,0xB2,0x8B,0xBE,0x8B,0xBD,0x8A,0xBC,
	0x8A,0xBB,0x89,0xBA,0x89,0xB9,0x88,0xB8,0x88,0xB7,0x87,0xB6,0x87,0xB5,0x86,0xB4,
	0x86,0xB3,0x85,0xB2,0x8C,0xBF,0x8E,0xBF,0x8F,0xBF,0x90,0xBE,0x90,0xBD,0x8F,0xBC,
	0x8F,0xBB,0x8E,0xBA,0x8E,0xB9,0x8C,0xB9,0x8F,0xB8,0x8F,0xB7,0x8E,0xB6,0x8E,0xB5,
	0x8D,0xB4,0x8D,0xB3,0x8C,0xB2,0x8A,0xB2,0x88,0xB2,0x87,0xB3,0x96,0xB9,0x97,0xB8,
	0x97,0xB7,0x96,0xB6,0x96,0xB5,0x95,0xB4,0x95,0xB3,0x94,0xB2,0x98,0xB8,0x99,0xB9,
	0x9B,0xB9,0xA1,0xB9,0xA0,0xB8,0xA0,0xB7,0x9F,0xB6,0x9F,0xB5,0x9E,0xB4,0x9E,0xB3,
	0x9D,0xB2,0xA2,0xBC,0xA2,0xBB,0xA9,0xBC,0xA9,0xBB,0xA8,0xBA,0xA8,0xB9,0xA7,0xB8,
	0xA7,0xB7,0xA6,0xB6,0xA6,0xB5,0xA5,0xB4,0xA5,0xB3,0xA6,0xB2,0xA8,0xB2,0xA9,0xB2,
	0xAA,0xB3,0xA5,0xB9,0xA6,0xB9,0xAA,0xB9,0xB2,0xB9,0xB1,0xB8,0xB1,0xB7,0xB0,0xB6,
	0xB0,0xB5,0xAF,0xB4,0xAF,0xB3,0xAE,0xB2,0xB3,0xBC,0xB3,0xBB,0xBB,0xB8,0xBA,0xB9,
	0xB8,0xB9,0xB7,0xB9,0xB6,0xB8,0xB6,0xB7,0xB7,0xB6,0xB8,0xB5,0xB9,0xB4,0xB9,0xB3,
	0xB8,0xB2,0xB6,0xB2,0xB5,0xB2,0xB4,0xB3,0xC5,0xBE,0xC5,0xBD,0xC4,0xBC,0xC4,0xBB,
	0xC3,0xBA,0xC3,0xB9,0xC2,0xB8,0xC2,0xB7,0xC1,0xB6,0xC1,0xB5,0xC0,0xB4,0xC0,0xB3,
	0xBF,0xB2,0xC5,0xB9,0xC6,0xB9,0xC7,0xB8,0xC7,0xB7,0xC6,0xB6,0xC6,0xB5,0xC5,0xB4,
	0xC5,0xB3,0xC6,0xB2,
]

import pygame

SCREEN_WIDTH = 320
SCREEN_HEIGHT = 200

color = (80, 80, 255)
black = (0, 0, 0)

pygame.init()
pygame.display.set_caption("Lord British Handwriting")
screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))
screen.fill(black)

clock = pygame.time.Clock()
i = 0
running = True
while running:
	clock.tick(60)
	for event in pygame.event.get():
		if event.type == pygame.QUIT:
			running = False

	if i + 1 < len(data):
		x = 10 + data[i]
		y = 260 - data[i + 1]
		pygame.draw.line(screen, color, (x, y), (x + 1, y), 1)
		i += 2

	pygame.display.update()

pygame.quit()

Line number 65 and 66 extract the x and y coordinate of the pixel to draw from the data. Why x is not just data[i] but 10+data[i], and why y is not just data[i+1] but 240-data[i+1]? It’s just to make the signature at the center of the screen at the right orientation. The points data that is stored is made that way, so we have to draw that way. I needed to do some experiments to make things work right, which anybody can do.

Actual drawing happens at line number 67. It doesn’t draw a pixel but a two-pixel-length line, again, because the points data the ultima IV has are stored that way.

However, the xu4 project that I admire doesn’t hold of Ultima IV’s data this way. It tries to extract the x and y coordinates of the signature from the original DOS version’s file, “title.exe”. The project team’s philosophy is, I think, to respect original game’s copyright. Even though they could choose to store the data right in their source code such as my code above, they decided to extract the data from the original file. It gives the ones who want to play xu4 a great inconvenience – he or she has to get the original program either from his/her Ultima CD, or from internet and extract the zip file to a directory to run xu4 – but I think their attitude toward the original game is right. But if you really want to extract every single data from the original files, your code will be messy and very hard to read. You know, even the definition of ‘data’ itself is not clear enough. So there should be some kind of compromise. For me, the coordinates of the Lord British’s handwriting should be extracted from the original files, so I did that.

I hope this post is helpful to the ones who really wanted to know how things work inside of the game.

Ultima IV Remake, how it began

I was bored. I had a little free time, but I was tired of reading novels, watching Netflix movies, or listening Podcasts. Well, I thought, this might be the right time to start a new project, and that project was something I wanted to do when I was younger. My thinking flew from here to there, and somehow, I decided to remake Ultima IV, and the target language was Python.

I googled a little bit, and found out Marc Winterrowd’s homepage and downloaded the u4decode source from there. The first attempt to run the code was not successful, because I used Python 3.x while the code was written in Python 2.x. After some struggling, finally I got the code running.

After that, I found out xu4 project and downloaded the source code. Then, I encountered ergonomy_joe’s Ultima IV decompiled source, which is an invaluable source for my project.

Those three things were very crucial for me to start my new project. Without them, I would not be able to start the project.

I had been always wondering how Ultima series were made since my youth. Nobody could teach me how to make that kind of game, and no book was telling me how I can hold of the forbidden magic. But now, as I am working for the remake, little by little, the hidden art of making the world-famous RPG is revealing to me.

It is like an archeological study – figuring out how the ancient Egyptians made the pyramid: what kind of support structures were used, how the massive stones were cut and moved, and how did the master architect designed the three dimensional layout, by using the most advanced science and human knowledge. It is so much hard work, but certainly a very fascinating thing to do.

I would like to write and post in this blog what I have figured out and learned in the process of remaking. It would be, I hope, more valuable information than just give out the source files without any explanation.