Graal Forums - MazeGenerator

Graal Forums (https://forums.graalonline.com/forums/index.php)

- Code Gallery (https://forums.graalonline.com/forums/forumdisplay.php?f=179)

- - MazeGenerator (https://forums.graalonline.com/forums/showthread.php?t=134260729)

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:

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:
Attachment 51796

NOTE: I have not tested this on a gmap!

Badass

Remind me why you arnt staff on Era/Manager?

Quote:

Originally Posted by salesman (Post 1604440)

has an O(n) running time proportional to the number of spaces in your maze.

Is the number of spaces in your maze something user-defined?

Quote:

Originally Posted by TheJames (Post 1604446)

Badass

Remind me why you arnt staff on Era/Manager?

Because Era isn't a giant server of mazes, duh!

Dude.. my mind is blown... o_o

That's awesome... ._.

very cool- but there isn't an exit!! :(

Reminds me of this, nice job though.

Badass music. :cool:

But really cool Generator Sales.

Very nice work Sales :).

Quote:

Originally Posted by Tigairius (Post 1604450)

Is the number of spaces in your maze something user-defined?

The width and height are user-defined, and number of spaces = width * height. I actually meant to say number of walls (because the important part of the algorithm looks at each wall once), but the number of walls is directly proportional to the number of spaces, regardless.

Quote:

Originally Posted by xAndrewx (Post 1604458)

very cool- but there isn't an exit!! :(

lol, that's your job.

Quote:

Originally Posted by salesman (Post 1604440)

One maze server coming up.

Really cool, randomly generated dungeon levels anyone?

You inspired me to take a shot at the maze generator thing.

Uses.. Depth-first search algorithm

The grid output is a fairly simple array.

grid[y][x][wall direction (0 to 3)] == wall alive boolean

My implementation does have it's limitations however I narrowed out the maximum size to be 35 by 35 but depending on your application (random dungeon level generator for example) that should be more than enough.

PHP Code:


		
			
function onCreated() {

  // Generate Maze

  temp.maze = generateMaze(35, 35);

  // For added fun!

  randomDestruction(temp.maze.link(), 20);

  // Example output

  drawGrid(temp.maze.link());

}



public function generateMaze(temp.width, temp.height) {

  // Generate Blank Grid

  temp.cells  = new[temp.height][temp.width][5];

  // Begin Adding Rows

  for (temp.y = 0; temp.y < temp.width; temp.y++) {

    // Begin Adding Columns

    for (temp.x = 0; temp.x < temp.height; temp.x++) {

      // Generate Cells

      temp.cell = {1, 1, 1, 1, false};

      // Add Cell to Column

      temp.cells[temp.y][temp.x] = temp.cell;

      temp.i++;

    }

  }

  // Pick Exit

  temp.exit_x = int(random(0, temp.width));

  temp.exit_y = int(random(0, temp.height));

  // Mark Exit

  temp.cells[temp.exit_y][temp.exit_x][4] = true;

  // Begin Carving

  carveMaze(temp.cells.link(), temp.exit_x, temp.exit_y);

  // Trim Visited Fat

  for (temp.y = 0; temp.y < temp.width; temp.y++) {

    for (temp.x = 0; temp.x < temp.height; temp.x++) {

      temp.cells[temp.y][temp.x].delete(4);

    }

  }

  // Return Grid

  return temp.cells;

}



function carveMaze(cells, cx, cy) {

  // Determine Grids Width and Height

  temp.height = cells.size();

  temp.width  = cells[0].size();

  // Find Unvisited Neighbour Cells

  for (temp.i = 0; temp.i < 4; temp.i++) {

    temp.tx = cx + vecx(temp.i);

    temp.ty = cy + vecy(temp.i);

    if (cells[ty][tx].size() == 5) {

      if (cells[ty][tx][4] == false) {

        temp.unvisited.add(temp.i);

      }

    }

  }

  // Check if has Unvisited Neighbours

  temp.neighbours = temp.unvisited.size();

  if (temp.neighbours > 0) {

    // Pick Unvisited Neighbour

    temp.neighbour = temp.unvisited[int(random(0, temp.neighbours))];

    temp.tx = cx + vecx(temp.neighbour);

    temp.ty = cy + vecy(temp.neighbour);

    // Remove Wall between Neighbours

    cells[cy][cx][temp.neighbour] = 0;

    cells[ty][tx][(temp.neighbour + 2) % 4] = 0;

    // Set Neighbour Cell to Visited

    cells[ty][tx][4] = true;

    // Continue Carving as Neighbour

    carveMaze(cells.link(), temp.tx, temp.ty);

    // Continue Carving Local Neighbours

    if (temp.neighbours > 0) carveMaze(cells.link(), cx, cy);

  }

}



public function randomDestruction(cells, walls) {

  // Determine Grids Width and Height

  temp.height = cells.size();

  temp.width  = cells[0].size();

  // Check for Proper Cell

  if (cells[0][0].size() != 4) return false;

  // Begin Random Destruction

  while (walls > 0) {

    // Pick a Random Cell

    temp.cx = int(random(0, temp.width));

    temp.cy = int(random(0, temp.height));

    // Pick a Random Neighbour

    temp.neighbour = int(random(0, 4));

    temp.tx = cx + vecx(temp.neighbour);

    temp.ty = cy + vecy(temp.neighbour);

    // Skip Non-Cells

    if (cells[temp.tx][temp.ty].size() != 4) continue;

    // Check if Wall Exists

    if (cells[temp.cy][temp.cx][temp.neighbour] == true) {

      // Remove Wall

      cells[cy][cx][temp.neighbour] = 0;

      cells[ty][tx][(temp.neighbour + 2) % 4] = 0;

      walls--;

    }

  }  

}



/*

   Example Rendering of a Maze

*/



public function drawGrid(cells) {

  // Determine Grids Width and Height

  temp.height = cells.size();

  temp.width  = cells[0].size();

  // Check for Proper Cell

  if (cells[0][0].size() != 4) return false;

  // Drawing Configuration

  temp.cell_width  = 24;

  temp.cell_height = 24;

  temp.lw          = 1;  // Line Width

  // Create Drawing Panel

  temp.panel = new TDrawingPanel();

  // Line Drawing Functionality (drawline is a jerk)

  temp.panel.drawhoriz = function (x1, y1, width) {

    this.drawimagestretched(params[0], params[1], width, 1, "whitefill.png", 0, 0, 1, 1);

  };

  temp.panel.drawvert = function (x1, y1, height) {

    this.drawimagestretched(params[0], params[1], 1, height, "whitefill.png", 0, 0, 1, 1);

  };

  // Set Panel Size

  temp.panel.setsize(temp.width * temp.cell_width, temp.height * temp.cell_height);

  // Fill Image

  temp.panel.drawimagestretched(0, 0, temp.width * temp.cell_width, temp.height * temp.cell_height, "blackfill.png", 0, 0, 1, 1);

  // Begin Drawing Cells

  for (temp.y = 0; temp.y < temp.width; temp.y++) {

    for (temp.x = 0; temp.x < temp.height; temp.x++) {

      temp.cell = cells[temp.y][temp.x];

      for (temp.i = 0; temp.i < 4; temp.i++) {

        // Check if Wall on that Direction

        if (temp.cell[temp.i]) {

          // Determine Top Corner

          temp.tx = temp.x * temp.cell_width;

          temp.ty = temp.y * temp.cell_height;

          // Draw Walls

          if (temp.i == 0) temp.panel.drawhoriz(temp.tx, temp.ty, temp.cell_width);

          else if (temp.i == 1) temp.panel.drawvert(temp.tx, temp.ty, temp.cell_height);

          else if (temp.i == 2) temp.panel.drawhoriz(temp.tx, temp.ty + temp.cell_height - 1, temp.cell_width);

          else if (temp.i == 3) temp.panel.drawvert(temp.tx + temp.cell_width - 1, temp.ty, temp.cell_height);

        }

      }

    }

  }

  // Save Image (change this to somewhere meaningful to yourself)

  temp.panel.saveimage("cartridge/testmaze.png");

  // Destroy Panel

  temp.panel.destroy();

}

Attached, images used in script and an example output.

http://img40.imageshack.us/img40/7562/whitefill.png
http://img259.imageshack.us/img259/9659/blackfill.png

Very nice, I was actually planning on implementing a depth-first search version myself!