@drpicox ~ $ ls

~ $ cd projects/maze && cat README.md

A maze you could not fly over

Realitat Virtual i Geometria, FIB, spring 2001, with Toni Preciado. The course was VRML, the language the web of 2000 was going to walk around in: a scene is a text file, and a plug-in in the browser lets you move through it. Our project was a maze. Not one drawn by hand: a Java program, LaberintoSimple, that grew one of any size and wrote it out as a VRML world, a floor for every room and a wall wherever two rooms were not joined.

aabb

The way out is 19 rooms long, and touches no sphere.

That is the maze the program wrote on 20 May 2001, seven rooms a side, from seed 543: the file it produced, test.wrl, is still there, and the maze above is grown again from the same seed and checked against it wall for wall. North is at the top, the way in is at the bottom left and the way out at the top right. Walk the camera follows the route the program dug the rooms in; another grows a new one.

The dig

Start in the corner. From the room you are in, try the neighbours in turn; for each one nobody has dug yet, knock down the wall between you and dig from there. When there is nowhere left to go, step back and try the next neighbour of the room before. That is a depth-first search, and since every room is entered exactly once, from exactly one other, the result is a tree: one way, and only one, between any two rooms. The report that went with it says it plainly: "todos los laberintos tienen una única solución", and from anywhere you can reach anywhere.

The steps back are kept too. The program wrote the whole route, back-tracks and all, into the VRML as an animation, and a camera rode along it: pick Cam DFS in the viewer and you watched the maze being dug, room by room. The report offers it as the first of the two games — a replacement for the Windows OpenGL screensaver — and the second as solving the maze on foot.

One thing about "try the neighbours in turn": the order is not shuffled. The program picks one of three fixed orders — north, east, west, south; west, south, east, north; or south, east, west, north — so of the twenty-four ways to order four directions it only ever uses three. The mazes do not look it.

The spheres

A week after the first version, the program learnt to cheat. In one room in ten, before digging on, it picks a room anywhere in the maze. If nobody has dug that room yet, it puts a green sphere in both, joins them, and digs on from the far one. In the viewer the sphere was a link, meant to take you to its pair through every wall in between. The maze above marks both ends of a jump with the same letter.

public void generar(int x, int y)
{
    int orden;

    anadirDFS(x, y);
    if (random.nextInt(10) < 1)
        generarHLink(x, y);

    orden = random.nextInt(3);
    switch (orden)
    {
        case 0:  generarNorte(x, y); generarEste(x, y); generarOeste(x, y); generarSur(x, y);   break;
        case 1:  generarOeste(x, y); generarSur(x, y);  generarEste(x, y);  generarNorte(x, y); break;
        default: generarSur(x, y);   generarEste(x, y); generarOeste(x, y); generarNorte(x, y); break;
    }
}

public void generarHLink(int x, int y)
{
    int x2 = random.nextInt(w);
    int y2 = random.nextInt(h);

    if (laberinto[x2][y2] != 0)
        return;

    laberinto[x][y] |= CNX_HLINK;
    laberinto[x2][y2] = CNX_HLINK;
    hLinks[x][y] = new Pt(x2, y2);
    hLinks[x2][y2] = new Pt(x, y);

    generar(x2, y2);
    anadirDFS(x, y);
}

That is LaberintoSimple.java, with the four switch cases set a line each. In English, name for name:

public void dig(int x, int y)
{
    int order;

    rememberStep(x, y);
    if (random.nextInt(10) < 1)
        digSphere(x, y);

    order = random.nextInt(3);
    switch (order)
    {
        case 0:  digNorth(x, y); digEast(x, y);  digWest(x, y);  digSouth(x, y); break;
        case 1:  digWest(x, y);  digSouth(x, y); digEast(x, y);  digNorth(x, y); break;
        default: digSouth(x, y); digEast(x, y);  digWest(x, y);  digNorth(x, y); break;
    }
}

public void digSphere(int x, int y)
{
    int x2 = random.nextInt(width);
    int y2 = random.nextInt(height);

    if (maze[x2][y2] != 0)
        return;

    maze[x][y] |= HAS_SPHERE;
    maze[x2][y2] = HAS_SPHERE;
    sphereTo[x][y] = new Point(x2, y2);
    sphereTo[x2][y2] = new Point(x, y);

    dig(x2, y2);
    rememberStep(x, y);
}

A jump is just another way into an undug room, so the maze is still a tree and still has one way through. But now the tree is no longer flat. The report: "El laberinto es de dos dimensiones (en ningún momento hay que subir ningún piso), pero dado que hay partes incomunicadas tan solo alcanzables con los hipervínculos se puede considerar que está en 3 dimensiones." Two dimensions you can walk, and a third you can only jump along. That was the point. A maze in VRML has a weakness a maze on paper does not: you can leave the floor and look down. We added fog, which also made large scenes faster, and the spheres, and with those a maze could not be solved from above, because from above there is no seeing where a sphere goes.

The report names five files, mini.wrl, med.wrl, gran.wrl, mm.wrl and 10k.wrl, "el más complicado y con diferencia". They did not survive; the program did, so the dial above goes to thirty a side, which is plenty on a screen. Untick the spheres and you have the version of 13 May, which never rolled for them.

What the spheres did that nobody noticed

Run the Java today and it grows the same mazes it grew then — the page's generator is checked against it — and it shows two things the report does not.

Some spheres lead nowhere. When the room a sphere lands in rolls a sphere of its own, the program overwrites that room's pair. The new pair works both ways; the first sphere now points at a viewpoint nobody wrote. And since the rooms behind it were reached only through that sphere, they are cut off, way out included if it was among them. In the first thousand seven-by-seven mazes the Java grows, 133 have a dead sphere and 117 have no way out at all; at twenty a side, it is most of them. The maze of 20 May happens to be one of the lucky ones. On the page a dead sphere is a dashed circle with a cross, and show the way out says when there is none.

The live ones all land in the same place. Each sphere carries the viewpoint it jumps to, but the viewpoint is written without a position, and VRML puts a viewpoint without one at its default, (0, 0, 10). Every link in the file takes you to that one spot, on a wall a few steps north of the way in. Here a sphere joins the rooms it was meant to join, which is what the report describes.

~/projects/maze $

~/projects/maze $