Agree on a serial labyrinth format

[WilliamHPNielsen]

Continuing the discussion from #8, it would be good to agree on a standardized, serial format that represents a limnos-generated maze. This format is then the data that should be exchanged between the generation part of limnos and other parts of limnos such as visualisation and disk-writing and third-party consumers.

Currently we have the following ideas on the table:

1. A serialization of all the routes
2. A collection of all walls
3. Both?

Once that has been agreed on, we can move to the question of implementation. But draft PRs outlining ideas to aid the discussion are most welcome!

@jeppetrost @petterbejo

[jeppetrost]

One mildly non-human-friendly serialization: go through all possible wall-spaces, first by rows, then by columns and mark a bit if it is present. The first some bytes (two ints?) could tell the size of the maze. Something like the following completely untested code

from bitstring import Bits, BitArray

from limnos.types import *

def all_walls(n: int, m: int) -> Walls:
    """
    Helper function to generate all possible walls in the rectangle
    TODO: Consider _not_ writing the outer wall, but generate that on deseiralization
    """
    x0 = 0
    x1 = n
    y0 = 0
    y1 = m

    vert_walls: Walls = [((x, y), (x, y + 2))
                         for x in range(x0, x1 + 2, 2)
                         for y in range(y0, y1, 2)]
    horiz_walls: Walls = [((x, y), (x + 2, y))
                          for x in range(x0, x1, 2)
                          for y in range(y0, y1 + 2, 2)]

    return vert_walls + horiz_walls

def serialize_maze(maze: Maze, n: int, m: int) -> BitArray: 
    walls_as_bits = BitArray()
    walls_as_bits.append(uint=n,length=32)
    walls_as_bits.append(uint=m,length=32)

    walls_as_bits.append
    for wall in all_walls(n,m):
        if wall in maze[1]:
            walls_as_bits.append('0b1')
        else:
            walls_as_bits.append('0b0')
    return walls_as_bits

def deserialze_maze(maze: BitArray) -> Walls:
    n = maze[:32].uint
    m = maze[32:64].uint
    walls_in_maze: Walls = []
    possible_walls: Walls = all_walls(n,m)
    # Do various sanity checks here ...
    assert n % 2 == 1
    assert m % 2 == 1
    assert maze[64:].length == len(possible_walls)
    for b,w in zip(maze[64:], possible_walls):
        if b:
            walls_in_maze.append(w)

[WilliamHPNielsen]

@jeppetrost, that's a nice idea, thanks! I like that it is very memory-efficient, probably as efficient as it gets, right?

I do, however, also have some reservations. The main one being that I do not agree that the walls are all there is to a labyrinth. We might reasonably expected a visualization module to visualize the solution to the maze, but it is not reasonable that said module should solve the maze itself. I think limnos should at the very least provide a labyrinth (either as walls or equivalently paths) and the solution. Additionally, I have a hunch that the information about the path tree is relevant for determining the difficulty of the labyrinth (the deeper the tree, the more difficult the labyrinth) and could be nice to have too... but I haven't thought too hard about that yet.

My other reservation is somewhat minor, but related: the asymmetry in the signatures of deserialize_maze andserialize_maze is unsettling. I think it's fair to request that applying both is the identity operation - which brings us back to the walls not being the full story.

What do you think? Should we extend the format presented here with the solution? The full tree? Or take another approach?

For inspiration, you can have a look at #12, where I went to the other extreme of basically just dumping the Trails object as-is and expect the consumer to deal with a tree like that. In that situation, there are no walls, which means that a visualization library would have to figure those out. That might not be great either?

Looking forward to your thoughts.