# HG changeset patch # User Steve Losh # Date 1471048420 0 # Node ID bb75d39cfff321141a9fbc0f31ce18ae29071092 # Parent 70fe7c0e825029cacffe2bdacb467c37f3226767 Add Lisp Game Jam Entry diff -r 70fe7c0e8250 -r bb75d39cfff3 content/blog/2016/06/diamond-square.html --- a/content/blog/2016/06/diamond-square.html Wed Aug 10 16:07:51 2016 +0000 +++ b/content/blog/2016/06/diamond-square.html Sat Aug 13 00:33:40 2016 +0000 @@ -231,7 +231,9 @@ Another way to handle this is to also wrap those edge coordinates around and pull the point from the other side of the heightmap. This is a bit more work -but gives you an extra benefit: the heightmap will be tileable. +but gives you an extra benefit: the heightmap will be tileable (**update**: like +everything where someone doesn't show you running code, it's [not actually that +simple](/blog/2016/08/lisp-jam-postmortem/#tiling-diamond-square)). ## Iteration diff -r 70fe7c0e8250 -r bb75d39cfff3 content/blog/2016/08/lisp-jam-postmortem.html --- /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: + +[![Screenshot of terrain in the original game](/media/images{{ parent_url }}/silt1-terrain.png)](/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: + +[![Screenshot of terrain in the new version](/media/images{{ parent_url }}/silt2-terrain.png)](/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: + +
+                      ╔══════════════════╗
+    ┌─┬─┬─┬─┬─┐       ║   ┌─┬─┬─┬─┬─┐    ║
+    │5│ │ │ │5│       ║   │5│ │ │ │5│    ║
+    ├─┼─┼─┼─╱┬╲       ║   ├─┼─┼─┼─╱┬╲    ║
+    │ │ │ │╱│││╲      ║   │ │ │ │╱│││╲   ║
+    ├─┼─┼─╱─┼▼┤ ╲     ║   ├─┼─┼─╱─┼▼┤ ╲  ║
+    │ │ │3├─▶◉◀──?    ╚═══════│3├─▶◉◀════╝
+    ├─┼─┼─╲─┼▲┤ ╱         ├─┼─┼─╲─┼▲┤ ╱
+    │ │ │ │╲│││╱          │ │ │ │╲│││╱
+    ├─┼─┼─┼─╲┴╱           ├─┼─┼─┼─╲┴╱
+    │5│ │ │ │5│           │5│ │ │ │5│
+    └─┴─┴─┴─┴─┘           └─┴─┴─┴─┴─┘
+
+ +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{{ parent_url }}/bad-tiling-ds.png)](/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: + +
+     ?       ?
+    ┌─╲─┬─┬─╱
+    │ │╲│ │╱│
+    ├─┼─◢─◣─┤
+    │ │ │◉│ │
+    ├─┼─◥─◤─┤
+    │ │╱│ │╲│
+    ├─╱─┼─┼─╲
+    │5│ │ │ │?
+    └─┴─┴─┴─┘
+
+ +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{{ parent_url }}/good-tiling-ds.png)](/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: + +[![Screenshot of entities with the visible aspect](/media/images{{ parent_url }}/aspect-visible.png)](/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: + +[![Screenshot of flavor text](/media/images{{ parent_url }}/aspect-flavor.png)](/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: + +[![Screenshot of creature inspection in the original game](/media/images{{ parent_url }}/silt1-inspect.png)](/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: + +[![Screenshot of creature inspection in the new version](/media/images{{ parent_url }}/silt2-inspect.png)](/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: + +[![Screenshot of creature names](/media/images{{ parent_url }}/silt-names.png)](/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 %} diff -r 70fe7c0e8250 -r bb75d39cfff3 media/css/sjl.less --- a/media/css/sjl.less Wed Aug 10 16:07:51 2016 +0000 +++ b/media/css/sjl.less Sat Aug 13 00:33:40 2016 +0000 @@ -38,7 +38,7 @@ h1 { font-size: 45px; line-height: 50px; margin: 25px 0; } // 3 h2 { font-size: 32px; line-height: 50px; margin: 25px 0; } // m7 h3 { font-size: 23px; line-height: 25px; margin: 25px 0; } // 3 - h4 { font-size: 18px; line-height: 25px; margin: 25px 0; } // r + h4 { font-size: 18px; line-height: 25px; margin: 25px 0; font-weight: bold; } // r code, pre { font-family: Consolas, Menlo, "Courier New", monospace; font-size: 14px; diff -r 70fe7c0e8250 -r bb75d39cfff3 media/diamond-square.monopic Binary file media/diamond-square.monopic has changed diff -r 70fe7c0e8250 -r bb75d39cfff3 media/images/blog/2016/08/aspect-flavor.png Binary file media/images/blog/2016/08/aspect-flavor.png has changed diff -r 70fe7c0e8250 -r bb75d39cfff3 media/images/blog/2016/08/aspect-visible.png Binary file media/images/blog/2016/08/aspect-visible.png has changed diff -r 70fe7c0e8250 -r bb75d39cfff3 media/images/blog/2016/08/bad-tiling-ds.png Binary file media/images/blog/2016/08/bad-tiling-ds.png has changed diff -r 70fe7c0e8250 -r bb75d39cfff3 media/images/blog/2016/08/good-tiling-ds.png Binary file media/images/blog/2016/08/good-tiling-ds.png has changed diff -r 70fe7c0e8250 -r bb75d39cfff3 media/images/blog/2016/08/silt-names.png Binary file media/images/blog/2016/08/silt-names.png has changed diff -r 70fe7c0e8250 -r bb75d39cfff3 media/images/blog/2016/08/silt1-inspect.png Binary file media/images/blog/2016/08/silt1-inspect.png has changed diff -r 70fe7c0e8250 -r bb75d39cfff3 media/images/blog/2016/08/silt1-terrain.png Binary file media/images/blog/2016/08/silt1-terrain.png has changed diff -r 70fe7c0e8250 -r bb75d39cfff3 media/images/blog/2016/08/silt2-inspect.png Binary file media/images/blog/2016/08/silt2-inspect.png has changed diff -r 70fe7c0e8250 -r bb75d39cfff3 media/images/blog/2016/08/silt2-terrain.png Binary file media/images/blog/2016/08/silt2-terrain.png has changed