#+TITLE: Common Lisp and Roguelike Games
#+AUTHOR: David O'Toole <dto@gnu.org>
* Introduction
** About the speaker
My name is David O'Toole, and I am a Lisp developer living in
Worcester County, Massachusetts. I frequently work in both Common Lisp
and Emacs Lisp. I've had a lifelong interest in video games, from
Atari 2600 up to the PlayStation 3, and this led me to study computer
science and eventually enter the games industry. I'm now an
independent consultant and do audio recording hardware, software, and
music production work.
** About the software
RLX is a next-generation roguelike engine currently being ported to
Common Lisp. RLX is in an alpha state, and only about 85% ported from
Emacs Lisp into CL. I will demonstrate various features of the engine
by showing a playable alpha game entitled "Void Mission Zero", and
attempt to show interesting code that gives my solutions to the
problems of creating roguelike games with Common Lisp, but I cannot
present a finished product at this date and I hope people will bear
with me if there are a few glitches and missing or not-yet-ported
features.
** Why Lisp?
*** Rapid development
**** Trying out new ideas
**** Original prototype elisp version written in about one calendar month
*** Compact code (engine currently about 6000 lines)
*** Roguelikes need good AI, there's lots of Lisp AI resources (PAIP etc)
*** Flexibility (I made my own custom object system for the task.)
** What is a roguelike game like (typically)?
*** The gameworld's space is [[http://en.wikipedia.org/wiki/Tile-based_game][2-D and Tile-based]]
The gameworld is divided into discrete cells of equal size, like
[[http://en.wikipedia.org/wiki/Checkers][Checkers]], but with no restrictions on the size or shape of the
board. This world is depicted from directly overhead as in the
familiar [[http://en.wikipedia.org/wiki/The_Legend_of_Zelda][Legend of Zelda]].
*** All objects are the same size: one square.
Although more than one item can occupy the same square, everything is
modeled (and depicted!) as roughly the same size. This is to be
contrasted with 2-D game engines such as that for [[http://en.wikipedia.org/wiki/Ultima_VII][Ultima VII]], in which
pieces can be different sizes and heights, and be stacked and overlap
one another as in [[http://en.wikipedia.org/wiki/Mahjong][Mahjong]].
*** Gameworld objects are represented iconically onscreen.
- Early roguelikes: a single monochrome [[http://en.wikipedia.org/wiki/ASCII][ASCII]] character per object
- Middle roguelikes: colored ASCII characters, or small graphical
tiles which can be substituted for the
characters.
- Recent roguelikes: true-color, Unicode, or full bit-mapped graphical
display with transparency.
*** World simulation, not "storytelling"
Objects and characters in a roguelike can react with one another in
logical but often still surprising ways. The interactions tell the
story, not screens full of expository text.
- Swords and bracelets become cursed and impossible to be removed.
- Scrolls catch fire, shields break.
- You can play a priest, pray to a God, and bless yourself or your
items.
- One can summon or possess other characters.
*** Turn-based action
*** Almost always single-player
*** Procedural content generation
**** Randomly generated settings with semi-realistic terrain
**** Many interesting algorithms available for trees, rivers, corridors, mazes
**** Re-playability
*** The game has a model of the player's knowledge
- Your knowledge of most found items is limited at first---it may
take time and experience (or an Identify spell) to learn that a
leather shield is actually a +3 magic leather shield of fire
protection. Drinking potions will generally clue you into the
effects, but they can be deadly.
- This requires at least some very simple [[http://en.wikipedia.org/wiki/Knowledge_representation][knowledge representation]].
*** "Permadeath"
Player death is permanent; you must re-start the game with a new
character if you die. This is a harsh restriction, but the
re-playability of roguelike games makes it feasible. Likewise, it would
make little sense for a game developer to include permadeath in a
Japanese-style [[http://en.wikipedia.org/wiki/Console_role-playing_game][console role playing game]], because these are generally
quite long and linear storytelling experiences and are usually played
through and completed just once.
* CLON: Common Lisp Object Network
** Overview
*** Simple and small, under 800 lines of code
*** No division into classes and objects
*** Instead you define template objects called prototypes
*** Any object (including prototypes) can be cloned
*** Single inheritance
*** Messages may be queued, filtered, and forwarded
**** TODO Explain later why these are so useful
*** Mix synchronous function calls and message passing in one function
*** Links for further reading
- http://en.wikipedia.org/wiki/Prototype-based_programming
- http://en.wikipedia.org/wiki/Message_passing
- http://www.cliki.net/Garnet
- http://iolanguage.com/about/
** Download
- [[file:../packages/clon-1.0.tar.gz][Release tarball: clon-1.0.tar.gz]]
- see also [[http://github.com/dto/clon/tree/master][CLON at github.com]]
** Code examples
*** What is an object in CLON?
[[file:~/clon/clon.lisp::defstruct%20object][file:~/clon/clon.lisp::defstruct object]]
**** Why property lists and not hash tables?
[[info:elisp:Hash%20Tables][info:elisp:Hash Tables]]
*** Defclass-like prototype definitions
First we must define a prototype and name its fields:
: (define-prototype rectangle ()
: x y width height)
[[file:~/clon/clon.lisp::defmacro%20define%20prototype%20name][file:~/clon/clon.lisp::defmacro define prototype name]]
We could also have provided initialization forms for the slots, and
documentation strings:
: (define-prototype rectangle ()
: (x :initform 0
: :documentation "The x-coordinate of the rectangle's top-left corner.")
: (y :initform 0
: :documentation "The y-coordinate of the rectangle's top-left corner.")
: (width :documentation "The width of the rectangle.")
: (height :documentation "The height of the rectangle."))
*** Single inheritance
And if there was a "shape" prototype, from which we would like
"rectangle" to inherit data and methods, we might have written:
: (define-prototype rectangle (:parent =shape=)
: (x :initform 0
: :documentation "The x-coordinate of the rectangle's top-left corner.")
: (y :initform 0
: :documentation "The y-coordinate of the rectangle's top-left corner.")
: (width :documentation "The width of the rectangle.")
: (height :documentation "The height of the rectangle."))
Notice the equals signs surrounding the parent object's name; all
objects made with define-prototype are accessible via special
variables with such names.
The reason for this is that usually you want to call a widget a
widget, but if that name is taken for a special variable "widget"
whose value was the prototype for all widgets, then you will have to
use some other probably less effective name for the binding, like "w"
or "wt" or "wydget", everywhere you want to just talk about a "widget"
in your code. So instead we only reserve the equals-sign-delimited
name:
: =WIDGET=
*** Cloning objects
The function CLON:CLONE is used to create new objects from these
prototypes. Now we write an initializer, which is passed any creation
arguments at the time of cloning:
[[file:~/clon/clon.lisp::defun%20clone%20prototype%20rest%20initargs][file:~/clon/clon.lisp::defun clone prototype rest initargs]]
: (define-method initialize rectangle (&key width height)
: (setf <width> width)
: (setf <height> height))
Notice how field accesses can be written with the angle brackets; this
works both for reading and for writing, so long as you use =setf= for
the latter.
[[file:~/clon/clon.lisp::defun%20transform%20tree%20tester%20transformer%20tree][file:~/clon/clon.lisp::defun transform tree tester transformer tree]]
Now when you say:
: (setf rectangle (clone =rectangle= :width 5 :height 12))
The rectangle's initializer method is invoked with those arguments,
and a rectangle of the correct height and width is created.
*** Basic field access
: (field-value :width rectangle)
: (setf (field-value :height rectangle) 7)
[[file:~/clon/clon.lisp::defun%20field%20value%20field%20object%20optional%20noerror][file:~/clon/clon.lisp::defun field value field object optional noerror]]
*** Methods
Now we define a few methods:
: (define-method area rectangle ()
: (* <width> <height>))
:
: (define-method print rectangle (&optional (stream t))
: (format stream "height: ~A width: ~A area: ~A"
: <height> <width>
: [area self]))
[[file:~/clon/clon.lisp::defmacro%20define%20method][file:~/clon/clon.lisp::defmacro define method]]
And invoke them with the aforementioned square bracket notation.
: (defvar rect (clone =rectangle= :width 10 :height 8))
:
: [print rect]
The result:
: "height: 8 width: 10 area: 80"
The bracket syntax is done with a reader macro:
[[file:~/clon/clon.lisp::defun%20message%20reader%20stream%20char][file:~/clon/clon.lisp::defun message reader stream char]]
*** Message queueing
CLON also supports a concept called message queueing. When there is an
active message queue, messages may be entered into the queue instead
of directly invoking a method:
: [queue>>render widget]
: [queue>>attack self :north]
The sender, receiver, method name, and arguments are all recorded in
the queue. The developer can then filter or process them before
sending.
[[file:~/clon/clon.lisp::Message%20queueing][file:~/clon/clon.lisp::Message queueing]]
*** Message forwarding
And finally, I will mention message forwarding, which handles the case
that an object has no handler for a particular method. This is akin to
[[http://en.wikipedia.org/wiki/Smalltalk][Smalltalk's]] "doesNotUnderstand" concept.
[[file:~/clon/clon.lisp::Message%20forwarding][file:~/clon/clon.lisp::Message forwarding]]
* RLX: A Next-Generation Common Lisp Roguelike Engine
** The "console" is a pretend home computer in 80's style
*** Basic input and output functions
**** LISPBUILDER-SDL
http://lispbuilder.sourceforge.net/lispbuilder-sdl.html
**** Drawing to the screen (list of active widgets)
**** Responding to key press events
*** Resources and Modules
**** From "driver-dependent objects" to string handles
**** The PAK file format
[[file:~/rlx/console.lisp::PAK%20resource%20interchange%20files][file:~/rlx/console.lisp::PAK resource interchange files]]
[[file:~/rlx/vm0/vm0.pak::0]]
**** Load-on-demand
[[file:~/rlx/console.lisp::defun%20index%20pak%20module%20name%20pak%20file][file:~/rlx/console.lisp::defun index pak module name pak file]]
**** The different resource types and their loading handlers
**** Not just links to other files: the "data" field
Not yet ported: the map editor
[[file:~/images/RogueLike-5.png]]
[[file:~/images/RogueLike-11.png]]
file:~/images/RogueLike-10.png
[[file:~/images/RogueLike-11.png]]
[[file:~/images/RogueLike-8.png]]
[[file:~/images/RogueLike-9.png]]
**** Standard resources (colors, icons)
[[elisp:(image-dired "~/rlx/standard")]]
file:~/rlx/rgb.lisp
**** Resource aliases and transformations
[[file:~/rlx/console.lisp::Functions%20to%20load%20find%20and%20transform%20resources][file:~/rlx/console.lisp::Functions to load find and transform resources]]
** Mathematics
[[file:~/rlx/math.lisp::math%20lisp%20math%20and%20geometry%20routines][file:~/rlx/math.lisp::math lisp math and geometry routines]]
*** Geometry calculations
*** Shape tracing
*** Line of sight
[[file:~/rlx/math.lisp::defun%20trace%20line%20trace%20function%20x0%20y0%20x1%20y1][file:~/rlx/math.lisp::defun trace line trace function x0 y0 x1 y1]]
*** Lighting
[[file:~/images/RogueLike-11.png]]
*** Plasma
[[file:~/images/RogueLike-10.png]]
[[file:~/images/RogueLike-7.png]]
*** Pathfinding with A*
http://en.wikipedia.org/wiki/A-star_search_algorithm
[[file:~/rlx/path.lisp::path%20lisp%20A%20pathfinding%20for%20RLX][file:~/rlx/path.lisp::path lisp A pathfinding for RLX]]
** Widgets: interactive graphical elements with offscreen drawing
*** Widget basics
[[file:~/rlx/widgets.lisp::define%20prototype%20widget][file:~/rlx/widgets.lisp::define prototype widget]]
*** Keymaps
*** Formatted text display
[[file:~/rlx/widgets.lisp::Formatted%20display%20widget][file:~/rlx/widgets.lisp::Formatted display widget]]
*** Command prompts
[[file:~/rlx/widgets.lisp::Command%20prompt%20widget][file:~/rlx/widgets.lisp::Command prompt widget]]
** Cells: the atoms of the game world
*** Overview
[[file:~/rlx/cells.lisp::define%20prototype%20cell][file:~/rlx/cells.lisp::define prototype cell]]
*** Statistics
[[file:~/rlx/cells.lisp::Statistics]]
*** Categories
[[file:~/rlx/cells.lisp::Cell%20categories][file:~/rlx/cells.lisp::Cell categories]]
*** Managing turns with the "Action Points System"
[[file:~/rlx/cells.lisp::Action%20Points][file:~/rlx/cells.lisp::Action Points]]
*** Cell movement
[[file:~/rlx/cells.lisp::Cell%20movement][file:~/rlx/cells.lisp::Cell movement]]
*** Containers
[[file:~/rlx/cells.lisp::Containers]]
*** Manipulating and picking up objects
[[file:~/rlx/cells.lisp::Finding%20and%20manipulating%20objects][file:~/rlx/cells.lisp::Finding and manipulating objects]]
*** Modeling player knowledge (not yet ported)
*** Equipment
[[file:~/rlx/cells.lisp::Equipment]]
*** Simple combat
[[file:~/rlx/cells.lisp::Combat]]
*** Proxying (not yet ported)
** Worlds composed of cells
*** The center of the action: time, space, messages
[[file:~/rlx/worlds.lisp::define%20prototype%20world][
file:~/rlx/worlds.lisp::define prototype world]]
*** Time: action points
[[file:~/rlx/worlds.lisp::unless%20can%20act%20player%20phase%20number][file:~/rlx/worlds.lisp::unless can act player phase number]]
[[file:~/rlx/worlds.lisp::loop%20while%20can%20act%20cell%20phase%20number%20do][file:~/rlx/worlds.lisp::loop while can act cell phase number do]]
*** Environmental conditions
[[file:~/rlx/worlds.lisp::define%20prototype%20environment][file:~/rlx/worlds.lisp::define prototype environment]]
*** Lighting
[[file:~/rlx/worlds.lisp::define%20method%20render%20lighting%20world%20cell][file:~/rlx/worlds.lisp::define method render lighting world cell]]
*** Schemes for automatic world generation
[[file:~/rlx/worlds.lisp::define%20method%20generate%20world%20optional%20parameters][file:~/rlx/worlds.lisp::define method generate world optional parameters]]
*** Narrating events and providing messages to the player
[[file:~/rlx/worlds.lisp::Narration%20widget][file:~/rlx/worlds.lisp::Narration widget]]
*** Viewports
[[file:~/rlx/worlds.lisp::Standard%20tile%20display%20viewport%20widget][file:~/rlx/worlds.lisp::Standard tile display viewport widget]]
** Void Mission Zero: An example game module
*** Particles and pistols
[[file:~/rlx/vm0/vm0.lisp::Muon%20particles%20trails%20and%20pistols][file:~/rlx/vm0/vm0.lisp::Muon particles trails and pistols]]
*** A health pick-up
[[file:~/rlx/vm0/vm0.lisp::the%20med%20hypo][file:~/rlx/vm0/vm0.lisp::the med hypo]]
*** A simple AI bot
[[file:~/rlx/vm0/vm0.lisp::The%20Purple%20Perceptor][file:~/rlx/vm0/vm0.lisp::The Purple Perceptor]]
*** Slightly more complex AI bot
[[file:~/rlx/vm0/vm0.lisp::The%20Red%20Perceptor][file:~/rlx/vm0/vm0.lisp::The Red Perceptor]]
*** Ion shield
[[file:~/rlx/vm0/vm0.lisp::The%20ion%20shield][file:~/rlx/vm0/vm0.lisp::The ion shield]]
*** Explosions and mines
[[file:~/rlx/vm0/vm0.lisp::An%20explosion][file:~/rlx/vm0/vm0.lisp::An explosion]]
*** The Player
[[file:~/rlx/vm0/vm0.lisp::The%20player%20and%20his%20remains][file:~/rlx/vm0/vm0.lisp::The player and his remains]]
* Future work
** Now comes the hard part: game design!
** Finish porting Emacs Lisp parts of engine
** Finish rewriting cell-mode and the RLX resource/ymap editor
** Mini-map radar view
** Sound effects
** Context-dependent music with .xm and .ogg files
** More stuff! Weapons, enemies, stories
** Redefining roguelike development
