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()    
Raw Format

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()    
RLE Format

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.

Lord British’s Signature

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.