Edd Biddulph

Twitter | CV

Articles

November 2015
Implicit Maze-Like Patterns

In the early days of homecomputing it was possible to write a very simple program in BASIC which seemingly produced a randomly-generated maze. The program would print a series of slashes to the display, switching between back slashes and forward slashes at random. The output would not really be a solvable maze but would consist of characteristic snaking corridors so you could at least trace some kind of path between the slashes. In fact the paths would all be loops, and there would be no dead-ends. Of course this is simple to recreate as a pixel-shader:




float maze(vec2 p) { vec2 p2 = (p - .25) * mat2(1, 1, 1, -1); vec2 c = floor(p2), f = p2 - c; return step(abs(dot(f - .5, vec2(1, 1 - 2 * step(.5, noise(c))))), .1); }

As you can see I rotated the grid by 45 degrees and scaled it by sqrt(2). The shader determines which cell the current pixel is in and then chooses a slash for that cell. The problem with this is that the walls of the maze are cut off at the edges of cells just like they would be on a character-based display. To solve this I added small squares to fill in the gaps:



float maze(vec2 p) { vec2 p2 = (p - .25) * mat2(1, 1, 1, -1); vec2 c = floor(p2), f = p2 - c; float a = step(abs(dot(f - .5, vec2(1, 1 - 2 * step(.5, noise(c))))), .1); return max(a, step(max(abs(fract(p.x * 2) - .5),abs(fract(p.y * 2) - .5)), .1)); }

This is okay, but feels like a hack and adds a lot of small isolated squares. So I decided to start again from scratch and came up with the idea to use two grids, one grid which fixes the locations of walls and another grid which determines the orientation of the walls. The orientation grid is rotated 45 degrees and scaled so that it has points at the centers of the first grid. If the walls are also positioned at the centers of the first grid then it's not possible to have any V-shaped cuts. The result looks like this:



float maze(vec2 p) { vec2 p2 = (p - .5) * mat2(1, 1, 1, -1); vec2 c = floor(p2), f = fract(p); return step(abs(mix(f.x - .5, f.y - .5, step(.5, noise(c)))), .1); }

So now the pattern is less maze-like but it's still explorable, it has dead-ends, and the code is much simpler. My next thought was about whether this could be extended to 3D, so that a completely implicit and completely procedural maze-like 3D structure could be rendered. This requires that an analogue in 3D to the rotated grid be used, and this equivalent consists of tessellating octahedrons:



Diamonds meeting in a square become octahedrons meeting in a cube.


To perform the same hash lookup per cell it's useful to know which octahedron the raymarcher is currently within but in fact it's only required to produce the same hash value for the same octahedron. So I realised that I could just snap the current position to the center of the nearest octahedron and use that new location as the input to the hashing function. This turns out to be pretty easy when there's already an axis-aligned grid being used because the centers of the octahedrons coincide with the centers of the cubes's faces.

// Snap to the nearest octahedron. vec3 cp = fract(p) - .5; vec3 acp = abs(cp); vec3 ofs = step(acp.yzx, acp.xyz) * step(acp.zxy, acp.xyz) * sign(cp); vec3 op = floor(p) + .5 + ofs * .5;


So putting that into a raymarcher and using simple cuboid primitives for the walls creates this:




float mazeSDF(vec3 p) { vec3 cp = fract(p) - .5; vec3 acp = abs(cp); vec3 ofs = step(acp.yzx, acp.xyz) * step(acp.zxy, acp.xyz) * sign(cp); vec3 op = floor(p) + .5 + ofs * .5; float f = noise(op); vec2 cp2 = abs(f > 1. / 3. ? f > 2. / 3. ? cp.xz : cp.yz : cp.xy); return max(cp2.x, cp2.y) - .1; }


This doesn't look like a maze at all really, but it does have the same randomly-oriented struts. Maybe it's more interesting to just present the original 2D variant in a 3D form:





In 3D it's easier to see that the maze extends to infinity. It's also begging for an automated first-person view, so I implemented just that and since the walls have a pattern which is easily determined then it's straightforward to ensure that the random walk doesn't go through any of the walls. You can check it out on Shadertoy.






That's it for my exploration of implicit maze-like patterns for now!