Cody Shepp

Twitter | Github | LinkedIn

Sokoban in ClojureScript

Published on 4/25/2015

For a fun project that was manageable in size, I decided to create a Sokoban clone/demo using ClojureScript and Quil. Quil provides ClojureScript users with a (mostly) idiomatic wrapper around processing.js for creating 2d graphics in the browser using the canvas.

I'm not going to go through my code step-by-step, but I would like to mention a few things I noticed while working on this project.

You can browse the full source code for this project on github.

Note: You can play the game above. Click inside the frame and use the [w], [a], [s], and [d] keys to move the player (@). The goal is to move all of the boxes (X) onto the goals (). If you get stuck, you can reset the game with the [r] key.

Game State and Data Structures

In the early stages of building Sokoban, I went through three separate iterations involving how to store the game's state. All three methods have the same general approach to setting/getting the state, in that the main state data structure is stored in an atom which is derefed and passed to the rendering function once per frame.

I also need a set of functions to get and set data within the state. The most common operations are finding the location of the player, finding the entities that neighbor a tile, and setting the entities at certain indices to reflect player movement.

Finally, all three iterations shared the same way of representing tiles. Each type of tile on the game board was represented by a keyword - :w for wall, :p for player, :g for goal, :b for box, and :n for nothing (empty space).

2d Vector Approach

My first approach to storing the game state was a simple 2d vector. It looked something like this:

[[:w :w :w :w :w :w :w]
 [:w :n :n :n :n :n :w]
 [:w :n :n :b :g :n :w]
 [:w :p :n :n :n :n :w]
 [:w :n :n :n :n :n :w]
 [:w :w :w :w :w :w :w]]

With this representation, the location of a given entity is a vector that contains the index of the column in the inner vector, as well as the index of the row within the outer vector.

In the example above, the player (:p) is located at [1 3] = [x y] = [column row].

If you want to find the location of the player, you need to map over the rows, and see if :p exists in them, and if so, at which index.

This is definitely a doable approach, but it seemed convoluted to I decided to try a different method of organizing the game's state.

Normalized Coordinates Approach

My second attempt centered around the idea of normalizing the coordinates of each entity, and storing them explicitly. It looked something like this:

[{:coords [0 0]
  :entity :w}
 {:coords [0 1]
  :entity :w}
 {:coords [0 2]
  :entity :w}...]

With all of our entities stored in one vector, finding the location of the player becomes easier. I can simply filter the vector with a function that inspects the :entity value for each entity, and checks to see if it's :p.

(filter (fn [x] (= :p (:entity x)))

Likewise, finding the entity at a certain set of coordinates is also easy.

(filter (fn [x] (= [0 0] (:coords x)))

This approach also solves a problem with the 2d vector idea - the player can stand on goal tiles. This means that for any given frame, we might need to render two entities on one tile. We can't do that with the vector approach.

But something still isn't right with this approach. The state is messy and verbose, and I didn't like sifting through the entities as I was building and debugging the game. So, time for approach number three.

Separate Tiles and Entities Approach

My final approach combines some ideas from the first two.

First, I decided to split up the 'entities' and the 'tiles' into two separate structures. This allows for rendering both a "goal" and the player at the same location on the game board. In the rendering function, I just paint all of the tiles first, and then go through and paint the entities.

For the tiles, I decided to represent the game board as a 1d vector. Using some easy math and the width of the board, I can convert a set of coordinates to an index and vice-versa. This also means that finding a certain tile is as easy as .indexOf (more on this in a bit).

For the entities, I decided to just store their index in the game board's 1d vector. Here's what it looks like:

{:tiles [:w :w :w :w :n :n :w :w :g ... ]
 :entities {:players [2]
            :boxes   [6 12]}}

Converting back and forth between an index and a set of coords is just some simple math:

(defn index->coords [a w]
  (let [x (mod a w)
        y (int (/ a w))]
      [x y]))

(defn coords->index [x y w]
  (+ (* y w) x))

Finding neighboring tiles' indices is also simple:

(defn above [i w]
  (- i w))

(defn below [i w]
  (+ i w))

(defn left  [i w]
  (- i 1))

(defn right [i w]
  (+ i 1))

ClojureScript and .indexOf

One slightly annoying thing about working with vectors in ClojureScript is that finding the index at which a value exists is a bit verbose. In Clojure, we can use Java's indexOf method directly, but in ClojureScript, we must convert our vector to a JavaScript array before performing an .indexOf lookup:

(let [coll [:a :b :c :d]]
  (.indexOf (clj->js coll) (clj->js :b)))

It's a minor annoyance (and one that can be abstracted away), but still worth mentioning.

Update Loop and Player Movement

Lastly, I wanted to quickly touch on the method I used to determine how the game state changes when the user presses a key. In Sokoban, we only need to be concerned with the 2 tiles next to the player in the direction they'd like to move.

#  @X####

Given the game state above, let's assume the player wants to move to the right. In order to determine whether or not that's a valid move, we need only look at the next 2 tiles in that direction. The first tile is a box, and we know the player can move a box. The 2nd tile, however, is a wall, and we know that the player cannot move a wall. The move must then be invalid.

I used core.match to determine the validity of moves, as well as the actions that correspond to certain valid moves.

;; n is a vector that contains the next 2 tiles in the direction the player wants to move

(match [n]
    [[:n  _]] ;; move player
    [[:b :n]] ;; move player and box
    [[:b :g]] ;; move player and box
    [[:g  _]] ;; move player
    [[ _  _]] ;; do nothing

I found this a succinct and readable way to summarize Sokoban's game rules.

Thanks for reading! Feel free to tweet @cas002 with any questions/comments.