• fullscreen
  • Cell.pde
  • Grid.pde
  • RecursiveDivisionMaze.pde
  • Wall.pde
  • mazeRd.pde
  • class Cell {
      int _width, _height;
      boolean isWall = false;
    
      Cell left = null;
      Cell right = null;
      Cell top = null;
      Cell bottom = null;
      
      Cell(int w, int h) {
        _width = w;
        _height = h;
      }
      void draw(int x, int y) {
        stroke(#303030);
        fill(isWall ? #303030 : #ffc4d9);
        rect(x, y, _width, _height);
      }
      
      boolean pathClear(PVector v) {
        boolean isClear = false;
        if (v.x != 0 && v.y == 0) {
          isClear = !this.isWall
                    && this.top != null
                    && !this.top.isWall
                    && this.bottom != null
                    && !this.bottom.isWall;
        } else {
          isClear = !this.isWall
                    && this.left != null
                    && !this.left.isWall
                    && this.right != null
                    && !this.right.isWall;
        }
        return isClear;
      }
      
      void setBottom(Cell cell) {
        bottom = cell;
        cell.top = this;
      }
      
      void setLeft(Cell cell) {
        left = cell;
        cell.right = this;
      }
    }
    
    class Grid {
      Cell[][] _cells;
      int _x, _y, _w, _h, _cellSize;
      Grid(int cellSize, int xcount, int ycount) {
        _x = 0;
        _y = 0;
        _w = xcount;
        _h = ycount;
        _cellSize = cellSize;
        _cells = new Cell[_h][_w];
        
        for (int i = 0; i < _h; i++) {
          for (int j = 0; j < _w; j++) {
            Cell currentCell = new Cell(_cellSize, _cellSize);
            _cells[i][j] = currentCell;
            if (i != 0) {
              currentCell.setBottom(_cells[i-1][j]);
            }
            if (j != 0) {
              currentCell.setLeft(_cells[i][j-1]);
            }
          }
        }
      }
      void setX(int x) {_x = x;}
      int getX() {return _x;}
      
      void setY(int y) {_y = y;}
      int getY(){return _y;}
      
      int getCellSize(){return _cellSize;}
      
      void draw(){
        int dx = _x;
        int dy = _y;
        for (int i = 0; i < _h; i++) {
          dx = _x;
          for (int j = 0; j < _w; j++) {
            Cell cell = _cells[i][j];
            cell.draw(dx, dy);
            dx += _cellSize;
          }
          dy += _cellSize;
        }
      }
      Cell[][] getCells() {return _cells;}
      Cell getCell(int x, int y) {
          return _cells[y][x];
      }
      int getWidth() {return _w;}
      int getHeight() {return _h;}
    }
    
    class RdMaze {
      ArrayList _walls;
      ArrayList _wallBricks;
      ArrayList _init;
      int _frame = 0;
      boolean _inProcess = false;
      
      Grid _mainGrid;
      RdMaze(Grid grid){
        _mainGrid = grid;
        _init = new ArrayList();
        int w = grid.getWidth();
        int h = grid.getHeight();
        if ((w >= 3 && w % 2 == 1)&&(h >= 3 && h % 2 == 1)) {
          _walls = new ArrayList();
          _wallBricks = new ArrayList();
          _init.add(_mainGrid);
        } else {
          println("Insufficient ammount of cells or amound is even: w="+w+", h="+h+";");
        }
      }
      
      void generate(ArrayList grids) {
        println("I have "+grids.size()+" grids to process");
        for (int i = 0; i < grids.size(); i++) {
          Grid grid = (Grid)grids.get(i);
          if (isOk(grid)) {
            println("Splitting grid No "+(i+1)+": w="+grid.getWidth()+", h="+grid.getHeight()+";");
            generate(splitGrid(grid));
          } else {
            println("Cannot process grid w="+grid.getWidth()+", h="+grid.getHeight()+"; further");
          }
        }
      }
      
      ArrayList splitGrid(Grid grid) {
        ArrayList splits = new ArrayList();
        
        int cellSize = grid.getCellSize();
        int gridWidth = grid.getWidth();
        int gridHeight = grid.getHeight();
    
        if (grid.getWidth() > grid.getHeight()) {
          int xwall = int(random(1, gridWidth-1));
          xwall = xwall % 2 == 0 ? xwall-1 : xwall; // wall should start at even position
          int ywall = 0;
    
          int xoffset = int(abs(grid.getX()-_mainGrid.getX())/cellSize) + xwall;
          int yoffset = int(abs(grid.getY()-_mainGrid.getY())/cellSize) + ywall;
    
          println("Vertical border at: x="+xoffset+",y="+yoffset+", w="+gridWidth+";");
          _walls.add(new Wall(xoffset, yoffset, gridHeight, 'v'));
          
          Grid leftGrid = new Grid(cellSize, xwall, gridHeight);
          leftGrid.setX(grid.getX());
          leftGrid.setY(grid.getY());
          println("Left grid: w="+leftGrid.getWidth()+",h="+leftGrid.getHeight()+";");
    
          Grid rightGrid = new Grid(cellSize, gridWidth-xwall-1, gridHeight);
          rightGrid.setX(leftGrid.getX()+leftGrid.getWidth()*cellSize+cellSize);
          rightGrid.setY(grid.getY());
          println("Right grid: w="+rightGrid.getWidth()+",h="+rightGrid.getHeight()+";");
          
          splits.add(leftGrid);
          splits.add(rightGrid);
        } else {
          int ywall = int(random(1, gridHeight-1));
          ywall = ywall % 2 == 0 ? ywall-1 : ywall; // wall should start at even position
          int xwall = 0;
    
          int xoffset = int(abs(grid.getX()-_mainGrid.getX())/cellSize) + xwall;
          int yoffset = int(abs(grid.getY()-_mainGrid.getY())/cellSize) + ywall;
          
          println("Horizontal border at: x="+xoffset+",y="+yoffset+", w="+gridWidth+";");
          _walls.add(new Wall(xoffset, yoffset, gridWidth, 'h'));
    
          Grid topGrid = new Grid(cellSize, gridWidth, ywall);
          topGrid.setX(grid.getX());
          topGrid.setY(grid.getY());
          println("Top grid: w="+topGrid.getWidth()+",h="+topGrid.getHeight()+";");
          
          Grid bottomGrid = new Grid(cellSize, gridWidth, gridHeight-ywall-1);
          bottomGrid.setX(grid.getX());
          bottomGrid.setY(topGrid.getY()+topGrid.getHeight()*cellSize+cellSize);
          println("Bottom grid: w="+bottomGrid.getWidth()+",h="+bottomGrid.getHeight()+";");
          
          splits.add(topGrid);
          splits.add(bottomGrid);
        }
        return splits;
      }
      
      ArrayList setVerticalBorder(int x, int y, int h) {
        ArrayList borderCells = new ArrayList(h);
        for (int i = 0; i < h; i++) {
          println("   brick at x="+x+", y="+(y+i)+";");
          Cell cell = _mainGrid.getCell(x, y+i);
          cell.isWall = true;
          borderCells.add(cell);
        }
        return borderCells;
      }
    
      ArrayList setHorizontalBorder(int x, int y, int w) {
        ArrayList borderCells = new ArrayList(w);
        for (int i = 0; i < w; i++) {
          println("   brick at x="+(x+i)+", y="+y+";");
          Cell cell = _mainGrid.getCell(x+i, y);
          cell.isWall = true;
          borderCells.add(cell);
        }
        return borderCells;
      }
      
      void setGate(ArrayList wallBricks){
        int position = int(random(1, wallBricks.size()-1));
        position = position % 2 == 0 ? position : position-1;
        
        Cell gate = (Cell)wallBricks.get(position);
        gate.isWall = false;
      }
    
      boolean isOk(Grid grid) {
        return (grid.getWidth() > 1 && grid.getHeight() > 1);
      }
      
      void addBorders(Grid grid) {
        for (int i = 0; i < grid.getHeight(); i++) {
          Cell cell;
          cell = grid.getCell(0, i);
          cell.isWall = true;
          
          cell = grid.getCell(grid.getWidth()-1, i);
          cell.isWall = true;
        }
        for (int i = 0; i < grid.getWidth(); i++) {
          Cell cell;
          cell = grid.getCell(i, 0);
          cell.isWall = true;
          
          cell = grid.getCell(i, grid.getHeight()-1);
          cell.isWall = true;
        }
      }
      
      void draw() {
        if (!_inProcess) {
          _inProcess = true;
          println("Generating maze...");
          generate(_init);
          println("Done.");
        }
        if (_walls.size() > 0 || _wallBricks.size() > 0) {
          if (_frame % 2 == 0) { // Even frame - draw wall
            Wall wall = (Wall)_walls.remove(0);
            if (wall.type == 'h') {
              _wallBricks = setHorizontalBorder(wall.x, wall.y, wall.size);
            } else {
              _wallBricks = setVerticalBorder(wall.x, wall.y, wall.size);
            }
          } else { // Odd frame - draw gate
            setGate(_wallBricks);
            _wallBricks.clear();
          }
          _mainGrid.draw();
          _frame++;
        }
      }
    
    }
    
    class Wall {
      int x;
      int y;
      int size;
      char type;
      Wall(int x, int y, int size, char type) {
        this.x = x;
        this.y = y;
        this.size = size;
        this.type = type;
      }
    }
    
    RdMaze _rdMaze1;
    void setup(){
      frameRate(2);
      int cellSize = 12;
      int xcount = 51;
      int ycount = 41;
      size(xcount*cellSize, ycount*cellSize);
    
      Grid rdMazeGrid1 = new Grid(cellSize, xcount,ycount);
      rdMazeGrid1.setX(0);
      rdMazeGrid1.setY(0);
      _rdMaze1 = new RdMaze(rdMazeGrid1);
    }
    
    void draw(){
      _rdMaze1.draw();
    }
    

    code

    tweaks (0)

    about this sketch

    This sketch is running as Java applet, exported from Processing.

    license

    advertisement

    Bogdan Vatulya

    Recursive Division Maze

    Add to Faves Me Likey@!
    You must login/register to add this sketch to your favorites.

    Illustrates recursive divison method for maze generation

    Thang Phan
    8 Mar 2011
    Cool!
    Daniel Gutierrez
    25 Mar 2014
    yeah !
    You need to login/register to comment.