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.