I wanted to play with some graphics. I don't know much about
graphics, so I wanted to start with the basics. I played around
with a couple of demos and I found that easiest to get reliably
working was SDL2.
After downloading the SDL binary library and installing the FFI
bindings with Quicklisp, I was off and running. You can find
numerous SDL demos and tutorials on line and I tried a number of
them. After I felt confident I decided to try something simple.
One thing I've noticed about graphics programs is the ubiquity of
mutable state. Everything seems mutable and is freely modified and
global variables abound. As a mostly functional programmer, I am
alarmed by this. I wanted to see where we'd get if we tried to be
more functional in our approach and avoid mutable data structures
where practical.
Now the pixels on the screen had best be mutable, and I'm not
trying to put a functional abstraction over the drawing primitives.
We'll encapsulate the rest of the state in a state machine that is
driven by the SDL event loop. The state machine will keep track of
time and the current world. The current world is simply an
immutable list of immutable objects. The state machine can
transition through a render! phase, where it renders
all the objects in the current world to a fresh frame. It attempts
to do this about 75 times a second. The state machine can also
transition through a next-world phase, where the
current world and a delta-t are used to compute a new
version of the world.
Our run program will take the initial list of objects.
We'll start by initializing SDL, creating a window, and allocating a
renderer for that window:
(defun run (initial-world)
(sdl2:with-init (:video)
(sdl2:with-window (window
:h +window-height+
:w +window-width+
:flags '(:shown))
(sdl2:with-renderer (renderer window :index -1 :flags '())
... )))
Now we need the event loop state. last-ticks
records the value from sdl2:get-ticks from the last
time we processed the :idle event. This will be used
to compute the elapsed time in ticks. render-ticker
will record how many ticks have elapsed since the last time we
rendered a frame to the screen. When render-ticker
exceeds a certain amount, we'll call (render!
current-world) and reset the ticker to
zero. title-ticker will record how many ticks have
occurred since the last time the window title was updated.
When title-ticker exceeds a certain amount, we'll
call sdl2:set-window-title to update the window title
with some stats. sim-count is simply the number of
times we've iterated next-world
and frame-count is the number of times we've
called render!. These are reset to zero every time we
refresh the window title, so we'll have the frames per second and
the world steps per second in the window title.
(let ((last-ticks 0)
(render-ticker 0)
(title-ticker 0)
(sim-count 0)
(frame-count 0)
(world initial-world))
(flet ((title-tick! (dticks)
(incf title-ticker dticks)
(when (>= title-ticker 1000)
(decf title-ticker 1000)
(sdl2:set-window-title window (format nil "Sim rate: ~d, Frame rate: ~d" sim-count frame-count))
(setq sim-count 0)
(setq frame-count 0)))
(world-tick! (dticks)
(incf sim-count)
(setq world (next-world world (/ dticks 1000))))
(render-tick! (dticks)
(incf render-ticker dticks)
(when (>= render-ticker 13)
(incf frame-count)
(decf render-ticker 13)
(render-world! renderer world))))
Now we can run the event loop. The idle event is where the action
happens:
(sdl2:with-event-loop (:method :poll)
(:idle ()
(let ((this-ticks (sdl2:get-ticks)))
(if (= this-ticks last-ticks)
(sdl2:delay 1)
(let ((dticks (- this-ticks last-ticks)))
(setq last-ticks this-ticks)
(title-tick! dticks)
(world-tick! dticks)
(render-tick! dticks)))))
(:keydown (:keysym keysym)
(case (sdl2:scancode keysym)
(:scancode-escape (sdl2:push-quit-event))
(:scancode-x (sdl2:push-quit-event))))
(:quit () t))
Now that's a bunch of state, but it's more or less under control
because what we have is a state machine and the state variables
aren't accessible to anything.
render-world! is straightforward. It clears the
renderer, calls render! on every object in the world,
and presents the renderer for display.
(defun render-world! (renderer world)
(sdl2:set-render-draw-color renderer #x00 #x00 #x00 #xFF)
(sdl2:render-clear renderer)
(mapc (lambda (object) (render! renderer object)) world)
(sdl2:render-present renderer)
)
next-world is a function that maps the current world
to the next. It basically calls next on each object in
the world and accumulate the results. We want objects to be able to
go away, so if (next object)
returns nil, we don't accumulate anything in the new
world. If next returns the object unchanged, it will
be accumulated unchanged in the next
world. (next object) returns a new version of an
object to simulate an update to the object. We want to be able to
increase the amount of objects, so we
allow (next object) to return a list of objects
to be accumulated.
(defun next-world (previous-world dt)
(fold-left
(lambda (items item)
(let ((more (next item dt)))
(cond ((null more) items)
((consp more) (append more items))
(t (cons more items)))))
'()
previous-world))
We'll start with a user-controlled player.
(defclass player ()
((x :initarg :x
:reader get-x)
(y :initarg :y
:reader get-y)))
Everything that is to be displayed needs a render!
method. This one just draws a little green triangle facing up.
(defmethod render! (renderer (player player))
(let ((x (floor (get-x player)))
(y (floor (get-y player))))
(sdl2:set-render-draw-color renderer #x00 #xFF #x00 #xFF)
(sdl2:render-draw-line renderer (- x 8) (+ y 8) (+ x 8) (+ y 8))
(sdl2:render-draw-line renderer (- x 8) (+ y 8) (- x 1) (- y 16))
(sdl2:render-draw-line renderer (+ x 8) (+ y 8) x (- y 16))
(sdl2:render-draw-point renderer x y)
))
The next method computes the player in the next
world:
(defun x-input ()
(- (if (sdl2:keyboard-state-p :scancode-right)
1
0)
(if (sdl2:keyboard-state-p :scancode-left)
1
0)))
(defun y-input ()
(- (if (sdl2:keyboard-state-p :scancode-down)
1
0)
(if (sdl2:keyboard-state-p :scancode-up)
1
0)))
(defparameter +player-speed+ 200.0) ;; pixels per second
(defmethod next ((player player) dt)
(let ((new-x (max 8 (min (- +window-width+ 8)
(+ (get-x player)
(* (x-input) +player-speed+ dt)))))
(new-y (max 16 (min (- +window-height+ 8)
(+ (get-y player)
(* (y-input) +player-speed+ dt))))))
(make-instance 'player :x new-x :y new-y)))
Once we've defined a render! method and
a next method, we're ready to go. If we
call run on a list containing a player object, we'll
have our little player on the screen controllable with the arrow
keys.
An enemy ship can be defined.
(defclass enemy ()
((x :initarg :x :reader get-x)
(y :initarg :y :reader get-y)
(dx :initarg :dx :reader get-dx)
(dy :initarg :dy :reader get-dy)))
(defmethod next ((enemy enemy) dt)
(let ((new-x (+ (get-x enemy) (* (get-dx enemy) dt)))
(new-y (+ (get-y enemy) (* (get-dy enemy) dt))))
(when (and (>= new-x 8)
(< new-x (+ +window-width+ 8))
(>= new-y 8)
(< new-y (- +window-height+ 16)))
(make-instance 'enemy
:x new-x
:y new-y
:dx (get-dx enemy)
:dy (get-dy enemy)))))
;;; Render method omitted
As given, enemy ships will drift at constant speed until they run
off the screen. We'd like to replenish the supply, so we'll make an
enemy spawner:
(defclass enemy-spawner ()
((timer :initarg :timer :initform 0 :reader get-timer)))
(defmethod next ((spawner enemy-spawner) dt)
(let ((new-time (- (get-timer spawner) dt)))
(if (> new-time 0)
(make-instance 'enemy-spawner :timer new-time)
(list (make-instance 'enemy-spawner :timer (+ 1 (random 4)))
(make-instance 'enemy :x (random (+ (- +window-width+ 32) 16))
:y 16
:dx (- 25 (random 50))
:dy (+ (random 100) 50))))))
(defmethod render! (renderer (enemy-spawner enemy-spawner))
nil)
The
render! method doesn't do anything so a spawner
doesn't have an image. It simply has a timer. To compute the next
spawner, we subtract
dt and create a new spawner with
the reduced amount of time. If that's not a positive amount of
time, though, we create two objects: a new spawner with somewhere
between 1 and 5 seconds time and a new enemy ship.
We'll modify our player to allow him to shoot at the enemy:
(defclass player ()
((x :initarg :x
:reader get-x)
(y :initarg :y
:reader get-y)
(fire-cycle :initarg :fire-cycle
:initform 0
:reader get-fire-cycle)))
(defmethod next ((player player) dt)
(let ((new-x (limit 8 (- +window-width+ 8) (+ (get-x player) (* (x-input) +player-speed+ dt))))
(new-y (limit 16 (- +window-height+ 8) (+ (get-y player) (* (y-input) +player-speed+ dt))))
(next-fire-cycle (- (get-fire-cycle player) dt)))
(if (and (sdl2:keyboard-state-p :scancode-space)
(< next-fire-cycle 0))
(list
(make-instance 'player
:x new-x
:y new-y
:fire-cycle .1)
(make-instance 'bullet
:x (- (get-x player) 8)
:y (- (get-y player) 16)
:dx 0
:dy (- +bullet-speed+))
(make-instance 'bullet
:x (+ (get-x player) 8)
:y (- (get-y player) 16)
:dx 0
:dy (- +bullet-speed+)))
(make-instance 'player
:x new-x
:y new-y
:fire-cycle next-fire-cycle))))
A bullet is a simple moving object:
(defclass bullet ()
((x :initarg :x :reader get-x)
(y :initarg :y :reader get-y)
(dx :initarg :dx :reader get-dx)
(dy :initarg :dy :reader get-dy)))
(defmethod next ((bullet bullet) dt)
(let ((new-x (+ (get-x bullet) (* (get-dx bullet) dt)))
(new-y (+ (get-y bullet) (* (get-dy bullet) dt))))
(when (and (>= new-x 0)
(< new-x +window-width+)
(>= new-y 0)
(< new-y +window-height+))
(make-instance 'bullet
:x new-x
:y new-y
:dx (get-dx bullet)
:dy (get-dy bullet)))))
At this point we can move around the screen and shoot at enemies
that spawn periodically. The problem is that the bullets go right
through the enemy. We need to handle object collisions. We'll
modify the next-world function. As it loops over the
objects in the world, it will perform an inner loop that checks for
collisions with other objects. If two objects collide, a function
is called to get the collision results and those results are added
to the list of objects in the world. If an object doesn't collide
with anything, the next method is called to get the
next version of the object.
(defun next-world (previous-world dt)
(let outer ((tail previous-world)
(next-world '()))
(cond ((consp tail)
(let ((this (car tail)))
(let inner ((those (cdr tail)))
(cond ((consp those)
(let ((that (car those))
(others (cdr those)))
(if (collides? this that)
(outer (append (collide this that) (delete that (cdr tail)))
next-world)
(inner others))))
((null those)
(outer (cdr tail)
(let ((more (next this dt)))
(cond ((consp more) (append more next-world))
((null more) next-world)
(t (cons more next-world))))))
(t (error "Bad list."))))))
((null tail) next-world)
(t (error "Bad list.")))))
We define collides? as a generic function that
returns nil by default
(defgeneric collides? (this that)
(:method ((this t) (that t)) nil)
)
so that most objects don't collide. In the case where
something
does collide, we'll define
collide
as a generic function that returns
nil by default
(defgeneric collide (this that)
(:method ((this t) (that t)) nil)
)
so when two objects collide, they simply disappear.
collides? will be called on pairs of objects in no
particular order, so method pairs will be needed to handle both
orders. We'll define collides? methods on bullets and
enemies that checks if the bullet is within the bounding box of the enemy:
(defmethod collides? ((this bullet) (that enemy))
(and (> (get-x this) (- (get-x that) 8))
(< (get-x this) (+ (get-x that) 8))
(> (get-y this) (- (get-y that) 8))
(< (get-y this) (+ (get-y that) 8))))
(defmethod collides? ((this enemy) (that bullet))
(collides? that this))
At this point, we can shoot enemy ships. The default method
for collide between an enemy and a bullet
returns nil so the enemy and the bullet simply
disappear. If we were fancy, we could arrange for it to return an
explosion object or several debris objects.
It would be nice to keep a tally of the number of
enemy ships we have shot. We don't have to add any extra machinery
for this. We create a score class and a point class:
(defclass score ()
((value :initarg :value
:reader get-value)))
(defmethod next ((score score) dt) score)
;;; Render method prints score on screen.
(defclass point ()
((value :initarg :value
:reader get-value)))
(defmethod next ((point point) dt) point)
(defmethod render! (renderer (point point)) nil)
Scores and points are immutable objects without positions, but we'll
define methods so that when a score and a point collide, the result is
a higher score.
(defmethod collides? ((this point) (that score)) t)
(defmethod collides? ((this score) (that point)) t)
(defmethod collide ((this point) (that score))
(list (make-instance 'score
:font (get-font that)
:value (+ (get-value this) (get-value that)))))
(defmethod collide ((this score) (that point))
(collide that this))
Now we'll define a bullet colliding with an enemy to produce a point:
(defmethod collide ((this bullet) (that enemy))
(list (make-instance 'point :value 1)
;; add explosion object here
))
(defmethod collide ((this enemy) (that bullet))
(collide that this))
So when you shoot an enemy, the bullet and enemy disappear to be
replaced by a point. On the next update, the point will collide
with the score to be replaced with an updated score.
At this point we've got a little demo game where we can fly a
ship around and shoot enemies and a running score is kept. The
world model is immutable and worlds are functions of previous
worlds. I'll call it a successful proof of concept.
But did this buy us anything? We don't have mutable state per
se, but we've kind of cheated. When we create new versions of
an object, each version is immutable, but the sequence of versions
taken as a whole seem to be evolving over time. For example,
consider the score. At each time step, there is an immutable
score object, but over time what is considered the current score
changes. We've eliminated the direct problems of mutation, but
we've introduced the problem of keeping track of what series of
immutable versions correspond to a single evolving instance.
In this small example, we're not keeping track of the evolving
objects. For instance, each bullet, as it is updated from step to
step, is actually created anew at its new position on each step. The
old bullet instance is dropped and the new instance really has no
idea how it got there. Bullets are such simple objects that this
doesn't matter, but the current score is different. It makes sense
for there to be a singleton score object that increases over time,
but we haven't built that in to our model. Instead, we've designed
a set of collision interactions that drive the score.
We've eliminated the direct mutable state in our objects and our
world, but sometimes we want to model stateful objects. We
therefore create objects that represent state transitions
(e.g. points) and then use the collision mechanism to combine
the transition objects with the objects that represent physical
entities. That seems a bit convoluted, and I don't think it will
scale.
On the other hand, we do gain the immediate benefits of the world
and the objects being immutable. Saving and restoring a world is
trivial. Reasoning about objects at each update is easy because the
objects don't change, but we now have to reason about how objects
appear to change in the long run.
The tradeoff of immutable objects is increased allocation. But
although a lot more consing is happening, most of it can be quickly
reclaimed by the generational collector, so noticable GC pauses are
infrequent. I haven't measured the performance, but it is certainly
adequate for the little example I wrote. If you had a mechanism to
reason about the objects as linear types (Sufficiently Smart
Compiler™), you could determine when you can update
objects in place and avoid reallocating.
The world model, simply a list of objects, is flexible, but not
well structured. For instance, the current score and the bullets
are among the elements mixed together in this list. You'd have to
search this list to find specific elements or filter this list to
find elements of a certain type.
The simple collision model is O(n2), so it can't
handle a ton of objects. A more sophisticated world model would
be needed to keep track of different classes of collidable objects
to avoid the O(n2) search. For example, if
bullets were kept separately, we could avoid checking if they
collide with each other.
The point of this exercise was to play with graphics and see what
you can do without the mutable state that is alarmingly ubiquitous.
It turns out that you can go pretty far, but it's kind of strange.
