--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/content/blog/2016/08/lisp-jam-postmortem.html Sat Aug 13 00:33:40 2016 +0000
@@ -0,0 +1,981 @@
+ {% extends "_post.html" %}
+
+ {% load mathjax %}
+
+ {% hyde
+ title: "August 2016 Lisp Game Jam Postmortem"
+ snip: "Porting a game from Clojure to Common Lisp."
+ created: 2016-08-15 13:30:00
+ %}
+
+ {% block article %}
+
+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/
+
+[TOC]
+
+## 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]: http://sjl.bitbucket.org/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:
+
+[](/media/images{{ parent_url }}/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:
+
+[](/media/images{{ parent_url }}/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:
+
+[](/media/images{{ parent_url }}/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:
+
+[](/media/images{{ parent_url }}/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]: http://sjl.bitbucket.org/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:
+
+[](/media/images{{ parent_url }}/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:
+
+[](/media/images{{ parent_url }}/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:
+
+[](/media/images{{ parent_url }}/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:
+
+[](/media/images{{ parent_url }}/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:
+
+[](/media/images{{ parent_url }}/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/
+
+ {% endblock article %}
