Finite Improbability

I guess I should be happy that I”m interesting enough to receive some comment spam. Anyways, I’ve found a relatively unobtrusive comment handling system that uses a combination of javascript and cookies to keep out the spammers. In my mind this is better than a captcha, hopefully it works out that way.

After getting the basic behavior of my game up and running, the first thing I tried to do was create a whole ton of objects. This was a little disheartening, as creating around four hundred moving ants pushed my macbook below 30fps. Looking at Activity Monitor told me that the slowdown was CPU bound, without too much memory usage.

So, I set about trying to figure out what was going on there. My initial thought was that the upcasting I had been doing in Java render game objects pulled from Clojure was the culprit. I had been contemplating switching that to Clojure anyways to make futzing with the render pipeline easier. So, I switched to the Java code simply passing the data map that stores my game data back and forth between the various functions for handling logic updates, rendering, and user input. This helped a little, but didn’t really do too much.

This is probably a good point to mention that one result of the hack I’ve had to do to get the Clojure environment running in the game is that I can’t see the output from Clojure. So the ridiculous amount of reflection my game was doing went completely unnoticed. Anyone familiar with Clojure probably already knows where the rest of this article is headed.

Anyways, one crash course in the basics of Java profiling later and I was shocked at how much time my code was spending using reflection. It was bad enough that running hprof with the default stack depth (4) told me the program spent the majority of it’s time in java.lang.Object.. After bumping that up a bit I could see that the top four or five frequently called functions in my program combined to take up around half of the execution time.

As a demonstration, here’s my initial render funciton. This function is called as often as the game can manage, punctuated on occassion with calls to the update function:

(defn render [data container g]
  "Render the data map to the given graphics context."
  (doseq f (get-beacons data) (. f (render container g)))
  (doseq f (get-ants data) (. f (render container g)))
  (when debug
    (. g (drawString (str "Number of beacons: " (count (get-beacons data))) 10 20))
    (. g (drawString (str "Number of beacons: " (count (get-ants data))) 10 30))))

This worked as expected, but was really slow. Coming from Scala, which handled somewhere around six thousand “ants” without breaking a sweat (albiet with much simpler behavior), seeing the system crawl trying to do three hundred was pretty upsetting. Some profiling told me that this function was one of the culprits, which I expected anyways due to the call volume. Just to help understand what’s going on “data” is a PersistentHashMap containing all of the game data. “container” is an object from Slick that gives me access to things like window properties. “g” is another object from Slick, that represents the graphics rendering context. The object “f” is either an Ant or Beacon Java object taken from a list stored in a similarly named key in the data hash.

My first optimization attempt was to put some type hints on the function’s arguments. Here’s what I ended up with:

(defn render [#^PersistentHashMap data #^GameContainer container #^Graphics g]
  "Render the data map to the given graphics context."
  (doseq f (get-beacons data) (. f (render container g)))
  (doseq f (get-ants data) (. f (render container g)))
  (when debug
    (. g (drawString (str "Number of beacons: " (count (get-beacons data))) 10 20))
    (. g (drawString (str "Number of beacons: " (count (get-ants data))) 10 30))))

This helped, but I was still getting a lot of reflection in the render function. Can you tell where? Here’s the final code:

(defn render [#^PersistentHashMap data #^GameContainer container #^Graphics g]
  "Render the data map to the given graphics context."
  (doseq #^Beacon f (get-beacons data) (. f (render container g)))
  (doseq #^Ant f (get-ants data) (. f (render container g)))
  (when debug
    (. g (drawString (str "Number of beacons: " (count (get-beacons data))) 10 20))
    (. g (drawString (str "Number of beacons: " (count (get-ants data))) 10 30))))

After a sequence of profiling the game, annotating the worst offender, and repeating I’m to the point where the top two time using functions are a Slick library function and a function out of boot.clj. Both of these use ~1% of the CPU time at most, so I’m happy. More importantly the game handles as many ants as I’m interested in sitting around creating. Being able to hash out an initial implementation of my game without type annotations was a huge productivity boost. I still have plenty of infrequently called functions that work dynamically because they aren’t worth optimizing. As an added bonus, here’s a comparison between an initial implementation of steering a game object and the annotated example:

(defn steer [obj dir]
  "Steer the given object into the given direction"
  (let [steer-force (truncate dir (get-max-force obj))]
    (. steer-force (scale (/ 1 (get-mass obj))))
    (. (get-vel obj) (add steer-force))
    (truncate! (get-vel obj) (get-max-speed obj))
    (. (get-pos obj) (add (get-vel obj)))
    (update-game-obj obj)))


(defn steer [#^GameObject obj #^Vector2f dir]
  "Steer the given object into the given direction"
  (let [#^Vector2f steer-force (truncate dir (get-max-force obj))
           #^Vector2f v (get-vel obj)
           #^Vector2f p (get-pos obj)
           #^float m (get-mass obj)
           #^float s (get-max-speed obj)]
    (. steer-force (scale (/ 1 m)))
    (. v (add steer-force))
    (truncate! v s)
    (. p (add v))
    (update-game-obj obj)))

Note that I could have simply added the annotations inline without pushing everything up into a let binding, but I think it looks cleaner with the let bindings and technically saves me two superfluous lookups of the velocity of an object.

Wow, I can’t believe I’ve let posting about this slip so far. I have been working on the game, just not as much as I would have liked. Obviously I haven’t been keeping up with my nonexistant readers about it.

The bits of time I could snatch to work on my game have mostly been spent building up a decent logging infrastructure. Simple things like hunting down a null pointer exception become grossly complicated now that I have two different language environments passing code between each other. Logging helps, and thanks to the power of Lisp I can write some pretty useful logging code. Here’s a sample:

(with-log "Failed to update an ant position"
 (update-pos ant))

This expands into a bunch of stuff, but basically any exception thrown in the code run by with-log is trapped, the message “Failed to update an ant position” is logged (as an error by default) and the exception is rethrown. Pretty basic I guess. Here’s where this really comes into play. When the game detects an exception that I could presumably fix without needing to restart it pauses. I can then modify any of the game code and my new code will run when I unpause the game. This combined with the logging code above lets me hunt through my code to pinpoint where the exception is being thrown. From there I can start working bacwards through the function call stack and instrument each function call to test for and log null arguments. Eventually I’ll pinpoint where my null argument originates and can fix that.

I’m planning on expanding the logging facility so it will only track certain errors. The idea is that I could write something like this:

(with-log
 [(NullPointerException "Null pointer encountered in foo")
 (BoredAntException "An ant has nothing to do")
 (OverthoughtExampleException "This example is gratuitous")]

 (code...))

One of the beautiful things about working with Lisp is that you can imagine how your program would be written in an ideal psuedocode, write it that way, and build up from your existing language to that one.

Anyways, in addition to writing logging code I’ve started implementing the steering and seeking behavior described here: http://www.red3d.com/cwr/steer/gdc99/

When I started it was working pretty well, but I managed to introduce some bugs that were pretty hard to track down. So, now that I have a better bug handling infrastructure I can get back to the fun part.

Update:

After I finally finished setting up my logging system I identified and solved my problems pretty quickly. The steering behavior didn’t take very long to perfect so I now have a good portion of the game implemented. At the least the ants are moving from A to B pretty consistently, although I’ll probably have to come up with a good mix of the steering and arrival code to simulate the ants picking at a piece of food.

I spent a lot of time the last two days doing a very poor job of chasing bugs in my game. I’ve tracked them all down, discovering and resolving an issue with .jar distributions in the process, but the process highlighted how difficult handling type information between Clojure and Java is going to be. A relatively simple mistake (like making a two-element form of an object and a list instead of consing it onto the list) produced some difficult to interpret error messages. This experience will probably help fixing such problems in the future. Being able to inject code straight into the running game has let me produce my bugs at never before seen speeds, which is what I wanted.

Anyways, I’ve got a basic rendering pipeline down, so now I can move on to the fun part of writing game logic.

Well, finals are officially over, which means I have most of a full week to dedicate to this little hobby of mine. All of the past few posts detail what I’ve accomplished in about two hours or so a night. Now I can spend as much time as I want on this and really get things done.

First things first though, I need to make a decision. I started out working with Scala for this project, and have a decent bit of it done there. The only problem is that I’m not super happy with how the environment works. The Scala compiler takes a long time to run at about six seconds to build a relatively small project. Since I have to drop out of the game to make changes that means I have to:

• Wait for the game to shut down
• Make my changes
• Wait for the project to recompile
• Wait for the game to load
• Make my way back to the point I was testing

So, giving Scala the benefit of the doubt and assuming most of it’s compile time penalty is in JVM startup, let’s estimate a bit. Game shutdown can be really quick, so that’s ~0 seconds. Making changes will happen either way, so that weighs in at ~0 seconds for the comparison. I’ll assume 10 seconds for project compilation (again, giving the benefit). Then it’s another 30 seconds for the game to load and who knows how long to get back to the test point. Since I’m going to have some pretty complex behavior that last one might be a doozy. Either way just the assumed times add up to 40 seconds per iteration to try and fix a bug.

Running the same numbers for Clojure is almost pointless, as I don’t have to shut the game down to make changes. Granted I’ve managed to kill the game a few times by creating a NullPointerException, but every instance that I can remember happened in the render pipeline, which (hopefully) won’t change too much after I really get going.

There are some distinct advantages to Scala though. One of the most obvious ones is that it supports OOP, and thus plays a little better with the game library I am using. So far the bit of playing around I’ve done with Clojure has been in the realm of transferring data from Java to Clojure and back. As I discover new tricks this gets easier, but the majority of my time has been spent in that area. Granted, the little bit of code that I’ve written to actually resemble a game has been pretty powerful, but there you have it.

Another point in Scala’s favor is documentation. I think the community around Scala is a little bigger, and the available documentation reflects this. Clojure has a useful reference in it’s website, and since much of it can be found in the boot.clj file I can always go read the source if I really want to know how something work, but I’m missing a lot of things through simple ignorance. For instance I’ve spent a while accessing elements of a map using ”(get map key)”. Today I learned that maps are functions of their keys so I could have simply called ”(map key)”. Granted the difference is small, but what else is there that I don’t know about?

In the end I think it comes down to me just liking playing with Clojure more than Scala. Scala seems like a pretty solid language, but it’s really hard to pass up the instant satisfaction of the REPL. That and a much slimmer runtime is really nice.

In thinking about how I want to manage my games, I’ve spent a bit of time mulling over the options for scene management. Specifically I want to handle collision detection efficiently, as most of my recent ideas start out with “what if we had a swarm of X”. I’d also like to have something useful to efficiently simulate an object interacting with neighboring objects.

One immediate idea is to base my scene graph on Quadtrees. These are relatively simple to implement (since they are two-dimensional binary trees) and would make scene subdivision easy. A quadtree could easily divide the scene up into whatever depth I want, and objects in the tree can discover their neighbors through simple tree traversal mechanisms.

The first problem I have with it is overloading. If I have fifty of item in one quadrant and relatively few in the rest I’m still not doing very well. Taking a page from Hans Reiser’s “Dancing Trees” algorithm I could provide a threshold mechanism so that quadrants rebuild themselves in various sizes after they become imbalanced. I’ll have to kick the idea around some more, and probably should just start with a relatively simple management system first and build up more complicated ones as I find I need them.

More fun playing around and not getting much done. I’m in the middle of finals week, so I’m trying not to get too involved with this.

Today’s current bit of playing around was at embedding the Clojure language in a Slick application. It wasn’t too hard to copy from the language’s repl implementation and make sure it wouldn’t block the thread waiting for input. After a bit of tinkering I came up with a class that does what I need, although I highly suspect that it isn’t thread-safe. Here it is:

import clojure.lang.*;
import clojure.lang.Compiler;

import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class ClojureInteract {

    static final Symbol REFER = Symbol.create("clojure", "refer");
    static final Symbol QUOTE = Symbol.create("quote");
    static final Symbol CLOJURE = Symbol.create("clojure");

    Object EOF = new Object();

    public ClojureInteract() {
    try {
        RT.init();
    }
    catch(Exception e) {
        e.printStackTrace();
    }
    }


    // Evaluate the current contents of system input
    public Object eval() {
    Object ret = null;
    try {
        if(System.in.available() != 0) {
        java.io.PushbackReader rdr = new java.io.PushbackReader(new InputStreamReader(System.in));
        Object r = LispReader.read(rdr, false, EOF, false);
        if(r != EOF)
            ret = Compiler.eval(r);
        }
    }
    catch(Throwable e) {
        e.printStackTrace();
    }
    return ret;
    }

    // Evaluate the given string
    public Object eval(String s) {
    Object ret = null;
    try {
        java.io.PushbackReader rdr = new java.io.PushbackReader(new java.io.StringReader(s));
        Object r = LispReader.read(rdr, false, EOF, false);
        if(r != EOF)
        ret = Compiler.eval(r);
    }
    catch(Throwable e) {
        e.printStackTrace();
    }
    return ret;
    }

    // Load the file specified by s
    public void load(String s) {
    try {
        Compiler.loadFile(s);
    }
    catch(Exception e) {
        e.printStackTrace();
    }
    }
}

Not too bad, eh? By the way, aren’t checked exceptions ugly? Anyways, this works out pretty well in that I can pass in direct strings, tell the class to read straight from standard input, or load a file. Running my game as an inferior lisp under emacs is a simple matter of typing ”C-u 1 C-c C-z ant -e -f /Users/ajones/programming/games/clojure-picnic/build.xml run”, what could be simpler? Seriously though, I need to figure out how to set this automagically.

At this point though, I’m happy that I can pipe new function definitions straight into my game as it’s running and have them rebound on the fly. Now modifying game behavior is a simple matter of pausing, updating a definition, and unpausing.

For anyone who’s been following this series you might have noticed a conspicuous absence of information about Scala. I’m seriously considering switching from it to Clojure just for this behavior. I’m sure Scala is capable of what I want somehow, but Clojure has the distinct advantage of being a Lisp and having built-in Emacs support for this since the dawn of time. The relatively tiny .jar file (360K vs 2M) is a bonus too. I like Scala, but I don’t think it’s a great fit for this project and the direction my development practices are heading.

I forgot to post anything yesterday … didn’t really get a whole lot done anyways. I played around for a while with setting up a command-line interface so I could pipe new Javascript definitions into the game as it is running. Eventually I realized I was wasting a lot of time on something that would be great for my bigger game, but wouldn’t help me get the rest of it done.

So, today I stripped out every bit of testing code and started implementing the game for real. It feels good to be getting work done. I have ants (still being played by triangles) that are moving across the game board to the latest beacon created by the player. Right now the get to the newest one and stop, but I could just as easily do other behaviors.

Worked on integrating the Mozilla Rhino javascript engine today. Here’s a brief example (in Java) of using it with slick:

/*
  This file demonstrates using the Rhino Javascript engine within the
  Slick 2d game engine.

  Rhino can be found at: http://www.mozilla.org/rhino/
  Slick can be found at: http://slick.cokeandcode.com/
 */

import org.newdawn.slick.AppGameContainer;
import org.newdawn.slick.BasicGame;
import org.newdawn.slick.GameContainer;
import org.newdawn.slick.Graphics;
import org.newdawn.slick.Input;
import org.newdawn.slick.SlickException;

import org.mozilla.javascript.Context;
import org.mozilla.javascript.ScriptableObject;


public class Rhino extends BasicGame {

    /*
      The ScriptProxy class defined here is one half of the interface
      between Java code and the Javascript environment. It is used to,
      among other things, provide access to Java objects within Rhino.

      The ScriptableObject class implements the majority of the
      Scriptable interface. The Scriptable interface is used to define
      functions and objects that will be available to the javascript
      environment.
     */
    class ScriptProxy extends ScriptableObject {
    String test1;

    /*
      This is the only method required to fully implement the
      abstract class ScriptableObject. I'm not sure what it is
      supposed to do. The "global" value is used in at least one
      example in the Rhino documentation.
     */
    public String getClassName() {
        return "global";
    }

    /*
      Access to the "test" object in the javascript environment is
      implemented through calls to the setTest and getTest
      methods.
     */
    public void setTest(String str) {
        test1 = str;
    }

    public String getTest() {
        return test1;
    }

    /*
      A test function that can be called within the JavaScript
      environment.
     */
    public void testfunc(String s) {
//      System.out.println("test function called");
        System.out.println(s);
    }
    }

    /*
      A Context is an instance of the javascript environment. The
      context is used to load and interpret .js files and interpret
      Javascript code as strings, among other things. In this example
      it is used exclusively to interpret Javascript strings.
     */
    protected Context scriptContext;
    protected ScriptProxy gameProxy;

    public void init(GameContainer container) throws SlickException {
    /*
      The static method Context.enter is, apparently, the easiest
      way to obtain a javascript environment.
     */
    scriptContext = Context.enter();
    gameProxy = new ScriptProxy();

    /*
      We'll set a string for the "test" property that will be
      exposed in Javascript now so we know it is calling across
      the bridge.
     */
    gameProxy.setTest("This was set within java, but called from javascript.");

    /*
      This must be called before scripts can be evaluated in this
      Context. It creates some of the basic Javascript objects.
     */
    scriptContext.initStandardObjects(gameProxy);

    /*
      Functions provided by a ScriptableObject (such as our
      example 'testfunc') are initialized in the following manner.
     */
    String[] scriptAvailableFunctions = { "testfunc" };
    gameProxy.defineFunctionProperties(scriptAvailableFunctions, ScriptProxy.class, ScriptableObject.DONTENUM);

    /*
      A "property" is a Javascript object that is exposed through
      getters and setters in the ScriptableObject. Rhino
      automatically prepends the "set" and "get" terms and
      uppercases the first letter, so exact naming is important.
     */
    gameProxy.defineProperty("test", ScriptProxy.class, ScriptableObject.DONTENUM);

    }

    public void render(GameContainer container, Graphics g) {
    /*
      Here we are using the context (javascript engine) to
      evaluate a string. The first parameter is our
      ScriptableObject, which is used to provide definitions for
      the engine. The second argument is the code to be evaluated.
      In this case simply writing "test" evaluates the Javascript
      object named "test", which is looked up in our gameProxy,
      which passed the result of it's getTest() method to the
      Javascript engine.

      Since this is the only instruction in the string to be
      evaluated it is used as the return value for
      evaluateString. To provide flexibility in return type
      handling evaluateString returns a java.lang.Object, which is
      why the result must be cast back into a String.

      The third parameter is a string that describes the source
      for the Javascript code being evaluated. This may be a
      filename if that is where the string comes from.

      The fourth parameter is the starting line number for this
      script, which might be useful if a script is being pieced
      together from a variety of components.

      The last parameter is used to provide a security domain for
      the script to run under. I *think* this is used to ensure
      that the Javascript code cannot execute certain methods or
      instantiate some objects, but haven't done enough research
      to be sure. Passing a null value here does not restrict the
      evaluation of Javascript code.
     */
    String result = (String) scriptContext.evaluateString(gameProxy, "test;", "js", 1, null);
    g.drawString("Javascript result: " + result, 40, 120);


    }

    public void update(GameContainer container, int delta) {

    }


    public void keyPressed(int key, char c) {
    if(key == Input.KEY_ESCAPE) {
        /*
          The script context will most likely be shut down
          properly, but it's a good idea to be neat and tidy,
          right?
         */
        scriptContext.exit();
        System.exit(0);
    }
    if(key == Input.KEY_SPACE) {
        /*
          This example is largely similar to the above, except
          that now we are calling the javascript function
          "testfunc()". This is found and executed on gameProxy,
          printing a string to the console."
         */
        scriptContext.evaluateString(gameProxy, "testfunc(\"testing console output\");", "js", 5, null);
    }
    }


    public Rhino(String s) {
    super(s);
    }

    public static void main(String[] Args) {
    try {
        AppGameContainer container = new AppGameContainer(new Rhino("Picnic Invasion!"));
        container.setDisplayMode(600,480,false);
        //       container.setShowFPS(false);
        container.setMinimumLogicUpdateInterval(30);
        container.start();
    } catch (SlickException e) {
    e.printStackTrace();
    }
    }
}

For the most part yesterday (and part of this morning) was spent working on the build environment. Up until this point I’ve been compiling my program “by hand” with a command line argument run in the background by Emacs. This worked well enough, but adding three new files to the compile list was enough for me to decide it was time to address building the project in a better way.

So, I got to spend the day playing around with Apache Ant. Scala has a bunch of ant task definitions that took forever for me to figure out how to import. From there getting the whole thing to compile worked well enough, but figuring out how to tell ant how to run the program was a pain. I somehow managed to segue into building distribution jars, where I discovered the brain-dead inability to pack a jar within a jar.

Anyways, at the end of the day I have a build file that compiles the project and can run it directly or package it into it’s own .jar file and dump that into a dist folder. Eventually I’ll have to get around to solving the webstart issue, but for now I’m happy with what I’ve got.

The little bit of actual coding work was some class reorganization. I cleaned up most of the mess in my classes left behind from all of the testing I’ve been doing. I actually have code that is intended to represent the ants, ant hill, and food objects sitting in the source tree.