Functional Programming for Game Development

Game development is often being done in a highly object-oriented mindset. This is not only because the vast majority of gameplay engineers program in object-oriented languages (such as C++, C#, Java, etc), but also because the way a videogame operates can easily be modeled as a collection of discrete, independent objects.

A videogame comprises a number of gameplay elements, such as individual game mechanics, narrative elements, dialogues, agents, boids, actors, impacts, cutscenes, scenarios, and so on. And these are all distinct, highly separable entities which are based off of different faculties of mind. A dialogue and an explosive effect, for example, may be related with each other via a segment of conversation such as, "NPC 1: Hey, look! There is an explosion!", yet they both can be implemented independently of each other because the articulation of neither of them requires the full avilability of the other. A writer doesn't require an actual, functioning explosion to be able to mention that there is an explosion, and a VFX artist doesn't require an NPC's description of the explosion's narrative implications in order to be able to implement an explosive impact.

And because of this nature of high modularity during the course of game development, a game's underlying software framework is almost always being modeled under the principles of object-oriented programming. Every "thing" inside a videogame is essentially an object, each of which is a state machine operating on its own (as a standalone system). When combined with one another via loose chains of causality, these objects give rise to all sorts of interesting phenomena based upon their mutual interactions.

However, the object-oriented approach also creates plenty of rooms for countless bugs and glitches, which may arise from the fact that a state machine's inner workings heavily depend on the exact timing of when something happens (which means the order of input values must be precise), as well as that there are multitudes of encapsulated bodies of state existing in a concurrent fashion, whose actions may contradict with each other (e.g. Conservation of energy being violated due to two explosions spawning out of a single bomb because of bad timing, etc). One might be able to prevent such scenarios by introducing some kind of buffer to the overall decision-making process by means of message-passing, queueing, and so forth, yet these methodologies add additional layers of complexity to the architecture.

A neat solution to this is to switch one's programming paradigm to an entirely different one. Take functional programming, for example, in which modifiable states are almost completely excluded from the computing environment's data management scheme.

Inside a purely functional framework, any changes in the state of the application simply undergo the process of being "appended" on top of the state's history (similar to how append-only databases work, such as a blockchain), which nicely solves the problem of race conditions. Since the system never tampers with existing state objects (which are, in a functional programming language, nothing more than function calls sitting inside the application's stack memory), external references which are still pointing to past instances of the state do not have to worry about their procedures making an unexpected turn due to sudden in-between data modifications.

One of the biggest challenges in the adoption of a declarative programming paradigm in game development is the conceptualization of time. The exclusion of the concept of time in a non-imperative language such as LISP, for instance, is both a blessing and a source of confusion. When we are making a game, we are essentially creating a virtual world which has its own timeline. As time passes by, various events happen inside the game's own environment at designated points in time, based upon their own time-dependent schedules. Such a temporal aspect of gameplay is what typically leads engineers to simply fall back to imperative programming when developing the core mechanics of the game, even if they may be great advocates of declarative syntax when implementing modules that are time-independent (e.g. interpretation of data, procedural generation, etc). However, it is my personal conviction that such a multi-paradigm approach is not necessarily the best solution.

In an imperative programming language such as Java, one can easily implement time-related gameplay mechanics by creating an Actor object, letting it have a queue of pending actions (e.g. represented as an array of tuples, each of which is made out of the expected time of occurrence and a function body that must be executed when the time is reached, etc), and then updating this queue whenever the Actor's update-function gets called at each frame of the game loop. This way of implementation, while it is highly intuitive and handy, often leads to a wide spectrum of bugs which may be too subtle to even find out before releasing the final product. The existence of tens or even hundreds of such time-dependent queues, all potentially interacting with one another in real time, is prone to give birth to countless unimaginable scenarios due to race conditions, co-occurrence of mutually contradictory events, and many other ensuing complexities.

Functional programming comes to our rescue when dealing with such difficulties. Since it avoids modifiable states as much as possible, it nicely prevents us from having to worry about our sources of computation (e.g. variables) unexpectedly being corrupted in the middle of computational processes. One might argue that the principle of encapsulation circumvents such a concern, yet it should be noted that having to decide which pieces of data should be public and which of them should be private is in itself a cumbersome and error-prone process.

If only we can represent gameplay in terms of a cascade of function calls instead of a group of independent objects, wouldn't it be great? That way, we will have the advantage of keeping everything in the game application as part of one large hierarchy of procedures, each of which only has access to its local state (e.g. variables that are either passed in as its function parameters or are locally declared) and nothing else. This means that all dependencies will have to be injected by means of arguments, which inevitably turns the overall syntax to be a bit verbose, yet nevertheless gets rid of any chance of interference which may otherwise be exerted to/from outside entities.

Let us start with a simple game loop. Any real-time game engine, as far as common sense goes, contains at least one "update" procedure which runs itself on a periodic basis. A typical object-oriented way of implementing it goes like this:

class Game
{
    private State state;

    Game()
    {
        state = new State();
        Thread.start(updateLoop);
    }

    void updateLoop()
    {
        while (true)
        {
            state.update();
            Thread.waitForNextFrame();
        }
    }
}
new Game();        

It is conventional of an OOP-centered programming language, such as Java or C#, to start embodying a game application by first making a class that represents the game as a whole. Inside this "home class", where everything related to the game is supposed to begin its life, we create the game's state object and then run a thread which periodically updates it on a per-frame basis. This is a pretty neat way of running the game, except that here we are already introducing quite a degree of complexity to the whole system despite not having done anything substantial yet. The "Game" class in the above example has its own constructor method, an "updateLoop" method which runs within its own thread, as well as an internal state object which requires extra care for encapsulation so as to only let it be modified from within the update loop and nowhere else. The "updateLoop" method's internal "while" loop must make sure to execute its internal procedures in the right order, while also making sure that their execution can be carried out safely along with things that are happening in other threads (e.g. networking thread, rendering thread, etc). Furthermore, the instantiation of the "Game" class must be done in the right order (i.e. after all of the external systems to which it depends have been initialized, yet before systems which depend on it are yet to be initialized). The peril of object-oriented programming is that it has a tendency of giving birth to a complex web of interdependencies, no matter how much we try to simplify our system.

A purely functional equivalent of the game loop system, on the other hand, could be written as below (in LISP).

(defun update-loop (state)
    (wait-for-next-frame)
    (update-loop (update-state state)))        

As you can see, there is no such thing as a class here. The entire game loop is just a single function call (namely, "update-loop"), which calls itself at the beginning of each frame by means of tail recursion. The game's state object is simply a parameter which repeatedly gets passed into the update-loop function as the only dependency, and by this, we can guarantee that the update loop is a purely functional system which does not interact with anything outside of its body. The "(update-state state)" function call returns the updated version of the current game state, and its definition is shown below.

(defun update-state (state
    (make-state (update-actors (get-actors state)))))        

The "make-state" function, as you may have already guessed, creates a newer instance of the game's state and uses it as the input state of the next "update-loop" call instead of just modifying the existing state object. The reason behind this is that we want to prevent any potential race condition which may occur if other systems happen to be accessing/modifying the same exact instance. The "update-actors" function, just like the "update-state" function, returns the updated version of the current state of the game, but only the portion which pertains to its collection of actors (aka "characters", "sprites", or "agents") and nothing else.

(defun update-actors (actors
    (cons (update-actor (car actor)) (update-actors (cdr actors)))))        

The chain of "cons" nodes, as shown above, is more or less a LISP construct which may not apply to other languages. The overall idea, however, applies quite universally. Every time we update the list of actors, we build a brand new list by cons-ing the newer instances of the actor objects in a recursive manner instead of just modifying the existing list.

This, again, is for the sake of preserving the entire history of state changes instead of tampering with the past remnants which may be still waiting to be visited by extraterrestrial beings (aka "external systems") whose present moment in time could have been delayed by as much as a few milliseconds, due to the nature of time dilation (special relativity) which oftentimes inadvertently gets simulated by the lack of perfect parallelism in modern computing devices.

The "update-actor" function checks to see if the "actor" argument it received is just the end of the list (i.e. nil). If so, it won't do anything. If not, it will proceed to search for the actor's own update function by means of "(get-actor-update-func actor)" and then execute it in order to get the updated version of the actor object. This newer instance of the actor, just like the aforementioned ones, is something that is completely separate from its past copy.

(defun update-actor (actor
    (cond ((= actor nil) nil)
        (else ((get-actor-update-func actor) actor)))))        

And in order to run the game as a whole, we must start the game's loop somewhere. This involves the creation of the initial state, as well as the manual invocation of the update loop based upon that initial state.

(update-loop (make-state initial-actors))        

But of course, the game itself consists of not just a list of actors but also many other things. This is not too complex a problem to solve, though. All we have to do is implement additional data types and their corresponding "get" and "update" functions, and then insert them into the game loop as additional function parameters.

(defun update-state (state
    (make-state
        (update-actors (get-actors state))
        (update-cells (get-cells state))
        (update-events (get-events state))
        (update-particleEffects (get-particleEffects state))
        (update-soundClips (get-soundClips state)))))        

One major advantage of using this purely functional, append-only approach to the implementation of a game loop is that, since we are preserving the history of the game's state instead of constantly overwriting it with more recent bits of data, the game's update functions can have full access to the state's past instances and therefore make decisions based upon the differential characteristics that can be derived by comparing the past and present (which means it opens up the gateway to the realization of first-order, second-order, and even higher order systems which often occur in physics/engineering and are represented in terms of differential equations). This is easily done by passing the copy of the state from the previous frame (aka "past instance") into the update loop as an additional argument.

defun update-loop (currState prevState
    (wait-for-next-frame)
    (update-loop (update-state currState prevState) currState))


(defun update-state (currState prevState)
    (make-state
        (update-actors
            (get-actors currState)
            (get-actors prevState))
        (update-cells
            (get-cells currState)
            (get-cells prevState))
        (update-events
            (get-events currState)
            (get-events prevState))
        (update-particleEffects
            (get-particleEffects currState)
            (get-particleEffects prevState))
        (update-soundClips
            (get-soundClips currState)
            (get-soundClips prevState))))


(defun update-actors (currActors prevActors)
    (cons
        (update-actor (car currActors) (car prevActors))
        (update-actors (cdr currActors) (cdr prevActors))))


(defun update-actor (currActor prevActor)
    (cond
        ((or (= currActor nil) (= prevActor nil))
            nil)
        (else
            ((get-actor-update-func currActor prevActor) currActor prevActor))))
...)
        

One of the specific use-cases of such a temporal stream of data lies on the area of kinematics. For a quick demonstration, let me first suppose that the "get-actor-update-func" function returns the "update-kinematic-actor" function if the type of "currActor" is equal to "kinematic". This means that, if the actor we are updating is of type "kinematic", the "update-kinematic-actor" function will be used update it. This function takes both the current and previous instances of the actor as its input parameters, and computes/updates the actor's current position based on the comparison of its two instances in time (which reveals its current velocity).

(setf actor-update-func-table () '
    ('static update-static-actor)
    ('kinematic update-kinematic-actor)
    ('dynamic update-dynamic-actor)
    ('abstract update-abstract-actor)
))


(defun get-actor-update-func (currActor prevActor)
    (get-actor-update-func-iter currActor actor-update-func-table))


(defun get-actor-update-func-iter (actor table)
    (cond
        ((= (caar table) (get-actor-type actor))
            (cdar table))
        (else
            (get-actor-update-func-iter actor (cdr table)))))


(defun update-kinematic-actor (currActor prevActor)
    (let ((currVelocity (- (get-position currActor) (get-position prevActor))))
        (make-kinematic-actor
            (+ (get-position currActor) (* currVelocity 0.8)))))


(defun make-kinematic-actor (position)
    '('kinematic position))(        

One might argue, "Well, why bother introducing such a bloated system, just to update the positions of the individual actors? Why not just let each actor have its own 'velocity' property, so that it can simply update its position at any moment in time base off of the explicitly specified velocity value?"

For a simple problem of kinematics, such a solution is sound indeed. It is when we start dealing with more complex, implicit kinds of problems that we seriously begin to face inevitable rise in complexity. Let us consider, for example, that each actor is not a kinematic point-mass but a self-conscious animal (i.e. living thing) which has its own set of memories, desires, feelings, metabolic states, and other biological processes whose causal relations are not necessarily instantaneous in time (as opposed to atomic events in Newtonian mechanics such as application of force or displacement of a particle), but rather prone to emit delayed influences upon points in time that are quite far apart from one another. The constructor of such an organic entity will have to look like this:

(defun make-animal-actor (physicalTraits mentalTraits physicalMemory mentalMemory
    '('animal physicalTraits mentalTraits physicalMemory mentalMemory)))        

"physicalTraits" and "mentalTraits" are both fixed lists corresponding to the intrinsic physical/mental characteristics of the animal, whose contents are not meant to be changed under usual circumstances. These two lists, therefore, can be said to be time-invariant. "physicalMemory" and "mentalMemory", one the other hand, indicate the most recently added elements of the two streams of data (which represent the history of the animal's physiological state and the history of the animal's psychological state, respectively) which continuously circulate their elements as time passes by in the form of a queueing system. At each update loop of the game, newer memory elements enter these streams via the animal's sensory organs (i.e. external stimuli), while memories that are sufficiently old get discarded becasue these streams cannot keep growing forever (unless the computer is endowed with infinite memory space). The animal makes decisions based on both its most recent memories as well as past memories that are extracted from its past self, and produces a newer copy of itself which corresponds to its future self.

(defun update-animal-actor (currActor prevActor
    (let ((physicalTraits (get-physical-traits currActor))
            (mentalTraits (get-mental-traits currActor))
            (currPhysicalMemory (get-physical-memory currActor))
            (prevPhysicalMemory (get-physical-memory prevActor))
            (currMentalMemory (get-mental-memory currActor))
            (prevMentalMemory (get-mental-memory prevActor)))
        (make-animal-actor
            physicalTraits
            mentalTraits
            (make-physical-memory currPhysicalMemory prevPhysicalMemory)
            (make-mental-memory currMentalMemory prevMentalMemory)))))        

The example shown here, however, only allows the animal's memory to refer to only 1 step (frame) back in time, which suppresses its ability to make long-term decisions based upon long-term memories. If we want to simulate realistic physiological/psychological phenomena, we will need streams of memory elements that are sufficiently long so as to allow each animal to look up not only its most and second most memories, but also memories that were created minutes ago, hours ago, days ago, or even months ago.

The realization of long-term memory streams can easily be done by adding additional references to the game's past, as shown below. "prevState2" refers to the past instance of the game's state that was made 2 steps back in time instead of just 1.

(defun update-loop (currState prevState prevState2
    (wait-for-next-frame)
    (update-loop (update-state currState prevState prevState2) currState prevState)))        

And if we want the game to be able to refer to up to 3 steps in time instead, we will need something like:

(defun update-loop (currState prevState prevState2 prevState3
    (wait-for-next-frame)
    (update-loop (update-state currState prevState prevState2 prevState3) currState prevState prevState2)))        

This, of course, starts to become too verbose as we keep elongating the game's memory stream. Therefore, a much more realistic implementation would be to represent the history of the game's state as a single list variable rather than a sequence of manually specified function arguments.

(defun update-loop (stateHistory
    (wait-for-next-frame)
    (update-loop (cons (update-state stateHistory) (without-last stateHistory)))))