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:
- An open cell with no walls around it is
0.
- A totally surrounded cell is
1111 = F.
- A cell with walls on its top and bottom would be
1010 = A.
- 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!