Finite Improbability

Well, it’s that time of the year and I’m joining in the fray as well. Here’s my (hopefully not entirely empty) set of promises for the year. I don’t know who would actually find this interesting, but it’s helpful to me.

1. Learn Haskell: This was on the list last year, and still hasn’t happened to my satisfaction. I’m generally able to follow along with Haskell code, but haven’t quite written anything yet. I’m considering working out my game idea here since it’s a concept that doesn’t seem to mesh well with functional programming and would really push me to learn the language.

2. Write a compiler: Technically this one is going to happen regardless since I am taking that course sequence. I’d like to do something targeting the llvm, but we’ll see how it goes. Maybe I’ll start by rewriting the backend from that project to generate code for the llvm.

3. Write that damn game: I’ve been kicking around the idea forever, it needs to get done. Hopefully this term’s computer graphics course will help me get over that hurdle, but the reality is I just need to apply myself to it. (see 4) Maybe I’m reaching too far with it, it could be done in SDL without too much work and hopefully prettified as I find interest and time.

4. Stop wasting time: This was on the list last year too, (as “get off reddit”) and I made some progress then as well. I end up falling into this productivity sink holding pattern of reddit->email->rss->game news->repeat. When I first started with reddit it was a real eye-opener. I can honestly say reddit has led me places I probably wouldn’t have gone on my own, but it hasn’t been sending me anywhere new for more than a year now, and this pattern is really sucking up time. I’ll still skim everything to find the new and interesting stuff, but I need to get to work.

5. Get productive: I don’t have any illusions that my programming dilettantism will mean beans to an employer (or grad school admissions). I need actual work done on projects to demonstrate my chops, and school projects only go so far. My reddit karma, no matter how impressive, won’t go further than I could throw it either. (see 4)

6. Settle the grad school issue: I want to find a topic and explore it with at least a masters. The point here is to hopefully avoid the programming equivalent of the drudgery I left systems administration to try and escape, and ultimately get a job doing something I like. So far the “fields” are narrowed down to graphics, security, and programming language research (i.e. “I like functional programming”). I need to figure out what I’m doing and start scouting out other schools to do it at, in addition to applying #5 here. Not a whole lot of time left here.

7. More blogging: When I was doing it regularly, it helped to keep me on task. Attempting to explain what I was thinking about helped me to organize and further develop my thoughts. I could probably launch into a long rant about the value of switching from being exclusively an information consumer to being a consumer/producer, but I wouldn’t be convincing anyone of anything. From my limited experience it works for me, and that should be enough.

All that said, this was a pretty good year. Nadia and I got married in July, took a trip we’d been talking about for years, and settled a lot of financial crap all in about two weeks. We both made progress on a lot of things we wanted to fix, which is why my list of resolutions is almost exclusively programming-related.

I spend a lot of time hopping between computers. My Windows “gaming rig” usually also sees a fair bit of programming research. Typically I’m about halfway through an article when I end up having to go somewhere else, and I end up wanting to continue from there on my Macbook. My trusty delicious bookmarks add-on gets me halfway there, but I want more.

Right now I’m reading through the book Real World Haskell, and finding my way back to where I was is kind of a pain. I don’t want to save intermediate bookmarks because I don’t want to have to clean up the mess, or pollute delicious with redundant links. (I think we can all agree that’s happened enough)

What I’d really like is something like version control for the browsing environment. Basically an add-on that saves the browser state somewhere online and checks for updates. This should preserve open windows, tabs, and scroll locations. Obviously things like restoring JavaScript/Flash/Java applet states would be more of a challenge than it is worth, but it would be pretty useful to me. My very brief search didn’t find anything like this, if it doesn’t exist I may have to see how hard it really is to make an add-on.

Update:

What I’m looking for kind of exists in the aptly named Session Manager add-on. The only problem is that it saves these sessions locally. It might not be too hard to make it work with a different (i.e. online) data store.

After seeing this game, which seems close to a lot of the ideas I’ve been working on, I’m trying to get back into writing mine. Here’s what I think needs to change from my previous work:

Graphics

I got seriously hung up over graphics. I kept flip-flopping between trying to do it in 2d and doing it in 3d. Could I make graphics that wouldn’t suck in either? I’m a programmer, not an artist. 3d models are a lot of work, and the game idea I have is inherently not three dimensional. This should have been a simple point, huh? Anyways, unless I can coerce my wife into doing something better, expect programmer-quality crap artwork.

No “Starter Games”

One idea I was pursuing was to try and do small games that encapsulated one portion of the functionality I was working on for Starbound. Since I wanted to have a bunch of ships semi-autonomously flying around the screen I came up with the idea of Picnic Invasion!, where a bunch of ants semi-autnomously crawl around a board.

In the right scenario, this could work out well. Unfortunately I couldn’t really stir up much enthusiasm for the smaller game, so pretty much nothing got done. I’m going to focus on Starbound and just that. Picnic Invasion! is pretty much dead, although I’ll hang on to the idea if I want to start doing simple applet games.

The Clojure/Java bridge

When I started working with Clojure, I pretty much assumed it would be easier to do my computation in Clojure and use Java for storage. This let me completely pass up learning all of the stuff in Clojure for handling mutable data by hiding all of my mutations in Java.

The end result was that I had a bunch of Java classes that constantly needed maintenance. The runtime modification that was the whole point of me using a Lisp dialect for this was pretty well lost. It also meant a lot of cumbersome stuff with objects that were little more than data holders, and code like this:

(defn update-game-obj 
  "Update the information provided to Java about the game object."
  [#^GameObject obj]
   (let [p (get-pos obj)
     v (get-vel obj)]
     (set! (. obj x) (. p (getX)))
     (set! (. obj y) (. p (getY)))
     (set! (. obj ang) (+ 90 (. v (getTheta))))))

Where a game object has to be told twice something it already knows just so the Java-based rendering function can know how to render the object. Except it’s not that simple, as the render loop is actually built from Clojure code, so there’s a lot of unnecessary indirection and duplication going on here.

The point is that I really should be wholly embracing one or the other. Clojure has a lot of beautiful parts that I’m missing out on because of this organization. The persistant data structures are pretty much useless in this approach as any of my Java-based objects directly violate their core assumptions, so any of the cool things I could do with them (like easily rewinding time) simply aren’t possible.

Slick?

Kevin Glass’ Slick library is really great. He’s spent a lot of time on it and it handles a lot of stuff I’d rather not deal with. Slick tries really hard to just do what you need and stay out of your way the rest of the time.

That said, I still am considering doing the whole thing “from scratch” using lwjgl. It would be nice to learn a bit more about OpenGL and some of the other technologies, and I would essentially be able to do all of the game in Clojure, which is a real plus. That said, I’d be taking on a lot more responsibility, and re-doing a bunch of things that Slick handles pretty admirably. The jury is still out on this one.

What Went Right?

With all of this complaining, there were a few things that went really well. When I didn’t have to shut everything down to monkey with one of my Java classes, using a Lisp for runtime development was awesome. It’s easy to get lost in tweaking something until it is perfect, which can be a bit of a time sink, but simply having that ability means that when it is time to start perfecting things the work will go a lot faster.

I realized that I sort of stumbled off into Lisp land without explaining why. For those who have worked with a modern Lisp environment, some of the advantages are probably obvious. For the other 98% of the programming world I probably look like a nut. Here I’d like to make a case for why Lisp is a good choice, inside certain parameters, for game development.

Syntax

The first advantage I see in Lisp is also the most cited problem with it. Lisp’s syntax is a powerful tool for extending the Lisp language. Speaking in terms of compilers Lisp doesn’t so much have syntax as a directly written abstract syntax tree. The upshot of this is that, since Lisp’s syntax is so regular, Lisp itself can be used to write macros for your program. This makes building a domain specific language for writing your game much easier.

If you’re going to go through the effort of using a scripting language for your game you might as well make sure it’s actually useful for the task. There’s two ways to do this, either luck into finding one that already has the tools you need or take an existing one and build up to that point. My assumption here is that there aren’t going to be too many scripting languages built explicitly to support writing a space shooter or RTS, so we’re stuck building on top of something that does exist. Lisp’s abstraction capabilities let you turn your scripting language into something specifically tailored for writing your game more quickly and less painfully than anything else.

Dynamic Language

Obviously if I’m going to be doing some scripting the goal is to save time over writing in straight C. There’s a few advantages people typically look for here:

• No Compilation
• More powerful abstractions

The first advantage is the biggest. One big advantage of scripting is that it allows you to modify the game’s behavior without having to recompile. Lisp lets me take that one step further, which is something I’ll get back to in just a bit.

The other big advantage people look for in scripting is in the realm of abstractions. The idea is that you push game objects around with logic written in your scripting language and let the “system” language deal with rendering, representing vectors, loading resources, etc. Since my specific Lisp dialect (Clojure) interacts well with my system languge (Java), I’m all set in this regard.

Interactivity

One feature of Lisp dialects that few other languages have caught up to is the read-eval-print loop (from now on: repl). This is a powerful idea where a minimal Lisp program is loaded that does nothing but take in and execute new definitions and statements. The programmer can type their definitions in on the command line (or more comfortably direct their editor to do so from within a file) and have the repl execute them.

This is the heart of my theory about Lisp’s productivity boosts. I have set my game up so that it can be loaded in a debugging mode. Within this mode the game watches for new Lisp definitions or statements to be sent in and executes them. If I don’t like how some part of my game logic works I can change it and see that change reflected in the game as it is running. I don’t have to shut down, I don’t have to reload a script, and I usually don’t even have to reload the game environment. This is development at breakneck speeds, especially in the later stages of a game where fixing bugs might involve quite a while to wait on resource loading and playing through a game until the point where the bug is encountered.

Right now I’m working on building a replay system into the game. The idea is to record all meaningful user input so that can be played back through the game and I can fix buggy behavior by jumping back to before that behavior happened, modifying the relevant code, and testing it to make sure it now works correctly. On paper this is even more powerful, but we’ll see how it happens in practice.

Considering I’m trying to spend a little more time working to keep up with bills for my wedding this summer, and still taking school, something has to give. I obviously haven’t been keeping to the daily updates I wanted, and realized I just can’t afford to spend two to three hours each night on this game. Hopefully some time constraints will encourage me to use the time I do dedicate to this a little more meaningfully.

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.