#+TITLE: LGDC10 Postmortem

*Tuesday March 30, 2010*

First let me thank everyone for participating in the 2010 Lisp Game Design Challenge! I think the whole contest has been a success. With ten registered entries (8 individuals and 2 teams), I think we'll have a lot to discuss in the coming days. The LGDC also brought some new people to the lispgames community, and we're continuing to build a knowledge base for developing and delivering games in Lisp across multiple platforms. For example the http://www.cliki.net/LispGameDesignChallenge cliki registration page now has a big list of links to various libraries and tools, and the IRC channel's ranks have swelled to an average of over 30 people. I've read the postmortems mailed so far and I think these documents will be a great contribution to the lispgames noosphere.

And now for my postmortem!

For my 7-day Challenge entry I implemented the core gameplay mechanics and settings of a loosely Lisp-themed sci-fi combat game called CONS. I'm classifying my entry as a failure because I did not finish a complete game within the time limit. I will continue working on CONS though, and I'm looking forward to fleshing out the design.

* What's lispy about my entry?

The player is a multi-segment Lisp list snake! See the design document at http://dto.github.com/notebook/cons.html for details. In addition some interesting "minilanguage" techniques were used for this game, see the algorithms section below.

* Tools and technology

My entry is programmed in Common Lisp running on SBCL. I used my own [[file:xe2-reference.org][XE2 game engine]], which is based on LISPBUILDER-SDL. Image editing was done with the GIMP, and program development with GNU Emacs and SLIME running on Ubuntu. For music and sound I used varying combinations of Hexter (a software Yamaha DX7 emulator), Audacity (digital audio editor), Ardour (digital audio recording workstation), and Milkytracker (MOD tracking application.)

* What went right?

- The 7-day process is good for focusing on the core play mechanics, despite being a bit stressful at times. - My design called for five different level types plus an overworld map. This forced me to focus on improving XE2's random level generation framework, and led to some interesting new functionality. See the "interesting algorithms" section below. - Focusing on usability led to simplified controls---gameworld interaction uses only the arrow keys, Z, X, and Shift. The number one category of user feedback complaints about my games relate to controls, so this is a big win. I also made the controls user-configurable through an interactive spreadsheet screen, which is also joystick-compatible (with some glitches at the moment.) This is (finally) a port of my circa-2006 OO spreadsheet program "Cellmode". However, this was a time-sink, see next section.

* What went wrong?

My only real mistake was developing CONS as a 7-day thing. The design is a bit larger than my recent games and only the skeleton was finished by that time. Also, I spent an inordinate amount of time on the input configuration screen, and on the music for the game, when I should have focused on fleshing out the gameplay.

* What did you learn?

Don't attempt to port major features from an old codebase while in the middle of a 7-day challenge. Although porting Cell-mode and creating the configuration UI was unquestionably time well spent, I should have waited until after my entry was complete to work on these features.

* What interesting algorithms or designs did i use?

There are two main points here, one relates to level generation and the other to user interfaces. (The combination of both elements mean we will soon have a user interface for level generation.)

Development on my 2010 7DRL challenge entry XIOTANK was troubled by the issue of how to generate solvable puzzles while still randomizing the layout. This is a hard problem, and occasionally-unsolvable levels have been a criticism of XONG (see http://playthisthing.com/xong ) In XIOTANK the more elaborate combination-lock style puzzle was unexpectedly hard to implement, and the result was still less than satisfying. Late in development, I overemphasized combat to compensate for this, and the result was (according to some players) an overly difficult game.

I realized I had a bunch of level generation tools but nothing to tie them together. With some new functionality implemented in XE2 this has changed.

First came support for randomly generating sentences (Lisp lists of individual words, strings, or symbols) according to simple context-free grammars. http://en.wikipedia.org/wiki/Context-free_grammar

This is similar to L-systems except that substitutions are not simultaneous.

Here's an example grammar for a fictional sci-mission:

: (defparameter *test-grammar* : '((mission >> (at location please goal+ in exchange for reward)) : (location >> mars zeta-base nebula-m corva-3) : (goal+ >> goal (goal and goal+)) : (goal >> (defeat foe) (defend friend) (activate button) (retrieve documents) : (collect mineral+)) : (mineral+ >> mineral (mineral and mineral+)) : (mineral >> endurium technetium molybdenum francium a-biosilicates) : (foe >> scanner biclops unique) : (friend >> transport skiff soldier scientist) : (unique >> zx-90 xioblade) : (reward >> money part) : (money >> 10000 20000 30000 40000 50000) : (part >> muon-pistol lepton-cannon ion-shield-belt)))

When "foe" is encountered for example, it is replaced with either "scanner" "biclops" or "unique". (Sublists represent concatenation.)

A few example output sentences.

: (AT MARS PLEASE COLLECT A-BIOSILICATES IN EXCHANGE FOR MUON-PISTOL) : (AT NEBULA-M PLEASE DEFEAT XIOBLADE IN EXCHANGE FOR MUON-PISTOL) : (AT CORVA-3 PLEASE RETRIEVE DOCUMENTS AND ACTIVATE BUTTON IN EXCHANGE FOR : ION-SHIELD-BELT)

These are unintepreted data, but it is straightforward to give them an interpretation. I haven't yet done this with mission structures as in the example, but I *have* made a working implementation of a simple LOGO-like language, to interpret randomly-generated LOGO programs like this:

: 9 :JUMP :PUSHLOC CONS-GAME::=BARRIER= :COLOR 90 :RIGHT 7 :DRAW :POPLOC 9 :JUMP : :PUSHLOC CONS-GAME::=BARRIER= :COLOR 90 :RIGHT 7 :DRAW :POPLOC 9 :JUMP : :PUSHLOC CONS-GAME::=BARRIER= :COLOR 90 :RIGHT 7 :DRAW :POPLOC 9 :JUMP : :PUSHLOC CONS-GAME::=BARRIER= :COLOR 45 :RIGHT 7 :DRAW :POPLOC 10 :JUMP 90 : :RIGHT :ORIGIN :PUSHLOC 45 :RIGHT 5 :JUMP CONS-GAME::=EXIT= :COLOR :DROP : :POPLOC 90 :RIGHT 20 :JUMP 90 :LEFT 25 :JUMP 90 :LEFT :PUSHLOC : CONS-GAME::=BARRIER= :COLOR 5 :DRAW :PUSH-COLOR :PUSHLOC 90 :LEFT : CONS-GAME::=BOMB-DEFUN= :COLOR 1 :JUMP 2 :DRAW :POPLOC :COLOR 5 :DRAW 90 : :RIGHT 4 :DRAW 2 :JUMP 4 :DRAW 90 :RIGHT 10 :DRAW 90 :LEFT : CONS-GAME::=BARRIER= :COLOR 5 :DRAW :PUSH-COLOR :PUSHLOC 90 :LEFT : :RIGHT 4 :DRAW 2 :JUMP 4 :DRAW 90 :RIGHT 10 :DRAW 90 :RIGHT 6 :JUMP :PUSHLOC : CONS-GAME::=PURPLE-BRICK= :COLOR 5 :DRAW 90 :RIGHT 5 :DRAW 90 :RIGHT 2 :DRAW 1 : :JUMP 2 :DRAW 90 :RIGHT 10 :DRAW 90 :LEFT CONS-GAME::=PURPLE-BRICK= :COLOR 5 : :DRAW 90 :RIGHT 5 :DRAW 90 :RIGHT 2 :DRAW 1 :JUMP 2 :DRAW 90 :RIGHT 10 :DRAW : :POPLOC :PUSHLOC CONS-GAME::=BLUE-BRICK= :COLOR 5 :DRAW 90 :RIGHT 6 :DRAW 90 : :RIGHT 5 :DRAW 90 :RIGHT 6 :DRAW 90 :LEFT CONS-GAME::=BLUE-BRICK= :COLOR 5 : :DRAW 90 :RIGHT 6 :DRAW 90 :RIGHT 5 :DRAW 90 :RIGHT 6 :DRAW 90 :LEFT 1 :JUMP : :NOOP :PUSHLOC 90 :RIGHT 3 :JUMP :DROP-REACTOR :POPLOC :POPLOC :POPLOC : :DROP-DRONES

The twist on LOGO is that it's a Forth-style prefix notation. I maintain a stack of data items for each world. The LOGO program is generated according to a supplied grammar. When a non-keyword symbol is encountered, push its value onto the stack. When a string or number is encountered, push it onto the stack also. But when a keyword-symbol is encountered, we invoke the correspondingly-named method on the =world= object, which may pull arguments from the stack. The operation :COLOR sets the "paint color", in this case the type of game object to draw. The operations :PUSHLOC and :POPLOC save and restore (respectively) the turtle's current position and orientation. :DRAW and :JUMP move N squares in the current direction, either painting (with :DRAW) or not painting (:JUMP).

Here's part of a "reactor level" generation grammar:

: '((world >> (rod-square : :origin : :pushloc : 45 :right : 5 :jump : =exit= :color :drop : :poploc : 90 :right : 20 :jump : 90 :left : 25 :jump : 90 :left : :pushloc security-structure :poploc : :drop-drones)) : (rod-angle >> 90 45) : (rod >> (9 :jump : :pushloc : =barrier= :color : rod-angle :right : 7 :draw : :poploc)) : (rod-row >> (rod rod rod rod rod 10 :jump 90 :right)) : (rod-square >> (rod-row rod-row rod-row rod-row)) : (side-chamber >> (:pushloc : room3 90 random-turn : room3 90 :left : 1 :jump : gun-maybe : :pushloc : 90 :right : 3 :jump : :drop-reactor : :poploc : :poploc)) : (gun-maybe >> :noop :noop (=shocker= :color :drop)) : (security-structure >> (room 90 :left : room 90 :left : room 90 :left : room 90 :right : 6 :jump : :pushloc room2 90 random-turn room2 :poploc : side-chamber)) : (random-turn >> :right :left) : (random-brick >> =purple-brick= =blue-brick=)

This is a big change for XE2. With turtle graphics it's easy to scale and rotate drawing elements, and express their mututal arrangement in both absolute and relative terms. But the drawing elements can be anything, because the keywords in the randomly generated sentences can trigger any method you choose to define---not just LOGO-like operations. So all the other existing tools in XE2 (lines, boxes, circles, plasma) are now tied together into a cohesive and extensible framework for procedural content generation of all kinds, not just levels. (I'm interested in seeing what can happen with procedural story elements.)

A related development is the porting of cell-mode from Emacs Lisp into Common Lisp. It's a sort of object-oriented spreadsheet program with dataflow from left-to-right amongst cells of different types. Instead of implementing a new grid structure, I made a new system called "forms". One can build a spreadsheet UI out of game objects, or open an editable spreadsheet view of a game world. Combine this ability to hand-edit with the procedural generation tools, and we could have a very powerful interactive gamesdev environment.

Thanks for reading everyone.