Tag: Javascript

Many languages: Düsseldorf Institute for Music and Media Seminar

Last week was my first official seminar at the Düsseldorf Institute for Music and Media with Julian Rohrhuber filling my new role as Associate Professor in Critical Programming. I wanted to start by introducing the cultures and history of programming, with a focus on the people who invented programming languages and what they were doing if for – from the early mathematicians to the military/space industry and in more recent times the rise of JavaScript from a language that would only ever be used for “animating buttons” to the language with widest reach.

pf

With that in mind I wanted to try teaching a fluxus workshop using planet fluxus, the version that compiles Scheme to JavaScript rather than the native code version. This is now working in a new url with quite a lot of fixes and now quite a lot of testing carried out on it. I’m pretty pleased with the support for webgl – and plan to use it for some upcoming games, other than needing switching on with some versions of Safari, it otherwise seems pretty widespread and fast.

My second day of teaching was followed by a presentation by Ellen Harlizius-Klück and Alex McLean on weaving, ancient mathematics, programming, mythology and music – which provided a great introduction for a meeting we had the next day on an upcoming project bringing these concepts together.

IMG_20140206_165357

Genetic programming egg patterns in HTML5 canvas

Part of the ‘Project Nightjar’ camouflage work I’m doing for the Sensory Ecology group at Exeter University is to design citizen science games we can build to do some research. One plan is to create lots of patterns in the browser that we can run perceptual models on for different predator animals, and use an online game to compare them with human perception.

The problem is that using per-pixel processing in order to generate the variety of patterns we need is hard to do quickly in Javascript, so I’m looking at using genetic programming to build image processing trees using the HTML5 canvas image composition modes. You can see it in action here, and the source is here. Here are some example eggs built from very simple test images blended together, these are just random programs, but a couple of them are pretty good:

random-eggs

A nice aspect of this is that it’s easy to artistically control the patterns by changing the starting images, for example much more naturalistic patterns would result from noisier, less geometric base images and more earthy colours. This way we can have different ‘themes’ for levels in a game, for example.

I’m using the scheme compiler I wrote for planet fluxus to do this, and building trees that look like this:


'("op"
  "lighter"
  ("op"
   "source-in"
   ("op"
    "source-out"
    ("terminal" (124 57 0 1) "stripe-6")
    ("terminal" (42 23 0 1) "dots-6"))
   ("op"
    "copy"
    ("terminal" (36 47 0 1) "stripe-7")
    ("terminal" (8 90 1.5705 1) "red")))
  ("terminal" (108 69 0 1) "green"))

Ops are the blend mode operations, and terminals are images, which include translation and scale (not currently used). The egg trees get drawn with the function below, which shows the curious hybrid mix of HTML5 canvas and Scheme I’m using these days (and some people may find offensive 🙂 Next up is to actually do the genetic programming part, so mutating and doing crossover on the trees.


(define (draw-egg ctx x y program)
  (if (eq? (program-type program) "terminal")
      (begin
        (set! ctx.fillStyle
              (ctx.createPattern
               (find-image (terminal-image program) 
                           image-lib) "repeat"))

        ;; centre the rotation
        (ctx.translate 64 64)
        (ctx.rotate 
            (transform-rotate (terminal-transform program)))
        (ctx.translate -64 -64)

        ;; make the pattern translate by moving, 
        ;; drawing then moving back
        (ctx.translate 
            (transform-x (terminal-transform program))
             (transform-y (terminal-transform program)))

        (ctx.fillRect 
            (- 0 (transform-x (terminal-transform program)))
            (- 0 (transform-y (terminal-transform program)))
            (* 127 2) (* 127 2))

        (ctx.translate 
            (- 0 (transform-x (terminal-transform program)))
            (- 0 (transform-y (terminal-transform program)))))
      (begin
        ;; slightly overzealous context saving/restoring
        (ctx.save)
        ;; set the composite operation
        (set! ctx.globalCompositeOperation (operator-type program))
        (ctx.save)
        (draw-egg ctx x y (operator-operand-a program))
        (ctx.restore)
        (ctx.save)
        (draw-egg ctx x y (operator-operand-b program))
        (ctx.restore)
        (ctx.restore))))

Planet Fluxus

Fluxus now runs in a browser using WebGL. Not much is working yet – (draw-cube), basic transforms, colours and textures. I’ve also built a small site in django so people can share (or perhaps more likely, corrupt) each other’s scripts. Also much inspired by seeing a load of great live coding at the algoraves by Davide Della Casa and Guy John using livecodelab.

fluxuswebgl2

fluxuswebgl

This is a spin off from the work I did a few weeks ago on a silly Scheme to Javascript compiler. It’s still pretty silly, but in order to explain better, first we take a scheme program like this:

;; a tree
(define (render n)
    (when (not (zero? n))
        (translate (vector 0 1 0))
        (with-state
            (scale (vector 0.1 1 0.1))
            (draw-cube))
        (scale (vector 0.8 0.8 0.8))
        (with-state
            (rotate (vector 0 0 25))
            (render (- n 1)))
        (with-state
            (rotate (vector 0 0 -25))
            (render (- n 1)))))

(every-frame 
    (with-state
        (translate (vector 0 -3 0))
        (render 8)))

Then parse it straight into JSON, so lists become Javascript arrays and everything else is a string, also doing minor things like switching “-” to “_”:

[["define",["render","n"],
    ["when",["not",["zero_q","n"]],
        ["translate",["vector","0","1","0"]],
        ["with_state",
            ["scale",["vector","0.1","1","0.1"]],
            ["draw_cube"]],
        ["scale",["vector","0.8","0.8","0.8"]],
        ["with_state",
            ["rotate",["vector","0","0","25"]],
            ["render",["-","n","1"]]],
        ["with_state",
            ["rotate",["vector","0","0","-25"]],
            ["render",["-","n","1"]]]]],

["every_frame",
    ["with_state",
    ["translate",["vector","0","-3","0"]],
    ["render","8"]]]]

Next we do some syntax expansion, so functions become full lambda definitions, and custom fluxus syntax forms like (with-state) get turned into lets and begins wrapped with state (push) and (pop). These transformations are actually written in Scheme (not quite as define-macros yet), and are compiled at an earlier stage. It now starts to increase in size:

[["define","render",
    ["lambda",["n"],
        ["when",["not",["zero_q","n"]],
            ["translate",["vector","0","1","0"]],
            ["begin",
                ["push"],
                ["let",[["r",["begin",
                        ["scale",["vector","0.1","1","0.1"]],
                        ["draw_cube"]]]],
                    ["pop"],"r"]],
            ["scale",["vector","0.8","0.8","0.8"]],
            ["begin",
                ["push"],
                ["let",[["r",["begin",
                        ["rotate",["vector","0","0","25"]],
                        ["render",["-","n","1"]]]]],
                    ["pop"],"r"]],
            ["begin",
                ["push"],
                ["let",[["r",["begin",
                        ["rotate",["vector","0","0","-25"]],
                        ["render",["-","n","1"]]]]],
                ["pop"],"r"]]]]],

["every_frame_impl",
    ["lambda",[],
        [["begin",
            ["push"],
            ["let",[["r",["begin",
                    ["translate",["vector","0","-3","0"]],
                    ["render","8"]]]],
            ["pop"],"r"]]]]]

Then, finally, we convert this into a bunch of Javascript closures. It’s pretty hard to unpick what’s going on at this point, I’m sure there is quite a bit of optimisation possible, though it does seem to work quite well:

var render = function (n) {
    if (!(zero_q(n))) {
        return (function () {
            translate(vector(0,1,0));
            (function () {
                push()
                return (function (r) {
                    pop()
                    return r
                }((function () {
                    scale(vector(0.1,1,0.1))
                    return draw_cube()
                })()))})();
        scale(vector(0.8,0.8,0.8));
        (function () {
            push()
            return (function (r) {
                pop()
                return r
            }((function () {
                rotate(vector(0,0,25))
                return render((n - 1))
            })()))})()
        return (function () {
            push()
            return (function (r) {
                pop()
                return r
            }((function () {
                rotate(vector(0,0,-25))
                return render((n - 1))
            })()))})()})()}};

every_frame_impl(function () {
    return (function () {
        push()
        return (function (r) {
            pop()
            return r
        }((function () {
            translate(vector(0,-3,0))
            return render(8)
        })()))})()})

Then all that’s needed are definitions for all the fluxus 3D graphics calls – the great thing is that these are also written in Scheme, right down to the low level WebGL stuff, so the only Javascript code needed is half of the compiler (eventually this also can be replaced). I was quite surprised at how easy this is, although it is greatly helped by the similarity of the two languages.

Compiling Scheme to Javascript

Recently I’ve been continuing my experiments with compilers by writing a Scheme to Javascript compiler. This is fairly simple as the languages are very similar, both have garbage collection and first class functions so it’s largely a case of reusing these features directly. There are some caveats though – here is an example of the canonical factorial example in Scheme:

(define factorial
  (lambda (n)
    (if (= n 0) 1
        (* n (factorial (- n 1))))))

The Javascript code generated by the compiler:

var factorial = function (n)
{
    if ((n == 0)) {
        return 1
    } else {
        return (n * factorial((n - 1)))
    }
}

Scheme has tail call optimisation, meaning that recursive calls are as fast as iterative ones – in Javascript however, a function that calls itself will gradually use up the stack. The factorial example above breaks with larger numbers so we need to do some work to make things easier for Javascript interpreters. When considering list processing, fold can be considered a core form that abstracts all other list processing. If we make that fast, we can reuse it to define higher order list processing such as filter, which takes a function and a list and returns another list. The function is called on each element, if it returns false it’s filtered out of the resulting list.

(define filter
  (lambda (fn l)
    (foldl
     (lambda (i r)
       (if (fn i) (append r (list i)) r))
     ()
     l)))

Compiling this with an iterative version of fold – which uses a for loop in Javascript, we generate this code:

var filter = function (fn,l)
{
    return (function() {
        var _foldl_fn=function (i,r) {
            if (fn(i)) {
                return r.concat([i])
            } else {
                return r
            }
        };

        var _foldl_val=[];
        var _foldl_src=l;
        for (var _foldl_i=0; _foldl_i<_foldl_src.length; _foldl_i++) {
            _foldl_val = _foldl_fn(_foldl_src[_foldl_i], _foldl_val); 
        }
        return _foldl_val; })()
    }
}

We have to be a little bit careful that variables created by the compiler don’t clash with those of the user’s code, so we have to make really ugly variable names. You also need to be careful to wrap code in closures as much as possible to control the scope. The problem with this is that there is probably a limit to the amount of nesting possible, especially comparing different implementations of Javascript. A interesting project that has got much further than this is Spock. More context to this work and some actual source code soon…

Aniziz: Keeping it local and independent

A large part of the Aniziz project involves porting the Germination X isometric engine from Haxe to Javascript, and trying to make things a bit more consistent and nicer to use as I go. One of the things I’ve tried to learn from experiments with functional reactive programming is using a more declarative style, and broadly trying to keep all the code associated with a thing in one place.

A good real world example is the growing ripple effect for Aniziz (which you can just about make out in the screenshot above), that consists of a single function that creates, animates and destroys itself without need for any references anywhere else:

game.prototype.trigger_ripple=function(x,y,z) {
    var that=this; // lexical scope in js annoyance

    var effect=new truffle.sprite_entity(
        this.world,
        new truffle.vec3(x,y,z),
        "images/grow.png");

    var len=1; // in seconds

    effect.spr.do_centre_middle_bottom=false;
    effect.finished_time=this.world.time+len;
    effect.needs_update=true; // will be updated every frame
    effect.spr.expand_bb=50; // expand the bbox as we're scaling up
    effect.spr.scale(new truffle.vec2(0.5,0.5)); // start small

    effect.every_frame=function() { 
        // fade out with time
        var a=(effect.finished_time-that.world.time);
        if (a>0) effect.spr.alpha=a; 
   
        // scale up with time
        var sc=1+that.world.delta*2; 
        effect.spr.scale(new truffle.vec2(sc,sc));

        // delete ourselves when done
        if (effect.finished_time<that.world.time) {
            effect.delete_me=true;
        }
    };
}

The other important lesson here is the use of time to make movement framerate independent. In this case it’s not critical as it’s an effect – but it’s good practice to always multiply time changing values by the time elapsed since the last frame (called delta). This means you can specify movement in pixels per second, and more importantly means that things will remain consistent in terms of interactivity within reason on slower machines.

Map rendering with OSM and HTML5 canvas

This week I’m trying to get as much code done on the borrowed scenery game as possible – today, fixing the map rendering.

I decided to load map tiles from OpenStreetMaps directly rather than using OpenLayers. This is done quite simply, accessing the millions of pre-rendered png files with URLs in this form:

a.tile.openstreetmaps.org/z/x/y.png

Where x and y are the tile coordinates and z is the zoom level. The question is, given a GPS coordinate – how do you find the right tiles? Luckily the OSM site is very helpful. This is what I’m using, where lat and lon are specified in degrees:

function latlon_to_tile(lat,lon,zoom) {
    with(Math){
        var m=pow(2,zoom);
        var lat_rad=lat*PI/180;
        return [floor((lon+180)/360*m),
                floor((1-Math.log(tan(lat_rad) + 
                       1/cos(lat_rad))/PI)/2*m)];
    }
}

I’m then doing quite a bit of work chopping the images up to create a 4×4 grid of game tiles for each map tile on the fly before the perspective transform. This brought up an issue with processing images loaded from domains other than the current server – try and do anything with the data you’ve loaded other than display it and this happens:

Unable to get image data from canvas because the canvas has been tainted by cross-origin data.

The answer is quite simple, as presumably it’s quite rare for this to actually cause vulnerabilities (perhaps if executing image data in some way?) you can simple add this property to the image:

image.crossOrigin = "anonymous";

And everything works as normal, cross origin data can be treated as if you’ve loaded it locally. I’ve also spent quite a bit of time fiddling around with the scaling to make the street names visible. There will probably be some more image processing to come. I also found another MMO game that used OSM data: Monopoly City Streets.

Websockets vs HTTP

A bit of R&D this morning into websockets. Previous games like Naked on Pluto and Germination X have made use of standard HTTP protocol for their client server communication. This is easy to set up (as a newbie web programmer) and fine for prototyping and proof of concept – but has some serious problems with regard to scale.

The first problem is that the direction is one way, clients always have to call the server in order to get data. This has serious impact on how realtime applications work – as they need poll – “has anything changed yet”… “has anything changed yet”…

More seriously, the server has no real notion of who the client is and what they have received already, so all the data needs to be sent for each poll. This results in duplicate data being sent, and is a waste of bandwidth.

Underlying the HTTP protocol are sockets for sending the data – each request is treated as a distinct event so a socket is created and destroyed to return the response. A better way is to hook into this lower level and use sockets directly – each client then has a unique connection on the server, and data can be sent in both directions. Also the server is told when the socket is disconnected so things can be cleaned up.

On the client side, websockets are a standard part of HTML5 so they are fairly simple to use from Javascript:

socket = new WebSocket('ws://localhost:8001/websocket');
socket.onopen= function() {
    socket.send('hello from client');
};
socket.onmessage= function(s) {
    alert('server says: '+s.data);
};

On the server I’m using Clojure, and after a bit of fiddling around with my own socket server implementation, I found Webbit which takes all the hassle away:

(defn -main []
  (println "starting up")
  (doto (WebServers/createWebServer 8001)
    (.add "/websocket"
          (proxy [WebSocketHandler] []
            (onOpen [c] (println "opened" c))
            (onClose [c] (println "closed" c))
            (onMessage [c j]
                (println "message recieved: " c j)
                (.send c "hello from server"))))

    (.add (StaticFileHandler. "."))
    (.start)))

This approach takes us from perhaps 100’s of simultaneous connections for an online game into more like 10,000 theoretically – so much more into the big league, but also more importantly persistent connections like this allow for some interesting game mechanics.

Fast HTML5 sprite rendering

After quite a lot of experimentation with HTML5 canvas, I’ve figured out a way to use it with the kind of big isometric game worlds used for Germination X which are built from hundreds of overlapping sprites. There are lots of good resources out there on low level optimisations, but I needed to rethink my general approach in order to get some of these working.

It was quite obvious from the start that the simple clear screen & redraw everything way was going to be far too slow. Luckily HTML5 canvas gives us quite a lot of options for building less naive strategies.

A debug view of the game with 10 frames of changes shown with two plant spirits and one butterfly moving around.

The secret is only drawing the changes for each frame (called partial re-rendering in the link above). To do this we can calculate sprites which have changed and the ones they overlap with. The complication is maintaining the draw order and using clipping to keep the depth correct without needing to redraw everything else too.

In the game update we need to tag all the sprites which change position, rotation, scale, bitmap image, transparency etc.

Then in the render loop we build a list of all sprites that need redrawing, along with a list of bounding boxes for each overlapping sprite of the changed sprites that touch them. There may be more than one bounding box as a single sprite may need to be redrawn for multiple other changed sprites.

For each changed sprite:
    Get the bounding box for the changed sprite
    For each sprite which overlaps with this bounding box: 
        If overlapping sprite has already been stored:
            Add the bounding box to overlapping sprite's list 
        Else:
            Store overlapping sprite and current bounding box.
    Add the changed sprite to the list.

Assuming the sprites have been sorted into depth order, we now draw them using the list we have made (we would only need to loop over the redraw list if we built it in depth sorted order).

For each sprite:
    If it's in the redraw list:
        If it's not one of the originally changed sprites:
            Set a clipping rect for each bounding box.
        Draw the sprite.
        Turn off the clipping, if it was used.

With complex scenes and multiple moving objects, this algorithm means we only need to redraw a small percentage of the total sprites visible – and we start to approach Flash in terms of performance for games (I suspect that flash is doing something similar to this under the hood). The code is here, currently written in HaXE, but will probably end up being ported to Javascript.