About runvs

We are runvs, a two person indie game development team and this is our portfolio.

We work solo, as a team or sometimes with close friends. We also like to participate regularly in Ludum Dare and OneGameAMonth.








Reading Code backwards

There is this nice book by Jason Turner called "Copy and Reference Puzzlers". It contains awesome brain teasers. You can do them alone, but they are also a nice warmup for meetings. We started our team meetings with a small competition who gets the right answer first.

Puzzler example

The book contains puzzlers, which read e.g. like the following:

char char_1{'j'};
char_1 = 'c';
char char_3{'s'};
char_1 = 'i';
char char_5{'d'};
char_5 = 'h';
char char_7{'t'};
char_1 = 'x';
char char_9{'p'};
char_1 = 'o';
char char_11{'u'};
std::cout << char_9 << char_11 << char_7 << char_3;

The task is to find the output that is printed by the given code.

The initial approach

My initial approach was to step through the code one line by line. This means reading the puzzlers top-to-bottom, front-to-back. After all, that is what the compiler does or how a debugger works.

However this approach places some high cognitive load on the reader. You need to keep track of all variables. A debugger does this automatically, and of course pen and paper will help. But it requires some effort to stay focussed. Naturally, some of the later puzzlers are way longer - even up to multiple pages. Finally, it is quite annoying to learn that some (in some puzzlers even most) of the variables are not even used for the answer. What a waste of brain power to keep track of all of them throughout the complete code.

The backwards approach

There surely is a better way to solve those types of puzzlers with a low cognitive load and without tracking variables in your head or on paper. This is by reading it back-to-front, or bottom-to-top.

In the given example: First start with the cout statement and pick the char_9 variable. Now follow the code upwards when this variable was changed last. Note that down as the first char of the answer and continue with the next variable, in this case char_11. Not only does this ignore all the variables that are not even needed, it will also allow you to stop for the current char, once you have found the lat time it was set.


While reading bottom-to-top is not a general approach for all source code, I found that it is quite useful also for non-pathologic code. For example I personally found it quite useful for getting a brief understanding of unit tests. Those often follow the "three As" (Arrange, Act, Assert). Mostly you are not interested in all of the details of the "Arrange" part and can simply skip to the assert statement directly. Reading code backwards also helps you to focus on the outcome.

For me it was very nice to experiment with a different approach to reading code.

Remote Team Interactions Workbook Review

Remote Team Interactions Workbook Cover

If you have been somewhere close to software development in the early 2020s, there is no way around the seminal book "Team Topologies". The widely acclaimed book was released in 2019 and describes how to organize teams in a software corporation. While it has an astonishing amount of 1322 ratings on Amazon, there is the 2021 "Remote Team Interactions Workbook" by the same authors, which only has 40 reviews so far.

One more reason to give it a more detailed look. With 63 pages it is rather short and based heavily on "Team Topologies". While you can read it without knowing its big brother, doing so definitely is a big plus.


The book's content is all about the new remote-first working mode, made necessary by the Covid lockdowns, that were imposed in most countries in 2020. The lockdowns radically changed the way of working for many people, especially in the software industry. A switch from working completely in the office to fully remotely was performed during just a few days.

It is in fact a workbook. While it shortly introduces the concepts and ideas, it does not go into full detail on them. There is rather a quite extended reference list - and just from reading 60 pages I got three new books on my wishlist. The focus is on implementing the concepts discussed. There are extensive examples as well as (online) material for you to fill out for your team, accomodated by a "now your turn" section, explaining the steps in detail.

While a lot of the topics are focused on remote-first activities, most of them are generally valid. To name just some of the topics:

  • Team APIs: How does a team interface to other teams? This includes description of artifacts, versioning, communication preferences.
  • Dependency tracking: Which teams depend on which other teams? Which dependencies are blocking, which can be accepted? How long-lived are the dependencies?
  • Team boundaries: How big should teams be? How to organize the communication between teams, especially with messenger tools, like Zoom, Teams, Slack, and others.


For "Team Topologies" I was quite unsure in the beginning how much I would like the book. hint: after a few chapters I was really hooked, because there is an abundance of concepts where I realized "Wow, this is generally helpful, I have not thought about it in this specific way!". For "Remote Team Interactions Workbook" I was immediately hooked on page one by this beautiful comment:

"While some companies have embraced this new reality [covid lockdowns] - ditching their downtown offices and telling staff they can work from home permanently - many other organizations are discovering for the first time that the physical office was covering up poorly defined teams and poorly defined areas of focus, threatening their DevOps transformation efforts and the overall health and success of their business."

Dependency Injection to test

The name OpenALpp suggests that is is directly dependent on the OpenAL functionality. This means that there are lower level calls to OpenAL directly in the code. This makes the code hard to test.

An example for the problem

One example would be the following code in the SoundContext constructor.

  /// call alcOpenDevice (low level function)
  m_device = std::unique_ptr<ALCdevice>(alcOpenDevice(nullptr));

  /// if alcOpenDevice failed, throw an exception
  if (!m_device) {
      throw oalpp::AudioSystemException { "Could not open audio device" };

  /// call alcCreateContext (low level function)
  m_context = std::unique_ptr<ALCcontext>(alcCreateContext(m_device.get(), nullptr));

  // if alcCreateContext failed, throw an exception
  if (!m_context) {
      throw oalpp::AudioSystemException { "Could not create audio context" };

Note: The actual code is a bit more complicated due to custom destructors. This is left out for presentation purposes, but the full code can be found here.

As OpenAL is a C-library there are not points to hook in custom behavior. Thus it is not easy to get the throw statements covered in unit tests, because the alc* functions can not be mocked. Of course one could write system level tests that would remove/block the audio device from the system, which would cause an exception, but that is strongly OS dependent and not very elegant. Additionally the could would still depend on the low level OpenAL library. decoupling the constructor code more from the low level functions would be beneficial.

Dependency Injection to the rescue

There is a very nice way to get the throw statements covered. With that the code can be tested even in simple unit tests. And the changes do not affect the users of the class at all.

I stated above that OpenAL does not provide points to hook in custom behavior. So let's create those hook in points our selves. The rough outline will be that for every low level function we will have a parameter to the constructor (this is called Constructor Injection). This will allow us to hook in custom behavior. The default (for the optional parameters) will be to just use the low level functions.

Prepare the solution

Let's first extract the low level functions into some functions that represent the actual behavior. Those functions will be used later as the local default.

namespace {
auto defaultDeviceFactory()
  return std::unique_ptr<ALCdevice>(alcOpenDevice(nullptr));

auto defaultContextFactory(ALCdevice* device)
  return std::unique_ptr<ALCcontext>(alcCreateContext(device, nullptr));

} // namespace

Additionally there are two using declarations to make the constructor more readable. They basically are just std::functions, which return a std::unique_ptr to the respective low-level type.

using DeviceFactoryT = std::function<std::unique_ptr<ALCdevice>()>;
using ContextFactoryT = std::function<std::unique_ptr<ALCcontext>(ALCdevice*)>;

Using DI in the implementation

The constructor now gets two additional arguments. The default argument is a nullpointer, which indicates that the default function should be used.

The constructor itself now checks for the factory functions. If one of them is a nullptr, the default function is used, otherwise the one provided by the user.

And voila, there are the points to hook in custom code.

SoundContext::SoundContext(SoundContext::DeviceFactoryT deviceFactory = nullptr,
SoundContext::ContextFactoryT contextFactory = nullptr)
  if (deviceFactory == nullptr) {
    deviceFactory = defaultDeviceFactory;
  m_device = deviceFactory();

  if (!m_device) {
    throw oalpp::AudioSystemException { "Could not open audio device" };

  if (contextFactory == nullptr) {
    contextFactory = defaultContextFactory;
  m_context = contextFactory(m_device.get());

  if (!m_context) {
    throw oalpp::AudioSystemException { "Could not create audio context" };

How to test?

The test is now plain simple to write: Provide a function that returns a nullpointer and expect the constructor to throw in that case.

TEST_CASE("Create SoundContext which cannot allocate ALDevice throws", "[SoundContext]")
  SoundContext::DeviceFactoryT factory = []() {
    return std::unique_ptr<ALCdevice>(nullptr);
  REQUIRE_THROWS(SoundContext { factory });


With this Dependency Injection it is now possible to provide custom "replacement" behavior for low level functions. This allows for detailed testing and does not affect the API for the user. They can still default-construct the SoundContext.

Finally this enables the complete set of DI benefits. If you would like to have custom logging, which includes the low level pointers, you could just provide a custom logging decorator. Buffering, security and access control are other possible benefits.

You can find the full PR here. Finally I can strongly recommend the book "Dependeny Injection" amazon link which explains the contents of this article (and much more) in an awesome way. Definitely a great read!

Design Patterns: Decorator

Why and What

Recently I read the book Dependency Injection. One concept that stood out to me was the Decorator design pattern as it elegantly separates conflicting concerns.

The idea is that a cross cutting concern (like security, performance monitoring, validation, logging, caching, ...) can be handled without imposing additional responsibility on the actual implementation. Let's take a look at an example: Logging.

Logging Camera example

The class under investigation is a 2d game camera. The following interface is stripped down to the bare minimum, but conveys the idea. The interface can easily be extended for further functionality.

class CamInterface {
    virtual ~CamInterface() = default;

    virtual Vector2f getCamOffset() = 0;
    virtual void setCamOffset(Vector2f const& newOffset) = 0;

    // more functions, e.g. zoom, rotate, shake, flash, ...

The actual Camera implementation class provides the implementation for those functions. The implementation details are not important here. However it is important, that the Camera implementation class should not know anything about logging. And vice versa, the logging part should ideally not need to know about the underlying implementation details. Both would be a violation of the Single Responsibility Principle (SRP).

The Decorator design pattern solves this in a nice way. First the code, some explanation afterwards:

class LoggingCamera : public CamInterface {
    LoggingCamera(CamInterface& decoratee, LoggerInterface& logger) : 
	  m_decoratee { decoratee }
    , m_logger { logger }
	    m_logger.info("Camera created");

    Vector2f getCamOffset() override
	    return m_decoratee.getCamOffset();
    void setCamOffset(Vector2f const& newOffset) override

    // other functions from the interface

    CamInterface& m_decoratee;
    LoggerInterface& m_logger;

The LoggingCamera class inherits from the CamInterface describe above. Its constructor takes two references, one for the CamInterface and one for the LoggerInterface. The references are stored as private members.

For every interface function the LoggingCamera class does two things: create a log entry delegate the call to the decoratee, possibly returning the provided return value.

How to use this?

Logger logger {}; // Implementation class of LoggerInterface

Camera cam {};
LoggingCamera loggingCamera { cam, logger };

Then every user of the Camera can just use the loggingCamera instead of the real camera.


The Decorator pattern neatly separates the logging concern from the actual Camera implementation. When something in the implementation changes, the LoggingCamera can stay unchanged and if something with the logging changes, the Camera implementation can stay unchanged. This is a very nice separation of concerns.

However there are of course also drawbacks: You need to use Inheritance and all users of the Camera need to only rely on the Interface. Furthermore if a Interface provides a large set of functions, the boilerplate code for the decorator needs to be written multiple times.

Note that because references are stored in the LoggingCamera class, the original camera must live longer than the LoggingCamera.

If you want to see some more examples, please take a look e.g. at Sounds or the StateManager in the JamTemplate.

Code optimization: Merging Colliders

Hi dear readers.

There was no post here for a long time, but I stumbled upon an interesting problem recently that I wanted to share with you: Code optimization.

The most important rule about optimization: Don't do it prematurely. Take action only if you know that something is too slow.

A software developer always has to balance three speeds which contradict each other:

  • a) the runtime speed of the software
  • b) the short term development speed
  • c) the long term development speed

Doing a) will often be counterproductive for b) and c). Also especially c) can have a major impact on a). And of course if you are doing very good at b), a) and c) will suffer a because you are just crunching features.

The project

Together with some friends I participated in the 14th Alakajam Gamejam and we went for Top-Down RPG game where the player charater Fungus McShroom has to defeat the evil crystal lord, Pinky. Play "Funky Trip" here or take a look at the sourcecode (disclaimer: mostly crappy gamejam code).

Of course we massively overscoped, but in the end (and after some post-jam fixes) we were all quite happy with the result, especially after we added quite some quality-of-life updates and proper dialogs.


The problem

At one particular point in the development, our level artist felt really comfortable with the level editor Tiled and created a huge level. Previously we had only levels that fitted one or two screens, now this monster was around 30x30 screens big. That immediately blew our level loading time into space. The crucial part was the calculation of the physical colliders. Each tile has a blocked property and if that property is true, the physics needs to be informed that a collider has to be created.

However we do not want to have one collider per tile, as we have tens of thousands of tiles. This would be an impractical solution. So the colliders have to be merged before they can be given to the physics. In our specific case we had around 15.000 small colliders. The final number of merged colliders was 275 colliders at the end. Pretty impressive, if you ask me.

The following pictures displays the general idea for merging colliders: collider merge

As you can imagine you need to check every collider with every other collider to check if they can be merged. This sounds initially like a O(N^2) problem, which sounds really bad for this specific problem (as it can be solved faster).

Initially the code took about 60 seconds to load a level and provide the final set of colliders. The final time was reduced to around 2 seconds. All times measured on my trusty (but old) gamedeve laptop without proper statistics applied.

Optimization strategies

1. use a fast algorithm

If the algorithm is crap ( O(N^2) in a case where O(N log(N)) would suffice ), your code can be as optimized as you like, it will still be slow. I won't go into details here, as this is a very specific part, most likely not helpful to a lot of people. If you are interested, find the two versions of the algorithms here (new) and here (old). Of course the post-jam algorithm was also properly developed using TDD. My first solution was iterative and thus had to walk over the complete list of small colliders multiple times, merging two of them at a time. While this worked great for small levels it was completely unusable for large levels due to runtime and memory requirements of the algorithm. A smarter and faster approach is to combine as many colliders in one step as possible as it avoids traversing a big vector multiple times.

This got the level loading time down from 60 seconds to around 8 seconds (all times on my laptop). This is the biggest speedup here with a factor of 7.5.

2. the power of hashing

The algorithm was now in place, but the lookup of tiles from the vector still took quite some time. std::unordered_map to the rescue. As tiles need to be looked up regularly (e.g. for merging colliders or later in game for pathfinding), this was a huge improvement. Instead of traversing the complete vector of all tiles every time and checking for the correct position (O(N)), it is way faster to use an unordered_map (basically a hashmap) and use that for lookup (O(1)). The code is pretty simple, all you need to do is provide a custom Hasher for your key, which in this case is just a tile position.


Although this was only a minor improvement for level loading, it made a big change in runtime performance on my machine: Loading time decreased from 8s to around 5 seconds. Not as big as the first one, but still a factor of around 1.6.

3. copies count

When doing optimization, it is important to know where and what to optimize. A profiler can help you with that. For Windows I really enjoyed working with Very Sleepy but of course there are other tools available e.g. google's orbit (win and linux) or cachegrind (linux only and a bit harder to use due to no gui). This performance analysis showed that a lot of time is spent in incref and decref functions. Those are from shared pointers and relate to the reference counter increase and decrease every time a copy of a shared pointer was created.

The simple solution after finding out that issue was to remove unnecessary copies of shared_ptr in inner loops and for temporary objects. The change set is rather simple


But remember this is in an inner loop which gets called 100000s times. So every small bit counts. The results speak for themselves: From 5s to 2s on my machine is a speedup factor of around 2.5. For such a small change this is pretty remarkable.

Of course I am looking forward to feedback and comments.

Arbitrary Precision Integers – converting to integer

This is the second part of the Arbitrary Precision Integer (ABI) workshop. Part one was about the introduction and how to convert integers to ABIs. If you haven't read that one, I suggest you do so now.

This one will be just a short snippet on how to convert our ABI back to a normal integer.

You can find the code in Haxe on github. However, the basic idea is easy to adapt for other languages.

Lets get to work!

The first thing we should do is to check if an integer variable can even hold the number we want to store, or if an overflow would occur. If that is the case, an appropriate warning should be printed. Depending on the use case, you might even thrown an exception.

Now we start by creating an empty integer (the return value) with value 0. We start to iterate through the individual bits of our ABI, starting from the end. This means we start the smallest number 1 and end with the biggest power of 2 that is a part of our integer.

Now we just need to check if the bit we are looking at is true. If this is the case, we add

(1 << i)

to the return value. Here the arrows indicate the bitshift operation (multiplication by a power of two) and i is the position of the bit we are looking at.

After summing up all the powers of two, we can just return the sum and voila: there is our integer.

Arbitrary Precision Integers – creating from normal integers

Some months ago I was in the need for an arbitrary precision integer class for one of my Haxe games. Although the Haxe library is quite exhaustive, there was no such class. So I decided to write my own version, and I learned a lot from that. You can find it on github and in the haxe library system.

They are put to action in the clicker-style game Idle Snowflake And now I want to share all my insights with you.

enter image description here

This tutorial will handle some math stuff. So you should know how basic operators work and you should be familiar with the basics of binary and decimal number representations.

Although my library was written in Haxe, the algorithms and concepts are universal and can be applied in any language.


The requirements for my arbitrary precision integers (API) are:

  • APIs can be created from normal integers
  • APIs can create their string representation in binary as well as decimal
  • An API can be converterd to a normal integer if the size is fitting
  • the usual mathematical operations are possible (+, -, *, /, pow, modulo, left shift, right shift, compare, calc logarithm)
  • Fully tested interface

Negative numbers are not required. I had no special requirements regarding memory or performance. My APIs are written in a way that you can create them as large as possible. However, they might become slow and at some point you might run out of system memory. Optimizations for special use cases are possible, however not required.

Basic representation:

I decided to go for a binary representation of numbers. This was mainly due to the fact that I really like binary numbers. So the basic building block of the API is just

public var values: Array<Bool> = [];

Which is just an array of booleans.

Craete an API from a normal integer

Ok, so lets dig into the first problem: How to create an API from a normal integer. At first we have to check whether the integer we want to create an API from is negative. Because we don't deal with that, I just throw an error in that case.

If the passed integer is zero, than we just return a binary representation which has exactly one false value in the array.

As those easy cases are fixed, we now can tackle the actual work to be done. This will be done in a loop as long as we have treated the complete number. The first thing to do is to check for the end condition, which is just checking if the current value is zero. Then we just break the loop.

If this is not the case, each loop iteration will check for the reminder (modulo) when the number is divided by two. The result can either be zero or one. Thus we either push false or true into the array. After that, the number is rightshifted by one (division by two). This happens until we reached the final representation of two and the number is zero, which will subsequentially exit the loop. As we were pushing to the array from the left, the order of the array has to be reversed to ensure the correct endianess. With this part of the code, we can convert numbers in binary representation. The following list gives an example of some numbers, decimal on the left, binary on the right:

4   =     100
10  =    1010
42  =  101010
100 = 1100100
101 = 1100101

As we can only feed normal integers there is no arbitrary presicion yet, but that will come once we have addition, pow and multiplication, which will be covered in another tutorial.

Planetary motion explained

When KSP was published, planetary mechanics got quite some attention. Coding this on your own is not hard at all and requires just some basic mathematical knowledge. During this tutorial you will learn everything you need to know. A c# console project accompanies this tutorial and can be downloaded from google drive (zip, 40kB). It contains all the code described here and you may use, adapt, modify and use it in your game.

Equations of motion


Let's start simple: Imagine a particle which can move only in one dimension (so to speak: on a line). To describe the motion of this particle all you need are some variables. The first one is, obviously the position x of the particle. That would be all we need, if we just have a look at it at one single moment in time. As we are interested in the so called trajectory of the particle, we need some more variables. One of them is obviously the time t. The other variable required is the velocity v of the particle. The position and velocity would be all we need, if the particle is just moving without any interactions. If we want to have the particle (satellite) be attracted by other objects (planets) we need one more variable which is the acceleration a. In Physics you can show that those three variables are enough to describe the movement of the particle completely deterministic.

Let's have a look at those variables and the equations, which connect them on physical level! As you know, velocity is the change of the position with time. Think about driving a car: your speed (the velocity) is given in kilometers per hour (for the metric unit system) which is exactly what I just wrote: The change of the position in a given time. When you drive 60km/h for one hour, your position will be different by 60 km after that hour. To put that into an equation, we can easily write:

v = delta_x / delta_t

Note that the delta corresponds to a difference. Think about your car at two different points in time: t1 and t2. delta_t is just the difference between them: delta_t = t2 - t1 The same holds for delta_x.

The acceleration is the change of the velocity with time. Think about ads for cars: "Accelerates from 0 to 100 in 15 seconds." 0 and 100 are known to be velocities. So it can be written:

a = delta_v / delta_t

For our one dimensional case all of those variables are numbers (double), but we can easily see, that all the relations are still true if we exchange the scalar values by vectors (of dimension two or three), as the different axis (x, y, z) can be calculated independently.

Setting up those equations

In the final code, we will be interested in the position at a given time. Therefore some refinements of the equations are required. We know the acceleration. from that we can compute the velocity:

delta_v = a * delta_t

as this is just the change in velocity the real velocity will be

v_new = v_old + delta_v

or as it will be written later:

v += a * delta_t

The same is true for the position and the velocity.

delta_x = v * delta_t
x_new = x_old + delta_x
x += v*delta_t

Those equations now tell us, how a new state of the system will look like, based on the old state of the system. Mathematically this is called "integrating the equations of motion".

Newton's axioms

For particles to interact(planets should attract each other) we need to know, how the forces translate into those equations of motion, we just talked about. This physics building block can be derived from Newton's axiom. One of them states that Force equals mass times acceleration. If we put that into an equation it can be written as:

F = m * a.

OK, so what are those F and m values. F is the type of the force we are looking at. If you want to see satellites move around planets, you need the law of gravity. If you want to have a look at electrons and protons, you need Coulomb's law. All we should care about now is that F tells you "what" is acting on the particle and only depends on the position of the particles. The mass m is just the mass of something you can pick up. The more mass it has, the harder it is to make it move. If you want to lift a light feather (low mass), that is easy. If you want to lift a large heavy crate, that's hard. The mass is sort of the "resistance" of the object against being moved.

As we know the Forces of the particles, we can now use that to calculate the acceleration of the particle.

a = F/m

The Gravitational law

Overcoming Gravity is not easy So how does gravity work? I can not give you an explanation to that on a fundamental level, but for what is required here you just need to know that two masses (m1 and m2) attract each other by the following law:

F_G = G * (m1*m2)/(r**2)

G is called the gravitational constant and r is the distance between the two masses (their centers). This distance can be calculated by Pythagoras' theorem in any dimension.

Show me some code already!

So let's put all that physics knowledge to some code!

We need a PhysObject class, which will store those variables and do the computations for us. The constructor just initializes the values. The addForce function will let a force act on the object. The most important part is the update function. Let's have a closer look at that! The update function puts the equations mentioned above into order.

public void update ( double dt )
    vx += ax * dt;
    vy += ay * dt;

    x += vx * dt;
    y += vy * dt;

    ax = ay = 0;

Those are exactly the equations explained above. At the end of the function, we reset the accelerations. This is required, since the particles have moved. As the Forces depend on the positions, we need to calculate them in each step.

So in the main function, we need multiple particles, so we create a list of PhysObjects. Then we can add as many particles with any starting conditions we like.

System.Collections.Generic.List<PhysObject> pobjs = new List<PhysObject>();
    PhysObject p1 = new PhysObject();
    p1.x = 0;
    p1.y = 1.4;
    p1.vx = 1.2;

    PhysObject p2 = new PhysObject();
    p2.x = 0.2;
    p2.y = 0.2;
    p2.m = 100000;
    p2.vx = 0;

Then we need an update loop which calculates as many integration steps as we want. In every step we need to determine the forces which are acting on each particle. This is done by looping over all the other particles and calculating the pairwise forces. The Force calculation depends on the distance, which we can easily calculate. After that we normalize the vector from object 1 to object 2 and use those values for the gravitational law. This yields the force. As we know "actio = reactio" from Newton, we can use this to apply the same force on both particles, just with different signs. This helps to reduce computational cost, as the second iteration loop can start at m+1. All previous particle pairs have already been treated completely.

for (int m = 0; m != pobjs.Count; ++m)
    for (int n = m+1; n != pobjs.Count; ++n)    // note that all particles <m have already been treated.
        PhysObject p1 = pobjs[m];
        PhysObject p2 = pobjs[n];   // get the objects

        double dx = p2.x - p1.x;    // distance in x and y
        double dy = p2.y - p1.y;

        double r = Math.Sqrt(dx * dx + dy * dy);    // euclidean distance

        dx /= r;    //normalized vector
        dy /= r;

        double c = p1.m * p1.m / r / r; // law of gravity is \propto m1*m2/r**2
                                                    // G is set to 1 without loss of generality.

        p1.addForce( dx * c,  dy * c);  // adding forces symmetrically. 
        p2.addForce(-dx * c, -dy * c);

After we have added all the forces, we can now call update. We cannot do the update earlier, as each particle has to know the forces which are acting on it.

// now the forces are calculated. Do the integration step now.
for (int m = 0; m != pobjs.Count; ++m)

A word about numerics

What is written in the code is the most basic numerical integrator, which is called after the mathematician Leonhard Euler. There are multiple versions of that (implicit, explicit) and many other sort of integrators (Midpoint, Runge Kutta (of arbitrary order), Leap Frog, Velocity Verlet, ... ) and all of them have their benefits and drawbacks. The benefit of this explicit Euler method is that it's simple and that it is computationally very efficient. Unfortunately it is not stable at all. For a large system (many particles, and many in the sense of ten thousands), the largest computational effort will be determining the forces, as each body interacts with all other bodies. This is called an N-squared loop. There are ways to boil that down, but they are out of the scope of this tutorial.

Another important point is the time step deltat. The integrator works well if deltat is small. If it is too large, strange things might happen. One of the drawbacks of the Euler method is, that it requires quite a small time step to work. So if strange things happen with your physics, try reducing the time step first.

The Game Jam Survival Guide

Hi there,

Game Jams are a thing! They are a way of life. (quote: Jammer.io)

Title Slide

Participating in a Jam is not hard, though it might contain some pitfalls. To avoid the most common ones, I created this presentation, which was given on 2017-09-30 at the Gaminfection Hackathon in Erlangen.

You can download the slides here (2MB, pdf) .

Interpolation pt.3: Spline Interpolation

This is the third part of the interpolation tutorial series. Here I will finally cover the so called spline interpolation. Part one and part two covered linear interpolation and tweening. Spline interpolation is close to linear interpolation as it works great on arrays of points. So you might want to check out the first part, if you missed it. Again, I will cover most of the mathematical foundation needed to implement the algorithm yourself, as well as provide ready to use code that you may use in your project.

What is spline interpolation?

Let's start from linear interpolation between a set of points. All that is needed for linear interpolation, are the positions (x,y) of the points. Spline interpolation takes this idea one step further. Each point now includes a slope k in addition to the x and y values. This allows not only to fit a linear function (aka a straight line) between the points, but a polynomial of order two. The most simple form of such a polynomial is a parabola. This will make the function smooth (and not zigzag like in linear interpolation) by including higher order terms. In other words, the additional information k will be used to smooth the interpolation function in a smart way.

k is a real valued number. It describes the slope of the tangent of the smooth function at that point. For k = 0, the tangent is horizontal. For larger values of k the tangent will get steeper counter clockwise. For smaller values, the tangent will rotate clockwise. For k equals +/- infinity, the tangent will be vertical (pointing up or down respectively). There are different ways to calculate k values for all points. Three ways will be described later in this tutorial. The smooth interpolation function will go through all points for any k values, but it can occur, that the interpolation function will overshoot.

The Algorithm

The interpolation algorithm is based on the equations introduced in the fist part of the tutorial. At first, the two neighboring points are searched. Then a value t (range 0 to 1) is calculated which describes where in between the two neighboring points the interpolation should be evaluated.

The major change in the algorithm is the calculation of the interpolated value, as the derivatives of the points are taken into account. The idea is to use a second order polynomial and to bring that to the symmetrical form. This means some lines of calculation, but luckily, the equation has been solved by countless maths students for you. And that's it: spline interpolation!

The haxe code is listed below.

private function interpolate (p : Array<SplinePoint>, x : Float ) : Float
  // this is all the same as in the first tutorial
  var pMin : SplinePoint =  new SplinePoint(Math.POSITIVE_INFINITY,0);
  var pMax : SplinePoint =  new SplinePoint(Math.NEGATIVE_INFINITY, 0);
  var pleft : SplinePoint = new SplinePoint(Math.POSITIVE_INFINITY, 0);
  var pright : SplinePoint = new SplinePoint(Math.NEGATIVE_INFINITY, 0);

  for (j in 0... p.length)
    var pt:SplinePoint = p[j];

    if (pt.x < pMin.x) 
      pMin.x = pt.x;
      pMin.y = pt.y;
      pMin.k = pt.k;
    if (pt.x > pMax.x)
      pMax.x = pt.x;
      pMax.y = pt.y;
      pMax.k = pt.k;

    if (pt.x < pleft.x && x < pt.x)
      pleft.x = pt.x;
      pleft.y = pt.y;
      pleft.k = pt.k;

    if (pt.x > pright.x && x > pt.x)
      pright.x = pt.x;
      pright.y = pt.y;
      pright.k = pt.k;

  if (x <= pMin.x) return pMin.y;
  if (x >= pMax.x) return pMax.y;

  // t is the local coordinate between i and i-1. 
  // t must be in the range of [0,1] and can be used for interpolation
  // if t == 0, the point [i-1] is chosen, for t == 1, the point [i] is returned.
  var t : Float  = (x - pleft.x) / (pright.x - pleft.x);

  var a : Float =  pleft.k  * (pright.x - pleft.x) - (pright.y - pleft.y);
  var b : Float = -pright.k * (pright.x - pleft.x) + (pright.y - pleft.y);

  // this would be linear interpolation
  var q : Float = (1.0 - t) * pleft.y + t * pright.y;
  // this is the addition from polynomial of order two
  q += a * t +(b - 2 * a) * t * t + (a - b) * t * t * t;

  return q;

How to set the k values (slope)

There is still one piece of information missing: How to get the derivatives (k). There is, as usual, no one fits it all way to do it. The simplest way to handle this, is to set all k values to 0. This means, that all points given are extremal values (or saddle points). This means there are no overshoots. For some points at the values (20, 200), (200, 400), (300, 110) and (500, 230, 0) the interpolation would look like this. spline interpolation with k = 0

You can also do a type of three point interpolation. This means, k for a point i is calculated as the mean value of the slopes between the points i-1 and i as well as i and i+1. Or you use some sort of forward integration. This is depicted in the following imagenine interpolation with mean k](httenter image title hereine interpolation with mean k")

One Last way to calculate the k values is to do this by solving a linear system of equations. This corresponds to the midpoint interpolation formula. Note that this is the way most spline interpolation libraries handle it and the results look "the smoothest". But since the math is cumbersome, most ready to use libs use some sort of linear algebra framework. There are many very good tutorials on this, and I could not explain better. (remember, this is purely optional)

Interpolation is easy (Summary)

This tutorial series started from linear interpolation, covered tweening and touched spline interpolation in this part. It was meant to give you a broad overview about interpolation and to give you the needed mathematical tools and the understanding of the meaning of the equations. You are free to use or adapt the presented code.

Interpolation pt.2: Tweening

This is part 2 of the interpolation tutorial series. In part 1, linear interpolation was covered between two points and for an array of points. This part covers tweening. Tweening describes how to change a value between two points. In most cases, tweening is used with time as a parameter (like tweening a sprite's alpha from 1 to 0 within a given time).


The basic idea is to have a number of tweening equations. Each equation gets a parameter t between 0 and 1 and produces an output value in the same range. Since all equations work on the same parameter range they can easily be exchanged, which is very helpful in day to day use.

If you want the function to tween not in the range between 0 and 1 but between two arbitrary values A and B, you can do this by the following transformation. f(x) is the tweening function between 0 and 1, g(x) the function between A and B.

g(x) = A + (f(x) /(B-A))

Power of x Functions

Let's dive into the tweening functions! The easiest thing to do is a linear function. But since this is no improvement to the first tutorial part, we will skip that. It is also possible to use functions in the form of f(x) = x^p with p being a positive number. This leads to curves as shown in the picture.

power of x functions

Thos functions are called power of x functions (as they contain only x to the power of p). Linear interpolation is the most simple case with p = 1. For some p there are special numbers, like p = 2 is "square", p = 3 is "cube" and p = 4 is "quad".

More functions

There are many more functions you can use. Instead of the powers of x as described above, you can use trigonometric functions (sin, cos), some exponential functions or some dampened wave equations. This site is a very good overview over all common tweening functions.

Taking a step back

Another nice thing about all tweening equations is that they are cut in half and that you can modify the first and the second part independently. The different types of tweening functions on the website are named with an In/Out/InOut suffifx. This suffix describes whether the tweening starts, ends or starts and ends with the respective equation.

As there are many tweening libraries/code files available, I recommend you try the one fitting to your language. A collection of the equations described above for about 15 different languages is available on Robert Penner's Website.

That's it for the second part of the interpolation tutorial. The third (and last) part will cover spline interpolation.

Interpolation pt.1: Linear Interpolation

Whenever something in a game should vary smoothly between two values this can be done by interpolating. Examples are changing an object's position to make it move from A to B or changing the alpha value of a sprite to fade it in or out of the scene. I tried to learn more about the idea and theory of interpolating, but there is not that much information available that is explained well and captures the math up to a point at which the reader can use it by himself confidently.

About this tutorial

This tutorial is part of a series, which will cover interpolation. At first I want to show you linear interpolation. A second part will cover tweening (often called easing). And the third part will cover the dreaded spline interpolation. The tutorial will empower you to implement interpolation on your own by explaining the math step by step. The code given is in haxe, but is easily applicable to the language of your choice as no advanced libraries or language features are used.

Linear interpolation

Ok, what is this interpolating thing about? At first I want to talk only about linear interpolation. Let's stick with the example of the moving object. A game object should move from A to B in a smooth way, e.g. in a cutscene. You (or your designer) provides the positions A and B (y0 and y1) as well as the time the movement starts (x0) and the time you want to reach position B (x1). Note that the y values do not have to be numbers, but can also be vectors, or if you want to interpolate a rotation, they can even be rotation matrices or quaternions. The x values will always be a number.

If you imagine a coordinate system with the time on the x axis and the position on the y axis, calculating a linear interpolation means drawing a straight line between the two points created by (x0, y0), (x1,y1).

To interpolate between those position you can use the following code. It will calculate a variable q which is the interpolation at the point x.

// first get a value t in the range [0,1].
var t : Float  = (x - x0) / (x1 - x0);
var q : Float = (1.0 - t) * y0 + t * y1;
return q;

The value t is in the range between 0 and 1. If x is equal to x0, t is 0. If x is equal to x1, t is 1. The variable t is then used to calculate the value q, which is in the range y0, y1. This represents an linear interpolation between two points.

Interpolation between multiple points

You can extend the same behavior to an array of points. This is shown in the following code example. SplinePoint is a class that has a x and y value. The function linterp takes an array of those SplinePoints and an x value which indicates where to evaluate the interpolation. The array does not have to ordered.

private function linterp (p:Array<SplinePoint>, x : Float) : Float
    var pMin : SplinePoint =  new SplinePoint(Math.POSITIVE_INFINITY,0);
    var pMax : SplinePoint =  new SplinePoint(Math.NEGATIVE_INFINITY, 0);

    var pleft : SplinePoint = new SplinePoint(Math.POSITIVE_INFINITY, 0);
    var pright : SplinePoint = new SplinePoint(Math.NEGATIVE_INFINITY, 0);

    for (j in 0... p.length)
        var pt:SplinePoint = p[j];

        if (pt.x < pMin.x) 
            pMin.x = pt.x;
    	    pMin.y = pt.y;
        if (pt.x > pMax.x)
            pMax.x = pt.x;
    	    pMax.y = pt.y;

        if (pt.x < pleft.x && x < pt.x)
            pleft.x = pt.x;
    	    pleft.y = pt.y;
        if (pt.x > pright.x && x > pt.x)
    	    pright.x = pt.x;
    	    pright.y = pt.y;
    if (x <= pMin.x) return pMin.y;
    if (x >= pMax.x) return pMax.y;

    var t : Float  = (x - pleft.x) / (pright.x - pleft.x);
    var q : Float = (1.0 - t) * pleft.y + t * pright.y;
    return q;

At first, the points with minimal and maximal x in the array p are searched. If the value x (this is where you want to evaluate the interpolation) lies outside of the values specified in the array, then the value of the most left or right Splinepoint will be returned. Furthermore the closest points to x from the left and right (pleft, pright) are searched. Then the interpolation formulae from above is used to calculate the value between the two points pleft and pright.

linear interpolation The result will look something like this. I added four points (indicated by the red squares) to the array p and called the function to calculate the values in between (white squares).

Ok, that's it for this part. The next part will cover tweening, which will cover mainly interpolating between two points, but with some fancy functions.

Another useful haxe macro

My current game, Dino Guy had a json file 'maps.json', that contained the filepaths to each map. As the game starts, the json file is parsed to an array of strings and all levels are loaded afterwards. But every time I added a map, I had to remember to add it's path to the json file.

This is a screenshot of the game

Dino Guy screenshot

A file list with haxe macros

Some months ago, I wrote a tutorial on a great feature of the haxe programming language. You can find all the basics there. Basically macros are functions that are run at compile time. So here is another cool haxe macro that solved the problem I introduced:

public static macro function getFileList ( folder :String, extension: String) : Expr
    // the list of files to return
    var list : Array<Expr> = [];	
    // read everything that is in the directory
    var content = FileSystem.readDirectory(folder);
    for (s in content)
        // if the file has the correct file extension, add it to the list
        if (s.endsWith(extension))
            var path = folder + s;
            // convert the string to an expr and add it to list
            list.push(macro $v{path});
    // convert Array<Expr> to Expr and return
    return macro $a{list};

This little function will now parse through a directory at compile time and return an 'Array<String>' with all files ending on the correct file extension. Another trick: Using an empty string ('""') as extension will automatically return all files in a folder.

Computational Creativity using Neural Nets


Last week I was giving a talk at Indie Outpost, a meeting of franconian Game Developers. My topic was Computational Creativity using Neural Nets. If you are interested in the slides, you can download them here.

Making cool stuff with Haxe macros

There is a rule in computer science: Whenever a developer learns a new feature, it will be used extensively in his next project.


During the past half year, I worked on many games using HaxeFlixel, for example the platformer Meteor Dave or the action RPG and Ludum Dare project Raiders of the Ancient Technology.

In the process of creating those games, I gained some knowledge of lower level parts of HaxeFlixel and Haxe itself. Just some clarification: Haxe is the programming language, HaxeFlixel is the game framework. In this post, I want to share one of the best features of Haxe with you: macros.

History of macros

If you know C or C++, you probably may have stumbled upon macros yourself. In this family of languages, they are preprocessor directives. It is a simple replace mechanism, that runs before the actual compilation of the code.

Some C++ code might look like this:

#define PI 3.141592
#define MIN(X,Y) ((X) < (Y) ? : (X) : (Y))

Often times, macros are also used for compiler flags or for the famous include guards (prior to pragma once). If you look at the code it looks perfectly fine. Everywhere you write PI in your code, the preprocessor will insert the numeric value. The use of the MIN macro also works (mostly) as intended.

...at least until you don't rely on type safety for the Pi example. The second one is even worse, because consider something like

int c = MIN(a,--b); 

What will be the value of c? Remember, the code will just get substituted. Even worse, depending on the value of a and b, b might even be decremented twice. For a = 3 and b = 4, c will have a value of 2, which is just wrong. On a side note: the modern way of doing this in C++ would be to use constexpr and the template function std::min.

Macros in C++ are a powerful tool, but cumbersome and dangerous. The Haxe language also offers macros, but with improved features like type safety, syntax checks and another connotation that is very powerful.

Macros in Haxe

Haxe macros do not run before the build process, but as a part of it. Thus all Haxe macros are completely type safe, offer syntax validation and meaningful error messages, in contrast to C++ templates. But the best part about macros is, that they allow you to execute and modify code at compile time. Lets check out some examples!


As stated with the rule at the beginning of this post, I wanted to use these macros in some of my projects. Most of the examples are based on the Haxe Code Cookbook.

Showing compile time

When working on some larger projects, it would be nice to have the latest commit message and compile date displayed somewhere in the main menu. This makes it easy to identify which version is currently being tested. You could manually add a version string in a global variable, but that's not what you want, because the string would have to be changed every time you create a build.

This macro can do just that:

// macro function for getting the build date
public static macro function getBuildDate() : Expr
    var d : Date = Date.now();
    var date : String = d.toString();
    return macro $v { date };

This is a static function that has the keyword macro. Despite some peculiar syntax at the end, this looks very familiar. The return value Expr is a macro type and can be understood as a Dynamic at compile time.

The function itself is not very complicated. It gets the current date and converts it to a string. The return statement is somewhat special: since it is a macro function, returning a macro Expr, it needs to create such a type. $v {} is an abbreviation for creating an Expr value object.

And that's it. Congratulations on your first Haxe macro.

Getting the commit hash

The same can be done with the git commit hash or commit message:

var process = new sys.io.Process('git', ['rev-parse', 'HEAD']);
if (process.exitCode() != 0) 
    var message = process.stderr.readAll().toString();
    var pos = haxe.macro.Context.currentPos();
    Context.error("Cannot execute `git rev-parse HEAD`. " + message, pos);
// read the output of the process and create the string expression
var commitHash:String = process.stdout.readLine();
return macro $v{commitHash};

The code block uses sys.io.Process to call git rev-parse HEAD, which retrieves the commit hash. Since this might fail for reasons (e.g. no git repo initialized, git executable not found in path, no commit performed), it will print an error if something went wrong. A nice bonus is, that the error gets a line number, so the compilation error message will show you exactly where you have to look. The return statement works just as in the date example.

To get the last commit message, exchange the process line with

var process = new sys.io.Process('git', ['log', '-1', '--pretty=%B']);

If you are on a Windows machine, make sure the git executable can be found in the path.

A remark about compiler flags

Haxe offers some compiler flags to check whether it is in normal compilation or code completion mode. Because Haxe also evaluates macros during code completion it is advisable to exclude the commit hash. This can be done using a #if display ... #end block to check if you are in code completion mode. I did not add this to the code block due to readability.

Checking JSON during compilation

For games, JSON files are a handy way for configuration and Haxe offers an easy way to parse them. Unfortunately it will throw an exeption and thus crash if the JSON file's syntax is wrong. This is something that could (and should) be checked at compile time.

This is a very handy feature. You can check out the code for this in the Haxe Code Cookbook.

Creating a class from a CSV file

The inspiration for this came from grapefrukt. In most of my projects there is a class called GameProperties which has only static members. It includes variables like Gravity, WorldSizeInTiles, TileSizeInPixel, PlayerMovementSpeed and so on.

It would be super nice to have a CSV File instead that contains all those values. But parsing this at runtime (an push the values to a dictionary) will not allow any code completion when writing code. Again, this can be solved with Haxe macros:

public static macro function addFunctions(file : String) : Array<Field>
  // get the currently available fields
  var fields = Context.getBuildFields();

  // parse the file and split it in separate lines
  var f : String = File.getContent(file);
  var lines : Array<String> = f.split("\n");

  for (l in lines)
    // get the info in the line
    var thisline : Array<String> = l.split(",");
    var myName : String = thisline[0];
    var value : Float = Std.parseFloat(thisline[1]);
    var pos = Context.currentPos();

    // create a new field
    var propertyField : Field = 
      name : myName,
      access : [Access.APublic, Access.AStatic],
      kind: FieldType.FProp("default", "null", macro:Float,macro $v{value}), 
      pos: pos,

    // append the field
  return fields;

The largest part of this code block is just parsing a CSV file and extracting the values from it. One of the more interesting lines is Context.getBuildFields();, which gets the fields of the class where this function is called from. Later, our custom fields will be added to this. The var propertyField is the field that is parsed from the CSV file. We set some access identifiers (fields should be public and static) and tell Haxe this is a property that just returns that parsed value.

If you want to use this, just create an empty class

class MyClass

If the file assets/data/test.csv looks like test, 10 gravity, -9.81

MyClass will now have two properties, called test and gravity, both with the respective values. This is done at compile time, so no performance loss for loading and parsing the file at run time.

The best part is, that this can also be combined with static members in the class. If your IDE supports code completion (like FlashDevelop) all the properties from the class and all that have been parsed from the CSV will show up in code completion.


I hope I could raise your interest for Haxe macros. Of course there are a lot of other applications not mentioned here and a lot of extensions for the examples I provided (like parsing a JSON file instead of a CSV and creating not only floats, but ints, strings or whatever you need). There are also great macro libraries on GitHub that can teach you a lot more about how to use macros.

IGJam Postmortem

Last week the gaming industry met in Cologne, Germany. But besides Gamescom, the largest video games convention, another event took place: IGJam, the first game jam at Gamescom. I was one of the lucky participants. This post is going to be a postmortem about the game Koza i Babushka which was a collaborative project.

The Jam

As I started jamming in 2013 with Ludum Dare and #1GAM, on-site game jams (which means, that you are gathering at a specific location for a game jam) are not what I am used to do. The IGJam was my second on-site game jam. The first one was the very nice SemesterGameJam (mini edition) in June 2016, where I created Clichee Wars.

As the tag (mini edition) implies, SemesterGameJam was not that big. I only realized how big game jams can grow, when I entered the IGJam room at the Koelnmesse conference center. Up to 200 people gathered there to create a game within 48 hours.

IGJam Room

All the people were very nice and I had many interesting discussions. I really liked the jammers being very diverse. Some developers even came from Indonesia. At first I was a little bit afraid of team building, because I knew no one prior to the jam. But the organizers did an awesome job and everybody found a team quickly. I got to work with three very nice game designers on our project. They worked on graphics, level design, animations and so on, while I worked on programming. For sounds and music there was a separate team, which provided excellent work for most of the teams at the jam.

Every jam needs a theme and the IGJam's theme was "Masks", which I personally liked very much.

The Game

We quickly decided to do a game about a russian woman who is looking for her goat. The old woman can use different animal masks (which you have to find first) to gain the animal's power or ability (like jumping higher, getting smaller or seeing in the dark). Using a mask will drain some of your personality, which you can refill in your house. If you loose all of your personality, the game is over for this run. Dangerous spikes and other obstacles also drain personality.

Koza i Babushka Screenshot

Day One

Besides team building and starting the jam on day one, I took some time and checked various booths at Gamescom. This was a great experience, since the last time I visited Gamescom was in 2010. The exhibition was even bigger and really good and inspiring. Back at the jam, we spent the evening with planning our workflow and setting up the basic project.

Day Two

... was the main day for working on the game. We started importing the level, implemented most of the gameplay features (like climbing on ladders, switching mask, losing and refilling energy. etc..) At some point during the day I felt really overwhelmed by the amount of work that would be needed for the game to be completed, but after starting to write down the tasks and removing the finished tasks, I slowly gained the feeling it would be a very nice game.

At the end of day two, there was a feedback round, where we could show our game to the public. Of course none of the games shown there were really finished. The idea to force all teams having a playable prototype after 24 hours is nice, because it forces you to focus on what is important.

The final day

In the morning of the third day there were only a few hours left and I felt like I was really struggling a lot. The game needed a lot of balancing (which mask uses how much energy?) and the cut scenes (mainly intro and outro) had still to be created. I really crunched for working for the last hours, and we finished 11 minutes before the deadline. I am very proud of the final game.

The real post mortem

Every post mortem needs to contain a "good vs. bad" section. Criticizing your own game is hard, but I like doing so, because I learn a lot from looking at one of my games some days after finishing. Yesterday I had some friends at my place who played Koza i Babushka and they mainly support my points.

Ok, so let's start ...

What went wrong

  • Due to time issues on the last day, no one did a play test of the game from start to end. This led to balancing just based on assumptions and gut feeling. It worked out ok-ish, but I had a really bad feeling about this.
  • The game can feel very frustrating due to the high difficulty in the second half.
  • It's permadeath, but we would have needed some sort of checkpoint system. Probably no player is going to play it again after dying 10 steps before the end.
  • Focus: I personally would have loved to be more focused during the jam, especially on the last day. I was jumping between different tasks and solutions, which is not a very relaxed way to work for me.

What went right

  • We created a game in 48 hours as a team that never met before.
  • Working in a team with (game) designers is a great opportunity. We really had a precise idea of how the game should feel and what the player's task would be.
  • Like every time when working with a larger team, it is a great experience to see all the parts of the game coming together the first time we loaded the level
  • The game has a remarkable playtime for being created in 48 hours. The level is large and even a speedrun would need about 5 to 10 minutes.
  • The gameplay mechanics, the puzzles and the level design for the first half of the game is great. Many people told me, they had the feeling of exploring a world. Once they bounced into obstacle, they had to search for the solution and were quite happy when they found it. I think the game can be very rewarding, which is a good thing.
  • Working with a dedicated sound team was awesome. Normally I doodle some melodies in cubase and create some blips and blops in SFXR. But this time, the sound was done by professionals and you can clearly hear that. This adds a lot to the mood of the game.

What's next

The IGJam has been a great experience and I am eager to visit more on-site game jams right away. Next weekend there is Ludum Dare, so August will have been a pretty creative month with three games done.

Publishing a HaxeFlixel Game on Android

Yesterday I released Pig Jumper on Android via the Google Play.

Pig Jumper Screenshot

It is a Game where you help Piggy jump from one to the next platform. It was originally created for the OneHourGameJam. In this gamejam it is the task of the developer to create a game in one hour. Of course Pig Jumper needed some additional polishing and bugfixing (in the original version you could land on the same platform, which would increase your score) after the one hour in the original jam. Porting it to android also took some time, as the jam version was built for the Flash target of HaxeFlixel.

Publishing on Android

For publishing a HaxeFlixel Game on Android via the Play Store there are some additional steps that need to be performed. You can find all of the information provided here on the internet, but I had not found one comprehensive guide which walks a developer through from beginning to start. Some links I recommend:

I assume a more ore less finished game in HaxeFlixel. We will go through the process step by step.

Setting up HaxeFlixel

At first it is a good Idea to update all HaxeFlixel libraries to the newest version. This is done by typing haxelib upgrade. Confirm the questions to upgrade. With haxelib list you can then get a list of all installed Libraries, including the installed and selected (square brackets) versions.

HaxeFlixel has to setup the Android Target. (If you want more information than provided here, there is a nice guide on the website.) This will take some time as a lot of tools have to be installed. Use lime setup android and follow the instructions. Then you need to select an Android SDK Version in the android virtual device managment software. I choose Version 16, since this works on a lot of devices and is compatible to many devices.

Now you can build your project with lime build android (in the respective project folder). This will work for some time. Don't worry. When you call it the first time, all HaxeFlixel Files will be compiled. After that only files that have changed will be compiled, so the process will be much faster.

In the export/android/bin/bin/ folder there will be a [Project Name]-debug.apk file. To get this working on your Android device, you will need to change the smartphone's settings to allow installation from unknown sources (which is not the official Play Store). The exact location of this property depends on your Android version, but you should be able to find it somewhere in the settings. Then you can copy the created apk to your device (by usb, email or ftp, jst get the file on the phone ;) ) and install it. Congratulations, you have created your first Android game!

Your first Android Game

Signing your apk

You will have noticed that the apk file is named ...-debug.apk. For creating a fully publishable release version, you need to sign the file. For signing you need a key. A key can be generated by a java tool, named keytool. You can find this for example in the java installation, that was done when you were setting up the android target.

Go to the bin folder and type:

keytool -genkey -v -keystore YOUR_RELEASE_KEY.keystore -alias YOUR_ALIAS -keyalg RSA -keysize 2048 -validity 10000

You should change the placeholders YOUR_RELEASE_KEY and YOUR_ALIAS to appropriate values. Follow the instructions. I suggest to use a strong password that you store some place safe. This will give you a keystore file.

In your project folder create a new folder, called templates and copy the keystore file here. If you use version control, you should not add the keystore file to it, as someone could spoof you app with this file.

Then open the Project.xml file and add the following line in the android section.

<certificate path="templates/YOUR_RELEASE_KEY.keystore" alias="YOUR_ALIAS" password="XXXX" if="android" unless="debug"/>

Again, use the correct values for the placeholders. Make sure to remove the Project.xml from version control as it contains your password in plain text.

If you build your game now, there will be a ...-release.apk.

Setting App Permissions and package name


When installing the app, the phone asked for some permissions, like network, vibrate or wake up. If you are not using any of those features, you should remove them. Actually, google requires you to remove any permissions you do not use.

This can be done by setting up a file called AndroidManifest.xml. You can find a template in your HaxeFlixel folder. I recommend to use the one from samcodes-admob as this is the most complete one.

Copy this file to the template folder. Now you should remove all of the uses-permission lines. This will get rid of the requirements that are not needed.

Package name

Also make sure, to set the correct package name in the AndroidManifest.xml. If you use com.example.myapp you will not be able to upload it to the Play Store.

Using your own AndroidManifest

One additional line is needed in the Project.xmlfile. Again, in the android part, add

<template path="templates/AndroidManifest.xml" rename="AndroidManifest.xml"/>

This will then use your own Manifest file.

Icon and Pictures

For your app to be memorizable, you want to have an icon. This must have a square size, but no further requirements to size. For example using a 100x100 px image is totally fine. I like to store that image in the assets/images folder.

Again in the Project.xml file, add some lines, like those:

<icon path="assets\images\icon_100.png"/>
<icon path="assets\images\icon.png" size="36" if="android"/>
<icon path="assets\images\icon_100.png" size="100" if="android"/> 

You can use different sizes and Haxe will pick the correct one to use. This is very handy.

When it comes to images: You will need some images for the Play Store. This is a little bit of work, since you need them to be of the correct size. You will need one 512x512 image and one 1024x500 image, and some screenshots of arbitrary size. A promotion video or trailer might also be helpful.

Going Live

You need to get a google developer console account. Google requires a 25$ fee (from a credit card) for setting it up. With that account you can then upload the game and create a store entry with all the images and some nice desctiption. You will also need to do a quick survey on how violent the game is.

After providing all this information you press "publish". This will take some minutes. Then you will be able to find you game in the Store.

Pathfinding Explained

Whenever an object in a game should move from A to B, pathfinding is involved. This is a dreaded topic, but I want to shed light on how to tackle creating a proper and fast pathfinding algorithm. This is an ab initio approach, so you don't have to know anything about pathfinding.

As an easy example I will relate to square tiles, but the method described here can be used for any sort of map and is not even limited to 2D. You can find a Haxe implementation on gamejolt and the relevant part of the source code on pastebin. This method is called A* and you can also find many lots of code examples on google or wikipedia. I encourage you to try this for your own and create your own pathfinding. It is not that hard! :)

Processing Info

As a first step, the information from the map needs to be processed to a set of variables so the algorithm can work with it in an efficient way. The x and y position of each tile is enough to continue. What is needed is a representation of the map as a graph. A graph is a set of nodes that are connected to each other. The absolute positions are not that important. What the algorithm is interested in is the local neighborood of each node. The graph for the square tiles example can be build by spawning nodes on the center of each passable square tile. Any tile that is not passable (like any obstacle) will not spawn a node. To connect the nodes, we want to use the nearest neighbors. For the 2d square tiles all 8 neighboring tiles. If you do not want to have diagonal movement, simply omit these tiles.

Each node needs to have three variables: The travelling distance (which should just be the distance between two nodes. 1 for horizontal and vertival connections, sqrt(2) for diagonal ones.) and the node offset. Normally the offset is 0, but it can be used to tag areas that should be avoided (like if they are in the range of enemy turrets => positive values) or that should be very likely to pass (e.g. to punish going up or down a hill => negative value). Finally the node value will be set by the algorithm and should be initialized to -1.

Forest path

With that we have our graph ready to be processed by the algorithm. From here on, it is safe to forget about the underlying map, as the graph contains everything needed.

Initial Search

The A algorithm requires a list of connected nodes, with one start and one end node. The algorithm checks all neighboring nodes of the start node and sets the respective node values to the node's offset plus the travelling distance. The algorithm will then do a heuristic search (for everyone who is intersted: this is what sets A apart from dijkstra). Use the straight line distance to the end node as a rough estimate. The node with the lowest heuristic value will be examined next. Then start with this new node as the next start node. Every time the node value will be set. The heuristic map will continue to be used over all iterations. It is worth mentioning, that the node value must only be calculated if the node has not been visited previously.

This continues until the end node is hit. If all tiles have been visited and the end this has not been found, there is no connection.

There and back again


The algorithm has found one or multiple paths from start to end. To get a valid succession of tiles as a usable path from that, it must perform a downhill search. Start at the end, which should be the node with the highest node value. From there on, search the neighbouring node with the lowest node value. This will be your next node to visit. Then do this over and over again, until you reach the start node again, which is the node with the lowest node value.

Then the last thing to do is to inverse the ordering.

... also worth mentioning

Since we use a heuristic, it can (and will happen) that not the optimal path will be found. An example would be if there is an obstacle in the way. Then the algorithm might take the long way around it, instead of the short one.

One easy trick to handle this is to swap start and end and calculate the path also the other way round. Then just use the path with the lower summed up node values.

If you are tempted to do pathfinding on a large map, there are many tricks on how to speed this up. One might be to divide your map into large regions and calculating a coarse grained travel map. Then you can use this as a starting point for a refined version.

There is also a dynamic version, which can handle events like a bridge that is no longer passable. This is useful, since you don't have to recalculate the whole path again.

As mentioned above, it is also possible to use any kind of graph, not just square tiles. This will allow for any type of layout, e.g. on hex tiles or on a map, which is not created by tiles at all.

Using irregular tiles

GameCamp Munich and Indie Outpost

Lately there have been two big events for the German game development scene: GameCamp Munich 2016 and Indie Outpost 18. I visited both and presented a 25 minute talk about name generation. If you are interested in the slides, please follow this link.

About 35 people visited Indie Outpost. Another talk was given by a good friend, Lisa about immersion in games and she provided a hands-on show of her bachelor project "Collect" which uses the Oculus Rift. After the talks we had some really nice discussions in a super friendly atmosphere at Coworking Space Nürnberg.

GameCamp was another ball park with about 200 participants. It is a BarCamp, so everyone can give one or multiple talks or prepare a workshop. I learned a lot about very different themes: how to use Facebook, why business cards are important, proper merchandise/giveaways, neuronal networks, "Bastarde" a great text adventure for android and some other great topics. This was a great experience and I can't wait for next year's GameCamp.

Generating Names

What is a name? What makes it unique? What makes you easily identify it as such? How can we intuitively see from which cultural domain it emerges?


For this week its PROCJAM. There are many resources and tutorials available on how to generate levels (like heightmaps or connected rooms). But when it comes to fill these levels with life and personality, not that much information is available. Nevertheless it is a requirement to generate Names for persons, cities, locations, enemies or anything in your game that should be identified uniquely. This task becomes even more interesting, when you want to have distinct names for different cultural or social domains or races. Of course your elvish cities should be named differently from your orc warriors.

Three Methods

In this post I will present three distinct ways to generate names. I will start with the most rigid way and end with the most flexible way. I implemented the second and third method in a C# program. The source code is available on Bitbucket.

Method 1: Lookup lists

The most simple (and not very procedural) way of creating names is just to have a list of names. When you need a name just randomly pick one from the list. If you want to avoid duplication just pop the name.

For different cultural domains it is feasible to have different lists. On the internet there are various lists of names, that can be used free of charge and will yield a large amount of input.

The big drawback of this approach is that you are limited to the names on the lists. Especially if you have some special requirements.

typo screenshot

For Example, for the game Typo I needed names that are more or less difficult to type and thus had to maintain different lists and could not just copy and paste some reference lists.

One large list (most common US citizen names) that I used for my name generation can be viewed here: Name List (bitbucket)

Method 2: Grammar rules

If you want to go one step further and really get a large amount of unique and procedurally generated names, you can use what is called grammar rules. For this you manually specify some rules on how names should be built out of basic blocks.

The most basic building block of names are single characters. But when you start to roll your name by appending randomly selected chars, you will get strange names like "grtnsa" or "mhowz". So we need a little bit more attention to detail here. What works very well is to divide all characters into groups, like consonants, vowels and special characters (inverted commas, e.g. for orc city names).

Then think about an arrangement of this building blocks. What works nice is to alternatingly use consonants and vowels. This will yield reasonable names that can mostly be pronounced correctly. The following list presents some five letter names created by alternating consonants and vowels.

Negic Tadal Caten Fahot Nafot Baber Lenal Warog Firig

Of course you can also create names of other length. If you want to do even better, think about the following: Not all letters of the alphabet occur with the same frequency. Therefore it is useful to aid the generator with a little help in the right direction. On Wikipedia you can find a frequency table that can easily be used to mimic this behaviour.

This Method works even better if you use some larger building blocks. Like fixed suffixes

il, en, ith, son, ... 

that can be concatenated to the names above. Some of them work better with three or four letter names.

What you can also do is some consonant duplication in the middle of the name. Therefore you need additional information, since some consonants can easily be doubled (like "n" or "t") while some can not (like "h" or "x"). Adding duplication the middle consonant in the upper list (with exclusion) and appending some suffix will yield

Neggicil Taddalen Catten Naffotson Babberman Lennalen Warrogil Firrigson

which are also perfectly fine names. Note how on Catten no suffix has been appended, since the last two characters already match one suffix. I encourage you to create your own set of rules. The possibilities are endless though not all rules will generate sensible names.

The big advantage is that this method allows you to generate random names by using some simple rules. The disadvantage is to create distinct cultural domains. A lot can be done with the suffix but again this is some kind of prepared list of words.

Method 3: Monte Carlo names

Monte Carlo methods describe a class of computational algorithms that are based on random decisions. The basic idea for this topic is to start with a name that is composed of completely random characters, which is most likely a bad name. Iteratively throughout the Monte Carlo process the name becomes better and better until it is good enough to hold as a name for a person, city or anything else.

To define bad or good names, we need some criteria, which can be trained by the lists mentioned earlier. This criteria can be anything you like (e.g. number of consonants in a name or how often the same letter appears twice or more). Here I will use two simple concepts: Pairs and Correlations. A pair of length N is just the sequential occurrence of N characters. As an example

Name: helen
Pairs N=2: he el le en
Pairs N=3: hel ele len
Pairs N=4: hele elen

A Correlation just looks N characters forward in the name and reports which chararacter follows in a certain distance

Name: helen
Correlation N=1: h?l e?e l?n
Correlation N=2: h??e e??n   

Where a ? denotes any arbitrary single character.

Armed with Pairs and Correlations and a list of names you can now create the rating function. By analysing all names in the list you will get some frequency table for Pairs and Correlations. For every occurrence (like in the "helen" example above) you add 1 to the respective Pair and Correlation count. As the input data have been real names you want to mimic the behaviour of those names and thus have criteria for good names. The rating function just checks the name it is given and looks for any Pairs and Correlations it has been trained with. For each hit it adds the number that is according to the Pair or Correlation that has been found.

Now we have the rating function and can start creating names. This is like rolling consonants and vowels according to the letter frequency table in the grammar method. You start over with a completely random name. Calculate the current rating of the name. Then exchange a random character in the name with another random character of the letter frequency table. Then calculate the new rating. If this value is better than the old rating, accept the change, otherwise refuse it and undo it. This should be done in a loop (you should make sure that each character has been touched at least some couple of times). After about 100 iterations you will have a very nice name. As Monte Carlo algorithms are iterative, the longer it runs the better the results will get.

Some names that have been created with this method are

Lana Eran Anaara Alan

An interesting fact is that you can feed the rating function lists with different cultures and will get names that follow that cultural rules. (notice how the training with Chinese city names also added ' to the name list).

Orc names: Ogrugu Kug Duguk Trugga
Chinese cities: Qhang Yangua Angsho Ing'ang

The drawbacks of this method are, that you need a list of names that you can feed in the rating function. Also it can be quite expensive to do all those iterations. The number of possible pairs with N=2 are 24*24 (number of characters for the first and the second letter multiplied) are 576. For Pairs with N=3 it is already 13824 and for Pairs with N=4 it is something over three million. Let's assume that only 5 percent of the combinations will occur. Then there is a massive amount of substring checking to be done. If you do many iterations (remember, that is what you need to do to get good names) this can take some time.

Nevertheless the Monte Carlo Name Generator is my favorite as it can produce huge varieties of very nice names that follow a certain cultural trend and is truly procedural.

Cleaning up

As you probably noticed, I did not investigate the questions proposed at the beginning. So far I am still a physicist and not a linguist. But at least I try to answer those questions in the way I have learned (namely statistical methods, numerics, data analysis and correlation functions). The proposed simple criteria for the rating function work surprisingly well - at least for me. It is also stunning that by using a really simple alternating grammar it is feasible to create such names.

I hope you enjoyed reading this tutorial on how to generate names procedurally.