Generating a maze with Javascript & Canvas

Question

I'm having a peculiar issue with a maze generation program I'm writing for my resume. I'm using canvas and the entire thing works perfectly, except it won't draw the square correctly in the end.

It works by using this object template:

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

And I use a depth first search to generate the maze. To break the walls, I detect where the neighbor is relative to the current tile and I shut the walls between them off.

For example, if I'm breaking a neighbor to the north, I'd do the following:

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

I triple checked with the google console and this part works fine. However, when I redraw it using the canvas, it doesn't remove the walls correctly, it looks like this:

Code from 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>

The gray lines shouldn't be there and I don't know why they are.

Answer 1

It's good to see others tackling maze generation! It's a lot of fun. :)

It looks like you're getting tripped up by swapping the row/column when you're drawing the maze. If you look in your redrawTiles function, you'll see that you're treating i as the row, and j as the column (because you're accessing the current tile as tiles[i][j], and drawBase sets up the array in row-major order).

However, drawCell expects the first parameter to be x (the column), rather than y (the row), but you're passing i (the row) as the first parameter. Thus, when you call drawCell, the row is being interpreted as the x-coordinate, and the column as the y-coordinate, rather than the other way around.

Swapping those first two arguments to drawCell fixes the issue. I would strongly recommend using variables named row and column, instead of i and j, and I'd also recommend standardizing all your functions so that if they declare row/column parameters, the row comes first, and then the column. That way you'll be less likely to trip over this issue.

Hope that helps!