Borrowed Scenery tendrils reach out

Some serious connecting work going on with borrowed scenery for joining physical and imaginary worlds together. A new Boskoi database is up and running, giving us a place to put all kinds of story elements and plants found in the city. Boskoi uses the Ushahidi platform, which provides an API the game is now using to pull all items tagged in the map (which can come from the Android app or web app) into the game where they can interact with players or other entities.

More of Theun’s artwork has gone in, including a magician tarot avatar on the left while the three plants in the screenshot above represent those tagged on the map below. Getting everything in the right place (map lat/long coordinates vs game location coordinates and then aligning the map) took a lot of time to get right!

Algorithmic fungi patterns

Central to the borrowed scenery game is an ecosystem of fungi that players will grow to feed the plants found by foragers in the city of Ghent using Boskoi. These fungi will work differently from the plants in Germination X, partly in response to some interesting game testing feedback – the fungi will only grow to the next stage when activated by a player, but the positions of new fungi will be algorithmically decided.

This calls on a kind of cellular automata, which requires a bit of prototyping to get the right values to make the kind of patterns I want. I mocked up something in clojure (so I can plug it into the game server easily) using ascii art for previewing the patterns resulting, the four stages of fungi are:

. : spore
o : young
O : adult
* : fruiting

Each fungi cell only goes from adult to fruiting if conditions are right (counting number of neighbours as in the game of life), after which 5 spores are created around it. After fruiting or adult stage the fungi dies and gets removed. This is a screenshot showing some different colonies which emerge starting with just two fungi spores:

                     .Ooo*.                o..O   
                     o*o ..                 *.O   
                      ..*.                 o*oo.  
                       ...                 .*OOoo 
                                            ..Oo  
                  O o                       ..*.  
                  O                            o  
              O       o                           
                oO                                
            .O                                    
           O*                                     
           oO..                                   
         o  o *.OO                                
             ..O                O O               
              ** o                O               
             .*..o              OooO              
             .o.*.             .oOO*O O           
               . .              ..O*O O.          
                                O*. O*o*.         
                                Oo OoO. .     

And here is the code:

(def *spore-count* 5)
(def *neighbour-distance* 15)
(def *max-neighbour* 60)
(def *min-neighbour* 0)

(defn make-cell-world [cells]
  {:cells cells})

(defn make-cell [x y]
  {:x x :y y
   :state "."})

(defn cell-dist [cell-a cell-b]
  (let [v {:x (- (:x cell-a) (:x cell-b))
           :y (- (:y cell-a) (:y cell-b))}]
    (Math/sqrt (+ (* (:x v) (:x v))
                  (* (:y v) (:y v))))))

(defn cell-process [cell neighbours]
  (if (< 50 (rand-int 100))
    (cond
     (= (:state cell) ".") (merge cell {:state "o"})
     (= (:state cell) "o") (merge cell {:state "O"})
     (= (:state cell) "O") (if (and (< (count neighbours) *max-neighbour*)
                                    (> (count neighbours) *min-neighbour*))
                             (merge cell {:state "*"})
                             (merge cell {:state "X"}))
     (= (:state cell) "*") (merge cell {:state "X"})
     :else cell)
    cell))

(defn cell-get-neighbours [world cell]
  (filter
   (fn [other]
     (< (cell-dist other cell) *neighbour-distance*))
   (:cells world)))

(defn cells-find [world x y]
  (filter
   (fn [cell] (and (= (:x cell) x)
                   (= (:y cell) y)))
   (:cells world)))

(defn cells-make-rnd-pos-list [cell]
  (repeatedly
   *spore-count*
   (fn [] {:x (+ (:x cell) (- (rand-int 3) 1))
           :y (+ (:y cell) (- (rand-int 3) 1))})))

(defn cells-spore [world]
  (merge world {:cells
                (concat
                 (reduce
                  (fn [r cell]
                    (if (= (:state cell) "*")
                      (reduce
                        (fn [r pos]
                          (if (empty? (cells-find world (:x pos) (:y pos)))
                            (cons (make-cell (:x pos) (:y pos)) r)
                            r))
                        r
                        (cells-make-rnd-pos-list cell))
                      r))
                  ()
                  (:cells world))
                 (:cells world))}))

(defn cells-death [world]
  (merge world {:cells
                (filter
                 (fn [cell]
                   (not (= (:state cell) "X")))
                 (:cells world))}))

(defn cells-run [world]
  (cells-death
   (cells-spore
    (merge world {:cells
                  (map
                   (fn [cell]
                     (cell-process cell (cell-get-neighbours world cell)))
                   (:cells world))}))))

(defn cell-world-print [world w h]
  (dotimes [sy h]
    (dotimes [sx w]
      (let [f (cells-find world sx sy)]
        (if (> (count f) 0)
          (print (:state (first f)))
          (print " "))))
    (print "\n")))

(defn cell-world-loop [world n]
  (println "-------------------------------------------------")
  (cell-world-print world 50 20)
  (when (> n 0)
    (recur (cells-run world) (- n 1))))


(defn -main []
  (cell-world-loop
   (make-cell-world (list
                     (make-cell 25 10)
                     (make-cell 27 10)))
   1000))

Clay mushrooms

More work on the Borrowed Scenery project and a first screenshot, experimenting with different visual styles. I’m trying modelling clay to get a 3D look on the fungi and using Theun Karelse’s mockup characters for player avatars. The floor is being built out of map tiles of Ghent pulled from OpenStreetMap, using the OpenLayers API which has been pretty fast to get running.

A lot is changing with code too, the client graphics are now entirely HTML5 canvas, the server is running a modified version of the Germination X game, switched to using websockets and upgraded versions of all the clojure libs.

Websockets vs HTTP

A bit of R&D this morning into websockets. Previous games like Naked on Pluto and Germination X have made use of standard HTTP protocol for their client server communication. This is easy to set up (as a newbie web programmer) and fine for prototyping and proof of concept – but has some serious problems with regard to scale.

The first problem is that the direction is one way, clients always have to call the server in order to get data. This has serious impact on how realtime applications work – as they need poll – “has anything changed yet”… “has anything changed yet”…

More seriously, the server has no real notion of who the client is and what they have received already, so all the data needs to be sent for each poll. This results in duplicate data being sent, and is a waste of bandwidth.

Underlying the HTTP protocol are sockets for sending the data – each request is treated as a distinct event so a socket is created and destroyed to return the response. A better way is to hook into this lower level and use sockets directly – each client then has a unique connection on the server, and data can be sent in both directions. Also the server is told when the socket is disconnected so things can be cleaned up.

On the client side, websockets are a standard part of HTML5 so they are fairly simple to use from Javascript:

socket = new WebSocket('ws://localhost:8001/websocket');
socket.onopen= function() {
    socket.send('hello from client');
};
socket.onmessage= function(s) {
    alert('server says: '+s.data);
};

On the server I’m using Clojure, and after a bit of fiddling around with my own socket server implementation, I found Webbit which takes all the hassle away:

(defn -main []
  (println "starting up")
  (doto (WebServers/createWebServer 8001)
    (.add "/websocket"
          (proxy [WebSocketHandler] []
            (onOpen [c] (println "opened" c))
            (onClose [c] (println "closed" c))
            (onMessage [c j]
                (println "message recieved: " c j)
                (.send c "hello from server"))))

    (.add (StaticFileHandler. "."))
    (.start)))

This approach takes us from perhaps 100’s of simultaneous connections for an online game into more like 10,000 theoretically – so much more into the big league, but also more importantly persistent connections like this allow for some interesting game mechanics.

Germination X: Player characters

After another code sprint on Germination X, I’ve added player characters (avatars) to the game. Based on the falmouth focus group feedback this seemed one of the major things missing that players felt would improve the game.

The character design came from the Mandrake plant, which has been cropping up in groworld projects for some time – as a magical plant known to resemble human forms as it grows.

This change also allowed a much needed clean up and decluttering of the user interface for the game – as navigation now happens by moving your mandrake around by clicking on things. Your location is persistent, so when you log in you go back to the same place. All existing players in the game have been given mandrakes scattered around the world.

As the mandrakes represented a new type of entity in the world, able to move around, and linked to players – this was quite a lot of work, particularly in terms of updating the existing database. I had a lot of trouble doing this manually with MongoDB’s save command in the script interface. This seemed to be creating duplicate records (and creating very hard to track down bugs) that took a long time to find. The better approach seems to be to upgrade the database automatically in the game code, by checking a stored version number – and mapping over entries like this:

;; map over each player in the db
(db-map!
 (fn [player]
   (println "upgrading" (:name player) "to include tile and avatar")     
   ;; get a random tile in the world
   (let [tile (first (db-get-random-one :tiles {}))]
     (db-update! ;; update it, adding an avatar
      :tiles tile
      (merge tile {:entities
                   (cons (make-avatar
                          (:id player)
                          (:name player)
                          (make-vec2      ;; random position
                           (rand-int 5)   ;; in the tile
                           (rand-int 5))
                          (:layer player) ;; show the player's score on the avatar
                          (count (:flowered-plants player)))
                         (:entities tile))}))
     ;; add the tile location to the player
     ;; so we can find the avatar again
     (merge player {:tile (:pos tile)})))
 :players)

This also means that the latest code will work with snapshots I’ve taken of the game world regardless of how old they are. This turns out to be really important – I can try some changes and rewind the whole world back to the same starting point, as well as testing code locally on a copy of the current public world version.

Run your own Germination X server

We are in the process of moving the Germination X game to a new server, which gives me the chance to properly document the steps required to set it up – this is based on a clean Debian Squeeze 6.0.1 box on Linode.

Step 1: Get the source and Clojure installed

sudo apt-get install subversion
svn co http://svn.lirec.eu/scenarios/GerminationX/
wget https://raw.github.com/technomancy/leiningen/stable/bin/lein
cp lein /usr/bin; sudo chmod +x /usr/bin/lein
sudo apt-get install default-jdk
cd GerminationX/oak
lein deps (automatically installs all the clojure dependancies)
cp fatjars/* lib/ (installs the FAtiMA precompiled jars)

Step 2: Install mongodb (used to store the game world)

sudo apt-key adv –keyserver keyserver.ubuntu.com –recv 7F0CEB10
add: “deb http://downloads-distro.mongodb.org/repo/debian-sysvinit dist 10gen” to /etc/apt/sources.list
sudo apt-get update
sudo apt-get install mongodb-10gen

Once the server is running, you can browse the database (players and tiles containing plants) using the “mongo” console, the database is called “oak”.

Step 3: Start the server

Configure core.clj to build a new world (see comments in source) and test by running as normal user (WARNING: this is not secure!!! – only for testing!!!)

./run.sh

This will start the game server printing output to stderr/stdout, and after a while the three plant spirit FAtiMA processes. Wait a moment then check port 8001 – the game should be running. Once checked, comment out world building in core.clj and kill the 4 java processes.

Step 4: Locking down the game server

For reasons of security the game server should be run as a user with very restricted permissions – this means if someone finds a way to run commands via the process in some way, they wouldn’t be able to do much to the server except access some game data. The standard user for this is called “www-data”.

sudo chown www-data:www-data public
sudo chown www-data:www-data public/log.txt
sudo ./server.sh start
Check port 8001

Check the server is running with “sudo ./server.sh status” or stop it with “sudo ./server.sh stop”. This code was based on a similar script for Naked on Pluto, thanks to Aymeric! The game logs it’s stdout/stderr output in /var/log/oak-server-8001.log while some in-game logging currently goes to public/log.txt (so it can be visible from a browser).

We are also running the game via apache using a reverse proxy, (again based on the setup used for NoP) this gives us an added layer of protection/load management etc.

Germination X – designing for cooperation

Over the last week I’ve been designing and implementing a lot more game mechanics for Germination X which are needed for an upcoming visit to the Mobile Life Lab in Stockholm. The more interesting ones involve some direct player – player interaction. The thing I’m trying to balance is keeping the central design simple (what you have to do), but adding just enough for it to be taken further by players (how you do it). One important part of this is emphasising cooperation without making it mandatory – something I think is a mistake to do, and leaving the way that people interact online as open to interpretation as possible. Tale of Tale’s Endless Forest is a good reference point here.

The focus is adding a kind of “levelup” system for players to progress through the game in a longer term way than currently, along with some surprises. Also adding a way for players to send fruit they pick to other players as gifts, or to the plant spirits as a kind of “offering”.

The other major change is updating the game to use MongoDB to store all it’s data. I’m using congomongo as the Clojure wrapper, and it’s been fairly simple to integrate with the existing game code as I can replace normal Clojure functions like reduce with versions that iterate over records in the database. These can also be written to load data and work on it in chunks, to keep the memory overhead fixed:

(defn db-reduce
  "run f on each item in the collection, return the result"
  [f ret coll]
  (loop [skip 0 ret ret]
    (let [limit 200 ; limit to loading 200 records at a time
          items (fetch coll :limit limit :skip skip)] ; do the fetch
      (if (not (empty? items)) ; are there any items?
        (recur (+ skip limit) ; do the next chunk
               (reduce f ret items)) ; reduce f over the items
        ret))))

Evolving musical bytecode #3

For the next attempt in BetaBlocker bytecode evolution I wanted to favour patterns that had a rhythmic nature by measuring them with this function:

(defn freq [l n]
  (defn _ [c]
    (cond
     (>= (+ c n) (count l)) 0
     (= (nth l c) (nth l (+ c n))) (+ 1 (_ (+ c 1)))
     :else (_ (+ c 1))))
  (_ 0))

Which looks for repeating values spaced apart by “n” positions, so (freq ‘(100 1 2 3 100 4 5 6 100 7 8 9 100) 4) returns 3, as it finds 3 pairs of equal values (100) distanced by the specified 4 positions.

With this fitness function:

(+ (* 50 (count (num-unique res))) ; unique notes are very good
   (freq res 4) ; equal notes every 4 beats are good
   (freq res 6)) ; equal notes every 6 beats are good

We favour rhythmic components of 4 or 6 beats and boost the uniqueness score by multiplying it by 50. After some generations, we get a high scoring individual: 23 23 13 22 7 12 17 20 12 23 23 5 0 7 12 3

Which disassembles as:

loop:
    note    ; play & remove top of stack (zero when empty)
    note    ; play & remove top of stack
    dec     ; decrement top of stack
    dup     ; duplicate - pushes a copy of stack top 
    pshi 12 ; push the value pointed at by address at 12 (self read)
    not     ; performs bitwise not on stack top
    pip 12  ; increment value at address 12
    note    ; play & remove top of stack
    note    ; play & remove top of stack
    pshl 0  ; pushes this literal number (the 0 is at address 12)
    pshi 12 ; push the value pointed at by 12 (self read)
    jmp loop

This program creates a pattern from 4 separate sources, using all 16 bytes of code:

A descending scale using the stack to store the current position.
A rising scale by self modifying address 12 (the 0 in “pshl 0″).
Playing it’s own code as a pattern of notes by using address 12 as a pointer.
Playing the bitwise NOT of it’s own code at the same time.

The result: “0 0 232 255 23 1 232 254 13 2 242 253 22 3 233 252 7 4 248 251 12 5 243 250 17 6 238 249 20 7 235 248 12 8″ scores poorly for it’s rhythmic patterns, but it’s probable that this surprising local maxima was found by the early influence of the rhythmic fitness criteria on it’s ancestor populations.

This one was strange enough to warrant dialing into Betablocker DS to see how it actually sounded. Here it is in Hungarian Gypsy scale:

Evolving musical bytecode #2

Following on from the first BetaBlocker genetic algorithm bytecode experiments, in addition to the “most different notes” fitness function I added a similar calculation for the first derivative (ie. the difference between the notes in time order). This was an attempt to steer the evolution away from simple scales and into more complex patterns.

(defn deriv [l]
  (cond
   (empty? l) '()
   (empty? (rest l)) '()
   :else (cons (- (first (rest l)) (first l))
               (deriv (rest l)))))

The code to find the first derivative of a sequence of notes – eg. (deriv ‘(1 2 3 2 6 7)) => (1 1 -1 4 1). We then add this to the fitness function which looks like this:

(+ (count (num-unique res)) ; unique notes are good
   (count (num-unique (deriv res))) ; unique gaps between notes are good
   (min (count res) 20)) ; lots of notes are good (stop at 20)

This resulted in the following bytecode to emerge from the primordial soup: 23 17 7 6 23 21 9 23 8 212 3 2 4 2 180 124 – which disassembles to:

The arrows show the indirection which helps as this one is a bit tricky to pull apart. It’s the first time I’ve seen self modification emerge – it decrements the “212” and uses it as a variable for the note sequence. Combining the pshi and pdp like this is a nice trick I can make use of when programming betablocker myself.

The program is self destructive – the “pop” which otherwise does nothing of use will eventually write zeros over the program itself if it’s run for a few more cycles than the 100 I’m testing the programs for.

The output looks like this:

0 212 255 211 0 210 0 209 0 208 0 207 0 206 0 205 0 204 0 203 0 202 0 201 0 200 0 199 0 198 0 197 0 196

According to our fitness function, the interleaved zeros give it a very high scoring derivative list:

212 43 -44 -211 210 -210 209 -209 208 -208 207 -207 206 -206 205 -205 204 -204 203 -203 202 -202 201 -201 200 -200 199 -199 198 -198 197 -197 196

However the actual pattern is not so interesting, so still more work needed on the fitness criteria.

GX – messages, colours and continuous worlds

A big update for Germination X today.

The main new stuff includes:

The process of moving around the world is now more continuous, as the land is split into sub-tiles that are loaded 9 at a time. When you move out of the central tile the 3 at the back are discarded while the 3 at the front are loading. Spirits can also “see” into the tiles surrounding their current one, and so can navigate the entire world slowly, but independently.

Spirit emotional colours – both in their character design and in their messages. I’ll post more fully about this later.

The messaging system has been rewritten and now forms the major information source from the spirits. It’s probably a little too much right now, and some thought is needed on effective ways to communicate some of these things. All the spirit’s messages are triggered by actions driven by the FAtiMA agent. Here is an example of what happens when a “praise” action is received for an object:

(defn spirit-praise [spirit plant]
  (modify :log
          (fn [log]
            (log-add-msg
             log
             ; we can't exactly be sure why the fatima agent
             ; has triggered the praise action, but we can make
             ; an educated guess by looking at the plant
             
             ; if it's not the same type as the spirit
             (if (not (= (:name spirit)
                         (layer->spirit-name (:layer plant))))
               ; we're happy as it's providing a benefit to our plant
               (make-praise-msg 'spirit_helper_praise spirit plant)
               ; it's the same type
               (cond
                (= (:state plant) 'grow-a)
                ; we're happy because a new plant is growing
                (make-praise-msg 'spirit_growing_praise spirit plant)

                (= (:state plant) 'fruit-a)
                ; our plant is flowering (first phase of fruiting)
                (make-praise-msg 'spirit_flowering_praise spirit plant)
                
                (= (:state plant) 'fruit-c)
                ; our plant is fruiting (last phase)
                (make-praise-msg 'spirit_fruiting_praise spirit plant)

                ; i give up!
                :else (make-praise-msg 'spirit_general_praise spirit plant)))))
          spirit))

The Haxe client then reads the messages which consist of these codes and a host of other information (eg. the spirit’s current emotional state and the players involved) and builds the text for display.