content/blog/2016/08/lisp-jam-postmortem.markdown @ 6c9b0b5db957

Transfer maintainership
author Steve Losh <steve@stevelosh.com>
date Wed, 04 Apr 2018 21:48:56 -0400
parents 696be47e585d
children f5556130bda1
+++
title = "August 2016 Lisp Game Jam Postmortem"
snip = "Porting a game from Clojure to Common Lisp."
date = 2016-08-15T13:45:00Z
mathjax = true
draft = false

+++

The [August 2016 Lisp Game Jam][] just wrapped up at the end of last week.
I had some free time so I decided to take part, but I did something a bit
different.  Instead of making a new game I ported an existing one ([Silt][]) to
Common Lisp.

I once read somewhere that when trying to build things and learn programming
languages you should either build something you know in a language you're
learning, or build something new in a language you already know, but *not* try
to do both at the same time.  I've been getting into Common Lisp over the past
year, so for this game jam I decided to port my [Ludum Dare 34 game][] from
Clojure to Common Lisp.

The game jam was ten days long.  I didn't work on the game every day, but I did
manage to finish porting it over.  I improved and polished a few mechanics along
the way, learned a lot, and ended up with a nice little library that sprung out
of the code.  I'm happy with the result.

The code is [on Bitbucket][Silt 2].  You can play the game over telnet if you
want to try it out: `telnet silt.stevelosh.com`.  In this post I'm just going to
jot down a few things I found interesting.

Disclaimer: I'm going to simplify some of the code snippets to make them easier
to read.  If you want the full details you can read the actual code.

[August 2016 Lisp Game Jam]: https://itch.io/jam/august-2016-lisp-game-jam
[Ludum Dare 34 game]: /blog/2015/12/ludum-dare-34/
[Silt]: http://bitbucket.org/sjl/silt/
[Silt 2]: http://bitbucket.org/sjl/silt2/

<div id="toc"></div>

## Development

[Silt 2][] is written in Common Lisp.  It uses [cl-charms][] (a wrapper around
[ncurses][]) to handle drawing to the terminal, and a few other Common Lisp
libraries like [iterate][] and [cl-arrows][].

I developed it on [SBCL][] and OS X, and the telnet server is running Debian so
it works there too.  It almost runs in [ClozureCL][], but something
Unicode-related is broken with ncurses under CCL and I didn't bother debugging
it.

I used [Roswell][] to build a standalone binary for "releases".  This binary
starts up much faster than loading everything from scratch.

I use [Neovim][] and was pleasantly surprised when running ncurses inside
Neovim's terminal emulator Just Worked (especially since the cl-charms `README`
specifically says you *can't* run it in emacs' terminal!).  It was really nice to
have the actual game running inside my text editor.

[iterate]: https://common-lisp.net/project/iterate/
[cl-arrows]: https://github.com/nightfly19/cl-arrows
[cl-charms]: https://github.com/HiTECNOLOGYs/cl-charms
[ncurses]: https://en.wikipedia.org/wiki/Ncurses
[SBCL]: http://www.sbcl.org/
[ClozureCL]: http://ccl.clozure.com/
[Roswell]: https://github.com/roswell/roswell
[Neovim]: https://neovim.io/

## ncurses and cl-charms

[cl-charms][] is a wrapper around [ncurses][] that I used to handle drawing the
game to the terminal.  The original Clojure version used [clojure-lanterna][].

The game's drawing code is pretty simple, so there's not a whole lot to say
here.  I loop over the screen, drawing the contents of each world coordinate at
each screen coordinate, and refresh the window.

cl-charms mostly worked out great.  It's a bit wordy at times (always having to
pass `charms:*standard-window*` to everything), but you can wrap it up pretty
easily.  I'd recommend it if you need to do console drawing in Common Lisp.

cl-charms has a low-level interface that's just an FFI wrapper around ncurses,
and a high-level interface that abstracts some of the Cishness away for you.
I mostly used the high-level interface, but one big thing that's missing is
support for colors.  Working with colors in ncurses is a bit tedious, but this
is Lisp so I can just abstract away all the boring stuff:

```text
(defmacro defcolors (&rest colors)
  `(progn
    ,@(iterate (for n :from 0)
               (for (constant nil nil) :in colors)
               (collect `(define-constant ,constant ,n)))
    (defun init-colors ()
      ,@(iterate
          (for (constant fg bg) :in colors)
          (collect `(charms/ll:init-pair ,constant ,fg ,bg))))))

(defcolors
  (+color-white-black+  charms/ll:COLOR_WHITE   charms/ll:COLOR_BLACK)
  (+color-blue-black+   charms/ll:COLOR_BLUE    charms/ll:COLOR_BLACK)
  (+color-cyan-black+   charms/ll:COLOR_CYAN    charms/ll:COLOR_BLACK)
  (+color-yellow-black+ charms/ll:COLOR_YELLOW  charms/ll:COLOR_BLACK)
  (+color-green-black+  charms/ll:COLOR_GREEN   charms/ll:COLOR_BLACK)
  (+color-pink-black+   charms/ll:COLOR_MAGENTA charms/ll:COLOR_BLACK)

  (+color-black-white+  charms/ll:COLOR_BLACK charms/ll:COLOR_WHITE)
  (+color-black-yellow+ charms/ll:COLOR_BLACK charms/ll:COLOR_YELLOW)

  (+color-white-blue+   charms/ll:COLOR_WHITE charms/ll:COLOR_BLUE)

  (+color-white-red+    charms/ll:COLOR_WHITE charms/ll:COLOR_RED)

  (+color-white-green+  charms/ll:COLOR_WHITE charms/ll:COLOR_GREEN))

(defmacro with-color (color &body body)
  (once-only (color)
    `(unwind-protect
      (progn
        (charms/ll:attron (charms/ll:color-pair ,color))
        ,@body)
      (charms/ll:attroff (charms/ll:color-pair ,color)))))

```

[clojure-lanterna]: https://sjl.bitbucket.io/clojure-lanterna/

## Using a State Machine as the Game Loop

One thing many games have in common is a [game loop][].  The original version of
Silt had one, but for the rewrite I decided to structure the main flow of the
game as a state machine instead.  This worked out really well and I'm glad I did
it.

At first I looked around and tried to find a state machine library for Common
Lisp, but then I realized I was being ridiculous and could just model a state
machine with vanilla Lisp functions:

```text
(defun state-title ()
  (render-title)
  (press-any-key)
  (state-intro))

(defun state-intro ()
  (render-intro)
  (press-any-key)
  (state-generate))

(defun state-generate ()
  (render-generate)
  (reset-world)
  (generate-world)
  (state-map))

(defun state-map ()
  (charms:enable-non-blocking-mode charms:*standard-window*)
  (state-map-loop))

(defun state-map-loop ()
  (case (handle-input-map)
    ((:quit) (state-quit))
    ((:regen) (state-generate))
    ((:help) (state-help))
    (t (progn
         (unless *paused*
           (iterate (repeat *frame-skip*)
                    (tick-world)
                    (tick-log)))
         (render-map)
         (when *sleep*
           (sleep 0.05))
         (state-map-loop)))))

(defun state-help ()
  (render-help)
  (press-any-key)
  (state-map))

(defun state-quit ()
  'goodbye)
```

This worked especially well with cl-charms and ncurses because for states like
the title and help screens there's no point in looping to redraw the screen over
and over again while waiting for input.  I just flipped ncurses into
block-while-awaiting-input mode and let it free up the CPU while waiting for the
user to continue.

In hindsight I probably should have split out the pause state into a separate
state, which would have let me use blocking input there too.

Using functions for states like this is only possible because SBCL (and CCL)
perform [last call optimization][], so the stack doesn't get blown by all the
recursion happening.

[game loop]: https://en.wikipedia.org/wiki/Game_programming#Game_structure
[last call optimization]: https://en.wikipedia.org/wiki/Tail_call

## Terrain Generation

The original Silt was made for Ludum Dare 34 in 72 hours, so I didn't spend too
much time on terrain.  I just created an empty world and scattered some lakes
around it, which looked like this:

[![Screenshot of terrain in the original game](/media/images/blog/2016/08/silt1-terrain.png)](/media/images/blog/2016/08/silt1-terrain.png)

This worked and was quick, but is pretty boring and ugly.  In the past few
months I've learned a lot more about terrain generation, so I fleshed things out
a bit more for the new port:

[![Screenshot of terrain in the new version](/media/images/blog/2016/08/silt2-terrain.png)](/media/images/blog/2016/08/silt2-terrain.png)

Now I've got oceans and mountains for the creatures to explore.

### Tiling Diamond Square

My initial impulse was to use [Perlin Noise][] or [Simplex Noise][] to generate
the heightmap for the world, but I ran into a problem.  I wanted the world to be
a torus, just like in the original game, so I needed a terrain generation
algorithm that would generate tileable/wrappable heightmaps.

One way to do this is to use higher-dimensional noise to get 2D noise that
tiles.  If you want to get a 2D heightmap that's tileable in one direction, you
can use 3D noise and take a cylindrical slice of it.  To get a heightmap that
tiles both ways you need to use 4D noise.  [This article][ron-noise] gives
a really nice overview of the process.

Unfortunately I couldn't find an implementation of 4D Simplex Noise in Common
Lisp.  [black-tie][] and [noise][] both only offer up to 3D noise, and I don't
feel confident enough to implement it myself, even after skimming the simplex
noise paper.

So I decided to try a different approach and figure out how to modify [Diamond
Square][] to tile.  The [Wikipedia article for Diamond Square][ds-wiki] says:

> Another option [for the diamond step] is to 'wrap around', taking the fourth
> value from the other side of the array. When used with consistent initial
> corner values this method also allows generated fractals to be stitched
> together without discontinuities.

This sounded great, but after thinking about it for a bit it's obviously not
correct.  If we have a heightmap and do what the article says, it will seem to
work at first:

<pre class="lineart">
                      ╔══════════════════╗
    ┌─┬─┬─┬─┬─┐       ║   ┌─┬─┬─┬─┬─┐    ║
    │5│ │ │ │5│       ║   │5│ │ │ │5│    ║
    ├─┼─┼─┼─╱┬╲       ║   ├─┼─┼─┼─╱┬╲    ║
    │ │ │ │╱│││╲      ║   │ │ │ │╱│││╲   ║
    ├─┼─┼─╱─┼▼┤ ╲     ║   ├─┼─┼─╱─┼▼┤ ╲  ║
    │ │ │3├─▶◉◀──?    ╚═══════│3├─▶◉◀════╝
    ├─┼─┼─╲─┼▲┤ ╱         ├─┼─┼─╲─┼▲┤ ╱
    │ │ │ │╲│││╱          │ │ │ │╲│││╱
    ├─┼─┼─┼─╲┴╱           ├─┼─┼─┼─╲┴╱
    │5│ │ │ │5│           │5│ │ │ │5│
    └─┴─┴─┴─┴─┘           └─┴─┴─┴─┴─┘
</pre>

Wrapping like this will indeed make sure that the averages match up, but there's
two problems.

First: the corners are all the same value, which means that when you put four
heightmaps next to each other there's an unnatural flat area of four identical
height values next to each other.  This probably wouldn't be noticeable in
practice, but if you want to do things *right* it won't be acceptable.

But the *real* problem is the jitter.  If the jitter on one side of the map
happens to be large and positive and the jitter on the other side happens to be
large and negative, you'll get a jarring "cliff" when you try to tile them:

[![Example of poorly-tiling diamond square](/media/images/blog/2016/08/bad-tiling-ds.png)](/media/images/blog/2016/08/bad-tiling-ds.png)

The solution I came up with is to reduce the size of the heightmap by 1.
Instead of the heightmap being \\(2^n + 1\\) in each dimension we can make it
\\(2^n\\) and adjust the coordinate-wrapping function appropriately.
Importantly, we *don't* change the calculation of the radius values as we
iterate over the array, so this means quite often we'll be "reaching" for that
final row/column:

<pre class="lineart">
     ?       ?
    ┌─╲─┬─┬─╱
    │ │╲│ │╱│
    ├─┼─◢─◣─┤
    │ │ │◉│ │
    ├─┼─◥─◤─┤
    │ │╱│ │╲│
    ├─╱─┼─┼─╲
    │5│ │ │ │?
    └─┴─┴─┴─┘
</pre>

When we try to access that nonexistent coordinate we just wrap around back to
zero.  Notice that we also only need to initialize a single corner cell now.

It's a simple change, but the result is *much* nicer:

[![Example of nicely-tiling diamond square](/media/images/blog/2016/08/good-tiling-ds.png)](/media/images/blog/2016/08/good-tiling-ds.png)

[Perlin Noise]: https://en.wikipedia.org/wiki/Perlin_noise
[Simplex Noise]: https://en.wikipedia.org/wiki/Simplex_noise
[ron-noise]: http://ronvalstar.nl/creating-tileable-noise-maps
[black-tie]: https://github.com/aerique/black-tie
[noise]: https://github.com/sebity/noise
[Diamond Square]: /blog/2016/06/diamond-square/
[ds-wiki]: https://en.wikipedia.org/wiki/Diamond-square_algorithm

## Entity, Aspects, and Systems

Terrain generation is pretty, but the next step in the port was to add some
plants, creatures, and artifacts.  In the original game I just represented
things in the world as vanilla Clojure maps, but that was getting kind of messy
and I wanted to try a different approach this time.

Recently I read through [Game Engine Architecture][] (a *fantastic* book) and
made a few games in [Unity][], which together made me want to try using an
[Entity/Component System][] this time around.  There are a couple of ECS
libraries out there for Common Lisp like [cl-ecs][] and [ecstasy][], but in true
Lisp fashion I ended up not being quite satisfied with any of them and writing
Yet Another God Damn Library.

It's called [Beast][].  It's subtly different than the others in that it prefers
to be a really thin layer over CLOS and uses inheritance instead of composition.
It uses the word "aspect" instead of "component" to try to overload that word
a bit less, so it's the "Basic Entity/Aspect/System Toolkit".  It ended up being
about 150 lines of code (not including docstrings), so I managed to avoid going
down too much of a rabbit hole during the jam.

If you want to know all the details, check out its documentation (it has
*actual* documentation).  But here I'll just talk about a couple of the
particular bits of Silt that I used it for.

[Unity]: https://unity3d.com/
[Game Engine Architecture]: http://www.amazon.com/dp/1466560010/?tag=stelos-20
[Entity/Component System]: https://en.wikipedia.org/wiki/Entity_component_system
[cl-ecs]: https://github.com/lispgames/cl-ecs
[ecstasy]: https://github.com/mfiano/ecstasy
[beast]: https://sjl.bitbucket.io/beast/overview/

### Coordinates

The first thing I needed was a way to keep track of where things are in the
world.

If the world space were continuous a [quadtree][] would have been my first
choice, but in Silt the world is split into discrete integer coordinates.
Creatures move directly from \\((x, y)\\) to \\((x+1, y+1)\\).  I decided to use
a simple array of lists to represent this:

```text
(defparameter *coords-contents*
  (make-array (list +world-size+ +world-size+)
              :initial-element nil))
```

Each value in the array is a list of the entities that are currently there.
This means looking up what things are at a given coordinate is a single fast
`aref`.

I tried using a hash table instead of an array at first, thinking that if the
world were fairly sparse it would be wasteful to allocate an array with a ton
of `nil` values in it.  But the array method is much faster for looking things
up (which happens a lot) and memory is cheap, so I decided against the hash
tables.  It worked great in the end.

Entities need to know where they are in the world, so I defined a Beast aspect
for that:

```text
(define-aspect coords x y)
```

Then I defined a few functions to handle moving entities into, out of, and
around the world:

```text
(defun coords-insert-entity (e)
  (push e (aref *coords-contents* (coords/x e) (coords/y e))))

(defun coords-remove-entity (e)
  (zap% (aref *coords-contents* (coords/x e) (coords/y e))
        #'delete e %))

(defun coords-move-entity (e new-x new-y)
  (coords-remove-entity e)
  (setf (coords/x e) (wrap new-x)
        (coords/y e) (wrap new-y))
  (coords-insert-entity e))

(defun coords-lookup (x y)
  (aref *coords-contents* (wrap x) (wrap y)))
```

Entities might also like to know what's near them:

```text
(defun nearby (entity &optional (radius 1))
  (remove entity
          (iterate
            outer
            (with x = (coords/x entity))
            (with y = (coords/y entity))
            (for dx :from (- radius) :to radius)
            (iterate
              (for dy :from (- radius) :to radius)
              (in outer
                  (appending (coords-lookup (+ x dx)
                                            (+ y dy))))))))
```

This ends up compiling down to a nice tight loop of \\((2 * radius + 1)^2\\)
`aref`s.  I only wish iterate had a nicer syntax for looping over nested
indices like this.  I'm sure it's possible to write an iterate driver for it --
maybe someday I'll try making one.

I also needed a way to get entities into the world array when they're created
and remove them when they die.  Beast (well, actually CLOS) makes this trivially
easy with auxiliary methods:

```text
(defmethod entity-created :after ((entity coords))
  (coords-insert-entity entity))

(defmethod entity-destroyed :after ((entity coords))
  (coords-remove-entity entity))
```

[quadtree]: https://en.wikipedia.org/wiki/Quadtree

### User Interface

Once I had a way of know where things are, the next step was to display them on
the screen.  I broke this into a few separate aspects.

#### Visible

The `visible` aspect is for things that are drawn on the screen with
a particular glyph and color:

```text
(define-aspect visible glyph color)

;; ...

(define-entity tree (coords visible ...))

(defun make-tree (x y)
  (create-entity 'tree
                 :coords/x x
                 :coords/y y
                 :visible/glyph "T"
                 :visible/color +color-green-black+
                 ;; ...
                 ))

```

The drawing code can then figure out what to draw for each screen coordinate:

```text
(defun draw-map ()
  (iterate
    (for sx :from 0 :below *screen-width*)
    (for wx :from *view-x*)
    (iterate
      (for sy :from 0 :below *screen-height*)
      (for wy :from *view-y*)
      (for entity = (find-if #'visible? (coords-lookup wx wy)))
      (if entity
        (with-color (visible/color entity)
          (write-string-at (visible/glyph entity) sx sy))
        ;;; otherwise draw the terrain
        (...)))))
```

Again: my kingdom for a `(for-nested ...)` iterate driver!  But the core is just
using `(find-if #'visible? (coords-lookup wx wy))` to find the first visible
thing and then drawing it:

[![Screenshot of entities with the visible aspect](/media/images/blog/2016/08/aspect-visible.png)](/media/images/blog/2016/08/aspect-visible.png)

I used `find-if` instead of `remove-if-not` because we can only draw one
character to a given position in the terminal anyway, so I just pick the first
thing that happens to be in the list.

#### Flavor

The `flavor` aspect is for adding [flavor text][] that appears when the user
puts their cursor over an entity:

```text
(define-aspect flavor text)

;; ...

(define-entity tree (coords visible flavor ...))

(defun make-tree (x y)
  (create-entity 'tree
                 :coords/x x
                 :coords/y y
                 :visible/glyph "T"
                 :visible/color +color-green-black+
                 :flavor/text
                 '("A tree sways gently in the wind.")))
```

Then when the user's cursor is at a certain position I can find all the entities
there and draw the flavor text for any that have the `flavor` aspect:

```text
(defun draw-selected ()
  (write-left
    (iterate
      (for entity :in (multiple-value-call #'coords-lookup
                        (screen-to-world *cursor-x* *cursor-y*)))
      (when (typep entity 'flavor)
        (appending (flavor/text entity) :into text)

        ;; ...

        (collecting "" :into text))
      (finally (return text)))
    1 1 :pad t))
```

Which looks like this:

[![Screenshot of flavor text](/media/images/blog/2016/08/aspect-flavor.png)](/media/images/blog/2016/08/aspect-flavor.png)

Of course the flavor text doesn't have to be a constant:

```text
(defun make-creature (x y &key
                      (color +color-white-black+)
                      (glyph "@"))
  (let ((name (random-name)))
    (create-entity 'creature
      :name name
      :coords/x x
      :coords/y y
      :visible/color color
      :visible/glyph glyph
      :flavor/text
      (list (format nil "A creature named ~A is here." name)
            "It likes food."))))
```

[flavor text]: https://en.wikipedia.org/wiki/Flavor_text

#### Inspectable

The last thing I wanted was an easy way to show attributes of entities in the
main game UI.  The original Clojure game just dumped the entire object to the
screen:

[![Screenshot of creature inspection in the original game](/media/images/blog/2016/08/silt1-inspect.png)](/media/images/blog/2016/08/silt1-inspect.png)

But this time I wanted a bit more control.  The `inspectable` aspect has a list
of things that should be displayed.  These can be symbols (which denote CLOS
slot names) or functions that return `(label . text)` conses:

```text
(define-aspect inspectable
  (slots :initform nil))

(defun inspectable-get (entity slot)
  (etypecase slot
    (symbol (cons slot (slot-value entity slot)))
    (function (funcall slot entity))))
```

When creating an entity I can just list out the slots I want to be displayed on
the screen, or use a little `lambda` if I want to show something that's not an
actual slot:

```text
(defun make-fruit (x y)
  (create-entity 'fruit
    ;; ...
    :inspectable/slots '(edible/energy)))

(defun make-creature (x y &key ...)
  (let ((name (random-name)))
    (create-entity 'creature
      ;; ...
      :inspectable/slots
      (list 'name
            (lambda (c) (cons 'directions ...))
            'metabolizing/energy
            'metabolizing/insulation
            'aging/birthtick
            'aging/age))))
```

Then I just append some extra text for `inspectable` entities when drawing
descriptions of things at the cursor position:

```text
(defun draw-selected ()
  (write-left
    (iterate
      (for entity :in (multiple-value-call #'coords-lookup
                        (screen-to-world *cursor-x* *cursor-y*)))
      (when (typep entity 'flavor)
        ;; ...
        (when (typep entity 'inspectable)
          (appending
            (indent
              (iterate
                (with slots = (mapcar (curry #'inspectable-get entity)
                                      (inspectable/slots entity)))
                (with width = (apply #'max
                                     (mapcar (compose #'length #'symbol-name #'car)
                                             slots)))
                (for (label . contents) :in slots)
                (collect
                  (let ((*print-pretty* nil))
                    (format nil "~vA ~A" width label contents)))))
            :into text))

        (collecting "" :into text))
      (finally (return text)))
    1 1 :pad t))
```

This is pretty ugly because I wanted to justify and indent things nicely, but
the result looks much nicer than the original game:

[![Screenshot of creature inspection in the new version](/media/images/blog/2016/08/silt2-inspect.png)](/media/images/blog/2016/08/silt2-inspect.png)

### Food

Seeing the world is nice, but we also want the things in it to actually *do*
something.  The world revolves heavily around food and energy, so I defined
a few aspects to handle things:

```text
(define-aspect edible
  energy
  original-energy)

(define-aspect decomposing
  rate
  (remaining :initform 1.0))

(define-aspect fruiting
  chance)

(defmethod initialize-instance :after ((e edible) &key)
  (setf (edible/original-energy e)
        (edible/energy e)))
```

I do wish there was a slightly less wordy way to default the value of one slot
to another one, but oh well.

Then I just added the aspects to the appropriate entities:

```text
(define-entity tree (coords visible fruiting flavor))
(define-entity fruit (coords visible edible flavor decomposing inspectable))
(define-entity algae (coords visible edible decomposing))
(define-entity grass (coords visible edible decomposing))
(define-entity corpse (coords visible flavor decomposing))
```

Trees can grow fruit, so they have the `fruiting` aspect.  The `grow-fruit`
Beast system handles growing some each tick:

```text
(define-system grow-fruit ((entity fruiting coords))
  (when (randomp (fruiting/chance entity))
    (make-fruit (wrap (random-around (coords/x entity) 2))
                (wrap (random-around (coords/y entity) 2)))))
```

Fruit is `edible`, but also decomposes over time.  It's got `flavor` and
`inspectable` aspects so you can see how much energy is left.

I added algae and grass as secondary food sources to spread out the food supply
a bit more and make the creatures a bit less dependent on the trees.  I didn't
give these flavor text to avoid cluttering up the UI too much.

I considered making corpses edible too, but figured that might be a bit too
gruesome.  So corpses decompose, but the critters aren't cannibals.

I made a couple of Beast systems to handle the process of decomposing things
every game tick:

```text
(define-system rot ((entity decomposing))
  (when (minusp (decf (decomposing/remaining entity)
                      (decomposing/rate entity)))
    (destroy-entity entity)))

(define-system rot-food ((entity decomposing edible))
  (setf (edible/energy entity)
        (lerp 0.0 (edible/original-energy entity)
              (decomposing/remaining entity))))
```

`rot` runs on everything with the `decomposing` aspect.  It ticks along the
progress of an entity's decomposition, and destroys it once it's finished.

`rot-food` runs on every entity that's both `decomposing` *and* `edible`.  It
reduces the energy value of the food over time, because rotten food is less
healthy.  I'm pretty happy with how easy Beast makes this kind of thing.

### Creatures and Mysteries

The final pieces of the world are the creatures and artifacts.

#### Energy
Creatures need food (energy) to survive.  I modeled this with a `metabolizing`
aspect and `consume-energy` system:

```text
(define-aspect metabolizing insulation energy)

(defmethod starve ((entity entity))
  (destroy-entity entity))

(defmethod calculate-energy-cost ((entity metabolizing))
  (let* ((insulation (metabolizing/insulation entity))
         (base-cost 1.0)
         (temperature-cost (max 0 (* 0.2 (- (abs *temperature*) insulation))))
         (insulation-cost (* 0.1 insulation)))
    (+ base-cost temperature-cost insulation-cost)))

(define-system consume-energy ((entity metabolizing))
  (when (minusp (decf (metabolizing/energy entity)
                      (calculate-energy-cost entity)))
    (starve entity)))
```

I made `starve` and `calculate-energy-cost` generic functions because I thought
I might eventually have different metabolizing things in the world and might
want to override them.  I didn't end up doing this in the end (creatures are the
only things that burn energy) so these could have been normal functions.

The energy mechanic works similarly to the original game:

* Creatures spend a bit of energy each tick to stay alive.
* When you make the temperature hotter or colder, it costs additional energy per
  tick for the creatures to live.
* Creatures sometimes gain/lose insulation during reproduction, which mitigates
  the energy cost of the temperature difference.
* Insulation itself costs a little bit of energy every tick.

The effect is that if you change the temperature gradually over time, the
population will evolve higher insulation values (because the children with more
insulation are more likely to survive longer).  If you then set the temperature
back to zero (the ideal) the population will eventually evolve to shed the
insulation, because it costs a little bit of energy and doesn't provide any
benefit when the world is pleasant.  Natural selection is fun.

The last piece of the puzzle is letting things actually take action.  Creatures
and some artifacts need to take an action on every tick, while other artifacts
only do things occasionally.  A pair of aspects and systems handles the
bookkeeping here:

```text
(define-aspect sentient function)
(define-aspect periodic
  function
  (counter :initform 1)
  next
  min
  max)

(define-system sentient-act ((entity sentient))
  (funcall (sentient/function entity) entity))

(define-system periodic-tick ((entity periodic))
  (when (zerop (setf (periodic/counter entity)
                     (mod (1+ (periodic/counter entity))
                          (periodic/next entity))))
    (setf (periodic/next entity)
          (random-range (periodic/min entity)
                        (periodic/max entity)))
    (funcall (periodic/function entity) entity)))
```

I'm not going to go over all the actual AI and actions, you can take a look at
the code if you're curious.

## Random Name Generation

I wanted to add a more personal connection to the creatures this time around, so
I decided they should have names.  I used a really simple form of
[syllable-based name generation][namegen] to give each creature its own random
name:

```text
(defparameter *name-syllables*
  (-> "syllables.txt"
    slurp
    read-from-string
    (coerce 'vector)))

(defun random-name ()
  (format nil "~:(~{~A~}~)"
          (iterate (repeat (random-range 1 5))
                   (collect (random-elt *name-syllables*)))))
```

To get a random name I just smash together one to four random syllables.  To
make a list of syllables I grabbed some Icelandic text and made a pair of really
janky shell and Python scripts to print out every 3/4/5-letter chunk of every
word, sort them by frequency, and take the top 500.

They're not *really* syllables but they're okay for just a couple of lines of
code and a few minutes work:

[![Screenshot of creature names](/media/images/blog/2016/08/silt-names.png)](/media/images/blog/2016/08/silt-names.png)

[namegen]: http://www.roguebasin.com/index.php?title=Syllable-based_name_generation

## Simple Data Structures

As I coded things up I wound up with a handy pair of data structures I might use
again for other things in the future.

### Weightlists

Each game tick a creature needs to decide which direction to walk.  At the start
of the game they just pick a random direction, but as they reproduce their
children can mutate to prefer certain directions over others.

The natural selection of Silt turns out to prefer creatures that wander around
to those that stay in place.  Fruit takes time to grow, so it's more effective
to travel around and gather it than to sit in place waiting for it to regrow.

The original game just used a Clojure vector of weights and directions to
represent how much a creature prefers each direction.  That worked, but the
weights are only ever set/changed when a creature is born, and a random element
is chosen every turn.  It's more efficient in the long run if we precompute
a few things up front, so I made a little "weightlist" API:

```text
(defstruct (weightlist (:constructor %make-weightlist))
  weights sums items total)

(defun make-weightlist (items weights)
  "Make a weightlist of the given items and weights."
  (%make-weightlist
    :items items
    :weights weights
    :sums (prefix-sums weights)
    :total (apply #'+ weights)))

(defun weightlist-random (weightlist)
  "Return a random item from the weightlist, taking the weights into account."
  (iterate
    (with n = (random (weightlist-total weightlist)))
    (for item :in (weightlist-items weightlist))
    (for weight :in (weightlist-sums weightlist))
    (finding item :such-that (< n weight))))
```

This is pretty straightforward.  Note that the weights can be integers or floats
(or some of each!) and things will Just Work, because Common Lisp's `random` can
take either.  Weights of zero are fine too, as long as at least one element has
a nonzero weight.

### Ticklists

In a couple of places I needed some kind of list where items in it expire over
time.  For example:

* The Fountain artifact only lets creatures drink from it once every thousand
  ticks, so I needed a way to keep track of the entities that had drank
  recently.
* The game log at the bottom of the screen contains messages that should be
  shown for a certain number of ticks, then disappear.

I made a simple little thing I called a "ticklist" to handle these:

```text
(defun make-ticklist ()
  nil)

(defmacro ticklist-push (ticklist value lifespan)
  `(push (cons ,lifespan ,value) ,ticklist))

(defun ticklist-tick (ticklist)
  (flet ((decrement (entry)
           (decf (car entry)))
         (dead (entry)
           (minusp (car entry))))
    (->> ticklist
      (mapc #'decrement)
      (remove-if #'dead))))

(defun ticklist-contents (ticklist)
  (mapcar #'cdr ticklist))
```

Internally a ticklist is just a list of `(remaining-ticks . thing)` conses, but
the rest of my code doesn't have to care about that:

```text
(defun fountain-act (f)
  (with-slots (recent) f
    (zapf recent #'ticklist-tick)
    (iterate
      (with already-drank = (ticklist-contents recent))
      (for creature :in (remove-if-not #'creature? (nearby f)))
      (unless (member creature already-drank)
        (creature-mutate-appearance creature)
        (ticklist-push recent creature 1000)
        (log-message "~A drinks from the fountain and... changes."
                     (creature-name creature))))))

(defun log-message (s &rest args)
  (ticklist-push *game-log* (apply #'format nil s args) 200))

(defun state-map-loop ()
  ;; ...
  (unless *paused*
    (iterate (repeat *frame-skip*)
             (tick-world)
             (zapf *game-log* #'ticklist-tick))))
```

## Profiling and Performance

When something starts slowing things down it's helpful to be able to turn on
profiling and see what's going on.  SBCL has a nice statistical profiler, so
I made a couple of functions to flip it on and off as needed:

```text
#+sbcl
(defun dump-profile ()
  (with-open-file (*standard-output* "silt.prof"
                                     :direction :output
                                     :if-exists :supersede)
    (sb-sprof:report :type :graph
                     :sort-by :cumulative-samples
                     :sort-order :ascending)
    (sb-sprof:report :type :flat
                     :min-percent 0.5)))

#+sbcl
(defun start-profiling ()
  (sb-sprof::reset)
  (sb-sprof::profile-call-counts "SILT")
  (sb-sprof::start-profiling :max-samples 50000
                             ; :mode :cpu
                             :mode :time
                             :sample-interval 0.01
                             :threads :all))

#+sbcl
(defun stop-profiling ()
  (sb-sprof::stop-profiling)
  (dump-profile))
```

When I wanted to check performance I could just evaluate `(start-profiling)`
over NREPL and let the game continue to run, then `(stop-profiling)` a little
bit later and look at the results.  It came in handy once or twice when tracking
down some slowness.

## Future Improvements and Ideas

This game jam was quite a bit of fun!  I'm happy with the results and feel like
I've learned a lot along the way.

I'm done with the game and don't plan on updating it any more, but I'll scribble
down a few extra ideas for things that could be improved here, just to get them
out of my head:

* Figure out the Unicode issues with cl-charms and CCL.
* Contribute to cl-charms to add some higher-level tools for working with color.
* Contribute to one of the Common Lisp noise libraries to implement the 4D
  variant of Simplex Noise.
* Flesh out the name generation into something much nicer and more polished.
* Implement different costs for moving over different terrain.
* Add health, fighting, and carnivores.
* Add more mysterious artifacts to the world.
* Flesh out the vegetation model to let trees grow and die, algae spread, etc.
* Improve the visuals. [Brogue][] proves you can do far more than you might
  think with just Unicode characters.
* Model senses like vision, providing the creatures with more information but
  with an energy cost.
* Give creatures "brains" by generating and mutating actual Lisp code.  This
  would let the creatures learn strategies over time, though I'm not sure how
  feasible it would be.
* Improve performance by profiling much more and fixing the hottest parts of the
  code.
* Add saving and loading of the world.
* Add the ability to seed the RNG and make everything deterministic, so people
  can share interesting seeds.  Doing this for the terrain generation at least
  should be pretty easy, the game as a whole might be slightly trickier.
* Improve the UI a bit more, maybe using ncurses' support for windows layered on
  top of other windows.

[Brogue]: https://sites.google.com/site/broguegame/