I programmed a web application rendition of a board game called Sternhalma.

2021-01-17

programming projects elixir

I programmed a classic board game from my childhood that my grandma taught me how to play. It’s called Sternhalma, or better known as Chinese Checkers. With the game actually being invented in America, neither names make sense…

Now that this side project is coming to an end, I want to highlight some of the parts that I found interesting, and try to explain my approach to building this game.

You can find the code on GitHub here and here. The game is available for now at gameswithfriends.app, although I’m not sure how long I will keep it there, and the server it’s running on is, “not meant for production.”

Rules of the Game

I decided to build this game because it’s simple but still fun to play.

Skip this section if you already know the rules.

The goal is to be the first one to move all of your marbles to the triangle on the opposite side of the board. Two to six players are needed to play.

There are two ways to move your marbles:

1. Move directly to an empty, neighboring spot on the board.
2. Move to an empty, distant spot on the board by jumping one or more marbles. Changing directions while jumping another marble is not possible, however, once an empty cell is reached, the direction can change. Here’s some pictures of valid and invalid jumps to help illustrate.

Project Design Overview

I picked the Elixir programming language for this project. It’s a lot of fun to work with. I’ll try to demonstrate some of the cool features it has as I get into the code.

The project is split into two separate code repositories. That’s because I didn’t know what I wanted the end-product to be like when I began. Should it run on the web, or just be a console applciation? Could I make it work for both? – these were some questions I had initially.

The first repository can be considered a library. It exposes primitive functions that are needed to manage a game. My intention was that other programs can use this library as a dependency.

I tried to build the library in layers, with the goal that the public API is the only thing that users of the library need to know about.

I didn’t want the library to be too opinionated about how it should be used, which was an interesting goal to try and achieve.

Here are some examples of the what library provides:

• Data structure to represent a “game board”
• Ability to add marbles to the board
• Pathfinding
• Ability to determine if marbles are in a winning position

The second repository is a Phoenix web app. It’s what uses the aforementioned library to create a fully-featured game.

The web app provides a way for people to play the game, so it needs to do things like:

• Provide a user interface to the game board
• Handle user input as players take turns moving marbles
• Facilitate game lobbies
• Manage game state

I found Phoenix to be a good fit for this kind of turn-based game. LiveView is the main workhorse that powers user-interaction. It uses Web Sockets to send messages between browser and server. I found the client and server API to be very intuitive and user friendly.

Since it’s a multiplayer game, each action taken must be reflected for all connected players. Phoenix PubSub makes that possible, allowing processes to subscribe to and broadcast game state updates.

Elixir has abstractions for managing state, among other things, which actually stem from the technologies (Erlang / OTP) that it is built on top of. The Phoenix app is able to take advantage of GenServer and DynamicSupervisor processes to manage the game state.

The end-result is a web application that allows players to join a game by entering a code and their name. Once the game begins, they take turns to race their marbles to their “home” or “target” triangle. If a game is full, or already in progress, others can join as a spectator.

That’s the general overview of the project. In these next sections, I’ll share a few of the details and challenges that I found interesting about this project.

Game Board Representation

The game board could be thought of as a graph, but really it’s just a grid. However, it’s not a traditional grid, where each cell is four-sided.

The board is a hexagonal grid, and if it wasn’t for Amit’s insanely useful resources about them, I’d probably not have this game to talk about.

There are three modules at play when it comes to the representing the star-shaped board.

• Hex
• Cell
• Board

An Elixir module can be thought of as a “bag of functions” that have similar concerns, or operate on the same data type.

The Hex module defines a type that represents a grid position, according to Amit’s guide, as well as functions like neighbor/2, and neighbors/1 as seen in the snippets below.

@doc """
Return the next Hex coordinate based on a provided direction.

## Examples

iex> neighbor(Sternhalma.Hex.new({1, -4, 3}), :top_left)
%Sternhalma.Hex{x: 0, y: 3, z: -3}


"""
@spec neighbor(t(), direction()) :: t()
def neighbor(hex, :bottom_left), do: %Hex{x: hex.x, z: hex.z - 1, y: hex.y + 1}
def neighbor(hex, :bottom_right), do: %Hex{x: hex.x + 1, z: hex.z - 1, y: hex.y}
def neighbor(hex, :left), do: %Hex{x: hex.x - 1, z: hex.z, y: hex.y + 1}
def neighbor(hex, :right), do: %Hex{x: hex.x + 1, z: hex.z, y: hex.y - 1}
def neighbor(hex, :top_left), do: %Hex{x: hex.x - 1, z: hex.z + 1, y: hex.y}
def neighbor(hex, :top_right), do: %Hex{x: hex.x, z: hex.z + 1, y: hex.y - 1}

@doc """
Return the surrounding Hex coordinates.

## Examples

iex> neighbors(Sternhalma.Hex.new({1, -4, 3}))
[
top_left: %Sternhalma.Hex{x: 0, y: 3, z: -3},
top_right: %Sternhalma.Hex{x: 1, y: 2, z: -3},
left: %Sternhalma.Hex{x: 0, y: 4, z: -4},
right: %Sternhalma.Hex{x: 2, y: 2, z: -4},
bottom_left: %Sternhalma.Hex{x: 1, y: 4, z: -5},
bottom_right: %Sternhalma.Hex{x: 2, y: 3, z: -5}
]

"""
@spec neighbors(t()) :: list({direction(), t()})
def neighbors(hex) do
[:top_left, :top_right, :left, :right, :bottom_left, :bottom_right]
|> Enum.map(fn direction -> {direction, neighbor(hex, direction)} end)
end

The Cell module defines a couple functions and a struct for working with the marbles that can be at various spots on the board.

The Board module contains functions to do things like adding marbles to different triangles. In general, it’s the module that helps with manipulation of the game board.

At just under 150 LOC, the public API of the library is pretty small, with a good portion of the module being documentation.

Pathfinding

Since players can jump to distant spots on the board, pathfinding is one of the main things that the Sternhalma library takes care of.

I needed to choose a pathfinding algorithm to determine if a player’s selected move from point A to point B was possible. The algorithm also needed to spit back each spot on the board in between points A and B. That’s because applications may want to indicate the exact path that the marble travels.

There were a few pathfinding algorithms that I considered. Ultimately I decided to use Breadth First Search (BFS) to traverse the graph, stopping when either there are no more nodes to visit, or when the target node was discovered.

To be honest, I chose BFS because it was simplest to implement. Dijkstra’s algorithm didn’t seem very applicable in this case because the cost of each location on the board would always be the same. Since A-Star (A*) can be thought of as a variation of Dijkstra, I ruled that out as well.

Just because BFS is one of the easiest to implement does not mean I didn’t screw it up several times before getting it right.

My first rendition was something closer to Depth First Search, which proved to be problematic. DFS does not guarantee that the path it takes is the shortest. My code also had a bug that caused an infinite loop to happen in some cases.

This is a code snippet of my final, working version of BFS from the Pathfinding module.

@type path :: %{Cell.t() => :done | Cell.t()}
@type visited :: %{Hex.t() => true}

@spec bfs(Board.t(), Cell.t(), path(), visited(), list(Cell.t())) :: path()
defp bfs(_board, target, path, _visited, [current | _to_be_explored])
when current.position == target.position,
do: path

defp bfs(_board, _target, path, _visited, []), do: path

defp bfs(board, target, path, visited, [current | to_be_explored]) do
neighbors =
current.position
|> jumpable_neighbors(board)
|> remove_visited_cells(visited)

path =
Enum.reduce(neighbors, path, fn neighbor, path_acc ->
Map.put(path_acc, neighbor, current)
end)

visited =
Enum.reduce(neighbors, visited, fn neighbor, visited_acc ->
Map.put(visited_acc, neighbor.position, true)
end)

bfs(board, target, path, visited, to_be_explored ++ neighbors)
end

The code reads as follows:

• Start with the current position
• Find the “jumpable” neighbors. These are empty spots on the board that are exactly one occupied spot away from the current position. For example, B, C, and D are A‘s only jumpable neighbors.

• Filter out any of the neighbors that have already been visited.
• For each neighbor that will be visited, add a key-value entry to the path mapping. The mapping is used to backtrack in order to find the route from target back to the starting position after the function has completed.
• Mark every neighboring position as visited so that the function doesn’t get stuck in an infinite loop.
• Append the new neighbors to the end of the existing neighbors and repeat. Appending is important, as BFS relies on a queue to process nodes.

The first two function heads are matched in the “Base case” scenarios:

• The target location is found.
• There are no more neighbors to be explored.

The return value of the bfs/5 function is passed to backtrack/3, whose job is to trace back through the key-value mapping to reveal the path taken.

@spec backtrack(path(), nil | Cell.t() | :done, list(Cell.t())) :: list(Cell.t())
defp backtrack(_path, nil, _result), do: []
defp backtrack(_path, :done, result), do: result

defp backtrack(path, finish, result) do
current = Map.get(path, finish)
backtrack(path, current, [finish | result])
end

State Management

How to manage state is always fun to think about. The constraints that a language like Elixir incurs makes this topic all the more interesting.

The Sternhalma library, like any plain Elixir module, can be considered a “bag of functions”. It defines some data structures, and provides some functions that hopefully make building a game easier. There isn’t really any state involved here.

It’s up to the calling code to decide how it wants to handle state. As an example, take a look at the empty_board/0 function.

@doc """
Generate an empty board.
"""
@spec empty_board() :: Board.t()
defdelegate empty_board(), to: Board, as: :empty

It takes no parameters, and returns a Board struct. The result of this function can be passed around and chained together with other functions, resulting in a new state of the game board.

board_with_two_players =
Sternhalma.empty_board()
|> Sternhalma.setup_marbles("player 1")
|> Sternhalma.setup_marbles("player 2")

I found it really nice and simple to build the library like this, but passing the state around is not realistic in complex applications.

The web application, which players interact with to play the game, can take advantage of processes to help manage state. All Elixir code runs within processes in the Erlang Virtual Machine.

Check out Sophie DeBenedetto’s article to learn more about the Erlang VM, or the Elixir tutorial about processes if you’re interested in learning more.

For managing the game state, I’m using GenServer, a process that can be used to keep state, and provides a standard way to interact with it.

Games are identified by a code, provided by a player when they join. Each game has it’s very own GenServer process, called GameServer.

Inside the GameServer module, you will find functions like, join_game/2, leave_game/2, start_game/1, and move_marble/3. These functions make up the client API of the GameServer.

# ...

@doc """
Move from `start` cell to `finish` cell if possible.
See `BoardGames.EventHandlers.MoveMarble` for details of what is involved in this.
"""
@spec move_marble(String.t(), BoardLocation.t(), BoardLocation.t()) :: term()
def move_marble(game_id, start, finish) do
GenServer.call(via(game_id), {:move_marble, start, finish})
end

# ...

Each of these functions have a corresponding handle_* function, which executes on the “server” side – in the GameServer process itself.

It’s fair to think of these handle_* functions as state reducers. They respond to a message, and update their internal state accordingly.

# ...

def handle_call({:move_marble, start, finish}, _from, state) do
with {:ok, new_state} <- EventHandlers.MoveMarble.handle({start, finish}, state) do
{:reply, {:ok, new_state}, new_state}
else
{:error, {code, state}} ->
{:reply, {:error, code, state}, state}
end
end

# ...

In the snippet above, {:ok, new_state} or {:error, code, state} is what gets returned to the calling process. This is how processes communicate with each other - via message passing. In the successful branch of code, you can see a new copy of the game state being returned, along with an :ok status code.

Here’s the shape of new_state, to give you an idea of what kind of data the process is keeping track of.

@type t :: %GameState{
board: list(BoardLocation.t()),
id: binary(),
last_move: list(BoardLocation.t()),
marble_colors: map(),
marbles: list(Marble.t()),
players: list(String.t()),
connected_players: list(String.t()),
seconds_remaining: non_neg_integer(),
status: game_status(),
timer_ref: nil | reference(),
turn: nil | String.t(),
turn_timer_ref: nil | reference(),
winner: nil | String.t()
}

Every player in the game has their own LiveView process. User interactions in the browser are sent as events to the LiveView server process.

A LiveView processes has some state of its own – things that don’t need to be shared with other players in the game. An example is when a player moves their marble. It’s a two step process:

1. Click the marble to be moved.
2. Click the destination spot on the board.

Other players don’t need to know about the first step, so the state related to keeping track of the clicked marble can be tracked on the LiveView process.

As for state updates that do need to be shared, PubSub is used to broadcast game state updates to all of the subscribed LiveView processes.

The snippet below shows how the LiveView process calls GameServer.move_marble/3 when a spot on the board is clicked. The game state will then be broadcast if the move was valid.

def handle_event("board-cell-click", %{"x" => x, "y" => y, "z" => z}, socket)
when socket.assigns.start != nil do

# ...

message =
with {:ok, game} <- GameServer.move_marble(socket.assigns.game_id, start, board_location) do
broadcast_game_state_update!(socket.assigns.game_id, game)
nil
else
{:error, code, _state} ->
message_for_code(code)
end

{:noreply, assign(socket, start: nil, message: message)}
end

GameServer processes are started up as new games are created, and destroyed when there are no remaining LiveView processes connected to the game.

An interesting thing about GameServer is that it’s not spawned directly from a LiveView process. It’s actually spawned by another process, called GameSupervisor.

GameSupervisor is a special type of process called a Dynamic Supervisor. It’s job is to watch over it’s children. The GameSupervisor itself is created when the web application first starts up, so that other processes can use it to tell which children to watch over.

If a LiveView were to start a GameServer directly, that would mean that it would get destroyed if the player who was connected to the LiveView process were to disconnect, ending the game for all.

Animations and Visuals

Basic CSS and HTML were used to create the user interface for this app. The game became fancy the moment that I slapped an image of a dragon onto the game board, courtesy of Wikipedia.

Each marble, and each empty spot on the board are just HTML buttons. Different CSS classes are applied to DOM elements as the game state changes. I also made use of CSS variables for parts of the UI that are more dynamic, such as a marble color, rotation, left & right position, etc.

All of the UI rendering related code can be found in the SternhalmaView module, as well as the SternhalmaLive template file.

I wanted to try and make it so that playing the game online was close to the same experience of playing in real life.

In real life, players sit behind their home triangle, so in my game, I made it so that the board is rotated such that each player’s home triangle is always at the bottom of their screen. The amount of rotation needed for each player can be found based on how many total players are in the game.

@spec rotation(non_neg_integer()) :: non_neg_integer()
defp rotation(0), do: 180
defp rotation(1), do: 0
defp rotation(2), do: 240
defp rotation(3), do: 60
defp rotation(4), do: 120
defp rotation(5), do: 300
defp rotation(_player_index), do: 0

Such a simple function for such a nice feature!

Another small, but nice detail is displaying white or black text based on the background color that is behind it.

This isn’t the prettiest looking function, and I won’t pretend to know how to explain the formula it uses, but it can decide whether to use white or black text, based on a background color. I remembered that I had a bash script that does essentially the same thing, and copied from that.

@spec text_color(String.t()) :: String.t()
defp text_color(<<"#", hex_color::binary>>) do
with {:ok, <<red, green, blue>>} <- Base.decode16(hex_color, case: :mixed) do
if red * 0.299 + green * 0.587 + blue * 0.114 > 186 do
"#000000"
else
"#ffffff"
end
else
_ ->
# default to black
"#000000"
end
end

The most important animation that I wanted to include was the marble jumping across the board. I fear that I may have bent the rules of LiveView a little bit in order to make this feature possible. Each time a player selects a move, I store a list of each position from the start to the end.

As soon as a valid move is chosen, the GameServer sends a message to itself which recursively handles each position along the path, broadcasting state changes as it goes.

The subscribed LiveView processes receive the state updates on an interval, and render their views accordingly. This is how the animation is achieved, along with the help of transition: left 0.4s ease-in-out, bottom 0.4s ease-in-out;. It gives me pause because I know that LiveView is not meant for doing client-side animations.

The alternative was to make the animation happen client side. I couldn’t come up with a way to do it that didn’t involve some major changes and added complexity. In any case, what I came up with seemed to work well. This is one thing I would love to get some feedback about.

Documentation, Testing, and Typespecs

I put an emphasis on writing tests, documentation, and annotating my functions with typespecs.

Going the extra mile to add typespecs to my code was well worth it in my opinion. Though Elixir is a dynamically typed language, you can still do some static code analysis with a tool called Dialyzer. Dialyzer notified me of inconsistencies with my code that I would have otherwise missed.

In my opinion, code annotated with typespecs is much more readable as well. Typespecs were especially helpful as I refactored various parts of my application.

I relied heavily on testing while working on the Sternhalma library. The tests I wrote for the pathfinding module saved me lots of time. I added test cases for bugs and edge cases that I encountered along the way, and it gave me confidence that my code was valid as I refactored.

Documentation is a first-class citizen in Elixir. I love how easy it is to write and read documentation for modules and functions. I feel very comfortable writing Elixir code on an airplane because when I have questions, I simply pop open an interactive console, and read the docs for whatever module or function I am wondering about. No need for the internet most of the time.

Notice the “Examples” section in the screenshot above. That’s not just for user reference – those are doctests. That code is actually executed and checked against the result as part of the test suite. Maybe the only thing worse than no documentation is documentation that is wrong. I love tools Elixir offers to help prevent this.

Here’s an example function with typespecs, documentation, and one doctest from the Sternhalma library.

@doc """
Return {x, y} pixel coordinates for a given Hex coordinate.

## Examples

iex> to_pixel(Sternhalma.Hex.new({1, -4, 3}))
{8.267949192431123, 4.0}


"""
@spec to_pixel(Hex.t()) :: {number(), number()}
defdelegate to_pixel(position), to: Hex

Running the suite is quick and easy, and the ExUnit testing library is included by default in Elixir projects.

I did fail to write any tests for the web app ☹️.

How Did it Turn Out?

Personally, I’m happy with how the project has turned out – both from a code perspective, as well as the game itself.

I worked on a similar project a few months back, which almost worked, but was buggy and a little disappointing in the end. I like to think that I learned from those mistakes here. I haven’t discovered any serious bugs yet (knock on wood…)

One thing that I was trying to accomplish was to make it so that the web application code was not too coupled to the Sternhalma library. I’m not sure if I succeeded at this or not…

Of course there’s no way to eliminate the dependency to the library completely, but I thought that I would be in good shape by putting all references to the Sternhalma library into one module rather than having functions and data structures scattered throughout my entire web app.

That’s the purpose of the SternhalmaAdapter module. It’s a boundary between the external library and the web app.

The functions were easy to throw into the module, but eliminating the use of data types throughout the app was difficult. My solution was to sanitize, or morph the external data to a different representation that my web app could depend on.

Was this a helpful improvement? Was there a better way to achieve the decoupling that I was after? Does it actually mean that my library is too opinionated? These are questions I’m not sure about.

So far I’ve played the game with a few members of my family. The feedback I received is:

1. It’s not immediately apparent that you have to click on the spot on the board you want your marble to end up on. Some people tried to click each point along the path that they wanted to take.
2. 10 seconds is not enough time for a turn.
3. The game is harder to play on touch devices, because the screen will sometimes zoom in.

This was a lot of fun to build and to think about. That’s maybe the most important thing for a side project. Thanks for reading!