Scape – a very ninja scripting language


I made a small scripting language that runs in the browser. It is very ninja. To see the ninja, first open Javascript console and write:

function recur() {recur()};recur();

Hopefully it blew the stack. Then type this into the Scape REPL:

def recur() recur(); recur();

When you are convinced it will infinitely loop without blowing the stack, hit ctrl-c to stop further processing.

Rincewinds rave, that is black magic! Also called tail call elimination. Scape code is not evaluated by snarfing functions from Javascript (JS functions do not have tail call elimination before ECMAScript 6), but instead is compiled to its own set of instructions, which are then run on a stack machine (running in the Javascript VM). During parsing Scape functions are checked for whether they can use tail call elimination. If they can, they get different instructions that reuse the existing stack frame.

More magic

Scape has forward mode automatic differentiation as a language feature. Automatic differentiation allows you to compute the derivative of a function, without having to define the derivative explicitly.

Without automatic differentiation, this would be the way to compute the partial derivative of the function f(x,y) =  x^{2}y^{2} for x and y:

def fun(x,y) * (* x x) (* y y);
def diff_fun(x,y) [* (* 2 x) (* y y),* (* 2 y) (* x x)];
diff_fun(4,5);
[200, 160]

With automatic differentiation in Scape, this is how it is done:

def fun(x,y) * (* x x) (* y y);
diff(fun(4,5));
[200, 160]

This is very useful for a number of numerical methods involving derivatives. The feature is currently experimental, it might interact with non-double types in funky ways.

Wai?

Mostly just for fun. I also started toying with the idea to make a safe scripting language for use in networked games. A language and runtime that would allow the player to define custom logic during gameplay without being able to ruin the experience for other players.

A dream would be a personalized Starcraft where it is you and your custom control scripts versus the other player and his scripts.

I hope to create a simple real time multiplayer game to show how I imagine it working. For now, playing with the Scape REPL is the only way to try the language.

Sayōnara

Pear pram construction

My 3 year old daughter’s current favourite book is Jakob Martin Strid’s Den utrolige historien om den kjempestore pæra. In the story a giant pear is made hollow, and eventually turned into a boat. I decided to try and make a similar upright floating pear-boat out of a normal pear. One that my my daughter could play with once finished. Off I went to buy a pear and tools, the pear I ended up with have these specs:

  • Weighs around 238 g.
  • Displaces approximately 225 ml of water. This means it is slightly more dense then water since the weight of that water would be approximately 225 g.
  • Judging from the pears available in the shop, the one I chose was slightly more symmetric then most pears.

In addition to the pear, the tools I used are shown in the image below:

pear-tools
Pear, knife, melon baller (the MVT in pear pram construction), coins, thread.

The first step in pear pram creation, is to cut the windows using a knife. Once that is done carve out the inside using the melon baller. I recommend making the windows close to the top of the pear. If you make them too low they will result in water intake when launched. It is better to create the windows high initially and expand them downwards once you have a feeling for how the pear floats.

After carving out the core and flesh.
After carving out the core and flesh.

Another great reason for making the windows high up is lowering the center of mass. Pears have not yet been cultivated to float upright, and the center of mass is way too high for that. Having a too high center of mass on a ship is catastrophic. In its unmodified form a hollow pear will most likely perform worse then the Vasa on its maiden voyage.

To lower the center of mass even more, it is important to carve out as much as possible of the “roof”. Since the stalk extends into the pear this is difficult. It is easy to ruin the pear if you use too much force; be careful.

Even with the windows high up and a very light roof, the center of mass is still too high. Initially I added coins on the inside as ballast, this worked if I put the pear very carefully into the water, but it was still prone to capsizing.

Pear in bowl
Coins on a thread prevents capsizing. The pear is finally approved for transport of Lego men

To remedy this I moved the center of mass even lower by adding ballast on a thread below the pear. This was done by creating a knot on the thread and using a needle to get it through the bottom of the pear. Then the coins were added as shown in the picture. To ensure that water would not leak along the thread into the pear, I greased the entry points.

In its finished form the pear is quite stable, it could hold a surprising amount of Lego men without capsizing. I never got around  to test adding a sail, but I think it might be stable enough to support a small sail.

Sadly rot is an inevitability facing all pear prams. If you have a great idea for prolonging pear pram life, please leave a comment.

 

 

Artifact-1.0.2

Today I released Artifact-1.0.2 after finally getting my ass around to create a close to fully automated build script for Mac OS X (a topic for another blog post). The full changelog is listed below, but I instead recommend you go get it and try it!

mech-sec-new
New second orb graphics

Changelog:

  1. Added full screen and resolution management in game.
  2. Removed splash screen.
  3. Adjusted difficulties and added new names (Apprentice, Journeyman, Master).
  4. Added additional fire button, allowing better control using a touch-pad.
  5. Redesigned second orb with additional graphics and new behavior.

More in detail:

  1. The splash screen in Artifact was unnecessary and the only issue keeping me from removing it was having in-game window and resolution management.
  2. See above.
  3. The Normal and Hard game difficulties were hardly different in version 1.0.0, while the Not sane difficulty was extremely hard. Now the Apprentice difficulty is much easier then the old Normal, Journeyman is similar to the old Normal, while Master is slightly easier then the old Not Sane difficulty. The change was mainly done to make the initial difficulty easier for new players.
  4. On a touch-pad moving the mouse and clicking might interfere with each other, so I added an alternate fire welder button for those who might prefer that.
  5. The Second orb was very hard to predict and its mechanic felt wrong. The new version is cooler , and most of the time way easier to predict. It also has a slight comeback factor, which is nice in this cutthroat game.

Get 1000 the game

My dad is a great teacher, not too long ago he taught me this game he was having his class play. To play you need a dice, pencils, and paper.

Pencil, paper and dice
All the equipment you need.

The game is quite simple, but complicated to master. It works like this:

  • Everyone draws a 3 by 3 table.
  • The dice is rolled and everyone places the rolled value in one of the empty positions in the table. Everyone has to place the value before the next roll.
  • This is repeated until every position in the table is filled.
  • To find your result you add your rows.

A game
A finished game with score 991.

  • The above table would result in the final sum of 123 + 634 + 234 = 991.
  • The winner is the player with the result closest to 1000. This means that 1001 beats 990 and 951 beats 1051 and so on. It is the distance from 1000 that matters.

To play decent in this game, some knowledge of addition is required. To play well you also need to figure out when it is best to play risky, and when to play safe. This is much harder than it may look.

I really hope that after reading this you will try to play this with your friends. If you have no friends willing to play nearby, you can try my asynchronous version. There you can start a game, and then send your friends a link to join that game. Then they can play whenever they want within a week.

Go play Get 1000

If you want to rejoin a game, your 10 last game links will be stored in your local browser storage for a week. These will be listed in your game list. If you saved a join link, you can also use that to join a game.

Prepare your Welding Blaster; play Artifact

I made a computer game together with Nils Eriksen Meling and Sven Meling; It is named Artifactgo try it! It plays similarly to Barrack, a favourite game from my youth. In addition to the action and strategy found in Barrack, Artifact also adds an aspect of resource management.

blaster
Prepare your Welding Blaster, the Artifact is a cruel mistress

In Artifact, each of 40 levels consists of a screen filled with a variety of different orbs. These orbs must be isolated by you. Once 75% of the playing field has been isolated, the level ends. You are rewarded for playing fast, and for ending the level with a high % of the screen isolated.

crystalsOn
Electricity is key

To accomplish your task you control a dual-direction Welding Blaster that can be transformed to fire vertically or horizontally. When fired, a welding beam will slowly traverse the screen in 2 directions. Once both ends reach a wall, the playing field will be cut, isolating balls on each side of the beam. However, care must be taken not to hit the orbs, as they will create a feedback surge, damaging the Welding Blaster.

future_whole
I hate orbs

Artifact is free and will stay so, but developing and maintaining it is not free. If you enjoy Artifact, I hope you will consider a donation. However, most of all, I hope you enjoy playing it.
If you have problems with installation on the supported platforms, please send a mail to: .

Download Artifact

Useful if caught in overly simplistic space combat

One of my favorite games, and by far the one I used the most time creating content for during my youth is Escape Velocity Nova. The Escape Velocity series are 2D space RPGs, which means there is lots of 2D space combat. In these types of games you typically have three main types of weapons, non-turreted, turreted and homing. Non-turreted and homing weapons are not really that complicated. The non-turreted fire in one direction (typically forward), while the homing weapon typically turns as hard as it can towards the target at maximum speed. Turreted weapons were always a puzzle to me though, they somehow knew where you would be, and fired to intercept your ship. I always wondered how this was done. Some years later during a visualization class (on how to find intersections between geometric primitives) I was wondering if I could use geometric equations to figure out where a spaceship needs to aim its torpedo, if it knows the position and velocity of the target. Below is the solution I came up with. It assumes constant speed for the target and the torpedo. The positions of something moving at constant speed, can be described by this equation where t denotes time, \vec{v} the current velocity and \vec{p_o} is the starting position. This restricts the position of the target to a line, where the position on the line is determined by t.

(1)   \begin{equation*} \vec{p} = \vec{p_o} + \vec{v}t \end{equation*}

For 2 dimensions this is:

(2)   \begin{equation*} \begin{pmatrix}p_x\\p_y\end{pmatrix} = \begin{pmatrix}p_{xo}\\p_{yo}\end{pmatrix} + \begin{pmatrix}v_x\\v_y\end{pmatrix}t \end{equation*}

The possible locations p of a constant speed (s) bullet fired from point c in any direction, are given by this equation, where again time is denoted by t. This restrict the possible positions to a circle which expands with time.

(3)   \begin{equation*} (st)^{2} = (\vec{p} - \vec{c})^{2} \end{equation*}

For 2 dimensions this is:

(4)   \begin{equation*} (st)^2 = (p_{x} - c_x)^2 + (p_{y} - c_y)^2 \end{equation*}

Now inserting the restrictions on p_x and p_y from 2 into 4 gives a polynomial that only depends on t:

(5)   \begin{equation*} (st)^2 = ((p_{xo}+v_xt) - c_x)^2 + ((p_{yo}+v_yt) - c_y)^2 \end{equation*}

Rearranging gives:

(6)   \begin{equation*} s^2t^2 = (p_{xo}-c_x + v_xt)^2 + (p_{yo}-c_y + v_yt)^2 \end{equation*}

Simplifying by setting constants i = p_{xo}-c_x and j = p_{yo} - c_y and moving towards standard form:

(7)   \begin{equation*} s^2t^2 = (i)^2 + 2iv_xt + v_x^2t^2 + (j)^2 + 2jv_yt + v_y^2t^2 \end{equation*}

Rearranging to standard form:

(8)   \begin{equation*} 0 = (v_y^2 + v_x^2 - s^2)t^2 + 2(iv_x + jv_y)t + (i)^2 + (j)^2 \end{equation*}

This is a quadratic equation, with coefficients:

(9)   \begin{equation*} a = v_y^2 + v_x^2 - s^2 \end{equation*}

(10)   \begin{equation*} b=2(iv_x + jv_y) \end{equation*}

(11)   \begin{equation*} c=i^2 + j^2 \end{equation*}

Solving the quadratic equation gives two solution for t, if an answer is positive and has no imaginary part, there is a solution to the problem. Inserting a solution for t in equation 1 gives the x,y coordinates where the torpedo should be aimed, and where it will hit the target. Below is an implementation of this, where the constant speed of the torpedo can be set. If there are two solutions, the smallest t is chosen. If there is no solution (typically because the target it too fast for the torpedo to catch) the torpedo is never launched.  
canvas
As you can see in some cases, this does not take into account the size of the target, only the targets center. This can be remedied by using a representative selection of boundary points of the target instead, and firing if one of them would connect. The solution does also not take into account how fast the target can change direction, or when the torpedo runs out of fuel. This can be handled by not firing if the time from the torpedo is fired to the impact is too long. This method can also quite easily be expanded for an accelerating weapon or target. This will result in a higher degree polynomial though, which are mostly only possible to solve using numerical methods like Newtons's method for example.

The van der Corput sequence

Lately I have been looking for a solid way to create a robust implementation moving a spaceship from one point to another. This turned out to be a hard problem, and led me to a lot of new literature, which included Steven M. LaValle’s Planning Algorithms. Randomly reading from it I found a small gem called the van der Corput sequence.

The van der Corput sequence is useful for sampling in an interval. LaValle discusses it as an option to random sampling within the context of sampling for planning algorithms. I had thought about similar issues in the context of root finding, where I always wondered how to predictably generate a sequence that would distribute samples evenly over an interval, as well as do so in a manner that would not “favor” parts of the interval over others.

One naive way to sample over an interval, is to split the interval in X pieces and do the samples in order. If X is 8 and this method is used the interval would be explored as shown to the left in the figure below (clearly this means the the early parts of the interval will be explored first). Using the van der Corput sequence would result in exploration as seen on the right (which explores the interval much more evenly).

Van der Corput
Naive sampling on the left. Van der Corput sampling on the right. Grey circles show performed samples.

Generating the van der Corput sequence is surprisingly simple and elegant, just flip the bits of the naive sequence as seen in the binary column above. I find this very peculiar, since mirrored donkeys do not normally turn into cheetahs.

The great properties of this sequence is that whenever you end it, it will have explored the interval pretty evenly. A second nice property is that you can easily continue the sequence beyond an initial size, by creating the naive sequence at the position you want to start from, and keep reversing the results.

This method will definitely go into my toolbox of things to consider whenever I am thinking about using random sampling.

Superb toy!

This toy is incredible. It is reasonably easy to construct things, while still providing a challenge once you get the basics. It is suitable for nearly all ages. It says 3+ but if you remove the smaller parts it is suitable for much younger children even though they might just enjoy tearing down your constructs. The absurd thing is that when they do, you wont hesitate to make another one, since building these are way too much fun.

WEDGiTS
WEDGiTS

 

Tips for more robust GPU programs using C++ and OpenCL

When I started programming for the GPU, I struggled to keep my GPU programs robust. This was partly because I was very new to C++ and C. OpenCL is very low level and this in combination with my inexperience led to a lot of not so robust prototypes. While my code worked for prototypes, it was very cumbersome to code and not very reusable.

In this post I will share some of the solutions I found to some of the issues I had. These deal with allocating and releasing memory on the GPU, as well as converting relatively cleanly between STL vector and GPU memory representation.

Simplifying release and allocation of memory

Basic memory allocating on the GPU using OpenCl is done by using the code below. Where memory is a reference to the memory on the GPU.

cl_mem memory = clCreateBuffer(context, CL_MEM_READ_WRITE, 
                               numberOfBytes,NULL, NULL);

To release the memory allocated, the below function has to be called with the memory object as argument.

clReleaseMemObject(memory);

This leads to several ways to leak GPU memory. Especially if your code throws exceptions or does something else which “looses” the reference to the memory object and you forgot to release the memory explicitly.

A way to mitigate this in C++ is to create an object which on initialisation allocates memory, and which when its destructor is called release the memory. This ensures that when the object goes out of scope or is deleted the memory on the GPU is also released. This is basically RAII (Resource Acquisition Is Initialization)

A very basic (leaving out code for copy constructors etc) object for GPU memory would look like this.

class GPUMemory {
private:
    cl_mem memory;
public:
    GPUMemory(size_t e,const cl_context &ctx) {
        memory = clCreateBuffer(ctx, CL_MEM_READ_WRITE, e,
                                NULL, NULL);
    }
    ~GPUMemory() {
        //release if out of scoped or deleted
        clReleaseMemObject(memory);
    }

    /*
     * Copy constructor, copy assignment operator etc goes here 
     * implementation should be according to your need 
     */
}

// Possible usage
void doAwesomeCalculation (size_t size,cl_context &context) {
       GPUMemory map(size,context);
       // Do calculation, throw exceptions, etc
} // Out of scope so GPU memory is released

This means that you do not have to explicitly release memory for every weird way your application could behave, which avoids a lot of code repetition and leak opportunities. As long as the memory in allocated in the correct scope you mostly do not have to think more about it. It should be noted that you should follow rule of three and implement copy constructor and assignment operator as well. The implementation may wary depending on how you want your object to behave. I’ll leave that for another blog post.

From vector to GPU memory

Vector is a very useful data structure when you want something sent to the GPU and back, since everything is stored adjacently in memory, no fetching or disbursing on the CPU side is needed. To convert a vector to the kind of memory object I designed above, this is the code i use:

template  GPUMemory createAndFillMemory(const vector data,
                                                    cl_context context,
                                                    cl_command_queue queue) {
   cl_int err;
   if(data.size() > 0) {
        GPUMemory mem = GPUMemory(data.size(),context);
        err = clEnqueueWriteBuffer(queue, mem.getMemory(), CL_TRUE, 0, mem.getBytes(),
                                       (void*)&data[0], 0, NULL, NULL);

        if(err != CL_SUCCESS) {
            throw runtime_error("Loading buffer failed");
        }
        return mem;
    }
    throw runtime_error("no content in vector");
}

As you can see the GPUMemory object has been extended to use templates, since the use I want in this case is a generic container for some struct. This saves a lot of code since you would need to do this conversion manually for each different struct you are planning to put on the GPU if you do not have a similar method. It also ensures that you do not make offset or type errors when converting to and from the different representations.

The GPUMemory class has also been extended to contain information about the amount of objects added, as well as type size.

Conversion back from GPUMemory object to a vector is done using this function:

template  vector readBackMemory(GPUMemory &data,
                                           cl_context context,
                                           cl_command_queue queue) {
   vector vec(data.getElements(),T());
   cl_int err;  
   if(data.getElements() > 0) {
        err = clEnqueueReadBuffer(queue, data.getMemory(), CL_TRUE, 0, data.getBytes(),
                                  &vec[0], 0, NULL, NULL);
        if(err != CL_SUCCESS) {
            checkError(err);
            throw runtime_error("Content not read back from GPU");
        }
        return vec;
    }
    throw runtime_error("No content in vector");
}

General conversion from a vector containing any object to GPU memory is not something I would recommend. While this is possible using the code above, conversion using these methods should be restricted to primitives and structs of fixed size. You should also avoid pointers, as it makes little sense to send a pointer pointing to objects in CPU memory to the GPU.

There is still room for mistakes as you will see by the following example. When you use memory on the GPU, no metadata carry over from the C++ code. So on the GPU side you are responsible for using the memory you transferred correctly, the methods above only ensure that the copying of memory back and forth from the GPU results in correctly typed and sized arrays.

An example

A simple example can be to copy some particles to the GPU, apply some calculation and then copy the particles back. On the CPU side I then define a particle struct:

struct GPUParticle{
    cl_float3 pos;
    cl_int identifier;
    cl_float3 direction;
};

On the GPU (OpenCL kernel) side, a simple kernel to be applied could look like this:

struct GPUParticle{
    float3 pos;
    int identifier;
    float3 direction;
};

__kernel void copyParticles(
                       global struct GPUParticle * data,
                       global struct GPUParticle * dataOut
                       )
{
    int x = get_global_id(0);
    //do calculation here
    dataOut[x] = data[x];
}

It is important to keep the structs on both sides similar in structure and byte size, so that there are no offset issues (you should run tests for this). This means that data is not type safe when sent and retrieved from the GPU, but I still think that partial type safety is much better then none at all, since this leave much fewer avenues for such errors to occur.

Finally to apply the kernel to the data I create this method:

vector Stuff::testCopy(vector &data) {
    GPUMemory mem = utils.createAndFillMemory(data, context, cmd_queue[0]);

    GPUMemory out = GPUMemory(mem.getElements(),context);

    size_t work_size[1];
    work_size[0] = mem.getElements();

    err  = clSetKernelArg(copyParticles,  0,
                          sizeof(cl_mem), mem.getMemoryRef());
    err |= clSetKernelArg(copyParticles,  1,
                          sizeof(cl_mem), out.getMemoryRef());

    if(err != CL_SUCCESS) {
        utils.checkError(err);
        runtime_error("Kernel setup failed");
    }

    // Apply kernel to data
    err = clEnqueueNDRangeKernel(cmd_queue[0], copyParticles,
                                 1, NULL, work_size, NULL, 0,
                                 NULL, NULL);
    if(err != CL_SUCCESS) {
        utils.checkError(err);
        runtime_error("Calculation failed");
    }
    return utils.readBackMemory(out,context, cmd_queue[0]);
}

There are of course problems where these techniques are not suitable or possible, but I use them a lot and they have made my GPU code much more robust. If you have suggestions for improvement or your own small snippets, please add a comment.

Some of my inspiration for this:
Bjarne Stroustrup Going native 2012