In a couple of weeks, we will be giving a presentation to our classmates on a technical paper of our choice. Mine will be Image-Guided Maze Construction by Jie Xu and Craig Kaplan from the University of Waterloo. Since the topic is pretty cool, I thought I'd share what it's all about!
Artists have long been creating beautifully artistic mazes. Take Christopher Berg as a modern example. He's been at it since the fifth grade, starting with countless varieties of amoebas as the basis for his mazes. Check out some of his more recent marvels, found on the Amazeing Art website:
Xu and Kaplan state early on that Berg was an inspiration for them. Unfortunately, the techniques that Berg uses to draw his mazes don't translate well to computational algorithms. The computer (with some help from the maze designer) must create lines that will artistically convey the tone, texture, and form of the original image. But in addition to this, there must be spaces between the lines that actually make the drawing a maze!
In an interactive system designed by Xu and Kaplan, a maze designer is able to identify various areas of the image they want to turn into a maze. Each of these regions can have a particular texture applied to them; that is, the maze can follow the general direction of lines in the original image, spiral in on itself, have random direction, or be completely user-defined. Once the mazes in these regions are created, they will be interconnected by breaking a hole in the "walls" between the regions. In addition, the designer can plan out a general solution path to ensure both an interesting and challenging puzzle.
To see how to construct a maze algorithmically, you can first imagine a grid laid out within the area the maze will be created (a planar subdivision). The faces of the grid (which isn't necessarily orthogonal) are called cells, where the edges between two adjacent cells are called cell walls.
Next, consider the dual of the grid, the cell graph, where each cell is represented by a vertex, and cells that share a wall are connected by an edge. Now if you want to get a maze from the grid that doesn't contain any cycles, you simply need to find a spanning tree of this dual and erase the walls between cells connected by the spanning tree in the cell graph. A random spanning tree could be generated, or certain walls could be biased such that they are more likely to be broken first.
Finally, notice that the four maze textures described above can be used to create the grid from which to generate a maze.
In the case of directional mazes, the walls of the maze should flow in a general direction that resembles what it happening in the image the maze is based on. This is done using vector fields, from which "streamlines" are placed. Then, streamlines perpendicular to these are added, thus creating a grid. The distance between the streamlines can be adjusted, helping depict the desired tone.
For regions marked to have spiral textures, the computer will create shrinking concentric rings of the boundary shape. Radial lines are added at regular intervals to complete the grid.
The random texture is created first as a square grid, and then relaxed using an algorithm created by Singh and Pederson. User defined textures obviously must be created by the maze designer.
Here are some examples of what Xu and Kaplan's system have created, taken from their maze design project page:
Noice
ReplyDelete