Design/structure for a game loop in clojure

[Daniel P. Wright]

Hello,

I am trying to structure the game loop for a simple game in clojure,
trying to keep things pure as far as possible to get a feel for how this
would work in a functional environment. Currently, I am working with
a message-based system, whereby various events create "messages" which I
then act on to change state. For example:

1. Read keypresses, generate a message for each keypress and add to
the queue.
2. Read from the network; add any incoming messages to the queue.
3. Add an "update" message to the queue which can be used for generic
update processing: AI, physics, whatever
4. Go through the entities in my world delivering these messages as
appropriate. Keypress and update messages will be processed by any
entity that implements a handler for them; network messages may be
"directed" so that they only get sent to a specific entity.
(The return value of the functions processing these messages is
itself a vector of messages, such as "update-state" to replace the
current state of an entity (position, etc) with a new state, or
perhaps a message to send information over the network.)
5. Send any outgoing network messages, perform any state updates, etc.
6. Draw the screen, return to 1 and begin the next game loop.

The issue I'm having is that this system results in rather a lot of
looping through every entity in the world. There are two full loops,
delivering the messages in step 4 and updating the state in step 5.
Originally I had the message handlers in step 4 return a new state
rather than new messages, so I just updated the entities in-place during
the first loop, but I found sometimes I wanted to do other things than
just update state -- for example send messages over the network, or to
another entity in the world. So it seemed more flexible to return
messages, even if some of those messages are directed toward the entity
sending it.

My other issue is that with messages intended to be processed by a
particular entity, I can either check that while looping through the
whole list of entities (which means for every entity it's not intended
for I'm running a wasteful check on the id of a message), or I can put
the entities in a map instead of a vector and look them up by some id
instead (in which case I'm doing a search for every directed message, on
top of the loop I'm already doing through all the entities).

I've come from a mostly C++ background, so my sense of when I'm doing
something really bad isn't very well-tuned in functional languages at
the moment. I write something that "feels" nice and looks pretty, and
then I step back and think about what it's actually *doing* and I can't
help but think "in C++ this would be unforgivably vile."

It seems the more I try to push function purity the more I have to loop
through some monolithic data structure holding all of my state, since I
can't just pass references around and modify them in-place. Writing the
code for the entities themselves is going quite well -- I am keeping
their functions pure, not referring to anything outside of the
parameters they're passed in, and thus always returning the same result
given the same input, and limiting their input to the information they
need without giving them access to the entire state of everything -- all
of which is great for testing, parallelisation, and all the rest. It's
at the higher level of managing the collection of these entities and
their relationships that I wonder whether I am working along the right
lines or whether I am in some sense "doing it wrong".

As an aside, right now I am avoiding storing entity state as atoms and
having the update functions modify those atoms because although clojure
helps update their values safely it still means the function has side
effects, and I'm trying to keep functions as "pure" as possible at least
until I can understand the limitations of doing that and see the
necessity for using global constructs.

I have a feeling this is only going to get more complex as I start
wanting to make smaller sub-lists that refer to the same entities. For
example my entities may be stored in some tree format in the world
state, but I might want to have a list of "all enemies within a certain
radius" or whatever just as a convenience for quick access to those
entities I'm interested in. Right now if I updated an entity in this
list it would remain not updated in the global state tree... I'm
guessing there's no way around holding an atom or similar in both lists
and updating that, but here I may be missing something also.

Sorry for the slightly rambling mail; thoughts/guidance appreciated!

-Dani.

[Raoul Duke]

potential food for thought for you:
http://s3.amazonaws.com/ns999/asteroids.html
http://prog21.dadgum.com/23.html
http://world.cs.brown.edu/

[Gary Trakhman]

I thought this approach was interesting: http://www.chris-granger.com/2012/12/11/anatomy-of-a-knockout/

A key insight I've seen promoted in other places is to use flattened structures and identities instead of nested object hierarchies, thus your handy sub-lists may be represented as graph queries.

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[George Oliver]

On Sunday, May 19, 2013 6:02:23 PM UTC-7, Daniel Wright wrote:

thoughts/guidance appreciated!

You might get something out of http://clojurefun.wordpress.com/2013/03/ -- "In this (somewhat extended) post I’m going to describe my experiences using Clojure for the 7DRL challenge – with discussion how to get the most out of Clojure for game development." 

The issue I'm having is that this system results in rather a lot of 
looping through every entity in the world.

I'm not sure if this works with your code design, but can you reduce that by subscribing entities only to specific events? 

[Mikera]

You've described almost exactly the state update model used in Ironclad:

https://github.com/mikera/ironclad

I'd strongly suggest taking a look at the Ironclad source if your game is anything vaguely turn-based / strategic.

Some comments:

- A big, single immutable data structure for the entire game state is the best way to go if you can make it work. I managed this for Ironclad and Alchemy, it might be hard for a FPS though.....

- For performance, you may need specialised persistent data structures (e.g. Ironclad uses a custom PersistentTreeGrid for maps and unit locations etc.). As part of this, I implemented things like efficient area searches (for nearby entity detection).

- You'll need to maintain indexes as part of your immutable data structure (e.g. a map of entity ID to entity location). This is the only real way to avoid expensive traversal of the whole data structure. This is also the way to efficiently process events targeted at a specific entity.

- The model of message -> [collection of atomic updates] is good.

- Keeping a queue of incoming events is also a good idea (probably essential if your game is networked / multiplayer)

- I would suggest *decoupling* screen redraw from the game event update loop. One of the big advantages of immutable game state is that it is easy to put rendering on another thread! Same can also apply for AI.

- If you want fluid animations resulting from discrete game events, consider doing the animations outside the main game state, e.g. by managing sprites within the rendering engine. It's a bit of a hack, but massively reduces the number of game state updates required for every little position update.

Finally, beware of unnecessarily creating/realising sequences - this results in a lot of GC overhead. A common culprit is running a map over a vector for example. Don't do this unless you have to - I ended up writing a bunch of non-allocating data structure traversal functions to avoid this problem (some of these are in https://github.com/mikera/clojure-utils)

[Daniel P. Wright]

Thanks everyone for your replies, in particular:

Mikera: Glad to hear we're along the right lines, and thanks for the
extra advice. I've found your blog series on Alchemy very helpful while
considering this stuff. This game is a little different, and I'm mainly
concerned with what's going on server-side, but a lot of the fundamental
structure is going to be quite similar I think. Definitely going to
take a look at Ironclad too.

Gary: Thanks for the link. Funnily enough I spent some time at a
previous job putting a component/entity system into the game I was
working on at the time with great success, don't know why I didn't think
of it this time! I can see how it would work even better with Clojure
-- a lot of the problems I had to deal with last time involved each
component having mutable state, and what happened when that state was
modified out of order... all of which will hopefully go away in
Clojure-land.

Thanks again, will keep the list posted if I come across anything
interesting!

-Dani.

Mikera (Mon, May 20, 2013 at 08:04:41PM -0700) >>

[Mikera]

On Wednesday, 22 May 2013 16:46:54 UTC+8, Daniel Wright wrote:

Thanks everyone for your replies, in particular:

Mikera: Glad to hear we're along the right lines, and thanks for the
extra advice.  I've found your blog series on Alchemy very helpful while
considering this stuff.  This game is a little different, and I'm mainly
concerned with what's going on server-side, but a lot of the fundamental
structure is going to be quite similar I think.  Definitely going to
take a look at Ironclad too.

No worries.

Ironclad is much more useful to look at from the server perspective: although it's currently set up as single player, it's been designed to allow multiplayer operation in the future. e.g. map updates have visibility filters so that you only send updates to players that can see the area under consideration. This is one of the advantages of the message -> [collection of updates] model.

I didn't bother with this extra layer of complexity for Alchemy since it's intrinsically single-player, but my long term plan is to make a split between the Ironclad client and server so it works as a multiplayer strategy game.

[atkaaz]

concurrency-wise, you might find useful Rich Hickey's ants simulation

https://github.com/juliangamble/clojure-ants-simulation/
the relevant video where he explains it:
https://www.youtube.com/watch?v=dGVqrGmwOAw

(if you want the slides too, see in the comments: someone suggested google for "Must watch: Clojure concurrency")