Badness 10k

Follow me on twitter.

Implementing Snake in Bacon.js

In this post we're going to explore the awesome reactive programming library Bacon.js by implementing the classic game Snake, which you may have played on your Nokia back in the good old days, before this modern fad of "smart" phones that break when you drop them on the floor.

Bacon.js is a javascript library for doing reactive programming, much like Microsoft's Rx. The fundamental abstraction here are observable event streams. Streams are similar to promises, except that they represent a series of multiple events. Using streams allows simple expression of behaviour that span over time and multiple events

Writing a game with streams is a great way to get more familiar with the event stream abstraction. You can go on to use it to structure any asynchronous programming task, such as your ajax or node callbacks.

Note: In this post I'll be using typescript notation for lambdas, e.g. the addition function will be written (x,y) => x + y.

Marble diagrams

When dealing with streams of events we often document the result of operations in terms of marble diagrams. Below is a marble diagram for the merge operation, that takes two event streams, and b and produces a stream containing the events from both streams.

Getting a hold of events

The first thing we need to do is get our hands some events so we have something to play with. For starters we'll skip the keyboard events and timers and just use buttons, so we can step through the game easily.

Bacon.js provides a single integration point with jQuery via the $.fn.asEventStream function. This takes the event name and creates a corresponding event stream as so:

 var clicks = $('#myButton').asEventStream('click')

This, of course, gives us a stream of events that occur each time we click myButton. The contents of the events will be jQuery click-events.

Subscribing

In order to actually do anything with these events we need to subscribe to the event stream. We can do this with the onValue method. This takes a callback to execute for each event from the stream.

clicks.onValue(() => alert('clicked!'))

It might seem confusing that we're already talking about callbacks. Bacon.js is supposed to let us escape from callback hell. However, Bacon lets us manage event streams through various combinators , like the already mentioned merge. We will look at these next. For now we are at least separating the concerns of defining what events take place, and how we react to them.

Here's an example of what we've learned so far, just doing some simple DOM manipulation with jQuery. Of course, this could have been just as easily implemented using a callback.

var go = $('#clickMe').asEventStream('click');
go.onValue (
  () => $('#output').append('clicked!'))

Ok, so hardly amazing. The point of Bacon is to use combinators to structure event streams, so lets take a look at some.

Map

One of the simplest combinators in Bacon is map. This lets us apply a function to the values inside a stream. In the code above we didn't look at the value inside the stream at any point, but that value would have been a jQuery event, as it came from asEventStream.

If the argument to map is not a function, Bacon will assume you mean the constant function which returns that value. This is often useful in combination with asEventStream as we're often not interested in the actual jQuery event.

Scan

Bacon's scan combinator lets us accumulate values. This works a lot like javascript's reduce over arrays, except its asynchronous and produces multiple values over time. To use it, we provide an initial value, and a function to combine values. The stream now contains the aggregated value at each point.

  var clicks = $('#example2 button').asEventStream('click')
  var counter = clicks
    .map(1)
    .scan(0, (x,y) => x + y)
  
  counter.onValue(x => $('#example2 .output').html(x))

Here we use map to create an event stream of ones for each click event. We then chain the scan combinator to create a new event stream containing the accumulated sum.

Merge

We've already seen the merge combinator. To remind you, it merges two event-streams into one containing the events from both streams.

Scanning function effects

Ok, se lets begin our first effort towards implementing the game. One of the most common patterns when using Observables is to use scan to accumulate effects of functions. What this means, is that we create an event stream that contain functions as its values.

Here's a marble diagram containing the functions double and inc, that doubles and increments its arguments, where we scan with function application.

We'll start off by defining the functions we'd like to accumulate. We're going to want to be able to control the snake by changing directions, so we'll define functions for that.

function rotateLeft(pos) {
  return new Vector2(pos.y, -pos.x)
}

function rotateRight(pos) {
  return new Vector2(-pos.y, pos.x)
}

We introduce two buttons for rotating left and right, and get the click event streams.

var lefts  = $("button.left").asEventStream('click')
var rights = $("button.right").asEventStream('click')

var actions = 
   lefts.map(() => rotateLeft).merge(
  rights.map(() => rotateRight))

We now accumulate the effects of the rotations from a starting value, startDirection.

var startDirection = new Vector2(0,1)
var direction = actions.scan(startDirection, (x, f) => f(x))

SampledBy

Sometimes we want to take the events from one stream, but receive events according to another signal. We can do this through the use of the sampledBy combinator.

Technically, Bacon requires you to

Back to the game: In order to get a current position, we need to accumulate the current direction. We'd like to advance the game on a timed signal, we're going to call tick. Lets again define it as the input of a button, before changing it to a timer later.

var tick = $('#tick').asEventStream('click')

Now we'd like to advance the position in the current direction, but with the advances timed according to the tick stream. We make use of the sampledBy combinator.

var currentDirection = direction.sampledBy(tick)

Of course, to get a current position, we now simply scan the current direction from a starting postion, startPosition.

var startPosition = new Vector2(0,0)
var position = currentDirection.scan(
  startPosition, (x, y) => x.add(y))

position.map(Array).onValue(drawSnake)

var lefts  = $('#example3 .left').asEventStream('click'),
    rights = $('#example3 .right').asEventStream('click'),
    tick   = $('#example3 .tick').asEventStream('click')

var actions = 
   lefts.map(() => rotateLeft).merge(
  rights.map(() => rotateRight))

var startDirection = new Vector2(0,1),
    startPosition = new Vector2(0,0)

var direction = actions.scan(startDirection, (x, f) => f(x) )
var position  = direction
  .sampledBy(tick)
  .scan(startPosition, (x,y) => x.add(y));

position.map(Array).onValue(drawSnake)
 

SlidingWindow

Bacon already has a combinator for creating a sliding (or should we say slithering, hur hur) window of the nth latest values. Lets try and apply it.

var snake = position.slidingWindow(3)
snake.onValue(drawSnake)

Ok, so pretty cool, though it only gets us so far, as there is no way to increase the length. We'll need to implement the possibility of eating fruit.

Filter

Take / Skip

The take and skip combinators allows you to take or skip a certain number of elements from the start of an event stream, much in the same way as array slicing.

Event Switching

var applePos = new Vector2(3,3)
var apple = position
  .filter(p => p.equals(applePos)) 
  .take(1)

This gets us the first event where the position of the snake is the same as the position of the apple. But how do we proceed from there? At this point we must somehow "move" the position of the apple, but as Bacon is essentially a functional library, we have no way of doing so in terms of side-effects, which would be more familiar to most programmers.

The solution to this problem will come in terms of event switching, a common and very important idiom in reactive programming. Essentially this lets implement functionality on the type "when x happens, start doing Y". x here will be an event, and Y will be an event-stream of the new events you're interested in.

Of course, the event x will in turn come from some event-stream X, as much of the point of Bacon is that we don't write program in terms of individual events. Event switching is implemented in Bacon primarily through the function flatMapLatest

FlatMapLatest

The flatMapLatest combinator takes an event-stream X, and from each event x in it, maps it to a new event-stream f(x), for a specified function f.

Here we map each numeric event x to the event-stream [x, x+1, x+2]. However, the delays are set such that the next event from the source stream occurs before the x+2 event, so it is skipped. Only on the last event 10, there are no more events from the source stream, so all the events for 10, 11, 12 appear in the output stream

Essentially, when an event x occurs in stream X, the resulting stream "switches" to f(x).

Now, one solution to our problem is to define an event-stream that is recursive in terms of itself. As javascript does not have laziness, we simply promote the apple stream to an argument-less function returning a stream, and pass that function to flatMapLatest

function apple() {
  var applePos = randomPos()
  return position
      .filter(p => p.equals(applePos))
      .take(1)
      .flatMapLatest(apple)
      .toProperty(applePos)
} 

That is, whenever the snake eats the apple, we switch to a new event-stream, which is the same stream as before, but with the apple in a new randomized position. We also call toProperty, which starts the stream with the apple's position. Without this, there would be no values in the stream.

Note that we define the entire behaviour of the apple value here. In a more imperative setting, this value would be updated from a multitude of places in the code as a reaction to the appropriate event. This has some advantages, and some drawbacks in it being less natural to a developer more used to imperative programming.

In fact, event streams are quite similar to values in a spreadsheet, where we might write something like A1 = B1 + C2. The value A1 defines itself in terms of other cells in the spreadsheet, and is never updated from an external location.

Here's what we have so far.

Increasing the length

Ok, so each time we eat an apple we want to increase the length of the snake by one. We want something like the slidingWindow combinator, except we want the window size to grow dynamically according to some other stream, but such a combinator does not exist in Bacon. Time to create our own combinator!

Implementing custom combinators

One typically adds to the Bacon prototype in order to be able to use the nice DSL style we're accustomed to.

Here's how we implement a custom combinator in Bacon. We're going to take as argument an observable that decides the length of the window.

Bacon.prototype.slidingWindowBy(lengthObs) = function() {
  var self = this
  return new Bacon.EventStream(sink => {
    var buf = []
    var length = 0
    
    self.onValue(x => {
      buf.unshift(x)
      buf = buf.slice(length)
      sink(new Bacon.Next(buf))
    })
    
    lengthObs.onValue(n => {
      length = n
    })
  })
}

What we do is simply to return a new event-stream. As argument to the constructor, we give a parameter sink that is a function. We send new events by invoking this function with the next value. Bacon has three type of events, Next, End and Error. Right now we're only interested in the Next type of events, which we specify by create a new Bacon.Next event to wrap the value that we want to send, in this case the current "window".

When we get a length value, we do nothing except for updating the length value, and so we don't call the sink function with anything.

This is of course quite a bit of code for something fairly simple, but I hope you appreciate how we've nicely encapsulated a pattern here, that is easily re-usable later if we'd like. This is typical of coding in this style. Abstracting over streams of events allow us to encapsulate many more behaviours than if we limit ourselves to something like promises.

So below is our, for now, final version of the game. The remaining features are left as an exercise for the reader to familiarize herself further with Bacon.js.

Hope you enjoyed following along in this tutorial. Here's out final version of the game with code. If you want to cheat and check out the finished version, you can play it here.

var lefts  = $('#example3 .left').asEventStream('click'),
    rights = $('#example3 .right').asEventStream('click'),
    tick   = $('#example3 .tick').asEventStream('click')

var actions = 
   lefts.map(() => rotateLeft).merge(
  rights.map(() => rotateRight))

var startDirection = new Vector2(0,1),
    startPosition = new Vector2(0,0)

var direction = actions.scan(startDirection, (x,f) => f(x))
var position  = direction
  .sampledBy(tick)
  .scan(startPosition, function(x,y) { return x.add(y) });

function apple() {
  var applePos = randomPos()
  return 
     position
      .filter(p => p.equals(applePos))
      .take(1)
      .flatMapLatest(apple)
      .toProperty(applePos)
} 

var appl = apple()
var length = appl.map(1).scan(1, (x,y) => x + y )

pos.slidingWindowBy(length)
   .onValue(drawSnake)

appl.onValue(drawApple)