The game levels that can be produced by the Generative Art Sverchok node in Blender are lots of fun to explore but there's nothing to stop them producing overlapping paths like this:
This is because the alogrithim behind the node is based on L-systems and knows nothing about where its already been. The code only keeps tracks of a current transform (encoding position and direction) and randomly chooses another transfom rule to apply. It has no way to know where anything has already been drawn.
The game levels from the Generative Art node can be edited to produce a playable layout. See this great puzzle game complete with a Gondola, from Hamish at TechMonkeyBusiness. But I wanted to produce some more orderly game levels so I started looking at maze generating algorithms. I found Jamis Buck's great posts on maze building and his book "Mazes for Programmers".
In my ususal magpie fashion I started off with someone else's bright shiny code, in this case this gist by Sami Salkosuo, which is a python version of some of the code from "Mazes for Programmers".
This implements the recursive backtracker algoritm as described on Buckblog. Imagine a grid of squares for a a 2D maze. The squares represent cells that will become paths in the maze. The lines at the edges of the squares are "carved" through to connect the cells to form a maze path.
Here’s the mile-high view of recursive backtracking
Choose a starting point in the field.
Randomly choose a wall at that point and carve a passage through to the adjacent cell, but only if the adjacent cell has not been visited yet. This becomes the new current cell. If all adjacent cells have been visited, back up to the last cell that has uncarved walls and repeat. The algorithm ends when the process has backed all the way up to the starting point.
Theres's an animation of this here.
The algorithm can either be implemented using recursive function calls, or with a stack that holds the cells visited, when a passage is carved through to another cell the new cell is added to the end of the stack. When the algorihtm backtracks cells are poped off the end of the stack.
I've included a version of this code in a Sverchok scripted node (maze_2d_gen) that like the Generative Art node has a matrices and a mask outputs. The matrices list is used to position objects and the mask list of integers is used to determine which object to place at each position. To use this you'll need both the the maze_3d.py and the maze_2D_gen.py files from github.
I'll start with a simple example maze_2D_simple.blendthat just has very basic components and show how to generate either a path maze or a wall maze. Then I'll show you how to make a 2D maze with some of the Steely Taws game components. Then I'll finish up with the blend file with the components, Sverchok node diagram and the game logic to allow anyone to generate and play an unlimited number of random Steely Taws game mazes. These mazes are all just 2D but the 3D code in maze_3d.py shows what I'm working on next.
For a demo version to show how this works I made simple straight, bend, t-intersection and 4 way cross intersection tiles. Each tile needs to fit in to a 1 unit by 1 unit square centered on the origin. The straight section goes from (-0.5, 0, 0) to (0.5, 0, 0). The bend goes from (1, 0, 0) to (0, 1, 0) and has its origin at (0, 0, 0). The t-intersection is the same length as the straight but has a path going to (0, 1, 0). In the maze_2D_simple.blend file these components are on the second layer.
The Sverchok node diagram is very similar to those used with the Generaive Art node. A Logic node and a Mask node are used to separate the matrices output into four lists for the four different types of tiles (straights, bends, tees and crosses) that need to be placed.
The size of the maze can be set with the height and width sliders on the node. Changing the rseed slider generates a new random maze. The scale sets the distance between components.
A braided maze is a maze that has loops. If braid is set to zero there will be no loops and there will be only one path between any two parts of the maze. This type of maze has lots of dead ends (cells with only one connecting path). If braid is set to 1 there will be no dead ends and lots of loops. In between, braid sets the proportion of dead ends that are turned into loops.
For some mazes there may be no 4 way intersections (or for braid = 1, no ends), in this case you need to turn the display of ths object off or you'll get an out of place cross (or end) at the origin.
With a different set of tiles its easy to produce a typical maze with walls between the passages. The maze_2D_simple.blend file has some tiles for this on the third layer. Swap them for the path tiles gives a maze like this.
Try hedges or a layout such as a garden that is less obviously a maze.
The steely_taws_2D_maze.blend file has all the parts to generate and play an unlimited number of marble run mazes.
Install a recent version of Sverchok then open the blend file. A simple maze with 100 tiles should be automatically generated. Maximise the 3D View (CTRL-UP). Select the camera view (NUMPAD-0) then press P to start the game. Controls are provided for either the arrow keys or a joystick. If you fall off the edge you will automatically respawn at the start.
To make your own levels, press ESC to close the game and return to Blender. Change the the "rseed" value in the node and get a new game.
In the blend file I've used "mesh instancer" nodes to the replace the "Objects In" and "Viewer Draw" nodes. This allows the same mesh to be used for every straight in a similar way to when you do a linked duplicate in Blender and produces a much smaller file.
Here's another screen shot of the game being played in the Blender Game Engine.
