MazeGenerator

[salesman]

I had an assignment for school to write a maze generator in Java, and decided to convert it to GS2. The purpose of the assignment was to apply a disjoint set data structure to something practical, like maze generating. It might not be the most efficient algorithm, and it might not generate the most difficult mazes, but it is fast and it works. The algorithm is essentially a randomized Kruskal's algorithm, and has an O(n) running time proportional to the number of spaces in your maze.

How it works:

• You start out with a grid where each space is closed off with walls.
• You then look at each wall in some random order and have two cases to consider:
  1. There is already some path that connects the two spaces on either side of this wall, leave this wall where it is.
  2. There is no path that connects the two spaces, remove this wall to make a path.
• We can tell if there is a path between two spaces if they are in the same set, so whenever we remove a wall, we union the two sets containing each space.
• After looking at each wall, you should be able to reach any space from any other space in the maze because they are all in the same set.

See it in action:

When generating a maze in the video, I'm actually generating 10 mazes with a .05 second sleep between each one to give it a cool "loading" effect. So it really is fast...seemingly instant when generating a full-level maze.

Suggested Reading:

• Disjoint sets
• Kruskal's algorithm

Implementation:
Simply put the code in a DBNPC and call this function:

PHP Code:

  MazeGenerator.generateMaze(level_obj, start_x, start_y, width, height);

  // EXAMPLE:

  // This code will generate a maze in salesman's level
  // The maze will cover the entire level
  temp.pl = findplayer("salesman");
  MazeGenerator.generateMaze(temp.pl.level, 0, 0, 64, 64); 


When the maze is generated, there will be exactly one path between any two points in the maze. Because of this, you can pick any two points to be your start and end locations of the maze. I recommend choosing opposite corners!

The code:
MazeGenerator.txt

NOTE: I have not tested this on a gmap!