Encoding the labyrinth

Following up on my post on walking through the labyrinth, I wanted to experiment with some of the ideas I thought through further by actually coming up with some code. In this post, I tackle the relatively simple challenge of how to encode the maze. But I also discuss how we might test a potential walkthrough function.

Following up on my post on walking through the labyrinth, I wanted to experiment with some of the ideas I thought through further by actually coming up with some code. In this post, I tackle the relatively simple challenge of how to encode the maze. But I also discuss how we might test a potential walkthrough function.

Encoding tiles

In my last post I mentioned the need to come up with a way of representing tiles through code. There are several options but for simplicity’s sake, I will go with one letter per tile. We already established that there are only sixteen possible configurations for a square tile.

I could have simply numbered the tiles from 0-16, or rather in hex 0-f to keep each tile representation to one character. But, in this case, that would have been as arbitrary as assigning random letters. Instead I decided to use characters that I would consider as mnemonics.

With single character representations of a tile, we have a compact way of representing a maze but we also need to have a dictionary for any function that needs to intepret the maze to work from.

So a single tile maze could be represented with a (not much of a maze I know but we’ll come to that later) whereas a 4 x 4 maze could be represented with aaaaaaaaaaaaaaaa (also not much of a maze as it’s all open space).

Expected behaviour

As mentioned in the last post, we want a function which will walk through a maze and give us some information about how difficult it might be.

Which measures?

The measures we will look for are:

1. How much of the maze can we actually cover from the entry point
2. If the maze can actually be completed (only relevant if it has an exit)
3. Number of paths until the maze is complete
4. Distance to the exit or needed to cover every tile

Where completion is mentioned but the maze has no exit tile, let’s assume that the entrance needs to be returned to but only after every possible tile has been covered. This is because if the maze has no designated exit, we can only assume that the challenge for the user is to find some objects in the maze.

We want a function to give us numbers for each of these measures so let’s give them names.

1. coverage
2. completion
3. paths
4. distances

So any walkthrough function should be able to accept a maze representation (a string of characters), a designated entrance location, and an optional exit location. We also need to provide it with a dictionary of character to tile definitions, like the one displayed in tabular form above. In return, we want an object containing the four properties listed above: coverage, completion, paths and distance.

Using Mocha

Let’s build a test function that will check this for us. The test won’t pass because we haven’t built a walkthrough function yet but it will give us something to work towards.

To do this, let’s use the Mocha test suite with the library should.js. This allows for some nice reporting on how our tests are performing but also makes the code really easy to read, so you don’t have to be completely familiar with how these libraries work to understand it.

For example, to test a one-tile maze we can do this:

var should = require("should")

var dictionary = {
    "a": "0000",
    "b": "1111",
    "p": "1010",
    "q": "0101",
    "n": "1000",
    "e": "0100",
    "s": "0010",
    "w": "0001",
    "r": "1001",
    "t": "1100",
    "j": "0110",
    "l": "0011",
    "u": "0111",
    "c": "1011",
    "m": "1101",
    "d": "1110"
}

describe("Walkthrough function", () => {
    var walkthrough = require("./../walkthrough.js").walkthrough

    it("should ", function () {
        walkthrough("a", [1, 1], false, dictionary).should.equal({
            "coverage": 1,
            "completion": true,
            "paths": 1,
            "distance": 1
        })
    })
})

Hopefully, this is relatively self-explanatory. Firstly the library should is required. Then the dictionary is defined showing the meaning of each character in tile terms. Finally, the test itself describes what the expectation is – namely that the walkthrough function, given the values specified, should return an object with certain properties.

The example of a single tile maze may seem overly simple but it seems like a good edge case to begin with.

Next: passing the test

The next challenge will be writing a function that can pass this simple test and other tests we may come up with as we develop. I’ll save this for the next post on this topic.