Randomized Spanning Tree Mazes.

418 Final Project Check In

Title: Randomized Spanning Tree Mazes.

Members : Bryce Summers (bwsummer)
Brandon Lum (jiajunbl)

1 Sentence Description.

We are using Union Find Data Structures to construct mazes by computing randomized planar embedded spanning trees from large sets of potential edges.


Please click on this image to see an example of a random maze generated on the 2D lattice set. Poster Sized Light Maze Power Point Description

The Challenge

Constructing data structures that use synchronization while also using them in the implementation of an actual algorithm.

Work so far


Progress Comments

I believe that it is highly probable that we will be able to complete the project with the time we have left.


For the parallelism competition, we will show graphs detailing how the various implementation decisions affect the performance of the Union find sturctures and the algorithm as a whole. We may also display some of the generated mazes along with time annotations. We may discuss the ramifications and practicality for using our system to make mazes that allows for objects such as curves, versus the traditional methods that only work on 2d grids.

Potential Issues

The testing of the uniformity of the distribution of generated mazes bothers me a little bit. I do not know if we will be able to make any definitive claims of results about the randomized mathematics of our system. While I can foresee several optimizations that may speed up the generation of mazes, they may inhibit the distribution of randomness. The important nuance of this angst is that we could potentially make a blazing fast algorithm that computes a spanning tree for a graph in a deterministic fashion. If we did this then our system would likely not need a union find structure or any other intellectually interesting work, but our system would also be inept at the task of generating interesting disparate mazes.
We may encounter some difficulties in clearly defining designing and refining the lock free implementation of the Union Find Structure and using it correctly in parallel to generate a maze. There are many questions of how each of the functions should be guaranteed to perform in the various cases.
We have done a lot of work on the algorithmic end, but we still need to choose the method of real world implementation and what parallel system we will be running the code on.