Wednesday, June 24, 2015

A Lunar Lander Game in Clojure

Introduction
In a prior post, I spent a great deal of time talking about Predator-Prey systems, ordinary differential equations, and solving these equations in Clojure. In this post, I describe a recent project I did that uses the same ODE solver to do something much more fun - implement a physics-based lunar lander game.

Here are the rules and operations for the game:
  • To win, you must land the lander on the terrain with a rotation of 0 and an absolute vertical velocity less than 10 m/s.
  • To engage the lander's thruster, press the 'f' key or space bar.
  • To turn the lander, press the left and right arrow keys.
  • If you go off the edge of the screen, land too fast, or land at an angle, you lose.
  • Press enter to start/restart the game.
The simplest solution is to just press the space bar when you get pretty close to the ground and carefully tap it so that you land very slowly. To give yourself a little challenge, turn the lander and give yourself some horizontal thrust. Then try to land it. I may later enhance the game with landing zones so you can't just land anywhere, but for now you can land anywhere you want.

Without further ado, here's the game:

If you are reading this blog via an aggregator that doesn't pick up the .js content, this is what the game looks like:

Implementation/Clojure Details
Now that you've had some fun trying the game out, here are a few high points. I won't go into a lot of detail in most of these sections since each could be a post in and of itself, but I will spend a good amount of time on multimethods, which were a big win in this application. If you want to build it, the entire project is available at https://github.com/markbastian/lander. Note that you will need to clone my numerics library for the Runge-Kutta solver and lein install it.

Platform Compatibility
Clojure 1.7 (Currently RC2) has the new cljc extension, which makes cross-compiling Clojure and ClojureScript a breeze. It is much easier and faster than the old cljx solution. I didn't make a JVM-based solution in parallel this time, but it would be pretty easy.

Game Physics
This was one of the easiest parts of the game since I just modeled the lander using differential equations and stepped forward using a Runge-Kutta integrator at each simulation step. The differential equations are:
\({dp\over dt} = v\)
\({dv\over dt} = -9.81 + thrust\)

Thrust is only applied when the user turns it on and the actual solution breaks the position (p) and velocity (v) vectors up into their x and y components.

And here's the code:
(defmethod sim :live [state-ref]
  (let [{:keys [theta thrust time state]} @state-ref
        t (.getTime (js/Date.))
        dt (* (- t time) 1E-3)
        dvx #(-> theta (* Math/PI) (/ -180) Math/sin (* thrust))
        dvy #(+ -9.81 (-> theta (* Math/PI) (/ -180) Math/cos (* thrust)))
        new-states (rk/rk-step [#(% 3) #(% 4) dvx dvy] state dt tableaus/classic-fourth-order)]
    (swap! state-ref into { :state new-states :time t })))

Terrain
Terrain is generated using the midpoint displacement method (source). Read about it here. Every new game procedurally generates a new terrain profile. There's a good chance I'll do a full on 3D terrain generation algorithm for a future blog post.

State
State is held in a single atom. As usual, when writing Clojure apps, I just modeled my problem as a data structure held by a Clojure concurrency primitive and everything else fell into place. The values tracked were game state (discussed later in the multimethods section), physical simulation state, time, theta (the lander's rotation), thrust (toggled on and off by user input), and terrain. All of this was easily managed in a single atom. One of the most beautiful things about Clojure is the simplicity of modeling your domain. When you stop thinking in objects and start thinking in terms of data and functions on data, life becomes much simpler.

Project Size
The project is ~200 LOC. Not too shabby for a complete game. There are certainly areas where I could have further reduced the amount of code, such as in the rendering section, but there comes a point where everything works fine and there's no need to mess with it further. Although I don't believe in brevity for brevity's sake, I do believe less code is easier to maintain and navigate than more code, so I always appreciate a concise solution.

Multimethods - The Big Win
In a computer game, you will have different stages of play, or game states (not to be confused with the physics state being maintained in the sim loop). For example, when you start a game there is a setup stage. Once everyone has joined there is a main game phase in which most play occurs. Finally, when someone wins there is usually some sort of congratulatory display or an option to play again. Each stage or game state entails a different set of rules regarding what input is received, what is rendered, and so on. However, each state has common functions such as receiving input and rendering. This is where Clojure multimethods come into play - they allow you to call the same overall game logic, but dispatch different functions based on some custom function.

In this game, the game is in one of four states:
  1. :before - The state of being before any game has been played.
  2. :live - A game is currently being played.
  3. :win - A game has been played and you won.
  4. :lose - A game has been played and you lost.
Depending on the state of the lander game, different logic is executed for the input, rendering, and simulation functions. For example, in :before, :win, and :lose state the game only allows you to start/restart a game, where in :live state the game accepts input to control the lander. In :live state the game renders the lander, terrain, and stats. In :before state the game only renders its directions.

The cool thing about all of this is that in Clojure I only have one main game loop (shown below). It repeatedly calls game-state, state, and render. At the same time, input is taken via the handle-keydown and handle-keyup methods. What happens when these methods are invoked depends on the current game state, with the right logic being dispatched via multimethods.
(defn ^:export init[canvas]
  (set!
    (.-onload js/window)
    (let [state (atom { :game-state :before })]
      (do
        (js/setInterval #(do
                          (gs/game-state state)
                          (sim/sim state)
                          (render/render state canvas)) 1)
        (set! (.-onkeydown js/document) (fn [e] (in/handle-keydown state e)))
        (set! (.-onkeyup js/document) (fn [e] (in/handle-keyup state e)))))))

Here is how it is done. I have 5 methods that I am invoking polymorphically based on the current game state (Note that they are shown together here, but are in separate files in the project):
;Watch the actual game state and transition to a new state based on the current physical state.
(defmulti game-state (fn [state] (@state :game-state)))

;Simulate the physics of the game based on the game state.
(defmulti sim (fn [state] (@state :game-state)))

;Draw to the screen based on the game state.
(defmulti render (fn [state _] (@state :game-state)))

;Handle input based on the game state.
(defmulti handle-keydown (fn [state _] (@state :game-state)))
(defmulti handle-keyup (fn [state _] (@state :game-state)))

The actual function dispatched when a defmulti is called depends on the dispatch function. In this case the dispatch function is (fn [state] (@state :game-state)). Now that I've defined the multimethods and their dispatch functions, I need to create methods that dispatch based on the right game state. Here's how it works for the render multimethod:
(defmulti render (fn [state _] (@state :game-state)))

(defmethod render :before [_ canvas] (intro-screen canvas))

(defmethod render :win [state canvas]
  (do
    (draw canvas @state)
    (win-screen canvas)))

(defmethod render :lose [state canvas]
  (do
    (draw canvas @state)
    (lose-screen canvas)))

(defmethod render :live [state canvas] (draw canvas @state))

So, given the state of the game, different render methods are called based on the state of the game. The same is true for all of the other multimethods defined above. For example, the :live method for the sim multi method was shown earlier. When the game is not in a live state, it simply calls the method show below, which conveniently makes the lander stop wherever it was when the game ended.
(defmethod sim :default [state-ref] ())
I won't go through all of the methods I defined, but you should get the idea from what I've posted. Multimethods provide a very effective and powerful way to dynamically dispatch different behaviors based on a custom defined function.

Finally, I could have defined my multimethods in one common namespace and provided implementations in another. Had I chose to provide both HTML Canvas and Swing/Graphics2D versions of this application, I could have implemented a single game loop that performs all logic in terms of multimethods and defined implementations in separate namespaces. Depending on which version of the application I wanted to run I would require the corresponding namespaces.

Conclusion
In this post, I presented a lunar lander game written in Clojure along with some observations about the code. As with my other Clojure projects, I am impressed by how I can make a non-trivial application with such a small amount of code. Various aspects of Clojure contributed to this, but the thing that most impressed me with this particular application was the use of multimethods to easily transition between game states and manage which functions should be dispatched under what conditions.

Thursday, June 11, 2015

Differences between Null, Nil, nil, Some, and None

Introduction
During a recent code review, a coworker who had the good fortune of jumping straight from Java to Clojure was asking me a few questions about some Scala code she'd been asked to edit. The particular problem involved recursive accumulation of some list data and our conversation drifted towards some questions regarding the different-yet-similar-sounding terms in these JVM languages. Java, Scala, and Clojure together have Null, Nil, nil, Some, and None. Most of these are related in their respective languages to how exceptional behaviors are handled with respect to references and/or collections. Here I explain each of these from the perspective of their host languages and my opinion of the effectiveness of each solution.

Before diving in, let me be clear that null exists in all JVM languages, including Scala and Clojure. However, these and other more modern languages provide additional facilities for dealing with situations where Java would default to using null and/or throw NPEs.

Java
In Java, you may encounter null when using an uninitialized reference (the default value for all references is null), when attempting to get a collection element that doesn't exist, or when someone decides to return null from their function to indicate a bad result. Java has no special handling for null. If you try doing anything with a null value, you get a NullPointerException and all is lost.

Not only is trying to do something with null exceptionally bad, Java (pre 8) has no built-in mechanisms to help you out. You just do lots of null checking.

Here are some methods for dealing with null in Java:
  • Always check your references. Liberally spread if(foo != null){ /*Do stuff with foo here*/ } everywhere you don't have absolute control of your references and aren't absolutely sure foo is initialized.
  • Always initialize your references at declaration or (preferably) make them final. Effective Java Item #15 says "Minimize Mutability." I find it very hard to be effective when writing Java, but this is definitely a good tip. Whenever possible, make everything final with a meaningful (i.e. non-null) value.
  • Don't write your code in Java. There are some perfectly good alternatives (See below).
  • Use the new Optional class from Java 8. This is the similar to Scala's Option type so I won't say much here aside from saying that Scala had it first. There's a trend there.
Scala
Recognizing the evils of null and NullPointerExceptions, Scala designed a better way - the Option type. Rather than returning null when something goes bad, the Scala way is to return either Some value if the computation succeeded or None if it failed. Here is an example of how you might use Option types to model a random food grab into your refrigerator:
  /**
   * A really lame function that might return a random food.
   */
  def randomFood = math.random match {
    case x if x > 0.75 => Some("Ham")
    case x if x > 0.5 => Some("Cheese")
    case x if x > 0.25 => Some("Bacon")
    case _ => None
  }
If you made a call to randomFood you could then call isDefined or isEmpty on the result to see if a meaningful result was returned. If the result is meaningful you can then call get to retrieve the value stored in the Some. In reality, nobody ever does this because it isn't any better than performing a null check. The only time you might do this is when calling Scala from Java because Java doesn't understand Scala functions.

What people really do with Options is use the fact that Scala implicity converts them to Iterables to perform functional operations on them. You can use functions on Options like map, foreach, flatten, reduce, and so on. Here's an example:
val sandwich = Some("Bread") :: 
  ((0 until 10) map { _ => randomFood }).toList ::: 
  Some("Bread") :: Nil

//Prints something like List(Some(Bread), Some(Ham), Some(Ham), None, Some(Bacon), Some(Bacon), Some(Ham), None, Some(Ham), Some(Bacon), None, Some(Bread))
println(sandwich)

//Prints something like List(Bread, Ham, Ham, Bacon, Bacon, Ham, Ham, Bacon, Bread)
println(sandwich.flatten)
Scala also has Nil, which is the empty list. Nil is the odd man out in this post as it is a specific instance of an empty collection rather than a construct for handling exceptional behavior, especially with respect to null. Due to Scala's powerful type system and inferencing, the Scala compiler will figure out what kind of list you are working with as soon as you add some items to your list.
scala> val x = 1 :: 2 :: 3 :: Nil
x: List[Int] = List(1, 2, 3)

scala> Nil
res0: scala.collection.immutable.Nil.type = List()
As you can see in the last line, Nil can't infer a type when no elements of any type are provided. Sometimes using empty collections like this in Scala can cause problems in which the compiler can't infer the type information. In such cases, you can just declare the type when declaring the def or val (we don't use vars). Here's an example that illustrates the point:
scala> Some(4) map { x => x * x } getOrElse 0
res0: Int = 16

scala> Some(4.0) map { x => x * x } getOrElse 0
res1: AnyVal = 16.0

scala> None map { x => x * x } getOrElse 0
<console>:8: error: value * is not a member of Nothing
              None map { x => x * x } getOrElse 0
                                ^
scala> val n : Option[Double] = None
n: Option[Double] = None

scala> n map { x => x * x } getOrElse 0
res3: AnyVal = 0

scala> n map { x => x * x } getOrElse 0.0
res4: Double = 0.0
As can be seen from the example, using operations such as map and getOrElse are convenient ways to transform Optional types to desired outputs. At the same time, care must be taken to make sure type information isn't lost so that you get the expected result. Despite these potential pitfalls, Scala's ability to treat Options as Iterables makes dealing with them very convenient.

Overall, Option is a much better solution than dealing with frequent null checking.

Clojure
Being hosted on the JVM, Clojure's nil is identical to Java's null. However, how Clojure treats nil is very different from Java. Rather than exploding every time nil is used a la Java or adding special features to handle exceptional behavior a la Scala, Clojure has a few simple rules that make it easy to work with nil. First, in logical expressions nil logically evaluates to false (along with false itself). In Clojure we call this "truthiness" and it is awesome. Second, when dealing with collections nil is treated like an empty list. These simple rules result in a simple, elegant solution to the dreaded null problem and it also results in a lot less code. To illustrate, here's our random food grab function in Clojure:
(defn rand-food []
  (condp < (rand)
    0.75 "Ham"
    0.5 "Cheese"
    0.25 "Bacon"
    nil))
As you can see, I don't do anything special (No Some/None construct) and just return nil (which is null in Java). It is the simplest solution, which is what Clojure is all about. In Java, this solution would be error-prone since it is using null. Here's how it works in Clojure:
(let[food (take 10 (repeatedly rand-food))
     layers (filter identity food)]
  (conj (into ["Bread"] layers) "Bread"))
=> ["Bread" "Ham" "Bacon" "Cheese" "Ham" "Bacon" "Ham" "Bacon" "Bacon" "Ham" "Ham" "Bread"]
Here's another snippet of examples that show how Clojure deals with nil when it is placed in the position of a null argument or collection. Compare or in Clojure with getOrElse in Scala. Much simpler.
(reduce + (map #(* % %) [1 2 3])) ;A non-nil example
=> 14
(reduce + (map #(* % %) nil)) ;I can reduce into a nil collection
=> 0
(or nil 4) ;Compare to getOrElse in Scala
=> 4
(and nil 4) ;Both items must exist
=> nil
(conj nil 4) ;I can conjoin 4 to nil to create the list (4)
=> (4)
As with Scala, Clojure provides a better way to handle null than Java. In contrast to Scala, Clojure does not add any special classes to handle null. Rather, it uses slightly different rules so that nil has meaning in collection and logical operations. For more on nil in Clojure, read about "nil punning" here.

Hands down, I prefer Clojure's handling of nil to either Scala or Java's approach.

Conclusion
Null is a unavoidable fact of life. Sometimes things go wrong and the best answer is no answer. How this situation is dealt with depends very much on the language you are working in. Java, realizing that null is bad, throws lots of exceptions that you get to deal with, usually with lots of error checking. Scala provides a mechanism to return something (Some value) or nothing (None) that allows you to more easily deal with situations that might go bad. Clojure has a few rules for how to deal with nil, primarily the concepts of "truthiness" and treating nil like an empty list. The rules pretty much solve all your problems when it comes to nil.

These approaches shed light on the designs of these languages, especially the more recent ones. Scala is, in my opinion, a complicated language that solves many problems via additional mechanisms to deal with the problems inherited from Java. I still think it is a great language, but it does take a decidedly baroque approach to solving problems. Clojure, despite seeming otherworldly at first, is a truly simple language. The more I use it, the more impressed I am with its simple design and philosophy. Either way, I think you'll find either of these language's solutions to the null problem preferable to Java's.