Vectors or Java arrays for Tetris?

Question

I'm trying to create a Tetris-like game with Clojure and I'm having some trouble deciding the data structure for the playing field. I want to define the playing field as a mutable grid. The individual blocks are also grids, but don't need to be mutable.

My first attempt was to define a grid as a vector of vectors. For example an S-block looks like this:

:s-block {
    :grids [
      [ [ 0 1 1 ]
        [ 1 1 0 ] ]

      [ [ 1 0 ]
        [ 1 1 ]
        [ 0 1 ] ] ]
}

But that turns out to be rather tricky for simple things like iterating and painting (see the code below).

For making the grid mutable my initial idea was to make each row a reference. But then I couldn't really figure out how to change the value of a specific cell in a row. One option would have been to create each individual cell a ref instead of each row. But that feels like an unclean approach.

I'm considering using Java arrays now. Clojure's aget and aset functions will probably turn out to be much simpler.

However before digging myself in a deeper mess I want to ask ideas/insights. How would you recommend implementing a mutable 2d grid? Feel free to share alternative approaches as well.

Source code current state: Tetris.clj (rev452)

Update
With the help of your suggestions and after some tinkering myself I came up with the following:

(defstruct grid :width :height)

(defn create-grid [w h initial-value]
  (struct-map grid
    :width  w
    :height h
    :data   (ref (vec (repeat (* w h) initial-value)))))

(defn create-grid-with-data [w h gdata]
  (struct-map grid
    :width w
    :height h
    :data (ref gdata)))

(defn get-grid [g x y]
  (let [gdata (g :data)
        idx   (+ x (* (g :width) y)) ]
    (gdata idx)))

(defn set-grid [g x y value]
  (let [data  (deref (g :data))
        idx   (+ x (* (g :width) y)) ]
    (dosync (alter (g :data) (fn [_] (assoc data idx value))))))

(defn get-grid-rows [g]
  (partition (g :width) (deref (g :data))))

I like it because it's a more generic solution. If it's totally wrong, or can be improved upon, feel free to say so.

Answer 1

How about a vector of vectors (as in your original approach), stored in a single Atom (or maybe Ref if you need coordinated concurrent updates to the playing field and something else... not very likely for a Tetris game), to be used with update-in? (If you're using a recent snapshot of Clojure (post-1.1), you might consider using vector-of to build your vectors. See (doc vector-of) for details.)

Example code:

(def field (atom (vec (doall (for [_ (range 10)] (vec (repeat 10 false)))))))

(defn set-occupied! [x y]
  (swap! field #(update-in % [x y] (constantly true))))

(defn set-unoccupied! [x y]
  (swap! field #(update-in % [x y] (constantly false))))

(defn toggle-occupied! [x y]
  (swap! field #(update-in % [x y] not)))

Actually the above are just meant to illustrate how you could go about manipulating the board. The real benefit of this approach, however, is that you don't need those destructive (side-effecty) functions in your core logic. Instead, you can write it as a bunch of pure functions taking the current state of the playing field, perhaps together with something to represent the player's input (or lack thereof).

Eventually you'd just need to wrap it in some Java interop code to plug it into your GUI, but that's going to be totally decoupled from your core logic. All in all, it should make for a more pleasant overall experience at no significant performance cost (I mean, how large is your playing field likely to get and how complex are the updates going to be...?).

Answer 2

Using a ref for every cell isn't necessarily a bad idea. Throw all your grid mutations into a dosync and Clojure should take care that each multi-cell update is done atomically. (I don't know if you plan to have multiple threads banging on your grid at once, but it's safe to do so this way.)

Below I use hash-maps as the values of each cell in the grid, because you might want to have it be more than just a boolean occupied/not-occupied; maybe you want to store color info or something. I kept your notation for defining blocks though.

(This version of indexed works with bleeding edge Clojure at the moment. In older versions you can find indexed in clojure.contrib.)

(def indexed (partial map-indexed vector))

(defn make-grid [x y]
  (let [f #(vec (repeatedly %1 %2))
        r #(ref {:occupied? false})]
    (f y #(f x r))))

(defn draw-block [grid x y block]
  (dosync
   (doseq [[i row] (indexed block)
           [j square] (indexed row)]
     (alter (get-in grid [(+ y i) (+ x j)])
            assoc :occupied? (= 1 square)))))

(defn print-grid [grid]
  (doseq [row grid]
    (doseq [cell row]
      (print (if (cell :occupied?) "X" ".")))
    (println)))

(def *grid* (make-grid 5 5))

user> (draw-block *grid* 2 1 [[1 1 0] 
                              [0 1 1]])
nil
user> (print-grid *grid*)
.....
..XX.
...XX
.....
.....
nil

Java Arrays might seem simpler, but they aren't thread-safe and most of the good Clojure functions that operate on seqs are going to un-array your arrays anyways. Mutating a bunch of arrays and objects is definitely not idiomatic Clojure. Java Arrays are usually used for interop with Java libraries.

Answer 3

I think it is totally fine to use a vector of vectors for this. Since you are only probably going to be doing a small number of updates per second I don't think there will be any downside to making the whole playing field immutable.

You will of course need to build some helper functions to manage this data structure, but here are some basic ones to get you started:

(defn make-row [w]
  (vec (for [x (range w)] 0)))

(defn make-grid [w h]
  (vec (for [y (range h)] (make-row w))))

(defn gget [grid x y]
  ((grid y) x))

(defn gset [grid x y v]
  (assoc grid y (assoc (grid y) x v)))

You can probably implement everything else you need using these or something similar.