Reconstructing Ecstatica’s Level Geometry MK2

Amazing! As it turned out, what I expected to be the navigation- and collision mesh is actually almost the complete level geometry including walls, stairs, windows, etc. What’s missing is triangle-based geometry like roofs and windows as well as all the static ellipse-based models (flowers, grass, etc.). Nontheless this are great news, because the whole game world can now be explored and looked at in 3D!

Extracted Level Geometry from Ecstatica

Extracted Level Geometry from Ecstatica

Reconstructing Ecstatica’s Level Geometry

Alone in the Dark 3

Alone in the Dark 3

Ecstatica 1 takes place in a small village upon a rock, surrounded by a deep valley. The walkable area is restricted to this very rock, but still it is quite big and it is open. Not just a bunch of rooms but an exterior area. If you take a closer look at Ecstatica’s backgrounds, you will be puzzled by the really high-quality of the level geometry. Yes, there is real geometry behind the backgrounds. It even looks like not only the characters are all made of Ellipses but the walls, the floor and the plants as well. Those stone floors and walls look just like something you would use displacement mapping or metaballs for today. The Compare that to titles like „Alone in the Dark“ (see screenshot below) which were using painted environments. Alone in the Dark is quite a visually appealing title. But having actual geometry to render the backgrounds from is something different. Remember: When Ecstatica was shipped it was 1994!  How the hell did those Britons do this? This was not a multi-million dollar production. On what hardware were they able to create and render this vast amount of geometric data?

Screenshot demonstrating the high qualify of Ecstaticas level geometry

Screenshot demonstrating the high qualify of Ecstatica's level geometry

I recently worked on some code doing a reconstruction of the level geometry based on the set of about 240 background images. I managed to mix this reconstructed geometry with the collision- and navigation mesh. The current state already looks interesting. I propably won’t be able to explicitely reconstruct the complete geometry…

  • the available camera views are too sparsly distributed
  • the texture infomation I reconstruct is quickly diminishing in quality as you get farer away from the camera due to the projection effect
  • It would require a LOT of post-processing in order to merge and clean up the generated mesh data
  • It’s actually too much geometry. Given my 8 Gigs of RAM I’m unable to represent all 340 backgrounds in one blender session – even though I threw away around 99,5% of all generated polygons (using the „Decimate“ modifier).

How did they do it in 1994? My current assumptions are

  • They chopped the game world into chunks swallowable for 1994 hardware
  • For individual chunks they used some CAD software to create coarse geometry (walls, floors, stairs, etc.)
  • The used a custom raytracer to shoot rays through the world, querying the relevant geometry chunk and then, as a final step, they generated the ellipses on-the-fly using some form of texture mapping. I base this assumption on the fact that the stone walls show certain patterns. The basic principle of this last step actually is rather simple. Instead of calculating the ray intersection with a plane from the coarse geometry you put a set of ellipses there, each only described by its center and its radii. Because you’re systematically scanlining over the sensor area of your virtual camera, you should be able to keep only those ellipses in memory which are actually hit by rays.
Current state of my attempt to reconstruct Ecstatica's level geometry

Current state of my attempt to reconstruct Ecstatica's level geometry

Approaching a breakthrough

Hi, It’s been a lApproachingBreakThroughong time again since my last update. For some months I was lacking motivation to continue work on my Ecstatica project. But now during the last week of my Christmas vacation, I started to work on it again and finally all the frustrating research into the data structures employed to describe characters in Ecstatica is starting to show signs of success. I think I have a pretty good picture now how Ecstatica is doing it and therefore I was able to put this knowledge into a little Python script run inside Blender to generate Ecstatica characters.

As you can see, the main character is missing its nose. I currently assume that it is described by a triangles. Triangles are not generated yet. I’m working on that. After that, the next milestone will be to translate character animations into blender animations.

Update on Reasearch on Ecstatica

Things move slowly forward. This weekend I have continued to implement some Python routines to

  • load an Ecstatica FANT file
  • write an Ecstatica FANT file
  • write a XML representation of the FANT file
  • read a XML representation of the FANT file

Those 4 building blocks are in an early stage right now. At the moment I have verified that I can load a FANT file and write it back without introducing any relevant differences. I’m still having some precision issues with converting the fixed-point numbers to floats and back.

Using these tools I will be able to modify the game data files and see, what happens. I’m thinking about giving the main character green hair or something like that 😀

Blockheads invade the village

Ecstatica fortunately still contains a lot of debug code, which is partly not even called anymore (strangely it was not stripped from the binary).

One of those tiny little debug features is to draw a box around every ellipsoid. The result looks kinda funny ;D

Ecstatica copy-protection mechanism (exit after intro)

Just for fun I googled for „Ecstatica no-cd patch“ some weeks ago and found: nothing. You could readily assume that there’s no need, that Ecstatica does not include a protection mechanism. Nothing could be farer away from the truth. You can witness the copy protection mechanism if you simply copy the ecstatica data files from your ecstatica CD onto disk and start it from there. The program will terminate suddenly after the intro. Googling for „ecstatica exit after intro“ does not bring up a solution nor even a explanation for the strange behaviour. It is obviously no crash, because it equally happend in

  • qemu
  • dosbox
  • dosemu
  • bochs

and there never is any error message visible. Well I now found out that there’s actually a protection mechanism at work here. Try this: Start Ecstatica in dosemu from (original) CD  and the program won’t terminate after the intro!

Ecstatica Scene Views

I invested quite some time into figuring out, how to decode the files containing the different camera views for all the scenes in Ecstatica. Well, I finally got somewhere, after some unsuccessfull attempts. At least those attempts made me learn a lot new things about Huffman codes, the LZW algorithm and RL enconding. The amazing game mod wiki helped much again.

The phenotypic facts

I rather quickly found out that:

  1. The scene files are much to small to contain a raw pixel representation.
  2. Changing a byte somewhere in the file sometimes affected a single pixel in the game, sometimes a sequence of pixels
  3. All changes had only local impact, just sometimes the decoding algorithm in Ecstatica seemd to crash and omitted all following pixels. Amazingly this didn’t make Ecstatica crash. Congratulations to the programmers for this stability!

Could it be LZW?

The wikipedia article about the LZW algorithm is quite insightful. After reading it and reconsidering the facts, I came to the conclusion, that it its propably not LZW. Why? As noted above, changes in the pixel values have only local impact. This is also true for the first few pixels. But in my opinion changing values in the first stage of a compressed  LZW data stream should have global impact on the decompressed stream. For example:

Input Output
LZW<256> LZWLZ
ZZW<256> ZZWZZ

Could it be RLE?

Well, could it be RLE? I learend a lot about the algorithm from the wikipedia article about the PCX format and the respective modding wiki article. What made me doubt that we have RLE here was, that in my favourite HEX editor, I could see no connection between the most-significant bits and the impact of a value change.

So what is it?

It is some kind of RLE. A special form of RLE: T’here are color bytes and there are RL bytes, like in the standard RLE. The RL bytes are structured in the following way:

  • The 6 most-significant bits are the run-length, let’s call the value L
  • The 2 least-significant bits are flags.

The flags have the following meaning

bit #0 bit #1 meaning
0 0 L pixels. Each pixel’s color is determined using the previous pixel’s color and a 4bit value giving the relative change of color
0 1 L pixels of the same color
1 0 L pixels whose colors are represented absolutely using 1 byte each. If none is set, there are following L pixels in which each pixel

The RLE data starts at position 10 (decimal) in the file.

Is that all?

No, absolutely not. What I was able to decode was merely a part of the scene files. There’s a lot more in there. Some candidates

  • z-Values. In order to correctly let walls occlude characters, there has to be a Z map or something like that.
  • Camera properties. To be able to render the characters correctly, the camera properties (focal length, etc.) have to be known.

Ecstatica RAW Image Files

I have invested some time today in understanding the RAW data files, which are image files.

Using the HEX editor

I started by taking a look at the title_s.raw file using my favourite hex editor. It became obvious very fast, that the RAW files contain raw pixel data, therefore earning their filename suffix. Now I had to find out, how the pixels are coded exactly. My Stone of Rosetta, so to speak, was a screenshot from the title screen

Titelscreen of ECSTATICA gametitle screen of ECSTATICA game

From this screenshot I could already derive some very important facts I could use in the next step.

Using C and SDL

Using C and SDL I quickly developed a little tool which simply

  • reads in the complete file
  • skips the first N bytes
  • renders the following <width>*<height>*<bytes per pixel> bytes onto the buffer

My little tools allows to change <width>, <height>, <bytes per pixel>, <skip amount> and <position of color palette> live using keybord keys. Using it I approved that the file contains 320*200 pixels, each 1 byte long, coded as conventional (line-wise) raw pixel data.

Now I had to decode the palette data. Why did I guess, that there’s a palette?

  • All cases, I examined yet, used palettes if the per-pixel-data had only 256 different states. Otherwise you would be forced to use only 256 color from a possible VGA color range of 262,144 (6 bit per channel).
  • The red color in the top line „ECSTATICA“ has index 02, but an R-value of 255. So actually it should be 03, if the RGB-color was coded directly into the 1 byte per -pixel data and red would have been given 2 bits.

I started by guessing, that the palette started at offset 20 in the file. Why? Because that’s the biggest possible offset, assuming the palette requires 768 bytes of data (3 bytes per color). Then I looked up the palette index for the solid white in the lower line „a state of mind“ in the screenshot. It has RGB 255, 255, 255 i.e. a maximum white. The palette index is 01. And, as a matter of fact, the file contains the byte sequence „FF FF FF“ for entry 01, „FF 00 00“ for entry 02.

The unknown land between 00 and 20

Unknown remains the bytes before the palette at offset 20. We can assume, that the width and height are hidden somewhere in there.

Using my tool, I figured out the widths for all files in sub-folder „graphic“

File Width Height
title1.raw 112 40
title2.raw 139 38
title3.raw 87 40
title4.raw 136 39
title5.raw 143 39
title6.raw 112 37
title7.raw 111 59
end1.raw 133 76
end2.raw 93 18
endend.raw 107 100

Now I looked for those values in the respective files.

For the images in subfolder graphics, we can the respective width, listed in the table above, at byte offset 9 in the files. For the original image title_s.raw there’s an 64. That’s strange. Looking for the height value, I came to the conclusion that they use

  • 2 bytes for the width at offset 9
  • 1 byte for the height at offset 11

This makes sense in so far, that the height can never exceed 200 pixels (fitting into a single byte value range of 0-255).

Ecstatica scene files

Well, we managed to load simple image files from ECSTATICA so far. Of course the next thing I tried was to load a scene file from the actual game. Rejoiced too soon: Those are something else. I cannot load them using my current setup. Well, this is not surprising, after all. The scenes in ECSTATICA have to contain some kind of Z channel, to allow to decide whether a character is visible or behind an object on screen.

Decoding the scene files is dealt with in the next article.

Ecstatica Files

Ecstatica provides a lot of discrete files, for which the purpose can be esteemed based on their path and filename. I consider it much more difficult to examine a program having a monolithic data file containing all sorts of file types in some unknown compressed form, packed together.

For example, all scene graphics seem to be present as individual .raw-Files, sitting in sub folders

  • views
  • graphics

Amazingly, the dialogues or at least the dialogue translations are represented using simple plain text files. An excerpt from the German version

/ THE TWO MONKS

sp_3/4_2
„Hey! Ihr dürft das heilige Relikt nicht berühren!“

sp_3/4_3
„Dieses Sakrileg muß bestraft werden!!“
—————————————————————————————————————
sp_3/4_4
„Ugh! Großer Gott!“
—————————————————————————————————————
sp_3/4_5
„Aaaaagh… Amen …“
——————————————————————————————————————————————————————————————————————————

You can use dosbox as a disassembler (read here about it). Though I didn’t manage to use that feature yet, I was delighted to see, that dosbox is also logging simple DOS API calls, like „open file“. That way, I was able to examine which files Ecstatica is accessing during game startup.

Remaking Ecstatica

This morning, while I woke up, I glanced at one of the CD-ROMS in my shelf. It was ECSTATICA, published some year in the 90s in the neon edition. There’s a nice article about the game and it’s successor on the brilliant hardcore gaming site.

3 year ago I spent some months working on a Little Big Adventure 1 Remake, using yazor’s C code, which he afaik derived directly from disassembling the LBA binary. Btw. there is still the great Little Big Adventure Community Magicball Network, I was active at back then. Well, this morning I felt the urge to make another try to create an open-source remake of a game. For example, there’s an open source remake of Alone in the Dark by yazor (yah, it’s the genius again :)) you can use to play the games if you provide the original game data. I want to do exactly the same for ECSTATICA.

So this is the first article in a hopefully long series of articles covering my attempt to recreate ECSTATICA.