Minicraft Mod: Teleporters

It lives!

Yes, this blog is not dead. I have simply been doing loads of stuff and was way too busy to write about them. Just to give you an impression, I spent between 3 days and two weeks a time in 7 different countries in between this post and the last one…

But this post comes back to the core of this blog. In some small pauses in between all the other things I have started the idea of small programming projects on the side again. And to get into this again, I decided to make a mod of Minicraft, the Ludum Dare entry of famous Minecraft-developer Notch. After finishing Portal 2 recently (I didn’t get around to posting it – I loved it!) the simple idea was to add a teleporter object to the game. Here’s how it looks in the game:

After building a teleporter (or GATEWAY, as the number of characters your item name can have is pretty limited) by combining 5 iron ingots and 2 units of glass), you can deploy it in the world. After you have deployed a second one, they are connected with each other, and using one of them will teleport you to the location of the other one. (Adding more teleporters will make the first one disappear.)

A couple of small notes from this project:

Notch seems to be opposed to the idea of comments. The only comments I can actively remember are commented out parts of the code. On the upside, the code is relatively clear, so after some prodding around and taking the bump of finding out how positions and orientations are saved, adding the rest of the code to the class hierarchy was straightforward.

In general it’s interesting to read other people’s game code, especially for a 2D game. I’m planning to do this more often, especially with source code to several interesting games available (including the other recent Mojang game, Catacomb Snatch).

The only part I couldn’t figure out from looking at the code alone is the way colours are implemented. Especially since the code leads you in the wrong direction when you first look at it. This blog post by mrspeaker helped me a lot there.

Back to the Future Episode 3 – Citizen Brown

Wow it’s been a while. I was really busy in other areas of my life and have spent really little of my time with games. However as a big BTTF fan I’ve enjoyed these games by Telltale a lot so far. Episode 2 was my favourite because it seemed to have the most action and was also closest to the movies so far. Episode 3 in comparison was a bit worse but still managed to capture a lot of the essence of the games. I’m really looking forward to the cameo by actual Michael J. Fox in Episode 5 and also to what Telltale will do with Jurassic Park

Helsing’s Fire

For the record: This is the first iPhone game I played through, and pretty much the first casual game I finished as well.

The idea of the game is that you place a light source/torch inside a level and send out a blast wave from there that destroys enemies. Complexity is introduced by differently coloured enemies which require planning the order in which the enemies are hit and by enemies which are not passive, e.g. which try to destroy the torch after having been hit.

The concept gets a bit old during the last levels. I was constantly expecting levels which required more thinking outside the box, for example having to “sacrifice” one blast wave in order to finish the level later on, but there was nothing like that.

What worked really well was being able to play one one or two minutes at a time, so I often got the iPod out during small breaks or when travelling and played for a couple of levels.

GDC Europe 2010 – Tuesday

The Tao of Level Design: A Study of 3 AAA Games
The first talk on my schedule featured an overview of level design from the level designers of three games: Mirror’s Edge, Alan Wake and Brink.

Eric Chahi and Ronan Bel – Creating a High-Performance Simulation: An Interactive Dynamic Natural World
This presentation featured two views on an upcoming game by Ubisoft featuring a completely deformable world, in which the interactions of water, soil, rock, lava etc. are all simulated in real time, resulting in dynamic creation of rivers, erosion and so on. The central part was the developer describing how computations are done on the current platforms, moving all simulation onto the GPU and making sure that all data is aligned well, resulting in very few cache misses. He mentioned that there is more information available upon request, and they had the following resources on their last slide:

Real-Time Fluid Dynamics for Games

Fast Hydraulic Erosion Simulation and Visualization on GPU

Shape & Structure – from Engineering to Nature

Peter Schickel – Web3D MMORPG with Online Game Engine
Even though the title suggested it, MMORPG wasn’t the main theme of this sponsored talk by Bitmanagement, it was rather an introduction to their suite of software, to which the BS Contact player (their own 3D browser plugin) is central.

Marc Hehmeyer – From J2ME to iOS: Galaxy on Fire 2 on the iPad and iPhone
Some key insights to get from this talk were:
Don’t port from J2ME to iOS, in the end, most of the game has to be developed anew.
Hardware is a lot better (no FPU on most Java phones, Sound support is better, Graphics is powered by a GPU – no need for software rasterizer, new input methods, e.g. touch, accelerometer etc.)
Texture compression can help a lot with keeping the download size small.

Mario Deilmann – Turbo Charge our game with Intel Threading Blocks
A nice introduction to Intel Threading Blocks, which add a layer on top of threads, keeping the low-level stuff from the developers and instead making the units of computation one has to think about while developing more aligned with the actual tasks found in the game and allowing the task scheduler to better scale with the number of cores. Side note, they’re pretty unhappy with the PS3 C++-compiler, which seems to be incapable of supporting the template-based system they use.

Hermen Hulst – Bottled Storm: Game Development Guerilla Style
This keynote sounded more like a story being told, which is appropriate since he seemed to read most of it off of something. He basically retold the history of Guerilla games and the Killzone franchise, pointing out for example which steps they took to improve their ratings which increased from an initial 70 metascore to above 90. One thing they did was identify the 5 weakest points from ratings and commit to making these 5 points the best in the next game in the series.

Kenny Shea Dinkin – You Gotta Fight for your Right to Story: Storytelling from Kids to Casual to Social Games
The talk was started with a comparison between the approaches of Jane McGonigal and Marian Bantjes concerning design. Later in the talk, he stated several times that, regarding storytelling, he always found that the following statement seems to be always true: Content/gameplay drives (meta)structure drives story. As an example, taking an educational game, one should not start with the story, but instead start with the learning content and create a game and story around it. He likened this to MDA (Mechanics, Dynamics, Aesthetics, see this paper).

Andreas Ojerfors – The Untapped Potential of the MMO
He touched on one of the major problems of most MMOs: Trying to follow the Hero’s Journey found in single-player games, the games set out to allow an epic journey through the world, but are unable to offer any lasting change, as can be commonly witnessed by things like quest mobs being killed every 5 minutes or the head of WoW’s Onyxia being hanged in Stormwind every couple of hours.
The line of thought in the presentation was that PVP is one remedy, but, backed up by findings of the daedalus project, many people do not enjoy PVP. One potential way out of this problem is having conflicts between factions which is carried out using PVE: Think of an army of NPCs which attacks castles/towns/… on its own, and which can be strengthened by PVE quests. It’s not the pinnacle of storytelling and will probably lead to endless conflicts which repeat all the time as was pointed out in the Q&A session, but the idea is still good food for thought.

Game Developers Conference Europe 2010 – Monday

Elastons: Moving Least Squares

I’m jumping a bit ahead in the paper since this is the part I’m currently working on (both understanding and implementing). In this post I’ll quickly cover the basic idea of Elastons as I understand it and continue moving towards the Generalized Moving Least Squares approach presented in the paper.

Elastons

The basic idea of how the function describing the displacement of the object is solved numerically is to evaluate it at certain points in space. These points are at the center of a small volume referred to as an Elaston. One part of the paper deals with how the positions, sizes and orientations of the Elastons are determined for any kind of object, but since I will first (and probably only) implement a grid of Elastons, I’ll skip that part.

Moving Least Squares

The next step towards computing the displacement is by using a Moving Least Squares (MLS) approach. The next section is based on a good overview paper by Andrew Nealen (who was working as a tutor in a computer graphics lecture I attended during my studies) which can be found here.

The basic Least Squares approach is used to approximate a function based on some sample values. It uses a polynomial function which is fitted to the samples by minimizing an error function which is squared (therefore the least squares). The minimization problem this is based on can be written down as

where is the approximation function and are the samples for the values . The coefficients of the polynomial can be computed by solving a system of linear equations (see the linked paper for details).

Moving on, Weighted Least Squares (WLS) introduces the idea that the approximation is only computed for an area around a given point, leading to approximation functions that are defined locally.

Finally, Moving Least Squares builds upon WLS in that it constructs a WLS approximation function for each point and evaluates this as the approximation in that point.

Elastons: Basics 3

Energy

The next step after stress and strain is to use them to compute the elastic energy (the energy due to deformations) in the body. It is computed as

(see also “Continuum Systems” on this wikipedia page). So basically the energy in each part of the object is summed up to arrive at the overall energy stored in the body.

Governing Equation

This is pretty much one of the major parts that one needs to understand to implement the method in the paper, I think. The governing equation is the equation that describes how external forces and the state of the object are related. The authors state the governing equation in their paper, shortly below equation 3:

along with the following definitions:

– acceleration

– a damping force

– velocity

W – the elastic energy

– displacement

f – external forces

Governing Equation 2

Looking at another paper by Eric Parker and James O’Brien  (that looks pretty good actually), we find a formulation of this equation when the displacement has been discretized, that is, broken down into small units which define positions at which the displacement is sampled. The displacement and it’s derivates are now vectors, and the values they are multiplied with matrices.

Here, the authors have the nomenclature of as acceleration , as velocity and as displacement. The three matrices are

– damping matrix

– stiffness matrix

Looking at this equation, it reminds me of some other things:

If we remove the damping and stiffness part, we get , which is very similar to the classical way of expressing Newton’s third law. The mass matrix here is the generalization of the mass for a rigid body, in that is defines how each element of the object resists changes in position as measured by the mass. The damping part is computed using the velocity, which reminds one of the way this happens in a spring as defined by Hooke’s law.

The stiffness matrix… Doesn’t really remind me of something else. What I thought when I saw this equation first is that this has to be where the connection between the individual units must happen. If you think about it, the state of all object parts/elastons must be connected. Otherwise, if an object drops onto the ground, the elastons couldn’t “know” that the object is being squashed from it’s own weight. Therefore, the stiffness matrix has to encode the relationships of all elastons, which also makes it (as is clear from the evaluation the authors have carried out) the most expensive computation during the simulation.

What strikes me as odd is that there seems to be no mention in the paper of the damping matrix. Do they not have one? Or maybe it’s too trivial and they feel they didn’t have to mention it. I guess I will see (if and when I actually get this running) if it is missing or not.

In the same paper where the second equation above is from there is a scheme how this equation can be solved:

Here, is the time step, is the velocity at the end of the time step. Keeping in mind that everything here are matrices and vectors, this is equivalent to an equation defining a set of linear equations that can be solved to get the value of . Using the velocity, it is possible to compute the actual displacement at the end of the time step based on the displacement at the start of the time step.

Implementation

Concerning implementation, I haven’t made a bit of progress. The next goal is to write the code to set up a simulation for a voluminous body made up by a grid of elastons. This body will start out in the air, fall to the ground (modelled as a plane) and interact with it (probably by checking each vertex on the outside of the body against the plane). We’ll see how this goes.

Elastons: Basics 2

Stress

After having defined the strain, i.e. the amount of deformation at a point in the object, the authors proceed to define stress, the measure of internal forces acting in the object as a result of strain.

The formula looks benign enough:

but keep in mind that what we see here is actually a 4-tensor , which is basically a 3×3x3×3 construct with 81 entries. Looking at this wikipedia page, we see that only 21 of those entries are independent. is the strain we saw earlier, which looks like a 3×3 matrix with 9 entries.

The funky thing here is the operator, which is defined as tensor contraction. To be honest, I only have a slight understanding of what tensors are in the first place, and this is the first time I actually saw a tensor contraction.

This paper has some of the same definitions as the Elaston paper and also explains the tensor contraction better. In a way we are defining a linear relationship between stress and strain. The tensor determines how the individual entries of the stress and strain tensors are connected.

Implementation issues

I have made some good progress with the implementation issue concerning the CHOLMOD library some days ago. I managed to set up a Visual Studio Solution for compiling it as well as all the dependencies. So far, it seems to work well, being able to compile the demo programs and running them (haven’t checked for correctness yet). The biggest problem was actually compiling the linear algebra library LAPACK, since it requires installing the Intel Fortran compiler and compiling the whole thing. Afterwards, I had to change all names of BLAS (a library associated with LAPACK) functions in CHOLMOD to upper case. No idea why they are not like that in the first place, since in the Fortran files, the names seem to be in upper case. Anyway, it doesn’t look like this part will be a large problem. The larger problem is how to construct the input to the CHOLMOD package…

Concerning this, I think I have worked out the two most important things coming up, how to construct the basis functions for the MLS approach and the mass and stiffness matrices.

Elastons: Basics

I’ll start my reading at section 3 of the paper, since it defines the basic notation used throughout the paper.

Undeformed positions

What we want to do is compute how an object is deformed during a simulation. For this purpose, we have to take the undeformed positions as the starting point. They are referred to as a , with being a vector in curvilinear coordinates. The are defined for the material domain , meaning that we have the undeformed positions of all particles making up the object.

One thing that made me think here is that the coordinates are curvilinear. Examples of curvilinear coordinates are cylinder or spherical coordinates, which are examples for the general property of curvilinear coordinates being defined over axes that are not straight as in Cartesian coordinates. Now, from googling a bit and remembering some conversations e.g. with people studying mechanical engineering, I guess that using curvilinear coordinates can make some equations easier. However, I guess it’s not really important to understand at this point since in section 9.1 the authors state that their implementation doesn’t use curvilinear coordinates.

Deformations

The change in position of the object’s particles is captured by the equation

which defines as the deformations. This shows that, when displaying the body at some point, we will be using the undeformed positions and add the deformations to them.

One thing that I’m not sure about practically is whether the undeformed positions are adjusted at some point. What I mean is that we will begin the simulation with the object in one place and undeformed. Then, the simulation starts. Let’s say the object is hanging in mid-air and drops to the ground due to gravity. This means that the displacements will initially all point downwards. Eventually, the object would have fallen (i.e. moved away from the undeformed position for some time) and therefore globally has a completely different position that initially.

For several purposes (collision detection, culling, …) it would be desirable to know where the object actually is at any point in time. Otherwise, it could be moved away far from it’s undeformed position. I guess one way of doing this is keeping track of the object’s center and adjusting the undeformed and deformed positions from time to time.

Strain

The next definition is that of strain. To quote wikipedia, strain is “the geometrical measure of deformation representing the relative displacement between particles in the material body.” The equation for strain given in the paper is

As noted in the paper, this is a 3×3 tensor, meaning that it is defined at all points of the object and describes the deformation at that point. To this end, the individal entries include the information about the amount of information mapped on all pairs of axes, which is achieved taking the dot product of the directional derivatives.

Implementation Issue

As you might have guessed from the screenshot yesterday, I’m developing on Windows. The downside is that the Cholesky solver referenced in the paper, CHOLMOD, doesn’t have Visual Studio makefiles or precompiled binaries. I tried linking to the cygwin versions of CHOLMOD and it’s dependencies, but that lead to C functions being multiply defined. So I have the possibility of switching to Linux for development or compiling by hand. I’m looking at all the dependencies of CHOLMOD and still haven’t decided if it can easily be done (for example, the LAPACK library is written in Fortran which is not really easy to compile, but for that library I found some precompiled binaries). If I get the thing to compile in the next days I’ll stay on Windows, otherwise I might switch.

New project: Soft body physics

Ok, after finally getting around to finishing another game, it’s also time to get back on track with these small projects.

This time I think I’ll take some inspiration from the keynote delivered at FDG 2010 by Prof. Markus Gross of ETH Zürich, which contained (among other things) the presentation of a paper coming up for SIGGRAPH 2010. The paper is “Unified Simulation of Elastic Rods, Shells, and Solids” and can be found here, along with some implementation notes. It is about a technique to simulate different kinds of deformable objects using the construct of Elastons.

I’ve wanted to give some more involved physics simulation a try, so I guess this is a good chance. I’m not sure if it is too much for one month, but we’ll see.

During the next time, I’ll be posting my progress on working on a demo using this technique and try to explain some of the things in the paper.

Update

No graphics or physics demo would be complete without the famous Stanford Bunny, so my first step was to take the DirectX Tutorial 2 and modify it to load the model. Loading is done by by using the RPly library, which is straightforward enough.

Even though this loading now works, I will probably start with a regular grid as shown in the video accompanying the paper. This saves me the trouble of having to do the sampling and elaston placement as described in the paper.