Modelling game states with Active Patterns


After a (long) hiatus from posting here I’ve decided to finally start up again. This week: F# and Active Patterns.

Game Logic in F#

I came across https://www.codingame.com/ recently – a great website that essentially has a set of “game challenges”. Your task for most of these games is to write the “message pump” (any Win32 developers will know what I’m talking about here) or “loop”. You take in a set of values that represent the game state, and then return a set of commands to affect the game. Because this sits on top of standard in / out, there are many languages supported, including F# 🙂

One of the things I like about these games is that many of the challenges show different aspects of domain modelling and problem solving using specific language features of F#. Active Patterns is just one such feature. It allows us to provide abstractions over arbitrary values and types, which in the context of games means that we can more easily reason about what is happening in the game.

Defining problems as a function

Let’s take one of the games as an example from the list of games: Chasm. In short, you have a bike driving on a bridge, which has a gap in it. You have to tell the bike: –

  • What speed to drive at
  • When to jump
  • When to slow down after jumping the gap

You can think of this as a pure function, which takes in the details of the bridge (length, gap size and landing size) as well as the current state of the bike (speed, position), and returns a single command, one of whether to slow down, speed up, jump or do nothing. Here’s a simple rules engine that determines the logic we should apply: –

  • If the bike is on the runway and going too slow then speed up
  • If the bike is on the runway and going too fast then slow down
  • If the bike is on the runway and the correct speed then do nothing
  • If the bike is in flight then do nothing
  • If the bike is just before the gap then jump
  • If the bike is after the gap then slow down

What I like about this is that we can break this problem down into a set of smaller problems which can then be composed together to solve the bigger problem at hand. This is classic divide-and-conquer stuff (but without any SOLID fluff getting in the way ;-)).

Active Patterns to the rescue

We can first create a couple of active patterns to gain a better understanding of the state of the bike in relationship to the bridge. Firstly, where is the bike, and secondly what speed is it going at: –

By doing this, we abstract away the implementation of “how” to reason about the speed of the bike, or where it is, into a few simple cases e.g. The bike is going too fast, the bike is approaching the gap etc. etc. In fact, having made those two patterns, we can now build our rules engine just by matching the bike’s state over both of them together: –

Notice how there’s a close affinity between the rules I wrote originally and the code above. We don’t need to think about “how” we’ve determined that we’re on the runway – it’s an artifact of the pattern match over the bike state (and the bridge state which I’ve omitted here).

All that’s needed is to write a simple parser for the input states into our record type and push that into a while loop that blocks until it receives the next game states, and returns the desired next command.

Summary

Dealing with a complex set of states can be difficult to reason about. Using Active Patterns is a great way to quickly and easily decompose problems into manageable chunks that can then be utilised together to build up ever higher levels of abstraction upon which you can easily reason about.

Advertisements

5 thoughts on “Modelling game states with Active Patterns

    1. Of course, APs are just a form of DU (albeit parameterised and partial ones are nice additions). I tend to think that they are particularly useful when you want to either re-use them in multiple places without having the overhead of creating a separate binding and / or only use them as a one off. I treat DUs as a proper value whereas APs to me are more about looking at some existing values through a different perspective.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s