programming in the
twenty-first century

It's not about technology for its own sake. It's about being able to implement your ideas.

A Worst Case for Functional Programming?

Several times now I've seen the following opinion:

For anything that's algorithm-oriented or with lots of math, I use functional programming. But if it's any kind of simulation, an object-oriented solution is much easier.

I'm assuming "simulation" means something with lots of moving, nested actors, like a battlefield where there are vehicles containing soldiers who are carrying weapons, and even the vehicle itself has wheels and different parts that can be damaged independently and so on. The functional approach looks to be a brain-teaser. If I'm deep down inside the code for a tank, and I need to change a value in another object, how do I do that? Does the state of the world have to get passed in and out of every function? Who would do this?

In comparison, the object-oriented version is obvious and straightforward: just go ahead and modify objects as needed (by calling the proper methods, of course). Objects contain references to other objects and all updates happen destructively and in-place. Or is it that simple?

Let's say the simulation advances in fixed-sized time steps and during one of those steps a tank fires a shell. That's easy; you just add a shell object into the data structures for the simulation. But there's a catch. The tanks processed earlier in the frame don't know about this shell, and they won't until next frame. Tanks processed later, though, have access to information from the future. When they run a "Were any shells recently fired?" check, one turns up, and they can take immediate action.

The fix is to never pollute the simulation by adding new objects mid-frame. Queue up the new objects and insert them at the end of the frame after all other processing is complete.

Now suppose each tank decides what to do based on other entities in the vicinity. Tank One scans for nearby objects, then moves forward. Tank Two scans for objects and decides Tank One is too close. Now it isn't actually too close yet; this is based on an incorrect picture of the field caused by Tank One updating itself. And it may never be too close, if Tank Two is accelerating away from Tank One.

There are a couple of fixes for this. The first is to process situational awareness for every actor on the field as a separate step, then pass that information to the decision/movement phase. The second is to avoid any kind of intra-frame pollution of object data by keeping a list of all changes (e.g., that a tank moved to a new position), then applying all of those changes atomically as a final step.

If I were writing such a simulation in a functional style, then the fixes listed above would be there from the start. It's a more natural way to work when there aren't mutable data structures. Would it be simpler than the OOP version? Probably not. Even though entity updates are put off until later, there's the question of how to manage all of the change information getting passed around. But at one time I would have thought the functional version a complete impossibility, and now it feels like the obvious way to approach these kinds of problems.

(Some of these ideas were previously explored in Purely Functional Retrogames, Part 4 and Turning Your Code Inside Out.)

permalink January 11, 2014


twitter / mail

I'm James Hague, a recovering programmer who has been designing video games since the 1980s. Programming Without Being Obsessed With Programming and Organizational Skills Beat Algorithmic Wizardry are good starting points. For the older stuff, try the 2012 Retrospective.

Where are the comments?