Writing a 2048 clone in elm

Go to comments

Several weeks ago, I, along with the rest of the internet, discovered 2048, a fascinating one player game based on powers of two. Although it has a simple premise, the game requires a complex set of carefully thought out non-linear strategies to win, in a way that makes it comparable to a Rubik’s Cube, or the two player game Go.

There are many interesting mathematical questions one could ask about the game, both trivial and non-trivial. For example:

  1. What is the least number of moves required to win?
  2. What is the lowest possible score when the game is won?
  3. What is the highest number of moves that can be carried out before a win?
  4. What is the lowest possible score when the game is lost?
  5. Is a win always guaranteed?

I intend to try to tackle some of these in another post.

For now, I have applied my new found love for functional programming and created a clone of 2048 in elm. Elm is a programming language based on Haskell that uses Functional Reactive Programming to enable the creation of interactive applications, while keeping the language functional.

Elm compiles to HTML, CSS and Javacript, and so is very easy to deploy — as a demonstration of this I have embedded the final product of this project below. Start a new game and give it a try!

I decided to write up the project to serve as a resource and a tutorial of sorts for those trying to get into FRP or elm. I am still learning about these topics myself, so if you notice anything that has been done in a suboptimal way do let me know. Also, this is the first time I have written a post like this of any significant length, so feedback with regards to that is also welcome.

The project is on GitHub. Feel free to submit pull requests if you want to fix any bugs, or indeed for any other appropriate reason.

Prerequisites and references

I expect you to at least have a working knowledge of functional programming, and preferably in the context of Haskell. If you do not, Learn You a Haskell for Great Good! can be read online and is an excellent beginner’s guide. If you are not comfortable with functors, monads, etc., you should still be able to follow this tutorial. Those concepts are not used in this project, and are not explicitly used in elm in general.

I don’t expect you to have used elm before. The general syntax in elm is very similar to that of Haskell, with a few key differences. Of importance is the fact that while in Haskell :: is the ‘has type of’ symbol, and : is the cons operator, in elm : is the ‘has type of’ symbol, and :: is the cons operator. Also, the function application operator in elm is <|, not $ as it is in Haskell. I will describe other differences as we encounter them. A useful syntax reference can be found here.

The main difference in programming style between elm and Haskell is that elm uses signals, which are values that change with time. I will explain how these work and how to use them in the next section.

A key feature of elm is that an elm file can be compiled to a component, which can be embedded into an HTML document, and can communicate with Javascipt via ports. We will use take advantage of this in our project, but it does not matter if you are unfamiliar with HTML and Javascript, as they are not the focus.

If you have installed cabal-install, elm can be installed with cabal install elm. Compiling elm files is as easy as using elm Main.elm to generate a file build/Main.html, which can be opened in a web browser.

About signals

Signals in elm are values that change with time. They are event-based, meaning changes in signals are discrete, and do not have to happen at regular intervals.

Note that here changes will not necessarily mean a change in the value held by the signal. For instance suppose a signal holds the value 2, and then an event occurs that makes its value 2. The value held by the signal has not changed, but an event has still been recorded by it.

Suppose we have a signal signal that holds the value "foo". We say that signal has type Signal String. After five seconds an event arrives on signal, changing its value to "bar".

Now suppose we have a function question that appends "?" to a string. We cannot apply question directly to signal because question takes values that are strings, and signal is a signal of strings. How then do we apply a function to a signal?

The answer is to use lift, a function provided by elm. lift takes a function of type a -> b and a signal of type Signal a, and returns a signal of type Signal b. This signal is what you might expect: for each event in the signal of type Signal a, the function of type a -> b is applied to the value of the signal after that event, and the result of this is made the value of a new event in the signal of type Signal b.

So suppose we define a signal signalQuestioned = lift question signal. We then have that the value held now by signalQuestioned is "foo?", and in five seconds an event will arrive on the signal that will change the value it holds to "bar?".

Elm provides symbolic operators to make this easier to read and type. lift question signal is equivalent to question <~ signal, read as “signal fed into question”. If we have a function that takes more than one parameter we can use ~ to feed a series of signals of the parameters into the function as follows: function <~ signal1 ~ signal2 ~ signal3. For more information on how this works, see here.

Definition of the game

The board on which 2048 is played is a 4 by 4 grid of tiles. Tiles can either be empty, or contain an integer number that is a power of two. The initial board contains two random tiles in random positions. Each of these tiles has a 90% probability of being a 2, and a 10% probability of being a 4.

At any time, the player has the option to slide all of the tiles in the grid in one of four directions: up, down, left or right. The tiles slide naturally as expected, filling empty tiles with tiles that contain numbers, but also have an additional behaviour. If there are two adjacent non-empty tiles (in the direction of the slide) that hold the same value, then those two tiles merge together, forming a new tile whose value is the sum of the original two. The new tile’s value is added to the score. If there are more than two adjacent non-empty tiles holding the same value, this pairing is prioritised to be between those most in the direction specified — so sliding a grid with a row \([2,2,2,8]\) to the left would result in \([4,2,8,0]\), whereas sliding it to the right would result in \([0,2,4,8]\).

After each slide, a new random tile (again being a 2 with 90% probability, and being a 4 with 10% probability) is placed in one of the remaining empty tile positions.

The game ends in one of two ways. If one of the tiles in the grid has the value 2048, then the game is won. If the grid is full of tiles, and no slides in any direction will alter the grid any further, then the game is lost. The win condition holds precedence over the loss condition.

To the text editor!

We’ve gone through some basic FRP concepts and have defined the game we’re going to make, and now it’s finally time to start coding.

A couple of utility functions

There are quite a few function in Haskell’s standard libraries that aren’t implemented in elm. Of these, there are two we are going to need to use. These functions aren’t specific enough to apply to just one part of the project, so we’ll create a file Utils.elm that defines them (.elm is the standard file extension for elm files).

We’ll start the file with a module definition:

-- Utils.elm
module Utils where

Note that every elm file must start this same way, and the name of the module must be identical to that of the file.

List index operator

Elm has no built in operator for extracting elements from a list by their index. We will define one ourselves, using elm’s case notation.

infixl 9 !
(!) : [a] -> Int -> a -- the nth element of a list
l ! n = case (l,n) of
    (l,0) -> head l
    ((x::xs),n) -> xs ! (n-1)

This should be easy to follow. The 0th element of a list is its head. The nth element of a list is the (n-1)th element of its tail.

Note that this is a little sloppy — we’d like to be able to throw errors for situations when for example an index is out of bounds, but this is beyond the scope of this tutorial. Fortunately, this implementation will satisfy the needs of our project.

List of lists transposition

The transpose of a list of lists ll is a list of lists llt defined as follows: if an element is in the ith place of the jth list in ll, then it is in the jth place of the ith list in llt.

For example, the transpose of

\[ \begin{array}{rcccl} [[ & 1, & 2, & 3 & ], \
[ & 4, & 5, & 6 & ], \
[ & 7, & 8, & 9 & ]] \
\end{array} \]

is equal to

\[ \begin{array}{rcccl} [[ & 1, & 4, & 7 & ], \
[ & 2, & 5, & 8 & ], \
[ & 3, & 6, & 9 & ]] \
\end{array} \]

You can view this as a reflection along the diagonal.

Again, although Haskell provides a transpose function, when using elm we will need to make one ourselves:

transpose : [[a]] -> [[a]] -- transposes a list of lists
transpose ll = case ll of
    ((x::xs)::xss) -> (x :: (map head xss)) :: transpose (xs :: (map tail xss))
    otherwise -> []

This is only slightly harder to understand than the list index operator — see if you can work it out. Again, this implementation ignores a lot of potentially error prone situations, but it will suffice for our needs. ### Input Model

When I refer to the input, I mean all of the information that causes the code to run differently each time. So for example input is not just limited to using the keyboard, but can also mean a source of random data.

Our first task is to model the input for the game. We create a new file InputModel.elm and define its module:

-- InputModel.elm
module InputModel where

We will need to make use of both keyboard input and a source of random numbers, so we import their respective libraries:

import Keyboard
import Random

There are three inputs in the game:

  1. The controls that the player changes, i.e. the direction for a slide.
  2. The state of the button to initiate a new game.
  3. Two pairs of two random floats, one for choosing a random tile value, and the other for choosing a random tile location. We need two pairs for the beginning of a new game, when we place two tiles.

First we define a new data type for the direction of a slide:

data Direction = Up | Down | Left | Right | None -- the direction to shift the grid

We need a way to store all of the input information in a single data structure. One of elm’s features is its implementation of records, which are essentially easily modifiable structures of data with labelled fields. We use the type keyword to define a new record type for the user controls:

type Controls = { -- define the user controls
    tilePushDirection: Direction  -- the direction the user wants to 
                                  -- slide the grid
  , newGameButtonPressed: Bool    -- whether the new game button is pressed
} 

We also define a new record type for all of the input:

type Input = { -- define the inputs that the game will depend upon:
    controls: Controls          -- the user controls
  , randomFloats: [Float]       -- a source of randomness
}

The syntax for defining record types is fairly self-explanatory, but for more information, see here.

Player Controls

We now need to define a signal that represents the direction that the user is choosing to represent. We want to be able to use both the arrow keys and the wasd keys, and luckily elm’s Keyboard library provides two signals that represent these keys: Keyboard.arrows and Keyboard.wasd. These functions return a signal of a record in the format {x: Int, y: Int} taking the obvious values: e.g. if the left arrow or a key is pressed, {x=-1,y=0}, or if the up arrow or w key is pressed, {x=0,y=1}, or if both are pressed, {x=-1,y=1}.

Making use of elm’s multi-way if syntax, we define a function to convert the values from these signals into a Direction, and then feed the signals themselves into that function. The result is a signal of the direction that the player is choosing:

playerDirection : Signal Direction -- make a signal that is the direction 
                                 -- that the user has chosen. compatible
                                 -- with both the wasd and arrow keys
playerDirection = let toDirection ds  = 
                      if | ds == {x=0,y=1} -> Up
                         | ds == {x=0,y=-1} -> Down
                         | ds == {x=1,y=0} -> Right
                         | ds == {x=-1,y=0} -> Left
                         | otherwise -> None
    in merge (toDirection <~ Keyboard.arrows) (toDirection <~ Keyboard.wasd)

Here we’re making use of elm’s merge function that combines the events from two signals.

Randomness

We will now define our source of random floats. To do this, we will need a few new functions. The first is constant, which simply provides an unchanging signal of the value that it is applied to, so constant "foo" is a signal that has the value "foo" and does not change.

The second function we require is sampleOn, of type Signal a -> Signal b -> Signal b. sampleOn s t provides a signal which has a new event every time s has a new event, and the value of the signal after each event is the value of t at the time of that event.

The last function is provided by elm’s Random library: Random.floatList, of type Signal Int -> Signal [Float]. Random.floatList n provides a list of floats that changes every time n has an event. The length of the list is equal to the value held by n at each event.

Using these together, we can construct the signal we require:

randomFloats : Signal a -> Signal [Float] -- provide two random floats that 
                                          -- will be used for random events in 
                                          -- the game logic. changes every time
                                          -- the signal s changes
randomFloats s = Random.floatList <| sampleOn s <| constant 4

We take a constant signal that holds a value 4, and sample it every time an event occurs in s. Then we apply Random.floatlist to this signal, and thus obtain a signal holding a list of four floats, the values of which are randomised every time an event occurs on s. We leave this as a function of s because we want to be able to control when the floats change.

And that’s our input model!

Game Model

Next we need to define the game model, and create a few basic functions that we can use to manipulate it. We start a new file GameModel.elm in the usual way:

-- GameModel.elm
module GameModel where

We will need to use the list index operator and transpose function, so we shall import them from the Utils module:

import Utils ((!), transpose)

There are two types of objects in 2048:

  1. The tiles, which can be either empty or contain a number.
  2. The grid containing the tiles.

We define two new data types for these objects, representing a grid as a list of lists of tiles, where each list is a row of the grid:

data Tile = Number Int | Empty -- a tile can either contain an int, or be empty
data Grid = Grid [[Tile]] -- a grid is a list of lists of tiles

We will also need a type of data to indicate what stage the game is at. A game can be either in progress, at game over, or won:

data Progress = InProgress | GameOver | Won -- a game can be in progress, 
                                            -- at game over, or won

Finally we will need a data structure that represents the state of the game at any given point in time. The state of a game consists of the grid of tiles, the player’s score, and the progress of the game. We will use a record to contain this data:

type GameState = { -- defines the various properties of a game state:
    grid: Grid              -- the grid of tiles
  , score: Int              -- the score
  , gameProgress: Progress  -- the progress of the game (in progress, 
                            -- game over etc.)
}

Note that we are not importing anything from the InputModel module. It is important that the game model and the input model stay separate.

We’ll now define the size of the grid, i.e. the length of its sides. In the standard game of 2048, this number is 4.

gridSize : Int -- the length of the sides of the grid
gridSize = 4

We could not do this and instead just assume that the grids have four tiles to a row when writing the rest of our code, but doing things this way will make the project easier to maintain and modify. For more information, see this Stack Overflow question on the topic of magic numbers.

Grid Manipulation

We need to be able to get and set tiles in a grid. The function to read a tile at a location is easy:

readTile : (Int, Int) -> Grid -> Tile -- the tile at (i,j) in a grid
readTile (i, j) (Grid g) = (g ! j) ! i

The function to set a tile is slightly more complex, but you should be able to follow the code:

setTile : (Int, Int) -> Grid -> Tile -> Grid -- change the tile at (i,j) in 
                                             -- a grid
setTile (i, j) (Grid g) t = let 
        r = g ! j -- jth row
        nr = (take i r) ++ [t] ++ (drop (i+1) r) -- ith element changed in
                                                 -- jth row
    in Grid <| (take j g) ++ [nr] ++ (drop (j+1) g) -- new grid with modified 
                                                    -- jth row

We also need to convert between a tile and the number it represents. We will take an empty tile to represent 0.

tileToInt : Tile -> Int -- convert a tile to the int it represents
tileToInt t = case t of
    Number n -> n
    otherwise -> 0

intToTile : Int -> Tile -- convert an int to a tile representing it
intToTile n = case n of
    0 -> Empty
    otherwise -> Number n

It will be useful to be able to get a list of tiles and their coordinates from a grid:

tilesWithCoordinates : Grid -> [(Tile,Int,Int)] -- a list of the tiles in a grid 
                                                -- with their coordinates
tilesWithCoordinates (Grid g) = concat
                   <| zipWith (\j r -> map (\(t,i) -> (t,i,j)) r) 
                        [0..(gridSize-1)] 
                   <| map (\r -> zip r [0..(gridSize-1)]) 
                   <| g

It will also be useful to have a function for rotating the grid:

rotateGrid : Grid -> Grid -- rotate a grid clockwise by 90 degrees 
rotateGrid (Grid g) = Grid <| map reverse <| transpose g

To understand this function, consider how each of map reverse and transpose will act on the grid. map reverse reflects the grid across the vertical line through it, and transpose reflects the grid across the diagonal from the top left corner to the bottom right corner. Using the mathematical fact that the composition of two reflections is a rotation, we can see why this works. The rotation in this case happens to be that of a clockwise rotation by 90 degrees.

The initial gamestate

The initial gamestate is the state of the game immediately after the compiled elm has been loaded, before any input has occurred. In the case of 2048, this means an empty grid, a score of 0, and the game is in progress:

emptyGrid : Grid -- a grid of empty tiles
emptyGrid = Grid <| repeat gridSize <| repeat gridSize <| Empty

defaultGame : GameState -- the default starting game state:
defaultGame = { 
    grid = emptyGrid            -- an empty grid
  , score = 0                   -- initial score is zero
  , gameProgress = InProgress   -- the game is in progress
}

And with that we have described and provided functions for the entire game model of 2048.

Rendering

So far, ignoring the signals we described in the input model, everything we have done has been well within the scope of Haskell’s capabilities. In fact, you could argue that it would have been easier to do with Haskell, given the fact that elm is a fairly new language and so is not as developed as Haskell.

But now it is time to write the code that will render our game. The facility to do this is a primary function of elm.

We set up a new file Rendering.elm, and import all of the types for the gamestate that we are displaying from the GameModel module.

-- Rendering.elm
module Rendering where

import GameModel (
    Tile
  , Number
  , Empty
  , Grid
  , gridSize
  , tilesWithCoordinates
  , GameState
  , GameOver
  , Won
  )

Displaying a tile

First we’ll define a few constants that describe the appearance of the tiles:

tileSize : Float -- the width of a tile
tileSize = 106.25

tileMargin : Float -- the width of the gaps between tiles
tileMargin = 15

tileColor : Tile -> Color -- the color of a tile
tileColor tile = case tile of
                  Number 2 -> rgb 238 228 218
                  Number 4 -> rgb 237 224 200
                  Number 8 -> rgb 242 177 121
                  Number 16 -> rgb 245 149 99
                  Number 32 -> rgb 246 124 95
                  Number 64 -> rgb 246 94 59
                  Number 128 -> rgb 237 207 114
                  Number 256 -> rgb 237 204 97
                  Number 512 -> rgb 237 200 80
                  Number 1024 -> rgb 237 197 63
                  Number 2048 -> rgb 237 194 46
                  otherwise -> rgba 238 228 218 0.35 -- empty tile

tileTextColor : Tile -> Color -- the text color of a tile
tileTextColor tile = case tile of 
                  Number n -> if n >= 8 then (rgb 249 246 242) 
                                else (rgb 119 110 101)
                  otherwise -> black -- empty tile

tileTextSize : Tile -> Float -- the text size of a tile
tileTextSize tile = case tile of 
                  Number 128 -> 45
                  Number 256 -> 45
                  Number 512 -> 45
                  Number 1024 -> 35
                  Number 2048 -> 35
                  otherwise -> 55 -- empty tile

tileTextStyle : Tile -> Style -- the text style of a tile
tileTextStyle tile = {
                  typeface = [ "Helvetica Neue", "Arial", "sans-serif" ]
                , height = Just <| tileTextSize tile
                , color = tileTextColor tile
                , bold = True
                , italic = False
                , line = Nothing
                }

The rgb and rgba functions provide a Color, elm’s color type, for given levels of red, green, blue and, in the case of the latter, alpha level or opacity. The Style record is used by elm to describe the various styles of text that is being rendered.

(In case you’re wondering, I was feeling uncreative, and so these values come straight from the original 2048. Feel free to mix it up with colors and fonts of your own.)

There are two main objects used for rendering in elm: elements, and forms. Elements are easily stackable objects that can be rendered. Forms are irregular objects that do not stack easily. For a better explanation of the difference between the two, see here.

We need a function that will take a tile and return an element that is the tile rendered. A tile consists of:

  1. A square colored background.
  2. If the tile is not empty, a number that displays its value.

Elm provides a function collage that takes a width, a height, and a list of forms, and returns an element composed of those forms. We use this function, along with several others like square, filled and centered whose functions should be obvious, to write a function that displays a tile (that is, converts a tile to an element):

displayTile : Tile -> Element -- display a tile
displayTile tile = let tileBackground = filled (tileColor tile) 
                                        <| square tileSize
                in case tile of 
                    Number n -> collage (round tileSize) (round tileSize) 
                       [ 
                         tileBackground -- the tile background
                       , toForm <| centered  -- and the number
                                <| style (tileTextStyle tile) 
                                <| toText <| show n
                       ]
                    Empty -> collage (round tileSize) (round tileSize) 
                       [ tileBackground ] -- just the background

Displaying a grid of tiles

We want to be able to display a positioned tile, where its position is based on its coordinates in the grid. Elm takes the origin to be at the center, so after a little bit of very basic geometry we can come up with the following function:

displayTileAtCoordinates : (Tile, Int, Int) -> Form
displayTileAtCoordinates (t,i,j) = let position = 
                        (
                          (tileSize + tileMargin) * (toFloat i - (toFloat gridSize - 1)/2)
                        , (-1) * (tileSize + tileMargin) * (toFloat j - (toFloat gridSize - 1)/2)
                        )
                    in move position <| toForm <| displayTile t

We are returning a form so that we can use the result of this function with collage. Note that we multiply the y coordinate by minus one. This is because elm takes the positive direction on the y axis to be upwards, but I prefer to think with the positive direction downwards. This is simply a matter of personal preference.

We define the width of the grid based on tileWidth and tileMargin:

gridWidth : Float -- the width of the entire game grid
gridWidth = (toFloat gridSize) * tileSize + (1 + toFloat gridSize) * tileMargin

Now we define a function that displays a grid by using collage on a background square, and a list of the displayed tiles at their coordinates:

displayGrid : Grid -> Element -- display a grid
displayGrid g = let
                    gridBox = filled (rgb 187 173 160) -- the grid background
                                <| square gridWidth
                    tiles = map displayTileAtCoordinates 
                        <| tilesWithCoordinates g
    in collage (round gridWidth) (round gridWidth) ([gridBox] ++ tiles)

Displaying overlay messages

We will want to display messages over the top of our game for when the player has won, or when the game is at game over. The overlay messages will consist of a square colored background the size of the grid, and a centered message.

First we write a function to display a general overlay for a given text style, color, and message:

displayOverlay : Style -> Color -> String ->  Element -- display an overlay 
                                                      -- with a message
displayOverlay s c t = collage (round gridWidth) (round gridWidth)
    [ 
      filled c <| square gridWidth -- background
    , toForm <| centered <| style s <| toText t -- message
    ]

Now we’ll define the parameters for the game over and victory overlays. We are fortunate in that the text style for the game over overlay is the same as that of a 2 tile, and the text style for the victory overlay is the same as that of a 16 tile.

gameOverOverlayStyle : Style
gameOverOverlayStyle = tileTextStyle <| Number 2

wonOverlayStyle : Style
wonOverlayStyle = tileTextStyle <| Number 16

gameOverOverlayColor : Color
gameOverOverlayColor = rgba 238 228 218 0.73

wonOverlayColor : Color
wonOverlayColor = rgba 237 194 46 0.5

gameOverMessage : String
gameOverMessage = "Game over!"

wonMessage : String
wonMessage = "You won!"

Now we can build the overlays:

displayGameOverOverlay : Element -- display a game over overlay
displayGameOverOverlay = displayOverlay 
                            gameOverOverlayStyle
                            gameOverOverlayColor
                            gameOverMessage

displayWonOverlay : Element -- display a game won overlay
displayWonOverlay = displayOverlay 
                            wonOverlayStyle
                            wonOverlayColor
                            wonMessage

Finally we create a function to apply an overlay to a grid:

applyOverlay : Element -> Element -> Element
applyOverlay overlay grid = collage (round gridWidth) (round gridWidth)
        [
          toForm <| grid
        , toForm <| overlay
        ]

Displaying the entire gamestate

After all of the work that we put into the above sections, actually displaying the game is comparatively easy. All we have to do is display the grid, and then if necessary apply one of the two overlays to it.

display : GameState -> Element -- display a gamestate
display gameState = (case gameState.gameProgress of
                        GameOver -> applyOverlay displayGameOverOverlay
                        Won -> applyOverlay displayWonOverlay
                        otherwise -> id)
                    <| displayGrid gameState.grid

Note how we are taking advantage of first-class functions here. We are able to use the case notation to choose a function based on a set of conditions, and then apply that function to the displayed grid.

And that’s our rendering done.

Game Logic

So we’ve described the input for the game and the structure of the elements of the game, and we’ve told elm what are game looks like. Now it’s time to get to the core of the project and actually program how the game plays.

By now you should know how we start the new file Logic.elm:

-- Logic.elm
module Logic where

The list of things we’ll need to import from the input and game models is quite long.

import InputModel (
    Input
  , Direction
  , Up
  , Down
  , Left
  , Right
  , None
  )

import GameModel (
    GameState
  , Tile
  , Number
  , Empty
  , defaultGame
  , emptyGrid
  , gridSize
  , Grid
  , setTile
  , readTile
  , tileToInt
  , intToTile
  , tilesWithCoordinates
  , rotateGrid
  , InProgress
  , GameOver
  , Won
  )

Note again that, in a way that is similar to the separation of game model and input model, we are not allowing the logic and rendering components in our game to directly interact. This too is very important.

Tile sliding

How exactly does tile sliding in 2048 work? Suppose we want to slide a row of four tiles to the left. The first step is to remove any empty tiles. Then we have to find pairs of tiles that are next to each other, and merge them together. Finally we have to add a number of empty tiles to the end of the row, to ensure that it still has length four.

In order to facilitate the middle step, we will write a function groupedByTwo that takes a list, and returns a list of lists which either contain one element, if that element was not in a pair, or two element, if they were in a pair together. For example, groupedByTwo ["a","b","b","b","c","d","c","c","c","c"] = [["a"],["b","b"],["b"],["c"],["d"],["c","c"],["c","c"]]. Notice that we are prioritising the pairings towards the left of the list — [1,1,1] becomes [[1,1],[1]], and not [[1],[1,1]].

groupedByTwo : [a] -> [[a]] -- takes a list of values and 'slides' them to 
                                -- the left, joining in lists pairs of adjacent
                                -- identical values.
groupedByTwo l = case l of
    [x] -> [[x]]
    [x,y] -> if (x == y) then [[x,y]] else [[x],[y]]
    (x::y::xs) -> if (x == y) then ([x,y] :: (groupedByTwo xs)) 
                    else ([x] :: (groupedByTwo (y::xs)))
    otherwise -> []

This function should be simple enough to understand. In a list containing one element, there can be no pairs, so return a list with one list containing that element. If a list contains two elements and they are equal, then return a list with one list containing those elements, and if they are distinct then return a list of singleton lists of those elements. All other cases can be recursively defined in terms of these two.

(We would usually prefer to write a function of this sort without explicitly making use of recursion, but I feel that this function is “different” enough to warrant it. Again, I may have this wrong — let me know what you think.)

Now we will write the function that will slide a row of tiles represented as a list to the left. We want our function to actually return two values in a tuple. The first of these will be the new row of tiles, and the second will be the number of points gained in sliding the row.

slideRow : [Tile] -> ([Tile], Int) -- slides list of tiles to left,
                                   -- merging tiles where necessary,
                                   -- and returning a full list of 
                                   -- four tiles, and the number of
                                   -- points gained
slideRow r = let grouped = groupedByTwo <| filter (\t -> t /= Empty) r
    in (
        take gridSize 
        <| (map ( intToTile . sum . (map tileToInt)) grouped) 
            ++ repeat gridSize Empty
      , sum . (map tileToInt)
        <| concat 
        <| filter (\x -> length x > 1) grouped
    )

In the first line we filter out the empty tiles from the row and then apply the groupedByTwo function, calling the result grouped.

To compute the new row, we convert the tiles in grouped to integers, sum each of the lists in the integer version of grouped (remember that these lists either contain a single tile or a pair of tiles), and then convert these sums back to tiles. We must also add on enough empty tiles to the end of the list such that the list to return is a full row — the simplest way to do this is to add four empty tiles to the end of the list, and take the first four tiles of the list that results.

To compute the number of points gained, we first filter out those lists in grouped that do not represent pairs, and then sum the integer versions of the remaining tiles.

We now wish to be able to slide all the tiles in a grid in a certain direction. For sliding to the left, this is easy — we can just use slideRow on each of the rows. If we wish to slide in other directions however, we will have to make use of our rotateGrid function.

Suppose we want to slide the tiles downwards. First we rotate the grid 90 degrees clockwise (i.e. we apply rotateGrid once). We then continue as if we were sliding to the left. After we are done, we rotate the grid back to its original position. That is we rotate it by 90 degrees anticlockwise, or 270 degrees clockwise (i.e. we apply rotateGrid three times). The idea is similar for the other directions.

We implement this with the function slideGrid, taking a direction and a grid, and returning a tuple with a new grid, and the number of points gained.

slideGrid : Direction -> Grid -> (Grid, Int) -- slide all of the rows of a grid
                                             -- in a certain direction
slideGrid dir grid = let 
                rotatedGrid = (case dir of
                    Down  -> rotateGrid 
                    Right -> rotateGrid . rotateGrid 
                    Up    -> rotateGrid . rotateGrid . rotateGrid
                    otherwise -> id)
                    <| grid

                rowsWithScores = map slideRow
                              <| (\(Grid h) -> h)
                              <| rotatedGrid

                slidRotatedGrid = Grid <| map fst rowsWithScores
                scoreGained = sum <| map snd rowsWithScores

                slidGrid = (case dir of
                    Up  -> rotateGrid 
                    Right -> rotateGrid . rotateGrid 
                    Down    -> rotateGrid . rotateGrid . rotateGrid
                    otherwise -> id)
                    <| slidRotatedGrid

            in (slidGrid, scoreGained)

First we check that the direction to slide is not None. If it is, we return the original grid, and a point gain of 0. If not, we rotate the grid as necessary. Then we map slideRow to the rows of the grid. We separate out the scores gained from each row and sum these together to obtain a total score increase. We then “unrotate” the grid as necessary, and return the results.

Finally, we want a function that will apply the sliding specified by an input to a gamestate, both modifying the grid and increasing the score. We’ve done all the heavy lifting already, so with elm’s record modification syntax this is simple:

slideGameState : Input -> GameState -> GameState -- push the tiles in the grid 
                                            -- according to the direction in 
                                            -- the input
slideGameState input gameState = 
   let newGridScore = slideGrid input.controls.tilePushDirection gameState.grid
    in if (fst newGridScore == gameState.grid) then gameState else
        { gameState | 
            grid <- fst newGridScore
          , score <- gameState.score + snd newGridScore
        }

Win and loss conditions

The condition for a win is that a 2048 tile is present in the grid. Unfortunately, elm does not have an elem function, but it is easy to check this anyway:

gameWon : Grid -> Bool -- checks if a 2048 tile present in the grid
gameWon (Grid g) = 0 /= (length <| filter (\t -> t == Number 2048) <| concat g)

The loss condition is that sliding the grid in any direction results in no change. To test this, we attempt to slide the grid in all directions, and check whether the result is the same as the original grid in all cases. We must also check that the grid is not empty, as this will satisfy the prior condition, but an empty grid does not mean the game is lost.

gameLost : Grid -> Bool -- check if none of the rows or columns of a grid
                        -- can be slid in any direction
gameLost g = let
        up = fst <| slideGrid Up g
        down = fst <| slideGrid Down g
        left = fst <| slideGrid Left g
        right = fst <| slideGrid Right g
    in and 
        [
          g /= emptyGrid
        , up == down
        , down == left
        , left == right
        , right == g
        ]

We will also write two simple functions to set a gamestate to be either won or lost:

win : GameState -> GameState -- set a game to be won
win gameState = { gameState | gameProgress <- Won }

lose : GameState -> GameState -- set a game to be at game over
lose gameState = { gameState | gameProgress <- GameOver }

Random tile placement

At the beginning of a new game, and after each time the grid is slid, we want to be able to place down a new random tile. We define the probability that a new tile is a 2, or equivalently the probability that a new tile is not a 4:

tile2Probability : Float -- the probability that a new tile is a 2.
                         -- equivalently, the probability that a new 
                         -- tile is a 4
tile2Probability = 0.9

Next, an easy function that returns a tile with a random value based on the probability we just defined. Note that although this function is pure, the float that we give it will come from a random signal.

newTile : Float -> Tile -- based on a float that will be random, 
                        -- return a new tile
newTile x = if (x < tile2Probability) then (Number 2) else (Number 4)

In order to pick a random empty tile’s coordinates, we first need to know which tiles are empty:

emptyTiles : Grid -> [(Int, Int)] -- a list of the coordinates of the empty 
                                  -- tiles in a grid
emptyTiles g = map (\(_,i,j) -> (i,j)) 
                   <| filter (\(t,_,_) -> t == Empty) 
                   <| tilesWithCoordinates g

We can now choose at random one of these empty tiles.

newTileIndex : Float -> Grid -> Maybe (Int, Int) -- based on a float that will
                                        -- be random, return Just the 
                                        -- coordinates of an empty tile in a 
                                        -- grid if one exists, or Nothing if 
                                        -- there are none
newTileIndex x g = let emptyTileIndices = emptyTiles g
    in case emptyTileIndices of 
        [] -> Nothing
        otherwise -> Just 
                    <| emptyTileIndices ! 
                     (floor <| (toFloat <| length emptyTileIndices) * x)

We are using Maybe here because it may be that there are no empty tiles, in which case we return Nothing.

We can now write a function that will place a random tile in a random location in the grid:

placeRandomTile : Float -> Float -> GameState -> GameState -- place a random 
                                                -- tile into a random position
                                                -- in the grid
placeRandomTile float1 float2 gameState = 
    let tileIndex = newTileIndex float1 gameState.grid
    in if (tileIndex == Nothing) then gameState else
        { gameState |
            grid <- setTile 
                    (maybe (0,0) id <| tileIndex)
                    gameState.grid 
                    <| newTile float2
        }

First we check that there is an empty tile in the grid. If not, newTileIndex will have returned Nothing and we just return the gamestate unmodified. We then generate a random tile, and a random position, and place the tile in that position in the grid.

The maybe function used here is unique to elm. We are using it as a substitute for fromJust, that will evaluate to (0,0) if applied to Nothing. (Note that this will never be the case as we have already checked whether tileIndex == Nothing. Nevertheless, we still have to provide this fallback value.)

Finally we will define a new game, based on the random floats we take from the input. A new game is just the default game with two randomly placed tiles:

newGame : Input -> GameState -- generate a new game with two random 
                             -- starting tiles
newGame input = 
    placeRandomTile (input.randomFloats ! 0) (input.randomFloats ! 1)
 <| placeRandomTile (input.randomFloats ! 2) (input.randomFloats ! 3)
 <| defaultGame

Game stepping function

Now it’s time for the very core of the game. The game stepping function is an analogue to the game loop in imperative game programming. Every time the input changes, the game stepping function takes the new input and the previous gamestate, and returns a new gamestate. It is what will pull together all of the logic we have programmed above and actually make it into a game.

The game stepping function is one function, but we will break it down and look at its constituent parts.

We declare its type, and start its definition:

stepGame : Input -> GameState -> GameState -- game stepper that is called every
                                           -- time the input changes
stepGame input gameState =

All of our game stepping will be wrapped in a big if-else clause. The first thing we want to do when the input changes is check whether the new game button has been pressed. If it has, we return a gamestate that is a new game:

    if | input.controls.newGameButtonPressed -- if the new game button is 
                                             -- pressed
            -> newGame input                 -- then start a new game

Next, we check that a game is actually in progress, and if it is not we do nothing (i.e. we return the previous gamestate):

       | gameState.gameProgress /= InProgress -- else if the game is not
                                              -- in progress
            -> gameState                      -- then do nothing

If a game is in progress, we check to see whether the win or loss conditions have been met, and modify the gamestate appropriately if they have:

       | gameWon gameState.grid -- else if the grid contains a 2048 tile
            -> win gameState    -- then set the game to be won

       | gameLost gameState.grid -- else if the grid is completely fixed
            -> lose gameState    -- then set the game to be lost

Next we check if the user is specifying a direction to slide the grid. If they are we attempt to slide the grid in that direction. If this results in a grid that is different to the initial grid, we place down a single random tile. If not, we do nothing:

       | input.controls.tilePushDirection /= None -- else if the controls 
                                                  -- indicate a tile push
            -> let pushedState = slideGameState input gameState -- then try to push 
                                                -- the tiles in that direction
                in if (pushedState == gameState) then gameState 
                                -- check whether the grid has actually changed
                    else placeRandomTile 
                        (input.randomFloats ! 0) -- and if it has, place a new
                        (input.randomFloats ! 1) -- random tile
                        pushedState 

If none of the above conditions are true, we do nothing:

       | otherwise -> gameState -- if for some reason none of the above 
                                -- are true, do nothing

In summary, our entire game stepping function is as follows:

stepGame : Input -> GameState -> GameState -- game stepper that is called every
                                           -- time the input changes
stepGame input gameState = 
    if | input.controls.newGameButtonPressed -- if the new game button is 
                                             -- pressed
            -> newGame input                 -- then start a new game

       | gameState.gameProgress /= InProgress -- else if the game is not
                                              -- in progress
            -> gameState                      -- then do nothing

       | gameWon gameState.grid -- else if the grid contains a 2048 tile
            -> win gameState    -- then set the game to be won

       | gameLost gameState.grid -- else if the grid is completely fixed
            -> lose gameState    -- then set the game to be lost

       | input.controls.tilePushDirection /= None -- else if the controls
                                                  -- indicate a tile push
            -> let pushedState = slideGameState input gameState -- then try to push 
                                                -- the tiles in that direction
                in if (pushedState == gameState) then gameState 
                                -- check whether the grid has actually changed
                    else placeRandomTile 
                        (input.randomFloats ! 0) -- and if it has, place a new
                        (input.randomFloats ! 1) -- random tile
                        pushedState 

       | otherwise -> gameState -- if for some reason none of the above 
                                -- are true, do nothing

And that finishes up on the logic for the game.

Putting it all together

It’s time to bring together all of the separate modules for the game in a main file that will actually compile. We start the new file Elm2048.elm and import what we will need from our various modules:

-- Elm2048.elm
module Elm2048 where

import InputModel (Input, Controls, playerDirection, randomFloats)
import GameModel (defaultGame, GameState)
import Logic (stepGame)
import Rendering (display)

(The reason this module is called Elm2048 and not 2048elm, which would more closely align with the name of the project, is that elm prefers its modules to not start with numbers.)

Ports and Inputs

Way back at the beginning of this post, I mentioned that elm files can be embedded in HTML documents, and communicate with Javascript in that document using ports, which are essentially signals that are not restricted to the elm app. There are two types of ports —, outgoing, and incoming.

We are going to define two ports. One of these ports will be an outgoing port that will indicate the score in the game. We will use this to display the score on the website for the final product. We declare a port using the port keyword:

port score : Signal Int -- Outgoing score port

We want this signal to hold the current score. In the next section we will define a signal gameState that holds the gamestate of the game. To define score, we simply need to feed gameState into a function that extracts the score from a gamestate:

port score = (\x -> x.score) <~ gameState

The second port will be an incoming one, and will connect a new game button in our website to the game. Since the signal is defined outside our elm file, we only need to provide a type declaration for this port:

port newGameButton : Signal Bool -- Incoming new game button port

(In some ways we would prefer to have defined this port in the InputModel module. However, elm requires that ports be defined in the document that defines the main function.)

Next we will set up our controls and input signals:

controls = Controls <~ playerDirection ~ newGameButton -- set up controls
input =  Input <~ controls ~ (randomFloats controls) -- set up input

Note that we are using controls as a parameter of randomFloats to ensure that the random floats change each time the controls change.

Gamestate folding and display

Elm provides a function foldp that is a useful analogue of the foldl function for working on signals. Whereas foldl applies a function from left to right on a list by its elements, foldp applies a function from past to present on a signal by its events.

We will use foldp to put our game stepping function into effect. Like foldl, foldp requires an initial state — this is defaultGame from GameModel. The function that foldp will apply is the game stepping function stepGame from Logic. The signal that we will be folding on is input, which we just defined.

So we can define a signal that holds the gamestate of the game as follows:

gameState : Signal GameState
gameState = foldp stepGame defaultGame input -- fold the input into the game 
                                             -- state, starting with the 
                                             -- default game state

And finally we will feed the gamestate signal into the display function from Rendering to get our main function:

main = display <~ gameState -- display the game

Embedding in HTML

We are finished with the elm portion of this project, but there is still a little work to be done. We must create the HTML document that we will embed the game in, and we need to write some Javascript to bind it to the ports.

First we will use the elm compiler to compile our project into a component:

elm -m -o Elm2048.elm

This generates the file build/Elm2048.js. The -m flag tells the compiler to automatically compile all imported modules. The -o flag tells the compiler that we don’t want an HTML document, but instead a Javascript file that we can import into our HTML document as follows:

<script type="text/javascript" src="Elm2048.js"></script>

We also need to import the elm runtime, which can be found here.

<script type="text/javascript" src="elm-runtime.js"></script>

Since this tutorial isn’t focussed on HTML, we will not go into detail on the page’s formatting and styling. Our HTML document can be found here.

What is important is how the Javascript that embeds the elm component and interfaces with its ports works. We have in our document a div with the id gameBoard, as follows:

<div id="gameBoard"></div>

In a script we have written the following to embed the component in this div:

var gameBoardDiv = document.getElementById('gameBoard'); 
    // The placeholder div that will accept our elm component
var elm2048 = Elm.embed(Elm.Elm2048, gameBoardDiv, { newGameButton: false }); 
    // Set up our elm component in the game board div

Note that we have provided an initial value for the newGameButton port, false because it is not initially pressed. We do not need to provide an initial value for the score port, as it is outgoing.

Elm provides a javascript function subscribe that will carry out a given function every time an outgoing port receives an event. In our file we have another div with the id score. We can use subscribe on the score port to change the contents of the score div to the value of the score, every time this value changes:

elm2048.ports.score.subscribe(function (x) { 
    // Every time the score port in the elm component changes:
    document.getElementById('score').innerHTML=x; 
        // modify the score displayed in the score box
});

Another javascript function provided by elm is send. It is used to send an event to and change the value of an incoming port. We can use it to define a function to send a value to the newGameButton port:

function sendNewGame(a) { 
    // A function to send the boolean status of the new game 
    // button to the elm component via its newGameButton port.
    elm2048.ports.newGameButton.send(a);
}

We now can place a new game button where we want in our HTML document:

<div onMouseDown="sendNewGame(true)" onMouseUp="sendNewGame(false)">
     New Game
</div>

Done!

And that is our project complete! Take a look here to play the final product (or just scroll up).

I hope you learnt something about elm and functional reactive programming in general. Here are some ideas if you want to extend the game, listed in rough order of increasing challenge:

  1. Allow the player to continue playing after having won the game.
  2. Augment the appearance of the game by for example rounding the corners on the tiles.
  3. Store a player’s high score using cookies and display it next to the current game’s score.
  4. Animate the sliding and merging of the tiles.
  5. Implement an artificial intelligence that can attempt to win the game. (Hint: take a look at this Stack Overflow post).

Thanks for reading and be sure to leave a comment!


comments powered by Disqus