Well, I have actors working correctly in the game … mostly.

Here’s a screenshot of the test running. That’s 625 actors all maintaining separate locations and an angle. The same class that implements the actors also draws the triangle image oriented correctly, currently they’re following the (not seen) mouse pointer.

The problem I’m running into is that I can get great performance out of this on my dual core macbook. For the most part I can allow all of the actors to run asynchronously without a problem and get about 350 frames/sec. A smaller test (400 actors, also asynchronous) on a creaky old athlon 3000 xp reveals the flaw in that idea: updates don’t have a chance to propogate between render calls, or possibly even between one game loop update and the next. Since this is asynchronous, the only thing I can conclude is that the overhead of managing 400 actors is just too much for that processor. I’m sure I could optimize it a bit, in fact I’m deliberately leaving a lot of the actor code on the “heavy” side so I’ll have some easy targets to optimize it later.

My big concern is that having a second core available is what really makes this whole thing kick ass. Even in scala’s event-based actor mode, which is what I’m using, there are still a few extra threads. Some tests to push the macbook show that my code is using both cores, so the results here just plain don’t translate to a single core system. It would really suck to finish up an awesome game and have it only work with dual core computers.

I’ll probably go through the hassle of trying to package everything for webstart and see if I can get some help testing it, or just run it on every system I can find.

Update:

As was entirely predictible, switching to direct method calls delivered an insane speedup. 7000 ants all adjusting to mouse movement (even if they’re too far away to see any kind of appreciable difference) ran at an acceptable-to-me 33 fps on the macbook. Granted, I’ll have to try it on my “minimum system requirements” box, but I’m happy again.

What I really wanted more than anything out of the actors library was the message passing and pattern matching. Now that I understand it a little better I can fake it pretty well without the overhead of the concurrency. It isn’t even all that hard, I just have to figure out how (or if) I’m going to return values.

Even less progress than day 1. I’m considering switching to weekly updates since my main focus right now is school, but doing them daily forces me to get something done, no matter how small.

Anyways, yesterday’s small bit of advancement was working on communication between an actor network and the game loop handling code. Specifically I want to be able to notify an actor about something (user input, a game tick happened, we need renderables, whatever) and wait for it to finish.

To test this I started modifying the pingpong example. A bit of playing around with it gave me this:

import scala.actors.Actor
import scala.actors.Actor._
import scala.actors.OutputChannel

abstract class PingMessage
case object Start extends PingMessage
case object SendPing extends PingMessage
case object Pong extends PingMessage
case object Done extends PingMessage

abstract class PongMessage
case object Ping extends PongMessage
case object Stop extends PongMessage

object pingpong extends Application {
  val pong = new Pong
  val ping = new Ping(100000, pong)
  ping.start
  pong.start
  val f = ping !! Start
  f()
  println("This happened after the actors")
}

class Ping(count: Int, pong: Actor) extends Actor {
  self.trapExit = true;
  var initiator = null : OutputChannel[Any];
  def act() {
    println("Ping: Initializing with count "+count+": "+pong)
    var pingsLeft = count
    loop {
      react {
        case Start =>
      initiator = sender;
          println("Ping: starting.")
          pong ! Ping
          pingsLeft = pingsLeft - 1
        case SendPing =>
          pong ! Ping
        pingsLeft = pingsLeft - 1
        case Pong =>
          if (pingsLeft % 1000 == 0)
        println("Ping: pong from: "+sender)
        if (pingsLeft > 0)
          self ! SendPing
        else {
          println("Ping: Stop.")
      pong ! Stop
      self ! Done
    }
    case Done =>
      initiator ! Done
      exit('stop)
      }
    }
  }
}

class Pong extends Actor {
  def act() {
    var pongCount = 0
    loop {
      react {
        case Ping =>
          if (pongCount % 1000 == 0)
            println("Pong: ping "+pongCount+" from "+sender)
          sender ! Pong
          pongCount = pongCount + 1
        case Stop =>
          println("Pong: Stop.")
          exit('stop)
      }
    }
  }
}

The original example is largely unmodified, except for the following changes:

• Added an “initiator” variable to the Ping actor, which is set with a reference to the actor that sent the “Start” message.
• Added a “Done” message to the Ping actor, which it sends to itself to call cleanup code and send its reply to the “initiator” saved in Start.

Granted, this would run into some problems if I were to send Start to Ping twice in a row without blocking until it completes, but I don’t plan on doing that.

Not a terribly productive day yesterday. Initiated a darcs repo and copied over a bit of generic stuff from my big game’s codebase. Spent a good deal of time futzing around with trying to get a rectangle (org.newdawn.slick.geom.Rectangle) to rotate the way I wanted it to. After doing a bunch of fire and pray changes I decided to look at the wiki and found that drawing any of the geometry classes isn’t particularly efficient, which throws them right out even for prototyping since I will have lots and lots. Have created a simple yellow triangle that can pretend to be an ant while I do testing.

Spent a while trying to understand Scala actors and see how they would fit in this context. My current idea is to have the ants, food objects, and beacons all represented as actors with non-actor methods to handle game loop interaction. Theoretically game updates and rendering could be handled as actors as well, maybe this is a good way to do this, I’m just worried about the overhead. I guess I could always switch later if needed.

I have a big game in the works. By “big” I mean much larger than any single person should reasonably expect to be able to finish soon. I’d like to see it done before I graduate, which should be in about two years. So I have a big idea that I want to accomplish in two years, working part time. I’m a big believer in constraints helping to focus creativity, but this really seems like it is pushing it. One aspect that helps here is I can look at the idea of doing this game in 3d and easily say “it won’t give me much but eye candy, and will multiply the time spent on art by at least a factor of ten”. That makes the decision to go 2d with this dead simple, which saves me a world of time. Without my two year deadline I’d probably decide to go ahead and do it since it would look better, which would probably push my time-to-completion from two years to never.

Another useful constraint is that the whole thing has to theoretically work on my Macbook. That means relatively light graphics requirements and controls operated with a single-button mouse. Sure I’ll probably get an external mouse later on for testing (I want the gameplay to be fast paced, so a trackpad might not be the best of tools), but limiting myself to a single button leaves me with the possibility of running this in an applet and ensures that the gameplay can’t get too complicated.

Even with all of those advantages, this is still a very complex game. I’m using Java so I don’t have to worry about manual memory management or deployment, so those aren’t elements of the project’s complexity. There’s a lot of well-designed Java libraries I can draw from, and it even has neat features like webstart so people can play the game without installing anything. I’m also using Scala, which has functional programming and actors and all kinds of other tools to manage complexity.

Despite all of this, I think I’m still going to need to be careful about how I go about writing this game. If I try to simply attack it directly I could easily get lost in the complexity of the game. This is compounded by the fact that I don’t know a whole lot about Scala or the programming libraries I want to use other than that they look like they offer useful tools.

So, my current goal is a lot smaller, mini-games that can be easily completed and are based on a subset of the big game. These should ideally be projects that can be finished in a week or two, and will leave me with code that I can easily port to the big game.

One aspect of my larger game is going to involve swarms of units. These swarms will have in-game objectives in the form of an in-game object that they should cluster around and perform some action based on their overal purpose. To get that idea off the ground I’m going to work on a game where you control ants trying to invade a picnic. The idea is to take a swarm of ants coming out of your ant mound and try to gather up as much of the food on the blanket as possible in the time limit before the picnic-goers return. The player can set targets that include a notion of how many ants should head toward that target, and the individual ants take care of moving toward the target, gathering a bit of food, and returning to the nest with it. Larger items of food give you more bits, and things that are further from the mound take longer to gather. The goal here is to have a rather basic game that relies on something fundamentally similar to the behavior I want for the big game.

Since this is a learning experience, here’s what I hope to get out of “Picnic Invasion”:

• A basic understanding of background and sprite loading
• Basic sprite manipulation (rotation and transformation for ants, scaling for food items and obstacles)
• Basic navigation
• An idea of how I want to structure the rendering and game update pipelines
• An understanding of actors (used to implement the individual ants in the swarm)

This is probably going to be a bigger project than most of the other small games, since a good portion of the list above will be reused practically without modification in later games. Still it seems like a great place to start. I’ll be documenting progress as I get things going.

One reason that I am playing around with Scala to begin with is that I am curious about the useful applications of FP ideas to game programming. Many functional programming techniques (at least on most implementations) are probably going to be too inefficient for big budget games. Since I’m just one person I have the luxury of not worrying about that, as I couldn’t write that kind of game anyways. For smaller games I think functional programming can offer some big advantages in productivity.

Anyways, for my first in what will hopefully be a series of meandering explorations of the interaction between game development and functional programming, I’m going to talk about rendering.

A Quick Overview

The traditional game structure includes a loop that runs a render function to display the game on screen, and an update function to updates the game logic. Things like the position of enemies and responding to player input happen in the update loop and the relevant changes are somehow communicated to the render loop. In the old days games were developed with the assumption that game logic could update at the game’s framerate without a problem. This worked at the time, but as processor speed increased and the speed of the entire game increased with the framerate it became obvious that the game logic needed to be updated in line with the wall clock, not the render speed. Current game design favors a significantly higher number of render passes to update ones. As game logic has grown more complex tiny incremental updates have been discarded in favor of less frequent larger batches.

Anyways, the point here is that we have an update function, which is not allowed to touch the graphics card, and a render function that doesn’t alter that game’s state. The first has to change the second whenever it updates the game.

The OOP Solution

The typical OOP solution is to have a Game class with render and update methods. The update method makes changes to internal state variables that are read by the render method when it displays the scene. A common approach to managing this data structure is to maintain a scene graph (named this even though it’s usually a tree) of specially designed objects that all have a “draw” function which accepts the graphics object and uses it to display themselves as well as any objects they contain.

This works relatively well. It’s conceptually simple to understand, and has advantages in larger games in that the nodes can easily be examined to determine if they (or any of their children) need to be rendered at all.

There are a couple of problems we can solve here though. One is that a scene graph is a data structure that is optimized for scene management. If you want, for instance, to interact with all of the physics-enabled objects in the scene you have two choices: maintain your own data structure or sweep through the scene graph looking for these objects. Considering things like lights, particle emitters, skyboxes, and HUD items are all part of the scene there’s a lot of stuff that will never interact with the physics system that you still have to touch each time you run an update. Maintaining your own data structure is often an acceptable solution here, but it requires careful management to ensure that the game logic entries and scene graph entries are kept in sync.

Another is that the scene graph has to be pruned for visibility on each render pass. Since objects only move during updates this represents a lot of effort for no particular reason. Advanced engines will quickly establish some means of maintaining pruned scenes between render calls to avoid this overhead, but not all of them do it. Besides there obviously is an element of “functional programming for functional programming’s sake” in all of this, why else would I be going to the trouble?

A Functional Approach

My current approach to this problem is to retain a render list. This is a list of functions that each take the graphics object as input and draw something to the screen with it. The update function examines my data structures and rebuilds this list each time it is called. This leaves me free to optimize my data structure for the needs of my game logic and still handle rendering easily. Things like z-indexing are a simple by-product of my method of data structure traversal, and I am now completely unable to perform visibility testing in the render loop. I can even start adding metadata to the list so the render function is able to discard nonessential render actions if the frame rate starts to slip. In addition, instead of the relatively inefficient traversal of a custom-built data structure I have my compiler’s handling of off-the-shelf list use, which often is better optimized than I could hope to implement myself.

The downside here is that, to make the whole thing work, I either need closures or anonymous functions built up on the fly. This limits the languages that could potentially pull this idea off, and depending on the implementation introduces some ugly overhead of its own. This entire idea may end up being too big of a memory hog for it to work. I won’t know the answer to that until I test it further.

Update: A quick test handled about 3500 relatively simple objects on a 2ghz macbook (with a pretty poor graphics card) before the framerate dropped into ugliness. This is using Scala on top of the Slick Java 2d library, so results on a more highly optimized functional language outside the JVM (OCaml) would probably be even better.

More playing around with Scala and slick. Here’s the GeomTest.java file rewritten in scala:

/* A conversion of the GeomTest.java program from the slick tests to
 scala. Of special note is the replacement of the ternary operator
 with a value storing an anonymous fnction.  */

import org.newdawn.slick.AppGameContainer;
import org.newdawn.slick.BasicGame;
import org.newdawn.slick.Color;
import org.newdawn.slick.GameContainer;
import org.newdawn.slick.Graphics;
import org.newdawn.slick.Input;
import org.newdawn.slick.SlickException;
import org.newdawn.slick.geom.Circle;
import org.newdawn.slick.geom.Ellipse;
import org.newdawn.slick.geom.Rectangle;
import org.newdawn.slick.geom.RoundedRectangle;
import org.newdawn.slick.geom.Shape;
import org.newdawn.slick.geom.Transform;

/**
 * A geomertry test
 */
object GeomTest {
  class GeomTest(s : String) extends BasicGame(s : String) {
    /** The rectangle drawn */
    val rect = new Rectangle(100,100,100,100);
    /** The rectangle drawn */
    val circle = new Circle(500,200,50);
    /** The rectangle tested */
    val rect1 = new Rectangle(150,120,50,100).transform(Transform.createTranslateTransform(50, 50));
    /** The rectangle tested */
    val rect2 = new Rectangle(310,210,50,100).transform(
      Transform.createRotateTransform(Math.toRadians(45).asInstanceOf[Float], 335, 260));
    /** The circle tested */
    val circle1 = new Circle(150,90,30);
    /** The circle tested */
    val circle2 = new Circle(310,110,70);
    /** The circle tested */
    val circle3 = new Ellipse(510, 150, 70, 70);
    /** The circle tested */
    val circle4 = new Ellipse(510, 350, 30, 30).transform(
      Transform.createTranslateTransform(-510, -350)).transform(
        Transform.createScaleTransform(2, 2)).transform(
          Transform.createTranslateTransform(510, 350));
    /** The RoundedRectangle tested */
    val roundRect = new RoundedRectangle(50, 175, 100, 100, 20);
    /** The RoundedRectangle tested - less cornders */
    val roundRect2 = new RoundedRectangle(50, 280, 50, 50, 20, 20, RoundedRectangle.TOP_LEFT | RoundedRectangle.BOTTOM_RIGHT);

    /**
     * @see org.newdawn.slick.BasicGame#init(org.newdawn.slick.GameContainer)
     */
    override def init(container : GameContainer) { }

    /**
     * @see org.newdawn.slick.BasicGame#render(org.newdawn.slick.GameContainer, org.newdawn.slick.Graphics)
     */
    override def render(container : GameContainer, g : Graphics) {
      g.setColor(Color.white);
      g.drawString("Red indicates a collision, green indicates no collision", 50, 420);
      g.drawString("White are the targets", 50, 435);

      g.scale(10, 10);
      g.setColor(Color.red);
      g.fillRect(10,0,5,5);
      g.setColor(Color.white);
      g.drawRect(10,0,5,5);
      g.scale(1/10.0f, 1/10.0f);

      g.setColor(Color.white);
      g.draw(rect);
      g.draw(circle);


//       Since Scala doesn't have a ternary operator (that I know
//       of) we'll replace it with a custom function here. Without
//       digging into support for lazy evaluation and such I can't
//       implement an exact analog of a ternary operator.

      val pickColor = (s1 : Shape, s2 : Shape) => {
    if(s1.intersects(s2))
      g.setColor(Color.red);
    else
      g.setColor(Color.green);
      }

//       Just to clean things up a bit, we'll encapsulate the
//       pickColor->draw motion in a named function.

      def drawIntersection(s1 : Shape, s2 : Shape) {
    pickColor(s1, s2);
    g.draw(s1);
      }

      drawIntersection(rect1, rect);
      drawIntersection(rect2, rect);
      drawIntersection(roundRect, rect);
      drawIntersection(circle1, rect);
      drawIntersection(circle2, rect);
      drawIntersection(circle3, circle);
      drawIntersection(circle4, circle);

      g.draw(roundRect2);
      g.setColor(Color.blue);
      g.draw(new Circle(100,100,50));
      g.drawRect(50,50,100,100);

    }

    /**
     * @see org.newdawn.slick.BasicGame#update(org.newdawn.slick.GameContainer, int)
     */
    override def update(container : GameContainer, delta : int) { }

    /**
     * @see org.newdawn.slick.BasicGame#keyPressed(int, char)
     */
    override def keyPressed(key : int, c : char) {
      if (key == Input.KEY_ESCAPE) {
    System.exit(0);
      }
    }
  }
  /**
   * Entry point to our test
   * 
   * @param argv The arguments passed to the test
   */
  def main(argv : Array[String]) {
    try {
      val container = new AppGameContainer(new GeomTest("Geometry Test"));
      container.setDisplayMode(800,600,false);
      container.start();
    } catch {
      case e : SlickException => e.printStackTrace();
    }
  }
}

I’m starting work on a 2d Java game. I’ve been kicking around an idea for a while, and some of the capabilities of the Java platform here make it a really good choice for this task. Webstart, for instance, would allow me to distribute the game to friends by simply having them click a link and let the program run. The JVM and some of the available 2d game engines make writing cross platform code a snap. And I don’t have to futz around with manual memory management, which is always a bonus.

The big problem in this equation is Java. The language isn’t outright bad, but it isn’t terribly good either. Some things that I think would make this game easier to develop simply aren’t available. So, I spent a while poking around on alternative langauges that compile to the JVM. Jython was out immediately for several reasons: speed (not that I worry much about this, but even slower than CPython? ouch), Java interoperability (at least the FAQ makes this look confusing), and lack of static type checking (evidently the borg have gotten to me). I didn’t consider JRuby, mainly by assuming that the same points about Jython would apply. Mozilla Rhino looks interesting, but the whole time I was looking at it I kept thinking I really would like to have static typing.

So, I went with Scala. I’m still getting up to speed on it and the game libraries involved, but so far it looks interesting if nothing else. The language is decently flexible, and seems to play nice with Java as much as possible. Most of my code will be pretty simple Scala->Java calls, so it should be fine. It looks like even building Java->Scala->Java code bases is a mess, but that seems kind of obvious to me.

As a teaser, here’s a simple translation of a “Hello World” program for the slick game library with the original Java code:

import org.newdawn.slick._

// Since we're planning on running this directly out of a .jar we need
// a (singleton) object so the main function is static, hence the
// object with an inner class implementation. An outer class would
// have worked as well, but there you are.
object TestProgram {
  // Take note: Due to scoping rules (i'm assuming) this TestProgram
  // is the one referred to in main below.
  class TestProgram(s : String) extends BasicGame(s : String) {

    override def init(container : GameContainer) {}

    override def update(container : GameContainer, delta : int) {}

    override def render(container : GameContainer, g : Graphics) {
      g.drawString("Hello, Slick (from scala) world!", 0, 100);
    }
  }

  def main(args : Array[String]) {
    try {
      val app = new AppGameContainer(new TestProgram("TestProgram"));
      app.start();
    } catch {
      case e : SlickException => e.printStackTrace();
      case ex : Exception => ex.printStackTrace();
    }
  }
}

And the Java version:

import org.newdawn.slick.BasicGame;
import org.newdawn.slick.GameContainer;
import org.newdawn.slick.Graphics;
import org.newdawn.slick.SlickException;
import org.newdawn.slick.AppGameContainer;
public class SimpleTest extends BasicGame {

    public SimpleTest() {
    super("SimpleTest");
    }

    @Override public void init(GameContainer container) throws SlickException {}

    @Override public void update(GameContainer container, int delta) throws SlickException {}

    @Override public void render(GameContainer container, Graphics g) throws SlickException {
    g.drawString("Hello, Slick world!", 0, 100);
    }

    public static void main(String[] args) {
    try {
        AppGameContainer app = new AppGameContainer(new SimpleTest());
        app.start();
    }
    catch (SlickException e) {
        e.printStackTrace();
    }
    }
}

The scala version is a line longer due to comments, but cheats a little with the unqualified import. Right now the happyplace for me is that I don’t have to write “T foo = new T()” and can let Scala infer from usage that if I’m making a new object of type T, I’m probably holding a reference to it that is of type T as well.