Weening myself off of global state - what's the idiomatic way to solve this?
Brandon Ferguson
with a few things in the world of Clojure. I've been using Processing
to learn Clojure (since I'm somewhat familiar with Processing) but the
tough part has been dealing with things like x, y positions of objects
without keeping some global state (I'm not sure if it's even
possible).
The code in question is: https://gist.github.com/887256
All this does is bounce a ball around a screen, for every frame
Processing calls draw which moves the ball one frame. Since I'm not
the one driving the loop I ended up using atoms to update some bits of
global state but that feels really dirty.
If I could drive the frames it would be easy to use recur or some
other bit of state passing as I render each successive frame. I've
considered using sequences and passing a frame number (which would be
stored in a global as well) in but then it'd (I assume) have to run
through every number up to that the one I passed it. Seems like
performance would degrade the longer it ran. There's also this idea
rattling around in my head where I'd just rewrite the function
everytime with the new state - but seems like you couldn't scale that
to multiple balls bouncing around (which is the next step) - and God
knows what, if any, performance implications that would have.
So I'm not sure where that leaves me - learning functional stuff can
be wonderfully mind breaking but sometimes I feel like I don't even
have the tools in my head to work some things out. Is there some
technique I'm missing for dealing with state between successive calls
of a function?
How would you solve something like this?
-Brandon
jweiss
draw-ball [ball] ...)
Ken Wesson
> I'm not sure if this is the place to ask this but I've been struggling
> with a few things in the world of Clojure. I've been using Processing
> to learn Clojure (since I'm somewhat familiar with Processing) but the
> tough part has been dealing with things like x, y positions of objects
> without keeping some global state (I'm not sure if it's even
> possible).
If you're currently using atoms, you already have a function to
compute the new position from the old, say, next-position, which you
use with something like (swap! ball-pos next-position).
Now consider this: (iterate next-position initial-ball-pos). That
evaluates to an (infinite!) sequence of ball positions. You could have
an animation loop step along this sequence, render a frame, wait,
step, render, wait, etc. until the ESC key is hit (or whatever).
For multiple balls that might interact with one another, a given
ball's next position becomes a function of the other ball positions
and not just its own. So you end up with:
(iterate next-world-state initial-world-state)
with world states being e.g. maps of ball-IDs to ball-positions or
something. Obviously, other kinds of changeable world state can be
included, too, e.g. Pong paddle positions, or the locations and amount
of damage taken by Arkanoid bricks.
This works until you get interactive (e.g. letting a human player
control a paddle or something). At that point, iterate becomes a bit
icky because the function becomes impure (as it polls the input
devices).
Then you probably just want two components:
1. A Swing GUI that captures mouse and keyboard events in the game's
JPanel as well as rendering the frames there.
2. A game loop.
The simplest case uses the Swing EDT as the game loop, with a Timer
triggering game updates. But that requires mutable state for the game
state to persist between Timer events.
The other case keeps most of the game state immutable, but requires a
bit of mutability to pass input to the game from the GUI:
1. The Swing event handlers post input messages to a
LinkedBlockingQueue, or update atoms or refs holding the current
position of the mouse and state (down or up) of relevant mouse buttons
and keyboard keys.
2. The game loop runs in its own thread and looks something like this:
(loop [foo bar other game state variables]
...
(recur new-foo new-bar new-other ...)...)
The game checks the input state, or drains the LinkedBlockingQueue, or
whatever when it comes around to updating the player's position.
One way to do it is just to have a set of game world objects:
(loop [time (System/currentTimeMillis)
world (hash-set (cons (new-player) (generate-initial-world-state)))]
(let [world (map (partial update-position world) world)
new-objects (mapcat new-things world)
damages (reduce (partial merge-with +) {} (map do-damage world))
world (concat
new-objects
(remove dead?
(map (partial apply-damages damages) world)))]
(SwingUtilities/invokeAndWait
(fn []
(let [g (get-the-jpanel's-double-buffer-graphics)]
(doseq [obj world] (draw-on! obj g)))
(flip-the-jpanel's-double-buffer!)))
(if (some is-player? world)
(let [elapsed (- (System/currentTimeMillis) time)
sl (- *ms-per-frame* elapsed)]
(if (> sl 0) (Thread/sleep sl))
(recur (System/currentTimeMillis) world))
world)))
Here, new-player generates a new player object and
generate-initial-world-state generates a seq of other objects for the
initial world-state. The update-position function takes the world and
a game object and runs the latter's ai, returning a new game object
representing the old one's changed position (and possibly other state
changes). The world is passed in so that collision checks can be done
when needed.
The new-things function allows some game objects to potentially
generate more (e.g. shooting projectiles); it can return nil if the
object hasn't spawned anything, or a seq of new things. For instance,
if the player shoots a rocket, it may return [(new-rocket player-x
player-y player-dx player-dy)]; when the rocket hits something and
explodes, it may itself return (repeatedly *num-shards*
#(generate-shrapnel rocket-x rocket-y)).
The do-damage function takes a game object and returns a map of zero
or more other game objects that are damaged by that game object. This
usually involves collision, which is handled in update-position, so
update-position needs to cache the damage information for do-damage to
retrieve. For instance, that rocket's update-position can discover
that it has collided with something and set the rocket's health to
zero as well as store a map of things within the blast radius and the
damage they should take. The new-things function sees the rocket's
health at zero and spawns decorative shrapnel objects, since it just
exploded; these will draw themselves and move for a short time in a
straight line but that's it. The do-damage function just retrieves the
map stored during update-position.
The apply-damages function takes a damages map and a world object,
looks that object up in the map, if not found returns it unchanged,
otherwise returns a copy with reduced health. The dead? predicate just
sees if a game object's health is zero or lower.
Then there's draw-on!, which takes an object and a Graphics. Without
that you'd be playing blind. It and flip-the-jpanel's-double-buffer!
are the only impure functions here, besides the player object's
update-position AI which needs to poll the keyboard/mouse state info.
So there's a basic skeleton for a functional game loop. The loop exits
if there's no player object in the world, which happens if all player
objects get nailed by the dead? predicate, so quitting can be
implemented by having the player's update-position check for a quit
keypress and set the player's health to zero (by returning a player
object with no health) if necessary.
The loop returns the final world-state, so it can be checked to decide
what kind of game-over screen to display. (If the game has a victory
condition, when this is detected the game can "kill" the player and
also put something in the world-state to allow victory to be
distinguished from quit or the player actually died.) You can also add
a surrounding loop to allow multiple lives. Pause can simply pause in
the middle of the player's update AI; the GUI won't hang since it's
not the EDT. The pause would of course replace the UI appropriately
until unpaused, and check periodically for the unpause (or resort to
Java's wait/notify to avoid a polling loop and use less CPU).
Of course, the above is somewhat naive. In particular the world state
is just an unordered seq of objects. This will scale poorly when the
game world has a big and complex scrollable map, or very many objects
to check for collisions. Then you'll want something smarter, with
"geography", such as an interval tree on the x coordinates or
something.
Note that a lot of game objects would display, but not do anything
(e.g. explosion and shrapnel graphics, particles, etc.); there should
be a decorative? predicate and collision checks can use (remove
decorative? world) to skip the things that should not collide with the
target. (The decorative? objects' own update AI presumably completely
eschews collision checks.) Other objects might not be visible, while
having an effect, e.g. an in-game timer that causes a timed effect.
If, for instance, new enemies are to be spawned randomly, this thing
can have a no-op draw-on! and a no-op update-position, but its
new-things can occasionally return a non-empty collection. Other
timers are better embedded elsewhere; e.g. if the player picks up an
invulnerability powerup, the time remaining can be stored in the
player object, or even the time when it will wear off. The latter
makes things very simple:
(let [invulnerable? (> 0 (- (:invulnerable-until this)
(System/currentTimeMillis)))]
...)
with invulnerability pickup working simply by making the return value
use (+ System/currentTimeMillis 5000) or whatever as the
:invulnerable-until key's value.
There's a few other things that could be done. For example, there's
nothing in there about sound effects, though since that's part of the
game's "display" perhaps sound can be handled with graphics in
draw-on!. That isolates more side effects into this bang-function.
(Music can be cued in the player's draw-on!; it can check the current
level and the invulnerability timer, among other things, to decide
what music to play or continue playing, buffering a bit more of it for
the Java Sound engine to play back.) Another is that everything
non-insubstantial gets checked for collision with a given other object
twice, first A's update function checking for collision with B and
then vice versa. This could be simplified by adding a separate pass
over the objects to find collisions:
(loop [w (seq world) cmap {}]
(let [x (first w)]
(if-let [r (next w)]
(recur
r
(assoc
cmap
x
(loop [ww r colliders []]
(let [y (first r)
colliders (if (collides? y x) (conj colliders y) colliders)]
(if-let [rr (next ww)]
(recur rr colliders)
colliders))))))))
This should return a map whose keys are game objects and values are
vectors; if objects A and B collide, *either* A's vector will contain
B or vice-versa. With this, you'd pass A's vector rather than the
world to update-position when calling update-position for object A:
(map #(update-position (cmap %) %) world) rather than (map (partial
update-position world) world). The update-position code for A would
have to know what to do if it found B in this vector, and vice-versa.
The code above would be further modified for interval trees, of
course: the second loop wouldn't be over all the objects later than x
in the world seq, but rather over all the interval tree nodes
overlapping x's bounding box. There'd also have to be code to compute
an updated tree after update-positions. Indeed, world would become the
tree, traversable as a seq; the expression (concat new-things (remove
dead? ...)) would have to be wrapped in a call to build a new interval
tree out of that seq.
If the length of the list of game objects got big enough that even
*linear* time operations on it got to be too expensive, you'd have to
go even further, "sleeping" everything not in a small zone around the
player. The whole game loop would now operate on a subtree close to
the player's position and generate a new tree via assoc, mainly
replacing that one subtree (but possibly peppering "sleeping" parts of
the tree with objects that flew out of the "awake" zone; and the
"awake" zone may have moved a bit for the next iteration). This
assumes a continuous play-field. With discrete "screens" it's natural
to "sleep" everything not on the player's screen. The game loop then
updates a short seq of the "live" objects on the current screen and
possibly also a map storing game state that is global in nature (e.g.
has the Dark Wizard been awakened yet?). If the player moves across
screens, the update-position function needs store this fact, the
damage function needs to kill everything other than the player, and
the new-things function needs to load the new screen and its enemies
and other objects and return all of them. This will include the screen
itself! The old one will have to be "killed" (health to zero) and new
one emitted by new-things when the latter hits the player; the
draw-on! loop will then paint the correct one. (If there is an opaque
background behind the foreground, this has to be handled separately
unless you have Z-buffered graphics or something. The draw loop will
have to find this in the world state and paint it first, then do the
draw-on! loop. If there are also things that should be in front of all
the actors, this layer will also need a separate pass to render.)
So there you have it: not only your bouncing balls animation but much
more complex animations and interactive games can be accomplished in a
nearly-pure-functional way, with impure functions a) to poll user
input and b) to update the display (and sound) and using loop/recur
with immutable game state objects. Efficient collision checks and
other algorithms can be made functional; interaction between game
elements simply requires taking several passes over the game state,
perhaps a separate one to detect collisions, one to do all the
movement/AI/damage calculations and store information in an object
about other objects it has hit or otherwise affected, one to extract
that information into a map of objects to effects/damage inflicted on
them, one to go over the objects applying these effects, and one to
draw the surviving objects to the screen.
The nonfunctional route is also possible, of course: atoms, or even
refs and dosync, with damage and other effects applied more or less
directly by using e.g. (alter target (update-in [:health] #(- % 20)))
to do 20 points of damage; with refs and dosync, the game's logic can
be multithreaded safely even when there are cross-object invariants to
maintain.
But it is not, I trust I have proven, impossible to eschew refs and
atoms and go the functional route here; even multithreading the game
logic is possible by using pmap and preduce in the above.
(Multithreading the nonnaive collision detection loop is possible too,
by changing the outer loop form to (pmap something world (iterate next
world)) where "something" is a function that includes the inner loop.)
Brandon Ferguson
of the functions away from the global bits. Thanks!
Brandon Ferguson
play with. For me and my purposes with Processing the big challenge
has been the fact that I have little say about the draw loop. It just
fires (or I can call it manually with a redraw, but then it just
executes whatever is in that function). I had a nice recursive
function with no state in the beginning but the first fire of draw
would set it off and it'd draw a bunch of the screen and I'd never see
anything after that from it (cause it'd never return and we'd not get
to the next draw call/frame). Think there might be ways around that
just not sure yet.
Thanks again, and I'll certainly post with an update with where I get
(probably won't be able to dive into it again until the weekend sadly :
( ).
On Apr 14, 1:00 pm, Ken Wesson <kwess...@gmail.com> wrote:
>
> read more »
Brandon Ferguson
https://gist.github.com/887256
Already feels much better! I do still have a bit of state with the
tracking of which frame we're on but I'll certainly take that over the
glob of atoms before.
Next up is handling some of the more hairy bits with user input and
the like just to see how that would map, and getting multiple balls
running. Hopefully I can even get away from the lazy sequence method.
Thanks for the help!
-Brandon
>
> read more »