Skip to content

Instantly share code, notes, and snippets.

@bigfleet
Created April 5, 2012 18:03
Show Gist options
  • Select an option

  • Save bigfleet/2312881 to your computer and use it in GitHub Desktop.

Select an option

Save bigfleet/2312881 to your computer and use it in GitHub Desktop.
Union find pseudocode instruction

Consider a 10x10 array that represents the coordinate system for a maze. I'll call each individual space in the array a cell.

To generate a maze, consider each cell as having "walls" up in each direction, indicating no ability to pass into it or from it. Assign each cell a unique number. In this scheme, when two cells have the same number, it indicates that you may pass from one cell to the other, either directly or through other cells. The success condition is when every cell has the same number-- at this point, you will have a perfectly traversable coordinate system. You can pick two random "edges" of the coordinates and relax the wall to the outside world to have entry and exit.

To apply the algorithm, begin with the fully partitioned system. Pick a cell. Check its neighbors to see if one of them has a different set number. If it's only one, lower the wall, and change all cells that are represented by one of the numbers to the other number. If there is more than one, choose between the choices randomly and perform the wall relaxation.

That's it. There are several optimizations possible to ensure that you generate the traversable system rapidly, I'll leave those as an exercise for the reader.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment