Maze Generation Problem!

Processing Coding Questions
,
1

image
image1920×1080 117 KB

i have some white spaces in the grid that are block while im trying to generate a maze on the grid.
each maze block covers 4x4 grid blocks so please help me figure out a way i can avoid blocked spaces in the grid so the maze will have clear paths that the player could walk there.

so here is the code for generating a maze automatically:
GenerateMaze.pde

// Function to generate the maze
void generateMaze() {
  // Clear previous maze blocks
  for (int i = 0; i < cols; i++) {
    for (int j = 0; j < rows; j++) {
      mazeBlocks[i][j] = false; // Start with no maze blocks
    }
  }

  // Define the size of the empty center square in pixels
  int centerSizePixels = 320; // Set a fixed size for the center square (e.g., 300x300 pixels)
  int centerSizeCols = centerSizePixels / cellWidth;
  int centerSizeRows = centerSizePixels / cellHeight;

  // Ensure the center space is a square by taking the minimum of the calculated cols and rows
  int centerSize = min(centerSizeCols, centerSizeRows);

  int centerStartX = (cols / 2) - (centerSize / 2);
  int centerStartY = (rows / 2) - (centerSize / 2);

  // Randomly place maze blocks within the interior, leaving the edges and center clear
  for (int i = 4; i < cols - 4; i += 4) {
    for (int j = 4; j < rows - 4; j += 4) {
      // Skip the area within the center square
      if (i >= centerStartX && i < centerStartX + centerSize &&
          j >= centerStartY && j < centerStartY + centerSize) {
        continue;
      }
      
      if (random(1) < 0.5) {
        // Mark a 4x4 block as part of the maze
        for (int x = 0; x < 4; x++) {
          for (int y = 0; y < 4; y++) {
            mazeBlocks[i + x][j + y] = true;
          }
        }
      }
    }
  }

  // Create outer frame
  createOuterFrame();

  // Ensure there are no fully enclosed white spaces
  boolean trappedSpacesExist;
  do {
    trappedSpacesExist = false;
    for (int i = 4; i < cols - 4; i += 4) {
      for (int j = 4; j < rows - 4; j += 4) {
        if (isTrappedSpace(i, j)) {
          removeRandomBlock(i, j);
          trappedSpacesExist = true;
        }
      }
    }
  } while (trappedSpacesExist);

  // Double check for trapped spaces
  do {
    trappedSpacesExist = false;
    for (int i = 4; i < cols - 4; i += 4) {
      for (int j = 4; j < rows - 4; j += 4) {
        if (isTrappedSpace(i, j)) {
          removeRandomBlock(i, j);
          trappedSpacesExist = true;
        }
      }
    }
  } while (trappedSpacesExist);

  // Triple check for trapped spaces
  do {
    trappedSpacesExist = false;
    for (int i = 4; i < cols - 4; i += 4) {
      for (int j = 4; j < rows - 4; j += 4) {
        if (isTrappedSpace(i, j)) {
          removeRandomBlock(i, j);
          trappedSpacesExist = true;
        }
      }
    }
  } while (trappedSpacesExist);
}

// Function to create an outer frame
void createOuterFrame() {
  for (int i = 0; i < cols; i += 4) {
    mazeBlocks[i][0] = true;
    mazeBlocks[i][rows - 4] = true;
  }
  for (int j = 0; j < rows; j += 4) {
    mazeBlocks[0][j] = true;
    mazeBlocks[cols - 4][j] = true;
  }
}

// Function to check if a 4x4 block is surrounded by maze blocks
boolean isTrappedSpace(int i, int j) {
  return mazeBlocks[i][j] &&
         mazeBlocks[i-4][j] && mazeBlocks[i+4][j] &&
         mazeBlocks[i][j-4] && mazeBlocks[i][j+4];
}

// Function to remove a random block to create an exit for a trapped space
void removeRandomBlock(int i, int j) {
  int direction;
  do {
    direction = int(random(4));
  } while ((direction == 0 && (i - 4 <= 0 || i - 4 >= cols - 4)) ||
           (direction == 1 && (i + 4 >= cols - 4 || i + 4 <= 0)) ||
           (direction == 2 && (j - 4 <= 0 || j - 4 >= rows - 4)) ||
           (direction == 3 && (j + 4 >= rows - 4 || j + 4 <= 0)));

  switch(direction) {
    case 0: mazeBlocks[i-4][j] = false; break; // Left
    case 1: mazeBlocks[i+4][j] = false; break; // Right
    case 2: mazeBlocks[i][j-4] = false; break; // Top
    case 3: mazeBlocks[i][j+4] = false; break; // Bottom
  }
}

// Function to draw the maze blocks
void drawMaze() {
  fill(128); // Grey fill for maze blocks
  stroke(0); // Black stroke for maze blocks
  for (int i = 0; i < cols; i += 4) {
    for (int j = 0; j < rows; j += 4) {
      // Check if the top-left corner of a 4x4 block is marked
      if (mazeBlocks[i][j]) {
        // Draw a block that spans 4x4 grid cells
        rect(i * cellWidth, j * cellHeight, cellWidth * 4, cellHeight * 4);
      }
    }
  }
}

Main.Pde:

import processing.awt.*;
import javax.swing.*;
import java.awt.*;
import java.awt.Dimension;
import java.awt.GraphicsEnvironment;
import java.awt.GraphicsDevice;

// Global variables for grid size
int targetCellWidth = 10;  // Set a target width for each cell
int targetCellHeight = 10; // Set a target height for each cell
int cols; // Number of columns
int rows; // Number of rows
int cellWidth, cellHeight;

GraphicsDevice device;
JFrame frame;
Dimension prevDimension;
Rectangle bounds;
int mode = 0;

// Maze blocks array
boolean[][] mazeBlocks;

void setup() {
  fullScreen(); // Start in fullscreen mode

  frame = (JFrame) ((PSurfaceAWT.SmoothCanvas)getSurface().getNative()).getFrame();
  prevDimension = ((PSurfaceAWT.SmoothCanvas)getSurface().getNative()).getPreferredSize();
  bounds = frame.getBounds();
  GraphicsEnvironment ge = GraphicsEnvironment.getLocalGraphicsEnvironment();
  device = ge.getDefaultScreenDevice();

  // Calculate number of columns and rows based on screen dimensions and target cell size
  cols = width / targetCellWidth;
  rows = height / targetCellHeight;

  // Calculate cell size
  cellWidth = width / cols;
  cellHeight = height / rows;

  // Initialize the maze blocks array
  mazeBlocks = new boolean[cols][rows];

  // Setup button position
  setupButton();
}

void keyReleased() {
  if (key == ' ') { // press space
    switch (++mode % 2) {
      case 0:
        frame.setVisible(false);
        frame.dispose();
        frame.setUndecorated(false);
        frame.setBounds(bounds);
        surface.setSize((int)prevDimension.getWidth(), (int)prevDimension.getHeight());
        device.setFullScreenWindow(null);
        frame.setVisible(true);
        break;
      case 1:
        frame.setVisible(false);
        frame.dispose();
        frame.setUndecorated(true);
        surface.setSize(displayWidth, displayHeight);
        device.setFullScreenWindow(frame);
        frame.setVisible(true);
        break;
    }
    ((PSurfaceAWT.SmoothCanvas)getSurface().getNative()).requestFocus();
  }
}

void draw() {
  background(255); // Set the background to white
  
  // Draw the grid
  drawGrid();
  
  // Draw the maze blocks (calls the drawMaze() function from MazeGenerator.pde)
  drawMaze();
  
  // Draw the button
  drawButton();
}

// Function to draw the grid
void drawGrid() {
  stroke(128); // Grey color for the grid

  // Draw the grid lines
  for (int x = 0; x <= width; x += cellWidth) {
    line(x, 0, x, height);
  }

  for (int y = 0; y <= height; y += cellHeight) {
    line(0, y, width, y);
  }
}

// Handle mouse clicks
void mousePressed() {
  handleButtonClick(mouseX, mouseY);
}

Buttons.pde

int buttonWidth = 200;
int buttonHeight = 50;
int buttonX, buttonY;

// Setup the button position
void setupButton() {
  buttonX = (width - buttonWidth) / 2;
  buttonY = height - 70;
}

// Draw the button on the screen
void drawButton() {
  fill(200); // Light grey fill
  stroke(0); // Black stroke
  rect(buttonX, buttonY, buttonWidth, buttonHeight, 10); // Draw the button with rounded corners

  fill(0); // Black text color
  textAlign(CENTER, CENTER);
  textSize(20);
  text("Generate", buttonX + buttonWidth / 2, buttonY + buttonHeight / 2);
}

// Handle button clicks
void handleButtonClick(int x, int y) {
  if (x > buttonX && x < buttonX + buttonWidth && y > buttonY && y < buttonY + buttonHeight) {
    generateMaze(); // Generate the maze when the button is clicked
  }
}
1 Like
2

apparently, this not trivial

here is a quick search in this forum: Search results for 'maze generator' - Processing Foundation

Hey, and welcome to the forum! Good job!

Warm regards,

Chrisir

2 Likes
3

The trick here is to turn the problem arround

  1. find an algorithm that can create a maze where any ‘open’ cell connects to every other ‘open’ cell. By open I mean any cell that can be visited / traversed other. This will result in something like this
    Screenshot 2024-08-08 at 19.02.30

Notice there is a path from every white cell to every other white cell.

  1. Create larger open areas by removing walls from selected areas to get something like this
    Screenshot 2024-08-08 at 19.02.30

Provided you do not add additional walls after step (1) it is impossible to get closed off / inaccessible areas in the maze. :smile:

3 Likes