OK I need a smarter way to encode the maze in #FingerMaze because the approach I'm using can't handle huge mazes (for example a 160×90 maze will result in a 414 Request URI Too Long error.)
One of the issues is that the encoding I'm using is extremely verbose. I discuss some of the details here https://dropthemath.oblomov.eu/fm/finger-maze.md.html but basically: each square in the maze can be represented by 4 bits, one for each side, that tells you if it's open or closed. There are 16 possible tiles, and a letter mnemonic is associated with each. The “id” of a maze is basically a sequence of these mnemonics, plus some metadata (number of rows and columns, and the entry/exit cells).
This kind of encoding allows for nonsensical mazes (there's an example in the document above), but also some interesting features such as one-way doors that are technically supported by the implementation, but never generated by the code (and are not represented properly in the graphics either). Even if we allow all of these features, though, the thing remains that we could pack two tiles in a single byte, while the ID currently uses one byte per tile.
Of course to keep the ID textual one would need to do something like base64-encode the bytes that represent pairs of tiles, and since base64 encodes 3 bytes in 4 characters, we'd get 6 tiles per 4 characters (or rather 3 tiles per 2 characters). That's still not enough (the 160×90 maze would drop from 14400 bytes to 9600 bytes —still too much).
I think we can do much better than that if we don't allow arbitrary mazes, but add some constraints such as no one-way passages and closed outer walls (except for entry/exit). In this case, you actually need LESS than 4 bits per tile, provided you choose an encoding order (for example, top/down, left/right, just because that's my writing direction). In fact, you need at most two bits per tile!
the north bit is unnecessary because it's going to be 1 for all the tiles in the first row, and equal to the south bit of the previous tile in the same column for all other tiles;
the west bit is unnecessary because it's going to be 1 for all the tiles in the first column, and equal to the east bit of the previous tile in the same row for all other tiles;
the tiles in the last column all have 1 as east bit;
the tiles in the last row all have 1 as south bit.
Two bits per tile is MUCH better: we can have 4 tiles per byte, or 3 tiles per base64 character: the 160×90 maze would shrink from 14400 to 4800 without any compression, which is better than what we get with the example maze I'm looking at when compressing with bzip2. I assume 4 tiles per byte + bzip2 + base64 would be even better, although it would massively grow the size of the library, so I'm still thinking about possible ideas to reduce things further without blowing up the JS side.
I think there's some good chance that run-length encoding the “side” bits could bring some solid benefits, better than trying to RLE the tiles themselves. For example, looking at the south walls of a single row, there's plenty of consecutive closed or open walls, even when the tiles with them are not the same. Of course the big question is if there is a good RLE scheme for bits: encoding 1,5,2,2,1,4,1 isn't necessarily more compact than 0111110011011110 (that's two bytes against several).
Anyway, I really don't feel like coding such a compression algorithm at the moment, so I've been focusing on improving the #FingerMaze presentation, which is … not easy. Here's what I would like to do: the maze is always defined in “landscape” mode (rows <= cols), and it should always fit the viewport. When the viewport aspect ratio doesn't match the maze orientation, the maze is rotated to fit (and movement is correctly remapped).
The maze itself is represented by an HTML table, which is actually rather straightforward.
There's some JavaScript involved in getting the sizing right without depending on too many experimental features —but it doesn't work when rows or cols is high, at least not in a cross-browser compatible way. So now I'm experimenting with different ways to do it.
But what's really difficult to get right is the rotation when the viewport is in portrait mode. CSS has the possibility to transform elements, but it doesn't really work as expected. I would have better luck stuffing the table inside a foreignObject inside an #SVG and transforming from there, but … some browsers have questionably poor rendering for these nested situation so that's not an option either.
The biggest problem is managing to get the rotated table correctly centered. You can't say “lay this thing out in a completely rotated context”. The layout is done in the normal context and then rotations are applied.
I have found a better solution than the one I was using before: nest the table inside a div, force the div to have the same size as the viewport if the viewport was landscape-oriented, and then rotate the div. There are a few extra details to take care of, such as the page thinking it has more stuff in the horizontal direction than it actually does (because it considers the “landscape” div, even if it has been rotated) that require some minor fixups (overflow-x: hidden), but it works.
In fact, the outcome is better than the hack I had before, and if you've played #FingerMaze before you can try again now (particularly on mobile) and appreciate the difference: https://dropthemath.oblomov.eu/fm/
There's a new problem now though: I've moved the new/permalink/help links into a details element, and while I can open and close it on desktop, it doesn't seem to work as expected on mobile, and I don't understand why. And debugging on mobile is … nontrivial.
Add comment