**Finger Maze** Giuseppe “Oblomov” Bilotta (#) Abstract ![][logo] **Finger Maze** is a maze generation and traversal game, designed for touch and keyboard controls, with two game modes: _standard_ (the whole maze is visible, trace your path from entrance to exit) and _exploration_ (night mode: only the tiles surrounding your current position are visible). [logo]: finger-maze.svg id="abstract-logo" # Features **Finger Maze** is designed to work with rectangular mazes with square tiles, where motion is possible between tiles only in the four cardinal directions (up, down, left and right or equivalently North, South, West and East). It can generate random mazes as well as use pre-defined mazes (the format is described in section [maze specification]). Since each tile has [16 possible configurations](#encoding), there is a finite number of possible mazes of any given dimension ([some of which are equivalent](#standard-form)). **Finger Maze** will only [generate solvable mazes](#maze-generation), but it will accept as input any maze configuration, even if it cannot be solved, or even if it makes no sense from a “human” perspective (completely random walls, no entry or exit points, …) ## Parameters The following parameters can be used when opening the game page: rows : the number of rows in the maze (defaults to 9); cols : the number of columns in the maze (defaults to 16); !!! warning The game is designed to work with mazes in ‘landscape’ orientation (number of columns no less than the number of rows); the roles of `rows` and `cols` will be swapped if the condition is not satisfied. id : an explicit maze specification (see section [maze specification]); by default generate a random maze. !!! warning `rows` and `cols` are ignored if `id` is provided. !!! warning it is possible to specify a ‘portrait’ maze by `id`. It will behave correctly, but the layout will not adapt to the screen. ## Navigation The game supports [touch](#touch), [keyboard](#keyctl) and [gamepad](#gamepad) controls. Icons are displayed to represent which controls are actually available, depending on browser capabilities. (###) Touch controls Drag the highlighted cell over to an adjacent cell without an intervening wall. (###) Keyboard controls Press the up/down/left/right key to move to the adjacent tile if there is no intervening wall. Vim-style hjkl is supported too, in which case uppercase HJKL can be used to move in the appropriate direction (resp. left, down, up, right) until a wall is found. (###) Gamepad controls If the browser supports the [Gamepad API](https://developer.mozilla.org/en-US/docs/Web/API/Gamepad_API), the D-Pad and joysticks can all be used to move. D-Pad always move by a single cell at a time, joysticks will move in the appropriate direction until a wall is found if the axis are fully tilted, single cell otherwise. ### One-way passages An interesting side-effect of the internal model used for the maze is that it allows “one way” passages, achieved by a tile with an open passage in a direction where the adjacent tile does not have an open passage in the opposite direction. For example, the one-dimensional maze `iEi` can be traversed from the west-most tile to the east-most tile, but not in the other direction. In this case, the visual representation of the tiles, which would separately be ************************ * * +---+ +---+ +---+ * | * +---+ +---+ +---+ * ************************ could be obtained e.g. with **************************** * * +------+------+------+ * \ * / * +------+------+------+ * **************************** to indicate the one-way passage in the `iE` boundary. !!! maybe One-way edges are not generated. Should we provide an option to the user for this? (It would make exploration mode particularly challenging.) !!! todo Visual support for one-way edges is not implemented yet.
(They do work as expected when user-generated though) # Technical details ## Tiling The game is designed to produce rectangular mazes with square tiles. Tile adjacency is only in the four cardinal direction: North, East, South, West. Each tile edge can be either passable (allowing the user to move to the adjacent tile, represented by 0), or a wall (preventing the user from crossing to the adjacent tile, represented by 1). With four directions and two possible states, there are $2^4 = 16$ possible tiles, half of which are the complement of the other half (e.g. the tile that represents a dead end with only passage to the east is the complement of the tile that represent a T junction where all edges are passable except the eastern one) (figure [tilecomplement]). ***************************************** * * +---------+ + + * | | * | vs | * | | * | | * +---------+ + + * ***************************************** [Figure [tilecomplement]: complementary tiles: east passage dead-end vs East wall T-junction.] With $R$ rows and $C$ columns, there are $RC$ total tiles, leading to $16^{RC}$ possible configurations for a maze. For example, with the default parameter values ($R=9, C=16$) there are over $2.4\cdot10^{173}$ possible tilings. Most of the configurations, however, will be completely meaningless (figure [nonsensemaze]). ******************************************************************** * * * +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ * * | | | | | | | | | | | | * * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--- * * | | | | | | | | | | | | * * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--- * * | | | | | | | | * * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--- * * | | | | | | | | | | | | * * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--- * * | | | | | | | | | | | | * * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--- * * | | | | | | | | * * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--- * * | | | | | | | | | | | | * * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--- * * | | | | | | | | | | | | * * | | | | | | | | | | | | * * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+--- * * * ******************************************************************** [Figure [nonsensemaze]: a completely bogus $16\times9$ maze.] ## Encoding ****************************** Encoding the edge state of each direction with a single bit, from least * * to most significant in the order North, East, South, West, we can * North * represent a tile with a single nibble (e.g. with the lowest half of a * bit 0 * byte). * +---------+ * * | | * For simplicity in import/export and readability by the user, * West | | East * we can use mnemonics to represent each state, using uppercase * bit 3 | | bit 1 * to represent open edges and lowercase to represent the complement. * | | * * +---------+ * The 16 possible tiles and their mnemonics are illustrated in table [tilestab]. * bit 2 * * South * * * ****************************** +------+----+-----------+-------------------+ |`WSEN`| n | Shape | Mnemonic | +======+===:+:=========:+===================+ | | | ******* | | | | | *+ +* | | | 0000 | 0 | * * | A (atrium, all) | | | | *+ +* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+---+* | | | 0001 | 1 | * * | n (not North) | | | | *+ +* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+ +* | | | 0010 | 2 | * |* | e (not East) | | | | *+ +* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+---+* | | | 0011 | 3 | * |* | l (not L corner) | | | | *+ +* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+ +* | | | 0100 | 4 | * * | s (not South) | | | | *+---+* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+---+* | | | 0101 | 5 | * * | i (not I corrIdor)| | | | *+---+* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+ +* | | | 0110 | 6 | * |* | J (corner shape) | | | | *+---+* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+---+* | | | 0111 | 7 | * |* | W (West end) | | | | *+---+* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+ +* | | | 1000 | 8 | *| * | w (not West) | | | | *+ +* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+---+* | | | 1001 | 9 | *| * | j (not J corner) | | | | *+ +* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+ +* | | | 1010 | 10 | *| |* | I (corrIdor) | | | | *+ +* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+---+* | | | 1011 | 11 | *| |* | S (South end) | | | | *+ +* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+ +* | | | 1100 | 12 | *| * | L (corner shape) | | | | *+---+* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+---+* | | | 1101 | 13 | *| * | E (East end) | | | | *+---+* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+ +* | | | 1110 | 14 | *| |* | N (North end) | | | | *+---+* | | | | | ******* | | +------+----+-----------+-------------------+ | | | ******* | | | | | *+---+* | | | 1111 | 15 | *| |* | a (not Any) | | | | *+---+* | | | | | ******* | | +------+----+-----------+-------------------+ [Table [tilestab]: finger maze tiles and their encoding] In summary, the tile code sequence is `AnelsiJWwjISLENa`, which is case-symmetrical around the West end and its complement. As an example, we illustrate the encoding of the Finger Maze logo tiles in figure [enclogo]. ********************* * +---+---+---+ + * * | j i i J | * * + +---+---+---+ * * | I | j i l | * * + + +---+ + * * | I | I | j J | * * + + + +---+ * * | L J | L l | * * +---+---+---+ + * ********************* [Figure [enclogo]: Finger Maze encoding of the Finger Maze logo] ## Maze specification A maze is defined by the number of columns (West to East) and rows (North to South), plus the matrix of tiles, plus the entry and exit point specification. The tiles are specified in row-major order from the north-western corner to the south-eastern corner. A user-accessible string form of the maze begings with the letters `FM` (for Finger Maze), followed by a positive integer representing the number or columns, followed by the first row of tiles, followed by a positive integer representing the number of rows, followed by the rest of the maze, followed by the specification of the location of the entrance and exit, each specified as a cardinal direction (N, E, S, W) and a tile number, with tiles counted in a clockwise manner starting from 0 and restarting the count on each side. !!! todo FIXME The entry/exit specification as it is now is potentially confusing, and incompatible with the row numbering used in the Standard form section. Consider an alternative where boundary tiles are counted from 0 to $2(C+R)-1$, starting from the north tiles and proceeding clockwise (with e.g. the northeastern tile has index $C-1$ when entering from the north, $C$ when entering from the east), using `/` to separate entry from exit index. For example, the full specification of the one-way maze [above](#one-waypassages) would be: [FM3iEi1W0E0](index.html?id=FM3iEi1W0E0). The following maze: **************************** * * +---+ v +---+---+---+ * | | | * + +---+ +---+ + * | | | * + +---+ + +---+ * | | | > * +---+---+---+---+---+ * **************************** would be specified as: [FM5jsnWS3IEAnJNEJLiN1E2](index.html?id=FM5jsnWS3IEAnJNEJLiN1E2). The Finger Maze logo itself is [FM4jiiJ4IjilIIjJLJLlN3S0](index.html?id=FM4jiiJ4IjilIIjJLJLlN3S0). !!! maybe For larger mazes, some form of compressed notation should be made available (e.g. packing multiple consecutive cells into a single symbols, with a dedicated notation; the `FMz` prefix could be used to denote compressed `FM`, and the available symbols could then be A-Za-z that would account for 52 distinct values). ## Maze generation Maze generation is based on a modified recursive backtracker algorithm, with the following changes: 1. start _and_ exit are marked visited at the beginning; 2. when a dead end is reached during the recursive backtracking, the _first_ cell in the stack becomes the currently active cell; 3. the cell adjacent to the exit activated with the deepest stack is connected to the exit; In my experience, this maze generator produces sufficiently long and intricated paths with a reasonably challenging number of branchpoints that work well in most cases. !!! warning When the start and exit location are close (e.g. both near the middle of the long side of a maze), the maze is usually not very challenging. !!! maybe Could more challenging mazes be achieved by preferring neighbors that move ‘away’ from the exit during the neighbor pick? ## Standard form We can define an equivalence relationship between mazes of a given size, when they can be brought to each other with one or more reflections (north/south and/or east/west) and transpositions. From each equivalence class we can extract a _standard_ representative satisfying the following conditions: [landscape orientation](#landscape-orient), [entry from the north-west](#nw-entry), [exit from the south-east](#se-entry). (###) Landscape orientation If the number of rows is larger than the number of columns (portrait), we can change to landscape orientation by transposing the matrix. (###) Entry from the north-west Let us call $C$ the number of columns of the maze, and $R$ the number of rows. We number columns from $0$ (westernmost) to $C-1$ (easternmost), and rows from $0$ (northernmost) to $R-1$ (southernmost). !!! warning Note that the row count is not the same used for the western tiles for the entry/exit point in the Maze specification section. The values $C_M = \left\lfloor \frac{C+1}{2} \right\rfloor$ and $R_M = \left\lfloor \frac{R+1}{2} \right\rfloor$ represent, respectively, the highest-numbered column in the western half of the maze, and the highest-numbered row in the northern half of the maze. !!! tip For odd $C$ (_resp._ $R$), we are including the middle column (_resp._ row) in what we consider the western (_resp._ northern) half of the maze. !!! todo Diagrams illustrating the maze halves for even vs odd rows/columns. By using reflections, we can always guarantee that the entry will be in the north-western quadrant of the maze. To be precise: * if the entry is in the southern wall, we can reflect the maze north/south to bring it in the northern wall; * if the entry is in the eastern wall, we can reflect the maze east/west to bring it in the western wall; * if the maze is square and the entry is in the western wall, we can transpose the maze to bring it in the northern wall; * if the entry is in the northern wall, and $C_E$ is the entry column, we can reflect the maze if $C_E > C_M$; * if the entry is in the western wall, and $R_E$ is the entry row, we can reflect the maze if $R_E > R_M$. (###) Exit from the South-Eastern part of the maze The previous two conditions are sufficient if $C$ and $R$ are even, but not if they are odd and the entry is in the middle column or row. In this case, we can force uniqueness by ensuring that the maze is in the south-eastern part of the maze: * if $C$ is odd, the entry is in the northern wall, $C_E = C_M$, the exit is in the southern wall with exit column $C_X$ and $C_X < C_M$, we can reflect the maze east/west; * if $R$ is odd, the entry is in the western wall, $R_E = R_M$, the exit is in the eastern wall with exit row $R_X$ and $R_X < R_M$, we can reflect the maze north/south. !!! todo There is still a condition missing in the odd case when $C_E = C_X = C_M$ or $R_E = R_X = R_M$.