javascript - 使用 Javascript 和 Canvas 生成迷宫

Question

我在为简历编写的迷宫生成程序中遇到了一个特殊问题。我正在使用 canvas 并且整个事情都完美无缺，只是它最终无法正确绘制正方形。

它通过使用这个对象模板来工作:

{row:nRow,
 col:nCol, 
 visited:false, 
 left:true, 
 right:true, 
 top:true, 
 bottom:true};

我使用深度优先搜索来生成迷宫。为了打破墙壁，我检测到邻居相对于当前瓷砖的位置，然后关闭它们之间的墙壁。

例如，如果我要破坏北面的邻居，我会执行以下操作:

   currentTile.top = false;
   neighbor.bottom = false;

我用谷歌控制台进行了三重检查，这部分工作正常。但是，当我使用 Canvas 重绘它时，它没有正确移除墙壁，它看起来像这样:

代码来自 GitHub :

      var canvas;
      var ctx;
      var tiles = [];
      var visitedStk = [];

      init();

      function createPoint(nRow, nCol) {
        /*Cell class*/
        var obj = {
          row: nRow,
          col: nCol,
          visited: false,
          left: true,
          right: true,
          top: true,
          bottom: true
        };
        return obj;
      }

      function init() {
        /*Initialize needed variables. */
        $("#newMazeBtn").click(reDrawMaze);
        canvas = $("#mazeCanvas")[0];
        ctx = canvas.getContext("2d");
        drawBase();

      }

      function drawLine(sX, sY, eX, eY) {
        /*Draw a line from the starting X and Y positions to  the ending X and Y positions*/
        ctx.moveTo(sX, sY);
        ctx.lineTo(eX, eY);
      }

      function drawCell(x, y, side, tile) {
        /* Draw cell based on wall properties */
        var left = tile.left;
        var right = tile.right;
        var top = tile.top;
        var bottom = tile.bottom;
        var size = 25;
        ctx.beginPath();
        if (left) {
          drawLine(x, y, x, y + size);
        }

        if (right) {
          drawLine(x + size, y, x + size, y + size);
        }

        if (bottom) {
          drawLine(x, y + size, x + size, y + size)
        }

        if (top) {
          drawLine(x, y, x + size, y);
        }
        ctx.stroke();
      }

      function drawBase() {
        /* Draw the tiles on the canvas*/
        var side = 25;
        for (var i = 0; i < 10; i++) {
          tiles[i] = [];
          for (var j = 0; j < 10; j++) {
            tiles[i].push(createPoint(i, j));
            drawCell(i * side, j * side, side, tiles[i][j]);
          }
        }
        generateMaze(0, 0);
      }

      function clearCanvas() {
        ctx.clearRect(0, 0, canvas.width, canvas.height);
      }

      function redrawTiles() {
        var currentTile;
        clearCanvas();
        var side = 25;
        for (var i = 0; i < 10; i++) {
          for (var j = 0; j < 10; j++) {
            currentTile = tiles[i][j];
            drawCell(i * side, j * side, side, currentTile);
          }
        }
      }

      function reDrawMaze() {
        /*Button Handle for 'New Maze' */
        var startCol = Math.floor(Math.random() * 10) - 1;
        var startRow = Math.floor(Math.random() * 10) - 1;
        clearCanvas();
        drawBase();
      }

      function generateMaze(row, col) {
        /* Depth First Search*/
        var currentTile = tiles[row][col];
        var neighbor = findNeighbor(row, col);
        /*Check if cell has been visited */
        if (!currentTile.visited) {
          currentTile.visited = true;
          visitedStk.push(currentTile);
        }
        /* Break Case */
        if (visitedStk.length == 0) {
          redrawTiles();
          return;
        }
        /*If a neighbor is found*/
        else if (neighbor !== undefined) {
          /*Break the wall in between*/
          if (neighbor.row > currentTile.row) { /*Bottom*/
            currentTile.bottom = false;
            neighbor.top = false;
          }
          if (neighbor.row < currentTile.row) { /*Top*/
            currentTile.top = false;
            neighbor.bottom = false;
          }
          if (neighbor.col < currentTile.col) { /*Left*/
            currentTile.left = false;
            neighbor.right = false;
          }
          if (neighbor.col > currentTile.col) { /*Right*/
            currentTile.right = false;
            neighbor.left = false;
          }
          /*Update Current Tile*/
          currentTile = neighbor;
        }
        /*If no neighbor was found, backtrack to a previous cell on the stacke*/
        else {
          var backtrack = visitedStk.pop();
          generateMaze(backtrack.row, backtrack.col);
          currentTile = backtrack;
        }
        generateMaze(currentTile.row, currentTile.col);
      }

      function findNeighbor(row, col) {
        /*Find the neighbor of the given tile using the tiles array.*/
        var top, bottom, left, right;
        var stk = []
        var neighbor = undefined;
        var n;
        /* Check for left neighbor */
        if (row >= 0 && col > 0) {
          left = tiles[row][col - 1];
          (!left.visited) ? stk.push(left): undefined
        }

        /* Check for right neighbor */
        if (row >= 0 && col < 9) {
          right = tiles[row][col + 1];
          (!right.visited) ? stk.push(right): undefined;
        }

        /* Check for top neighbor */
        if (col >= 0 && row > 0) {
          top = tiles[row - 1][col];
          (!top.visited) ? stk.push(top): undefined
        }
        /* Check for bottom neighbor */
        if (col >= 0 && row < 9) {
          bottom = tiles[row + 1][col];
          (!bottom.visited) ? stk.push(bottom): undefined
        }


        var len;
        while (stk.length > 0) {
          /* Choose a random neighbor */
          len = stk.length;
          n = Math.floor(Math.random() * stk.length);
          neighbor = stk[n];
          if (!neighbor.visited) {
            break;
          } else {
            stk.splice(n, 1);
          }
        }
        /*Return, will return undefined if no neighbor is found*/
        return neighbor;
      }

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.2/jquery.min.js"></script>

<div id="maze" style="width:500px; margin:0 auto;">
  <canvas id="mazeCanvas" width="550" height="550"></canvas>
</div>
<div id="buttons">
  <hr />
  <button id="newMazeBtn">New Maze</button>
  <button id="aboutBtn">About</button>
</div>

灰线不应该在那里，我不知道为什么会这样。

Answer 1

很高兴看到其他人解决迷宫生成问题!其乐无穷。 :)

看起来您在绘制迷宫时因交换行/列而被绊倒了。如果查看 redrawTiles 函数，您会发现您将 i 视为行，将 j 视为列(因为您正在访问当前图 block 作为 tiles[i][j]，并且 drawBase 以行优先顺序设置数组)。

但是，drawCell 期望第一个参数是 x(列)，而不是 y( 行)，但您将i(行)作为第一个参数传递。因此，当您调用 drawCell 时，行被解释为 x 坐标，列被解释为 y 坐标，而不是相反。

将前两个参数交换到 drawCell 可以解决这个问题。我强烈建议使用名为 row 和 column 的变量，而不是 i 和 j，我也会建议标准化所有函数，这样如果它们声明行/列参数，则行在前，然后是列。这样你就不太可能被这个问题绊倒。

希望对您有所帮助!