S-expressions for fun and profit.

26 Jan 2011

So I’m making a turn-based tactics game (think Tactics Ogre, Final Fantasy Tactics, Disgaea, etc.). I need a way to build levels, but I have neither the artistic talent to work in a modelling program or the time to really build myself a level editor.

Since I’m still in the prototyping/flesh out stage, my level needs are pretty simple. The goal I’m shooting for is easier to show than to tell, so take a look:

Map Example

That’s the basic level I’m shooting for at this point. Basically a chessboard with differing heights. It’s inspired by Danc’s Miraculously Flexible Prototyping Tiles. So think Legos, or Minecraft.

I want an easy way to specify this, in just a text file. So what pieces of information do I need at this point?

And because I want to make things pretty:

I’ll need to add more in the future (object placement, unit starting locations, etc), but that’s enough to get going. Let’s take a first pass at a text format for this:

dimensions 12 12
num-layers 2
background "cloudy-sky.png"
light-color #D1AE4D
light-direction -0.1212 -0.4848 0.4848

layer 2 2 2 2 2 2 2 2 2 2
      2 2 2 2 2 2 2 2 2 2
      2 2 2 6 6 2 2 2 2 2
      2 2 2 6 6 2 2 2 2 2
      2 2 2 6 6 6 2 2 2 2
      2 2 2 2 6 6 2 2 2 2
      2 2 2 2 2 2 2 2 2 2
      2 2 2 2 2 2 2 2 2 2
      2 2 2 2 2 2 2 2 2 2
      2 2 2 2 2 2 2 2 2 2

layer 3 5 5 3 3 3 3 3 3 3
      3 5 5 3 3 3 3 3 3 3
      3 5 5 0 0 3 3 3 3 3
      3 5 5 0 0 3 3 3 3 3
      3 5 5 0 0 0 3 3 3 3
      3 5 5 3 0 0 3 3 3 3
      3 5 5 3 3 3 3 3 3 3
      3 5 5 3 3 3 3 3 3 3
      3 5 5 3 3 3 3 3 3 3
      3 5 5 3 3 3 3 3 3 3

Most of those fields are self explanatory. Dimensions are just width and height, light-color is a HTML/CSS style color specifier, the direction is a 3 component vector.

Remember, the level is structured like a collection of legos that all happen to be a uniform size, so we can consider it as a set of flat layers. There are 2 layers in this map, hence num-layers.

Finally, the layer fields give you the actual block layouts. Each number corresponds to a block type in the game code, with 0 representing an empty space. (If you’re curious, 2 is dirt, 3 is grass, 5 is stone and 6 is water). There will be (width * height) numbers following each layer command.

It’s simple and relatively easy to type in by hand. But damn, that means I have to write a parser. I hate writing text parsers. But I have an idea! Let’s try massaging that text format into something a little more structured:

(define-map
 (name "The Blocky River")
 (background "cloudy-sky.png")
 (light-color 209 174 77)
 (light-direction -0.1212 -0.4848 0.4848)

 (dimensions 10 10)
 (layer 2 2 2 2 2 2 2 2 2 2
        2 2 2 2 2 2 2 2 2 2
        2 2 2 6 6 2 2 2 2 2
        2 2 2 6 6 2 2 2 2 2
        2 2 2 6 6 6 2 2 2 2
        2 2 2 2 6 6 2 2 2 2
        2 2 2 2 2 2 2 2 2 2
        2 2 2 2 2 2 2 2 2 2
        2 2 2 2 2 2 2 2 2 2
        2 2 2 2 2 2 2 2 2 2)

 (layer 3 5 5 3 3 3 3 3 3 3
        3 5 5 3 3 3 3 3 3 3
        3 5 5 0 0 3 3 3 3 3
        3 5 5 0 0 3 3 3 3 3
        3 5 5 0 0 0 3 3 3 3
        3 5 5 3 0 0 3 3 3 3
        3 5 5 3 3 3 3 3 3 3
        3 5 5 3 3 3 3 3 3 3
        3 5 5 3 3 3 3 3 3 3
        3 5 5 3 3 3 3 3 3 3))

That is an s-expression (http://en.wikipedia.org/wiki/S-expression). They happen to be super easy to parse and are probably best known as the syntax of the Lisp family of languages. But I still don’t want to write a parser.

Instead, I’m going to fire up a Common Lisp environment and let that handle parsing it:

CL-USER> (with-open-file (f "/Users/jfischer/Desktop/map-sexp.txt")
           (read f))
(MAP (NAME "The Blocky River") (BACKGROUND "cloudy-sky.png")
     (LIGHT-COLOR "#d1ae4d") (LIGHT-DIRECTION -0.1212 -0.4848 0.4848)
     (LAYER 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 6 6 2 2 2 2 2 2 2 2 6
      6 2 2 2 2 2 2 2 2 6 6 6 2 2 2 2 2 2 2 2 6 6 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
      2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)
     (LAYER 3 5 5 3 3 3 3 3 3 3 3 5 5 3 3 3 3 3 3 3 3 5 5 0 0 3 3 3 3 3 3 5 5 0
      0 3 3 3 3 3 3 5 5 0 0 0 3 3 3 3 3 5 5 3 0 0 3 3 3 3 3 5 5 3 3 3 3 3 3 3 3
      5 5 3 3 3 3 3 3 3 3 5 5 3 3 3 3 3 3 3 3 5 5 3 3 3 3 3 3 3))

Now easy as that, instead of a text file I have a data structure that I can pull apart and use to define the level.

First, let’s make a basic container class to hold the information, and a quick function to take the list (s-expression) above and turn it into an instance of that container class.

;; Helper structure to hold the data.  Not really necessary, but it makes
;; the rest of the code cleaner
(defclass blockmap ()
  ((name        :accessor map-name)
   (background  :accessor map-background)
   (light-color :accessor map-light-color)
   (light-dir   :accessor map-light-dir)
   (width       :accessor map-width)
   (height      :accessor map-height)
   (layers      :accessor map-layers :initform (list))))

;; Parse a list of the above form out into a blockmap class
(defun parse-blockmap-list (l)
  (let ((map    (make-instance 'blockmap))
        (fields (cdr l)))
    (loop for item in fields do
         (let ((key (first item))
               (value (second item)))
           ;; This is pretty much just a switch statement.  The format
           ;; has each field as a list with the first value being the
           ;; field name/type.
           (cond ((eq key 'name)
                  (setf (map-name map) value))
                 ((eq key 'background)
                  (setf (map-background map) value))
                 ((eq key 'light-color)
                  (setf (map-light-color map) (cdr item)))
                 ((eq key 'light-direction)
                  (setf (map-light-dir map) (cdr item)))
                 ((eq key 'dimensions)
                  (setf (map-width map) (first (cdr item)))
                  (setf (map-height map) (second (cdr item))))
                 ((eq key 'layer)
                  (push (cdr item) (map-layers map)))
                 (t
                  (format t "Unknown key ~a~%" key)))))
    map))

Now to load a file and turn it into a blockmap object we do:

CL-USER> (defvar my-blockmap (with-open-file (f "/Users/jfischer/Desktop/map-sexp.txt")
                             (parse-blockmap-list (read f))))
#<BLOCKMAP {1003290E21}>
CL-USER> (map-name my-blockmap)
"The Blocky River"
CL-USER> (length (map-layers my-blockmap))
2
CL-USER> (map-layers my-blockmap)
((3 5 5 3 3 3 3 3 3 3 3 5 5 3 3 3 3 3 3 3 3 5 5 0 0 3 3 3 3 3 3 5 5 0 0 3 3 3 3
  3 3 5 5 0 0 0 3 3 3 3 3 5 5 3 0 0 3 3 3 3 3 5 5 3 3 3 3 3 3 3 3 5 5 3 3 3 3 3
  3 3 3 5 5 3 3 3 3 3 3 3 3 5 5 3 3 3 3 3 3 3)
 (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 6 6 2 2 2 2 2 2 2 2 6 6 2 2 2 2
  2 2 2 2 6 6 6 2 2 2 2 2 2 2 2 6 6 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
  2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2))

Sweet, now all that’s left is to make it easily available to C. We could probably just write out .c files, but generating the proper syntax for that sounds tedious, so I’m just going to write out a binary format that we can load easily. Something like:

struct BlockMapFile
{
    uint8_t  magic;              // Identify the file type
    uint8_t  version;            // Cause you know you'll need it
    char     title[256];         // Fixed length strings make life happy
    char     background[256];
    uint32_t light_color;        // ARGB light color ready to drop into OpenGL
    float    light_direction[3]; // 32-bit floats written out as uint32s;
    uint8_t  num_layers;         // Dimensions of the layers
    uint8_t  width;
    uint8_t  height;
    uint8_t  layers[1];          // num_layers * width * height entries
};

// NOTE: Depending on the compiler you may need to worry about structure
// field alignment.  For GCC, add __attribute__((packed)) to the end
// of the above structure definition.

That can be loaded in one shot with a simple fread() or [NSData dataWithContentsOfFile:];. From there, just verify that the magic/version is good and you’re good to go.

To write that out from Common Lisp, we’ll need to pull in an extra library to deal with encoding floating point values. I use Marijn Haverbeke’s ieee- floats. With that, the code to write out a binary block map file looks like this:

(defparameter *blockmap-magic* 123)
(defparameter *blockmap-version* 1)

;; Take a blockmap object and write it out to a file.
(defun write-blockmap (map filename)
  (with-open-file (f filename
                     :direction :output
                     :element-type '(unsigned-byte 8)
                     :if-exists :supersede)
    ;; Write out the header
    (write-byte *blockmap-magic* f)
    (write-byte *blockmap-version* f)

    ;; Then the title and background strings
    (write-sequence (make-c-string (map-name map)) f)
    (write-sequence (make-c-string (map-background map)) f)

    ;; Light color
    (write-int32 (make-argb (map-light-color map)) f)

    ;; Light direction
    (write-int32 (ieee-floats:encode-float32 (first (map-light-dir map))) f)
    (write-int32 (ieee-floats:encode-float32 (second (map-light-dir map))) f)
    (write-int32 (ieee-floats:encode-float32 (third (map-light-dir map))) f)

    ;; Layer information
    (write-byte (length (map-layers map)) f)
    (write-byte (map-width map) f)
    (write-byte (map-height map) f)

    ;; And the layers themselves
    (loop for layer in (map-layers map) do
         (let ((data (make-array (* (map-width map) (map-height map))
                                 :element-type '(unsigned-byte 8)
                                 :initial-contents

I’ve left out some helper functions (make-c-string, write-int32 and make-argb); they’re in the source package linked below. But really, that’s all there is to it.

So technically yes, I wrote a parser. But the language did all the hard work for me; I just took the data it provided and chucked it into a binary file. And importantly, it’s extremely easy to add/remove fields from this.


Source Code: s-expressions.zip