# Serializing Mazes!

Last week we improved our game so that we could solve additional random mazes after the first. This week, we'll step away from the randomness and look at how we can serialize our mazes. This will allow us to have a consistent and repeatable game. It will also enable us to save the game state later.

We'll be using the Megaparsec library as part of this article. If you aren't familiar with that (or parsing in Haskell more generally), check out our Parsing Series!

## A Serialized Representation

The serialized representation of our maze doesn't need to be human readable. We aren't trying to create an ASCII art style representation. That said, it would be nice if it bore some semblance to the actual layout. There are a couple properties we'll aim for.

First, it would be good to have one character represent one cell in our maze. This dramatically simplifies any logic we'll use for serializing back and forth. Second, we should layout the cell characters in a way that matches the maze's appearance. So for instance, the top left cell should be the first character in the first row of our string. Then, each row should appear on a separate line. This will make it easier to avoid silly errors when coming up with test cases.

So how can we serialize a single cell? We could observe that for each cell, we have sixteen possible states. There are 4 sides, and each side is either a wall or it is open. This suggests a hexadecimal representation.

Let's think of the four directions as being 4 bits, where if there is a wall, the bit is set to 1, and if it is open, the bit is set to 0. We'll order the bits as up-right-down-left, as we have in a couple other areas of our code. So we have the following example configurations:

1. An open cell with no walls around it is `0`.
2. A totally surrounded cell is `1111 = F`.
3. A cell with walls on its top and bottom would be `1010 = A`.
4. A cell with walls on its left and right would be `0101 = 5`.

With that in mind, we can create a small 5x5 test maze with the following representation:

``````98CDF
1041C
34775
90AA4
32EB6``````

And this ought to look like so:

This serialization pattern lends itself to a couple helper functions we'll use later. The first, `charToBoundsSet`, will take a character and give us four booleans. These represent the presence of a wall in each direction. First, we convert the character to the hex integer. Then we use patterns about hex numbers and where the bits lie. For instance, the first bit is only set if the number is at least 8. The last bit is only set for odd numbers. This gives us the following:

``````charToBoundsSet :: Char -> (Bool, Bool, Bool, Bool)
charToBoundsSet c =
( num > 7,
, num `mod` 8 > 3
, num `mod` 4 > 1
, num `mod` 2 > 0
)``````

Then, we also want to go backwards. We want to take a `CellBoundaries` item and convert it to the proper character. We'll look at each direction. If it's an `AdjacentCell`, it contributes nothing to the final `Int` value. But otherwise, it contributes the hex digit value for its place. We add these up and convert to a char with `intToDigit`:

``````cellToChar :: CellBoundaries -> Char
cellToChar bounds =
let top = case upBoundary bounds of
(AdjacentCell _) -> 0
_ -> 8
let right = case rightBoundary bounds of
(AdjacentCell _) -> 0
_ -> 4
let down = case downBoundary bounds of
(AdjacentCell _) -> 0
_ -> 2
let left = case leftBoundary bounds of
(AdjacentCell _) -> 0
_ -> 1
in toUpper \$ intToDigit (top + right + down + bottom)``````

We'll use both of these functions in the next couple parts.

## Serializing a Maze

Let's move on now to determining how we can take a maze and represent it as `Text`. For this part, let's first apply a type synonym on our maze type:

``````type Maze = Map.Map Location CellBoundaries

dumpMaze :: Maze -> Text
dumpMaze = ...``````

First, let's imagine we have a single row worth of locations. We can convert that row to a string easily using our helper function from above:

``````dumpMaze = …
where
rowToString :: [(Location, CellBoundaries)] -> String
rowToString = map (cellToChar . snd)``````

Now we'd like to take our maze map and group it into the different rows. The `groupBy` function seems appropriate. It groups elements of a list based on some predicate. We'd like to take a predicate that checks if the rows of two elements match. Then we'll apply that against the `toList` representation of our map:

``````rowsMatch :: (Location, CellBoundaries) -> (Location, CellBoundaries) -> Bool
rowsMatch ((_, y1), _) ((_, y2), _) = y1 == y2``````

We have a problem though because `groupBy` only works when the elements are next to each other in the list. The `Map.toList` function will give us a column-major ordering. We can fix this by first creating a transposed version of our map:

``````dumpMaze maze = …
where
transposedMap :: Maze
transposedMap = Map.mapKeys (\(x, y) -> (y, x)) maze``````

Now we can go ahead and group our cells by row:

``````dumpMaze maze = …
where
transposedMap = …

cellsByRow :: [[(Location, CellBoundaries)]]
cellsByRow = groupBy (\((r1, _), _) ((r2, _), _) -> r1 == r2)
(Map.toList transposedMap)``````

And now we can complete our serialization function! We get the string for each row, and combine them with `unlines` and then `pack` into a `Text`.

``````dumpMaze maze = pack \$ (unlines . reverse) (rowToString <\$> cellsByRow)
where
transposedMap = …

cellsByRow = …

rowToString = ...``````

As a last trick, note we `reverse` the order of the rows. This way, we get that the top row appears first, rather than the row corresponding to `y = 0`.

## Parsing a Maze

Now that we can dump our maze into a string, we also want to be able to go backwards. We should be able to take a properly formatted string and turn it into our `Maze` type. We'll do this using the `Megaparsec` library, as we discussed in part 4 of our series on parsing in Haskell. So we'll create a function in the `Parsec` monad that will take the dimensions of the maze as an input:

``````import qualified Text.Megaparsec as M

mazeParser :: (Int, Int) -> M.Parsec Void Text Maze
mazeParser (numRows, numColumns) = ...``````

We want to parse the input into a format that will match each character up with its location in the `(x,y)` coordinate space of the grid. This means parsing one row at a time, and passing in a counter argument. To make the counter match with the desired row, we'll use a descending list comprehension like so:

``````mazeParser (numRows, numColumns = do
rows <- forM [(numRows - 1), (numRows - 2)..0] \$ \i -> do
...``````

For each row, we'll parse the individual characters using `M.hexDigit` and match them up with a column index:

``````mazeParser (numRows, numColumns = do
rows <- forM [0..(numRows - 1)] \$ \i -> do
(columns :: [(Int, Char)]) <-
forM [0..(numColumns - 1)] \$ \j -> do
c <- M.hexDigitChar
return (j, c)
...``````

We conclude the parsing of a row by reading the newline character. Then we make the indices match the coordinates in discrete (x,y) space. Remember, the "column" should be the first item in our location.

``````mazeParser (numRows, numColumns = do
(rows :: [[(Location, Char)]]) <-
forM [0..(numRows - 1)] \$ \i -> do
columns <- forM [0..(numColumns - 1)] \$ \j -> do
c <- M.hexDigitChar
return (j, c)
M.newline
return \$ map (\(col, char) -> ((col, i), char)) columns
...``````

Now we'll need a function to convert one of these `Location, Char` pairs into `CellBoundaries`. For the most part, we just want to apply our `charToBoundsSet` function and get the boolean values. Remember these tell us if walls are present or not:

``````mazeParser (numRows, numColumns = do
rows <- …
where
cellSpecToBounds :: (Location, Char) -> (Location, CellBoundaries)
cellSpecToBounds (loc@(x, y), c) =
let (topIsWall, rightIsWall, bottomIsWall, leftIsWall) =
charToBoundsSet c
...``````

Now it's a matter of applying a case by case basis in each direction. We just need a little logic to determine, in the `True` case, if it should be a `Wall` or a `WorldBoundary`. Here's the implementation:

``````cellSpecToBounds :: (Location, Char) -> (Location, CellBoundaries)
cellSpecToBounds (loc@(x, y), c) =
let (topIsWall, rightIsWall, bottomIsWall, leftIsWall) =
charToBoundsSet c
topCell = if topIsWall
then if y + 1 == numRows
then WorldBoundary
else Wall
else (AdjacentCell (x, y + 1))
rightCell = if rightIsWall
then if x + 1 == numColumns
then WorldBoundary
else Wall
else (AdjacentCell (x + 1, y))
bottomCell = if bottomIsWall
then if y == 0
then WorldBoundary
else Wall
else (AdjacentCell (x, y - 1))
leftCell = if leftIsWall
then if x == 0
then WorldBoundary
else Wall
else (AdjacentCell (x - 1, y))
in  (loc, CellBoundaries topCell rightCell bottomCell leftCell)``````

And now we can complete our parsing function by applying this helper over all our rows!

``````mazeParser (numRows, numColumns = do
(rows :: [[(Location, Char)]]) <-
forM [0..(numRows - 1)] \$ \i -> do
columns <- forM [0..(numColumns - 1)] \$ \j -> do
c <- M.hexDigitChar
return (j, c)
M.newline
return \$ map (\(col, char) -> ((col, i), char)) columns
return \$ Map.fromList (cellSpecToBounds <\$> (concat rows))
where
cellSpecToBounds = ...``````

## Conclusion

This wraps up our latest part on serializing maze definitions. The next couple parts will still be more code-focused. We'll look at ways to improve our data structures and an alternate way of generating random mazes. But after those, we'll get back to adding some new game features, such as wandering enemies and combat!

To learn more about serialization, you should read our series on parsing. You can also download our Production Checklist for more ideas!