递归分割迷宫算法路径被墙阻断问题及代码修改咨询

Looking at your recursive division maze code, the issue causing blocked paths comes from randomly choosing the skip cell instead of placing it in the exact middle of the divided section. This random placement can create walls that cut off the only possible path between sub-regions. Here's how to fix it:

Key Problem in Original Code #

In your current implementation, you use getRandomInt(startX+1, endX-1) and getRandomInt(startY+1, endY-1) to pick where to skip the wall. This can place the gap anywhere in the wall, which might not align with the middle of the adjacent sub-regions, leading to disconnected paths that have no valid route through.

Solution: Force the Skip Cell to Be in the Middle #

Instead of a random skip position, calculate the exact middle of the current section for the gap. This ensures the gap connects the two sub-regions properly without blocking the only path between them.

Specific Modifications Needed: #

• For horizontal walls: Calculate the middle Y position of the current section (between startY and endY) for the skip cell.
• For vertical walls: Calculate the middle X position of the current section (between startX and endX) for the skip cell.
• (Optional) You can keep the wall's position random to maintain maze variation—only the skip position needs to be fixed to the middle.

Modified Code #

export const recursiveDivision=(grid)=>{ 
  const visitedNodes=[]; 
  const height=grid.length; 
  const width=grid[0].length; 

  // Set up border walls
  for(let i=0;i<height;i++){ 
    const tempNode=grid[i][0],tempNode1=grid[i][width-1]; 
    tempNode.isWall=true; 
    tempNode1.isWall=true; 
    visitedNodes.push(tempNode); 
    visitedNodes.push(tempNode1); 
  } 
  for(let i=0;i<width;i++){ 
    const tempNode=grid[0][i],tempNode1=grid[height-1][i]; 
    tempNode.isWall=true; 
    tempNode1.isWall=true; 
    visitedNodes.push(tempNode); 
    visitedNodes.push(tempNode1); 
  } 

  recursiveDivisionMaze(grid,visitedNodes,1,height-2,1,width-2); 
  return visitedNodes; 
} 

function recursiveDivisionMaze(grid,visitedNodes,startX,endX,startY,endY){ 
  const height=endX-startX+1; 
  const width=endY-startY+1; 

  if(height<3 || width<3){ 
    return; 
  } 
  if (startX < 0 || startY < 0 || endX >= grid.length || endY >= grid[0].length || startX > endX || startY > endY) return; 

  const hOrV=getOrientation(height,width); 

  if(hOrV==='Horizontal'){ 
    // Keep wall position random for maze variation
    const wallX=getRandomInt(startX+1,endX-1); 
    // Calculate middle Y position for the skip cell
    const skipY=Math.floor((startY + endY)/2); 
    for(let wallY=startY;wallY<=endY;wallY++){ 
      if(wallY===skipY ){ 
        continue; 
      } 
      const node=grid[wallX][wallY]; 
      node.isWall=true; 
      visitedNodes.push(node); 
    } 
    recursiveDivisionMaze(grid,visitedNodes,startX,wallX-1,startY,endY); 
    recursiveDivisionMaze(grid,visitedNodes,wallX+1,endX,startY,endY); 
  } else if(hOrV==='Vertical'){ 
    // Keep wall position random for maze variation
    const wallY=getRandomInt(startY+1,endY-1); 
    // Calculate middle X position for the skip cell
    const skipX=Math.floor((startX + endX)/2); 
    for(let wallX=startX;wallX<=endX;wallX++){ 
      if(wallX===skipX){ 
        continue; 
      } 
      const node=grid[wallX][wallY]; 
      node.isWall=true; 
      visitedNodes.push(node); 
    } 
    recursiveDivisionMaze(grid,visitedNodes,startX,endX,startY,wallY-1); 
    recursiveDivisionMaze(grid,visitedNodes,startX,endX,wallY+1,endY); 
  }
}

Explanation #

• Middle Skip Calculation: Using Math.floor((start + end)/2) ensures the gap is exactly in the center of the wall, connecting the two sub-regions that the wall divides. This guarantees there's always a valid path between sections, eliminating blocked paths entirely.
• Wall Position Flexibility: I kept the wall's position random to maintain natural-looking maze variation, but if you prefer more structured, symmetric mazes, you can also set wallX/wallY to the middle of the section instead of using getRandomInt.

内容的提问来源于stack exchange，提问作者java-user