Home > Blockchain >  How can I change my DFS maze algorithm to generate more than one path/be not perfect?
How can I change my DFS maze algorithm to generate more than one path/be not perfect?

Time:05-26

So far I got an DFS maze algorithm that gets me and perfect maze with one path exactly. I was wondering how I could get more than one path to my end with little change. Should I just randomly remove walls? But the thing is that I do not want just empty squares with no walls at all...

Here's my algorithm so far:

private void computeMaze(){
    
        Random random = new Random();
        Stack<Block> stack = new Stack<Block>(); //Stack
        Block current = blocks[0][0]; //First cell is the current cell
        current.setVisited(true);     //Mark as accessed
        
        //Create a count; first cell has been accessed, if no unvisited cells left == 0
        int unVisitedCount=ROWS*COLS-1;
        
        //Create a list of neighbors
        List<Block> neighbors;
        Block next;
        
        while(unVisitedCount > 0) {
            //Find neighbor collection (unreachable)
            neighbors = current.findNeighbors();
            
            //If the current cell has unvisited neighbors then:
            if(neighbors.size() > 0) {
                //Randomly select a neighbor from this list
                int index = random.nextInt(neighbors.size()); 
                next = neighbors.get(index);
                
                //Stack the current cell
                stack.push(current);
                
                //Remove the walls between the current maze cell and the randomly selected neighbor cell
                this.removeWall(current,next);
                
                //Mark the neighbor cell as visited and use it as the current cell
                next.setVisited(true);
                current = next;
                
                //If an access is marked, the counter is decreased by 1
                unVisitedCount--;   
            }
            else if(stack.isEmpty() == false) {//If the current maze cell does not have an unreachable adjacent maze cell, and the stack is not empty
                /*
                    1.The maze unit at the top of the stack comes out of the stack
                    2.Make it the current maze unit
                */
                Block cell = stack.pop();
                current = cell;
            }
        }
    }

//Find neighbors as well as the getneighbors methods:

//Find out whether the current cell has an unreachable neighbor cell
    public List<Block> findNeighbors() {
        //The neighbors are divided into upper, lower, left and right
        List<Block> res = new ArrayList<Block>();
        
        Block top    = this.getNeighbor(0,false);
        Block right  = this.getNeighbor(1,false);
        Block bottom = this.getNeighbor(2,false);
        Block left   = this.getNeighbor(3,false);
        
        if(top != null){
            res.add(top);
        }
        if(right != null){
            res.add(right);
        }
        if(bottom != null){
            res.add(bottom);
        }
        if(left != null){
            res.add(left);
        }
        return res;//Return neighbor array
    }
    
    
    //Get neighbors according to direction
    public Block getNeighbor(int type,boolean lose_visited) {
        Block neighbor;
        int neighbor_i = 0, neighbor_j = 0;
        
        switch(type) {
            case 0:
                neighbor_i = this.i-1;
                neighbor_j = this.j;
                break;
            case 1:
                neighbor_i = this.i;
                neighbor_j = this.j 1;
                break;
            case 2:
                neighbor_i = this.i 1;
                neighbor_j = this.j;
                break;
            case 3:
                neighbor_i = this.i;
                neighbor_j = this.j-1;
                break;
        }
        

        Block[][] blocks = panel.blocks;
        //It's beyond the boundary, therefore no neighbor
        if(neighbor_i < 0 || neighbor_j < 0 || neighbor_i >= panel.ROWS || neighbor_j >= panel.COLS) {
            neighbor = null;
        }
        //The dimensions are permitted, neighbor is found
        else {
            //Find the neighbor, either top/bottom/left/right
            neighbor = blocks[neighbor_i][neighbor_j];
            //Judge whether it is accessed. If it is accessed, null is returned
            if(neighbor.visited && !lose_visited) {//lose_visited equals true to ignore access
                neighbor = null;
            }
        }
        return neighbor;
    }

CodePudding user response:

To make a maze with multiple solutions, you would want to remove walls that would connect the solution path to a non-solution path. That would then add that non-solution path to the alternate solutions.

You might also want to remove some walls between multiple non-solution paths just to make it interesting.

The question of leaving an empty area is more interesting. You can remove all 4 walls from a cell, if it is a 4-way junction, so you need to check that the neighbouring cells have walls connecting to the corners.

And then the question of is the removal trivial - is the connection close to the point where the 2 paths already junctioned?

  1. Identify all the wall sections that have that joining property,
  2. and don't lead to trivial solutions
  3. check that removing that wall section does not break the corners rule.
  4. Randomly select one
  5. Repeat until you have enough alternate solutions.
  • Related