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

Python script to calculate the Madelung constant of an infinite lattice

During my Diploma thesis in Physics I had to calculate the Madelung constant for a lattice of ZnO supercells. For this purpose, I implemented a small Python programm. The only prerequisite is SciPy. The script calculates the Madelung constant for an infinite lattice of point charges, neuralized by a counter-charged jellium background. All documentation is inside the file madelung.py. There’s another script sc_mad.py (supercell madelung constant) in there which demonstrates reading a POSCAR file describing an atomic lattice and calculating the Madelung constant for it.

Maybe someone can so something useful with the stuff. I would be happy about feedback whether the implementation actually works for your specific case 🙂

https://github.com/fHachenberg/pymadelung

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.

Create a list with predefined number of entries in python

You want to create an array-like data structure in python. You know, how many entries you will need for your list. What do you do?

I always thought you have to do something like

lst = []
for i in range(N):
   lst.append(None)

Today i learned here, that in python you can simply say

lst = [None]*N

and it is even much faster. I never stop learning, even after several years of using python 🙂

completing file paths in python cmd module

python’s cmd module is great. You derive your class from the provided command interpreter and you can start right away implementing command. Let’s have a look at a small command interpreter for a beer-drinking bot.

import cmd

class BeerRobotCmd(cmd.Cmd):
	def __init__(self):
		cmd.Cmd.__init__(self)
                #for the sake of simplicity we make
                #those states part of the cmd object. Normally,
                #of course you would use your cmd class to drive
                #some external interface.
		self.stomach_filled = 0
		self.drunkness = 0
		self.singing = None

	def do_drink(self, line):
		if self.stomach_filled >= 100:
			print "robot is full of beer"
		else:
			print "robot drinks beer"
			self.stomach_filled += 10
			self.drunkness += 1

	def do_throwup(self, line):
		print "robot throws up"
		self.stomach_filled = 0

	def do_sing(self, line):
		if len(line.strip()) > 0:
			if self.singing != None:
				print "robot is singing already"
			elif self.drunkness < 15:
				print "robot is too shy"
			else:
				print "robot starts to sing", line
				self.singing = line
		else:
			if self.singing:
				print "robot stops singing"

commandline = BeerRobotCmd()
commandline.cmdloop()

Our robot now understands 3 important commands

  1. drink makes him drink a beer, until he’s full.
  2. throwup makes him throw up (wow, surprising 🙂 ) so his stomach is empty again
  3. sing makes him sing a custom sing. You can tell him to sing, for example, the national anthem or a lullaby. If you call „sing“ without any arguments, he will stop to sing

We have amazingly created those commands simply by implementing 3 methods

def do_commandname(self, line)

In those line contains all the characters entered by the user after the actual command string. So in order to extract arguments from there, we simply have so split or search or process the line argument in some way.

This quickly-implemented command interpreter even contains completion for commands already. Pressing TAB without entering any character will show the user all avaible commands.

argument completion

The cmd module allows you to implement a simple completion callback intended not for the command strings but for the arguments.

Here’s a completion callback for the sing command, proposing to the user a list of songs.

	def complete_sing(self, text, line, startidx, endidx):
		return [ song for song in ['yesterday', 'uptown girl', 'anything goes', 'old mcdonald has a farm'] if song.startswith(text) ]

Like in the unix shell, where hitting TAB while entering a file name will prompt you with possible completions, this callback will provide possible completions as well. It works as follows

  • the line argument contains the complete line, like in the do_foo methods
  • the text argument contains the part of the current argument, the user has entered already. This is, of course, inteded to be used as a filter for the set of possible completions. If i enter „sing yest“ and hit TAB, this callback is called with text = „yest“.
  • the startidx and endidx arguments are indices into the line string, describing which subset of line is contained in text. For the case of „sing yest“ and hitting TAB, those args would contains 1 and 4 respectively (not 0, because the space between „sing“ and „yest“ is interpreted as the first character of the line string).

argument splitting problem

Well, this is all great. Until you try to complete arguments containing characters, interpreted by the completion mechanism as separators. Like a guiltless „/“. This is bad. You won’t be able to implement the completion of file name arguments. Assume, for example, the user has entered „SOMECOMMAND /home/foo/bar/“ and wants to see now (similiar to the unix shell) what files are there in the directory /home/foo/bar/. He hit’s TAB. The completion mechanism scans the current command line and splits it into SOMECOMMAND<start of argument line> /<first argument>home</first argument>/<second argument>foo</second argument>/<third argument>bar</third argument>/<fourth argument></fourth argument>. Now your completion callback is called with text=““ (fourth argument). This does not work!

Maybe there’s a simple solution by changing the separators used? I didn’t find a way to do that. So I implemented the following workaround. First let’s introduce a function to do completion from filenames

import os

def get_possible_filename_completions(text):
	head, tail = os.path.split(text.strip())
	if head == "": #no head
		head = "."
	files = os.listdir(head)
	return [ f for f in files if f.startswith(tail) ]

def extract_full_argument(line, endidx):
	newstart = line.rfind(" ", 0, endidx)
	return line[newstart:endidx]

The first function extract possible file names from a given input path. If you have files a, b and c in a folder /foo/bar/, passing „/foo/bar/“ to this function will result in the list [„a“, „b“, „c“]. Careful: In order to work together with the cmd completion mechanism splitting arguments at „/“ characters, this function must not return absolute file paths. Assume for a moment we would have written in the above code

return [ head + "/" + f for f in files if f.startswith(tail) ]

What would happen?

We would enter „SOMECOMMAND /foo/bar/a“, then hit TAB. get_possible_filename_completions would receive text=“/foo/bar/a“, split it into head=“/foo/bar“ and tail = „a“. It would then search in „/foo/bar“ and find [„a“, „b“, „c“]. This list would then be filtered and only „a“ would remain. Now, head + „/“ + f would be the full path „/foo/bar/a“. Now comes the important point: the cmd completion mechanism would substitute what it deems to be the argument to be completed, which would be „a“ for the return value of get_possible_filename_completions. So we would end up with „SOMECOMMAND /foo/bar//foo/bar/a“. This is certainly not what we inteded!

The second function is the workaround. It takes the end index for the argument – this is where the cursor is. It then searches from this point on for a space character left of the end index. This way it does not stop at the next „/“ character. It returns the complete argument, which can then be fed to get_possible_filename_completions.

boost python and debug python binary

Today I had to deal with a rather naughty problem. At work, I have a C++ shared library which is made avaible for python using boost::python. In order to track down a segmentation fault in my C++ library , I created a python binary including debug data using
./configure --with-python-debuggingWhen I used the respective python binary, it crashed with a segmentation fault during import of the shared library. With the help of gdb I found out, that a data structure used at a specific point seemed to be screwed up or uninitialized. The memory access using a pointer from that struct caused the segmentation fault. Using a non-debug binary of python, I verified, that it was the debug version of python only, for which the error occured. After some thinking, I came to the conclusion, that the boost shared library might not be binary compatible to the debug version of the python shared library.

And later I found this link

http://www.boost.org/doc/libs/1_44_0/libs/python/doc/building.html

which explains, why there’s a binary incompatibility. Damn, boost python docs reveal the important details in the smallprints! Sometimes I sincerely have the impression that they try to make it hard to use the library from the official documentation alone.

Btw. here they explain, how to debug your module without using a python debug-enabled binary.

http://www.boost.org/doc/libs/1_44_0/libs/python/doc/v2/faq.html#debugging

Python-Ogre build misery I

Oh god, their linux build scripts suck. And the linux installation user guide in the wiki as well. It’s completely useless, because they expect you to download all required libraries and build them – without thinking about the very likely possibility that you already have a lot of those libraries on your system. Let’s cite another frustrated user

i gave up, useless guide.

Why is it so complicated to use an established build system like scons to automate the search for required libraries? No, the python-ogre guys hacked together their own little build system which is lacking the basic ability to recognize that a user has his ogre installation in /usr/local/lib instead of /usr/lib. Oh and if you answer now „ok, then i change it by hand in the build script“ then you will learn that they enforced the use of either /usr/local or /usr for all library access because they derive every f*cking library search path from a single base path. Thanks!

Anki

Some time ago i stumbled across this nice little Python software Anki, which is kind of a digital flash-card board. You can either write your own cards (front and back) or choose from one of the online avaible sets. Myself, I’m at the moment trying to expand my English word pool using „Advanced English Vocabulary – 2000 Sentences“. But Anki is not just showing you the cards but keeping track of your success – that’s why you have to answer, after every card, if this question was hard, medium or easy for you or whether you simply failed. Depending on your answer, the card is put back into the stack of cards for you to learn. The more difficult you deemed the task, the earlier a card reappears. The algorithm doing that is obviously based on established efficient learning strategies. Also Anki introduced new cards into every learning session you pass.

The cards can be freely designed using text, html and even LaTeX. Also there a bunch of plug-ins. For example, you can record speech in order to help learning a foreign language. Apart from all that, Anki is really a nice example of what you can do using Python. 🙂