Holy Bitcode Batman, You’re Writing a Compiler!

Recently I’ve taken an interest in programming language design and have started working on a compiler for a new language. The reasons for doing that are perhaps less practical than I’d like, because I’m a practical man, or sometimes pretend to be. At least I’m usually more interested in the application of mathematics than the beauty of mathematics itself. The same used to go for programming languages.

As the few readers of this blog may know, I’ve been experimenting with game programming now and then, but haven’t been driven enough to actually complete and publish a game. In early years I tried Pascal and C++. I did complete some stupid little games in Pascal, but C++ was more a hindrance to me than an enabler. At some point I learned UnrealScript while developing a Deus Ex mod and kind of liked it. Actually I think that was part of what lead me to Java and getting jobs in Enterprise Java programming. I never really thought to write games in Java, though.

When I discovered Scala I fell in love and thought it was the be-all and the end-all of programming languages and very applicable to games. Tried to write a couple of games in it, wrote some libraries for my own use and even ported a physics engine from Java and C++ to Scala. I loved doing it, loved the language features, the type system, the syntax, the preference of immutability over mutability. Perhaps most of all I loved Scala’s elegant mixture of object-oriented and functional programming.

Eventually something about making games in it started nagging me, though. The performance was good enough for the type of game I was making, but the game was also using a lot of resources for the type of game it was. It started to feel wasteful. The idea that games are a big part of what is pushing hardware forward and have to take the most out of it was somehow stuck in my head.

Scala runs on the JVM, which has the nice abstraction of a big heap, and the memory management is done for you. My boss Jevgeni has given a really awesome talk on that topic titled “Do you really get memory?”. But whatever tricks the JVM does to make that abstraction work well enough for most applications, it does produce some amount of waste — extra CPU cycles and garbage objects which need to be collected to free the memory for new objects. And that is a big part of what the JVM engineers are continuously improving on. They are probably the most efficient at collecting (virtual) garbage in the world! But there are cases where that kind of heap abstraction doesn’t seem to hold well, and high-performance games are one of those cases.

My game engine used lots of immutable, short-lived objects. Things soon to become garbage, in other words. Garbage, dying a slow death in the heap. Every small Vector2(x, y) tracked by the collector, maybe living in a separate heap region from its closest friends. And looking up bits from here and there in the heap is really expensive from the CPUs perspective. Even when the Sun Java VM started optimizing away heap allocation of very short-lived objects (enabled by escape analysis), that only gave me a small performance boost. The situation has improved, but back then I decided to try and avoid so much garbage being produced. I optimized some functions manually, doing scalar replacement of Vector and Matrix objects. That made the code look really ugly and unreadable because it hid the mathematical formulas.

I couldn’t stand it. Neither could I stand all these cycles wasted on GC. So I wrote an optimizer that plugged into the Scala compiler and did the scalar replacement automatically. It worked, and gave a more significant improvement than the JVM’s escape analysis optimizations at that time; garbage production was being reduced, I was going green! But it was hard for me to maintain the optimizer as I knew almost nothing about compilers and was just going by my nose. There were some corner cases that were hard to handle correctly. It only worked on code written against a very specific library, optimizing away well-known constructor and method calls.

Writing that optimizer got me somewhat interested in compilers, though. I remember saying to someone during a job interview a few years ago that I like complex problems, but am not interested in the really complex stuff like compilers. Sometimes things work out as the reverse of what you think.

Anyway, working on my game engine, I wanted to create a really powerful entity system. I wanted to use mix-ins and other nice Scala features. Reading some blog posts about game entity systems, I realized that most people seemed to be moving away from inheritance-based systems into component-based systems. Reading more about component-based systems made me run into the topic of data oriented design (PDF), which is all about thinking about data first, and how the program processes it. A couple of presentations on that left an impression on me and made me realize just how expensive it actually is to make the CPU churn through megabytes of random memory.

But I didn’t want to switch to C++ or C to be able to take advantage of the kinds of optimizations that data-oriented programming can give. I had the idea that maybe there should be a language that was object-functional like Scala, but compiled down to very CPU- and cache-friendly data structures and functions, the kind of structures one would use when doing data-oriented programming manually. And I have huge respect for people who do the latter. But I noticed that some of them seemed to be wanting a better language than C++ as well.

So, a language as expressive and type safe as Scala, similarly object-functional, but with more efficient memory access, CPU cache and parallelization friendly, enabling a data-oriented programming style with less hassle than C++. Perhaps one that could even run some functions on the GPU. What could that look like? I started thinking that maybe I should find out first-hand. [Update to clarify my goals] Well, at least I want to find out what it would be like to try to get there. I’m sure combining the type safety and power of Scala with the raw performance of C is way too ambitious for me. So I’m setting the goal way lower, but more about that in the next post.[/Update]

I’ve never really been a language geek. I’ve programmed in several different languages and at the moment am good friends with only two: Java and Scala. There are scores of other programming languages out there and I’m sure there is some language that is at least 2/3 of what I’m looking for.

But I think some bug bit me, because I couldn’t let go of the idea of creating one myself. And this blog post was a lengthy, boring preface to a series of hopefully less boring posts documenting my experiment. I have no illusions — I don’t think I’ll create the “next big language” or anything close — there are people much smarter than me who have been working on programming languages for years and decades. But this will be a fun learning experiment and maybe something useful will come out of it. Next time I will talk about the kind of language(s) I want to create. The (s) is because I want to create a really simple language first, to learn more about compilers during the process, and later expand from that base.

Taking Advantage of Scala 2.8: Replacing the Builder

In Scala 2.8, using the builder pattern is no longer necessary (or the most optimal solution) in many cases, as Scala 2.8 adds support for named and default parameters.

I’ll give an example of this based on ScalaBox2D. In the Box2D object model, physics Bodies are defined mostly by a set of Fixtures, which in turn are defined by a Shape, density, friction, restitution and some other parameters.

In the Scala 2.7 version of ScalaBox2D, there were mutable fixture definitions, which were used by the engine to create the actual fixtures. The user code only worked with definitions, through an internal DSL that looked something like this (note: all code examples are simplified for clarity):

body {
  box(halfWidth, halfHeight) density 1 friction 0.3f restitution 0
  computeMassFromShapes
}

For the DSL implementation, I used simple builders which left values to defaults if not specified:

def box(halfW: Float, halfH: Float) = new FixtureBuilder(FixtureDef(PolygonDef.box(halfW, halfH)))

class FixtureBuilder(defn: FixtureDef) {
  def userData(userData: AnyRef) = { defn.userData = userData; this }
  def material(material: Material) = { defn.apply(material); this }
  def friction(friction: Float) = { defn.friction = friction; this }
  def restitution(restitution: Float) = { defn.restitution = restitution; this }
  def density(density: Float) = { defn.density = density; this }
  def filter(filter: FilterData) = { defn.filter = filter; this }
  def sensor(isSensor: Boolean) = { defn.isSensor = isSensor; this }
  def define = defn
}

The FixtureDefs are mutable mostly to simplify the builder. In Scala 2.8, I can use named and default parameters, and drop some more lines of code by not having builders at all. As a bonus, I can easily make the definitions immutable.

def fixtures(fd: FixtureDef*) {...}
val fixture = FixtureDef // a shorthand to the companion object of FixtureDef
val box = BoxDef // a shorthand to a BoxDef object that creates PolygonDefs

case class FixtureDef(
  shapeDef: ShapeDef,
  /** The friction coefficient, usually in the range [0,1]. */
  friction: Float = 0.2f,
  /** The restitution (elasticity) usually in the range [0,1]. */
  restitution: Float = 0f,
  /** The density, usually in kg/m^2. */
  density: Float = 0f,
  /** A sensor collects contact information but never generates a collision response. */
  isSensor: Boolean = false,
  /** Contact filtering data. */
  filter: FilterData = FilterData.Default,
  /** Use this to store application specific fixture data. */
  userData: AnyRef = null
)

As you can see, the FixtureDef is now a case class with immutable parameters that have default values. Previously it looked very similar, but had only one parameter (ShapeDef) and all fields were mutable. The usage of the “DSL” now becomes a little bit more verbose (maybe I shouldn’t even call it a DSL any more) but I think it also becomes easier to understand for someone who knows the language but not the library, due to less moving parts and using built-in features instead of more code:

body {
  fixtures(
    fixture(box(halfWidth, halfHeight), density = 1, friction = 0.3f, restitution = 0)
  )
  computeMassFromShapes
}

Deleting code while maintaining functionality always makes me glad and this is one of those cases. I guess there may be some more complex cases where builders may still work better, but for simple things like the above example, I really like the named and default arguments feature.

Note: moving ScalaBox2D to Scala 2.8 is still a work in progress for me and there may be some further changes to this “DSL” as well.

Baseline Eclipse for Java Game Development?

The Eclipse IDE as it is offered for download at eclipse.org has become quite large. Size in bytes is probably not the biggest issue, but I think some of the functionality showing up in the UI is unnecessary clutter for many purposes that Eclipse could be used for. One such purpose I’m personally interested in is game development on the Java Platform (using Scala, Java, or another JVM language).

Some Java game development tools are already being built as Eclipse plug-ins and most likely more will be in the future. But right now they must provide them as a plug-in for an existing Eclipse installation that has all the clutter or build a completely custom Eclipse-based application, possibly an RCP app that doesn’t even include the Java Tools. I think this shouldn’t have to be the case: users of Java game dev tools should be able to download a version of Eclipse that is freed (as much as possible) from the cruft that they will not need, and be able to install specific tools and engine specific libraries into that baseline game development environment.

So I’m thinking of creating a lighter distribution of Eclipse JDT + XML tools that removes rarely used features from the Eclipse for Java Developers distribution and is specifically geared towards game development rather than enterprise Java or application development. Perhaps this should also extend to C/C++, but I am not familiar with the CDT so I’m not considering that aspect right now.

This distribution shouldn’t come from eclipse.org of course, but rather from the open source game engine and tools developers. I am willing to work on such a project, as long as it provides actual value to game developers and doesn’t eat up too much of my time. The first version of it could be fairly basic, just a lighter distro of Eclipse. Later versions can start incorporating game dev specific tools and UI concepts. Is there anyone interested in contributing to such a project? Or using such a build of Eclipse? Please let me know.

The first step of the project should be to create a reduced version of Eclipse JDT + XML tools that is still updateable, so that game development plug-ins and plug-ins such as Scala IDE, M2Eclipse, Subclipse, EGit can be installed. I have done some initial experiments and found an approximate list of features that can be easily removed from Eclipse JDT. If you would be interested in using such a distribution, please comment what you would like to be kept:

  • APT or Annotation Processing Tool support — I think this is very rarely used and just clutters the UI in some screens.
  • Ant support — I think a lot of people would be against this, so it should probably stay
  • CVS support — CVS should not be used by anyone for other than legacy reasons, now that we have Git, Mercurial, SVN etc. And I expect that games development will not involve much poking around in legacy repositories. I think most open source game tools use SVN (correct me if I’m wrong).
  • Help — this is debatable, but I would remove it from the first version and decide later what to do with it
  • Welcome screen — same as help, can be added back later if it’s found to have some use
  • JUnit3 support — JUnit4 should be enough, I think
  • Various internal tools and plug-ins, backwards compatibility stuff

I’m estimating that the size of this distro would be somewhere between 50-70 MB. The P2 update manager included in Eclipse will increase the size on disk though, because it may create a lot of meta data and caches. But disk space is relatively cheap, and I don’t think there’s a better update manager available. My main concern is removing UI clutter so that game dev tools that plug into it will have more UI space and better visibility. Compared to the Eclipse IDE for Java Developers distribution, which lists the following “features” (feature in Eclipse terms is a collection of plug-ins):

  • org.eclipse.cvs
  • org.eclipse.epp.usagedata.feature
  • org.eclipse.equinox.p2.user.ui
  • org.eclipse.help
  • org.eclipse.jdt
  • org.eclipse.mylyn.bugzilla_feature
  • org.eclipse.mylyn.context_feature
  • org.eclipse.mylyn.ide_feature
  • org.eclipse.mylyn.java_feature
  • org.eclipse.mylyn.wikitext_feature
  • org.eclipse.mylyn_feature
  • org.eclipse.platform
  • org.eclipse.rcp
  • org.eclipse.wst.xml_ui.feature

Only these would remain (and even those not in complete form):

  • org.eclipse.equinox.p2.user.ui (this is the update manager)
  • org.eclipse.jdt (custom lite version with APT and maybe a couple of more small things removed)
  • org.eclipse.platform (custom, with various plug-ins removed)
  • org.eclipse.rcp
  • org.eclipse.wst.xml_ui.feature (possibly custom with a couple of plug-ins removed)

Later versions could add optional updates that bundle engine-specific tools and libraries, Scala, SVN, Mercurial, Git or Maven support etc.

What do you think? Is there need for such an Eclipse distribution? I’m especially interested of the opinion of Eclipse based game tool developers, if any of you happen to read this post. Would you contribute if someone does the initial work? Has someone already done something like this (not engine specific)?

ScalaBox2D is getting SVG support

ScalaBox2D is going to get an SVG scene importer soon. This will let you draw a scene in Inkscape and load it as a Box2D world in ScalaBox2D. I already pushed a very basic version of this to GitHub. It uses Slick‘s SVG parser and has many limitations as of now, but you can already draw a Scene like this:

SVG Drawing

Inkscape SVG drawing

And bring it to life in a ScalaBox2D application:

ScalaBox2D Scene

ScalaBox2D scene

Currently every circle, box or polygon that has a red (#ff0000) fill will be turned into a dynamic body, the rest will be static bodies. There are also some limitations to the shapes, including: polygons must be convex, and have at most 8 vertices (or they’ll become static edges). Ellipses/arcs are not supported, only circles. You may get exceptions when loading some shapes.

The goal right now is to make this as robust as possible, so you can run the ScalaBox2D testbed and load (almost) any SVG file saved by Inkscape into it. After that, I’ll add support for loading scenes from game code and tying the physical bodies to game objects.

The code for the app looks like this:

import org.villane.box2d.svg._
import org.villane.box2d.draw.DrawFlags._
import org.villane.box2d.testbed.slick._

object SVGApp {
  val scale = 15

  def main(args: Array[String]) {
    val loader = new SlickSVGSceneLoader("C:/drawing-1.svg", scale)
    val world = loader.create
    val flags = Shapes
    SlickDisplayWorld.runWithSimulation(world, false, flags)
  }

}

Modelling Game Entities Using Traits

For a while now I’ve thought that Scala would be a good language to write games in. Well, I’m putting those thoughts into practice: I resurrected a couple of old game ideas and am now working on a 2D game or two as hobby projects. I decided that it would be a good idea to try my hand on simpler games before I embark on a longer project (which will likely be a platformer), so the one I’m working on now is something of a mix between Breakout and Peggle.

As part of writing those games, I’m also designing a generic game entity system, which will be integrated with Slick2D (for graphics, sound, input and other stuff) and a Scala port of Box2D (for collision detection and physics) that I’m also working on. So far I am very pleased that I chose Scala for this project — the code is generally more concise than Java (requiring roughly 2 times less lines), but what I like most is that traits, pattern matching plus some other features make Scala a great language for building components.

With the entity system I’m trying to take full advantage of that, implementing the building blocks for entities as traits that deal with different concerns. Some of these traits only define an interface for some type of behavior, but some also implement it, reducing the amount of code needed in concrete entities. Here are some of the most basic traits I’ve got implemented so far and descriptions of what they do:

Entity – the base trait for all my game entities, which extends Updateable, making it able to act on updates (or “ticks”) from the game engine during each frame.

PhysicalEntity – can be mixed into an entity class to add a physical body to an Entity, which takes part in the physics simulation and collision detection.

GraphicalEntity – adds a render method, which the entity can implement to render itself.

WithStates – for more complex entities that behave differently depending on their current state. For example a camera in a sneaking game may have states “Off” and “On”. In the Off state, the camera might not do anything, but in the On state it might be listening to some game events to react to seeing the player. To do this, a specific state (which are implemented as internal classes of the Entities) could mix in the Updateable and/or EventListener traits to react to events differently when that state is active. Additionally, defining state transitions can limit how the entity moves from one state to the other and allows to run some code when the state changes.

EventListener – an entity (or one of its states) with this trait will receive notifications of events it is interested in. This can be used in other objects besides entities and states, but only the latter two are automatically registered as listeners in the event queue.

Environment – this is the container for entities, the physics world and the event queue.

This is not all, but these are the most basic building blocks. Here is the code for a simple entity that makes use of some of these:

class Paddle
    extends PhysicalEntity with GraphicalEntity
    with EventListener with GameStateAware[InGame] {

  // we define the physical body for the PhysicalEntity
  val bodyDef = new BodyDef
  bodyDef.pos = (0,-10)
  bodyDef.fixedRotation = true
  bodyDef.allowSleep = false

  // the radius at which the paddle moves around world center
  val radius = 10
  // keeps track of the number of balls shot from the paddle and currently in play.
  var ballsInPlay: Int = 0
  def noBallsInPlay = ballsInPlay == 0

  // we call a convenience method of the EventListener to listen to some specific kinds of events
  listenTo {
    case ce @ ContactResultEventBetween(body1, body2) =>
      val other = 
        if (body1 == body) body2
        else if (body2 == body) body1
        else null
      if (other != null) {
        gameState.scorer.hitPaddle(this, other.userData.asInstanceOf[PlayerBall])
        PlayerBallSounds.hitPaddle.play
      }
  }

  // we override the function that is called when a PhysicalEntity is inserted into the world
  override def enterWorld(w: World) {
    super.enterWorld(w)
    val shape = PolygonDef.box(1, 0.1f)
    shape.density = 0f
    body.createShape(shape)
  }

  // define the render method to render the paddle (currently just rendering the physical body as a placeholder)
  def render(g: Graphics) = {
    import org.newdawn.slick.Color
    g.setColor(Color.white)
    rendering.RenderUtils.renderBody(g, body)
  }
}

I am already pleased that I was able to separate the different basic concerns using Scala’s traits and making them easily composable as seen above, but I hope that the real benefits should become apparent in a larger game with lots of different entities. Mick West talks about creating game entities as components in his blog post “Evolve Your Hierarchy” – I think he is right and that Scala’s language support for this (especially in the form of traits) is better than in C++ or Java, where you could do something similar with inheritance, interfaces and object composition. Note: I’ve never been a professional game developer or even got to the point of releasing a hobby project to the wider audience so I’m not speaking from reliable personal experience exactly, but I’ve worked with a few entity systems and this just seems right to me.

I will post more about this in the future, hopefully after having released a simple game :) and I’m considering releasing the code for the entity system under an open source license.