src

maze.js (11327B)

---

 /* eslint-disable no-bitwise, no-continue */
 import * as direction from '/static/js/minotaur/direction.js';
 
 // Maze represents a maze with:
 // - A player character, Theseus,
 // - An enemy, the Minotaur, which chases the player.
 // - An exit from the maze.
 export default class Maze {
   constructor({ canvas, padding = 1, side = 24 }) {
     this.canvas = canvas;
     this.exit = null;
     this.height = Math.floor((canvas.height - (padding * 2)) / side);
     this.layout = [];
     this.minotaur = null;
     this.side = side;
     this.solution = null;
     this.theseus = null;
     this.width = Math.floor((canvas.width - (padding * 2)) / side);
 
     // Generate the maze.
     for (let i = 0; i < this.height; i += 1) {
       this.layout[i] = [];
       for (let j = 0; j < this.width; j += 1) {
         this.layout[i][j] = 0;
       }
     }
     // Connect the cells.
     const stack = [{ x: 0, y: 0 }];
     const visited = { '0,0': true };
     while (stack.length > 0) {
       const current = stack[stack.length - 1];
       let found = false;
 
       const rd = direction.random();
       for (const d of rd) {
         // x and y are the coordinates of the neighboring cell.
         const { x, y } = this.coordinateAtDirection(current, d);
 
         // Ignore coordinates that are out of bounds.
         if (!this.inBounds({ x, y })) {
           continue;
         }
 
         // Check if we've already visited this cell.
         // If we have, skip it.
         const key = `${x},${y}`;
         if (visited[key]) continue;
 
         // If we've found a new cell, mark is at visited.
         // Throw it on the stack to continue generating from it.
         found = true;
         visited[key] = true;
         stack.push({ x, y });
 
         // Connect the cells.
         // Set the current cell.
         this.layout[current.y][current.x] |= d;
         // Set the neighbor.
         this.layout[y][x] |= direction.opposite(d);
 
         break;
       }
 
       // Remove expended cells.
       if (!found) stack.pop();
     }
 
     // Set the location of the maze exit.
     this.exit = this.randomCell();
 
     // Set the location of Theseus.
     this.theseus = this.randomCell();
 
     // Set the location of the Minotaur.
     this.minotaur = this.randomCell();
   }
 
   // clearEscapePath remove the maze solution.
   clearEscapePath() {
     this.solution = null;
   }
 
   // coordinateAtDirection returns the coordinates reached with the passed in
   // starting point and direction.
   coordinateAtDirection({ x, y }, d) {
     if (d === direction.up) return { x, y: y - 1 };
     if (d === direction.right) return { x: x + 1, y };
     if (d === direction.down) return { x, y: y + 1 };
     if (d === direction.left) return { x: x - 1, y };
 
     throw new Error(`unrecognized direction ${d}`);
   }
 
   // escaped returns whether Theseus has reached the exit.
   escaped() {
     if (this.exit.x !== this.theseus.x) return false;
     if (this.exit.y !== this.theseus.y) return false;
     return true;
   }
 
   // hasDir returns whether a particular cell has a connection to the
   // specified direction.
   hasDir({ x, y }, d) {
     return (this.layout[y][x] & d) !== 0;
   }
 
   // inBounds returns whether or not the provided coordinates exist in the maze.
   inBounds({ x, y }) {
     if (x < 0 || y < 0 || x >= this.width || y >= this.height) return false;
     return true;
   }
 
   // killed returns whether the Minotaur has reached Theseus.
   killed() {
     if (this.minotaur.x !== this.theseus.x) return false;
     if (this.minotaur.y !== this.theseus.y) return false;
     return true;
   }
 
   // openDirections returns the open directions for a cell.
   openDirections({ x, y }) {
     const directions = [];
 
     for (const d of direction.clockwise) {
       if (this.hasDir({ x, y }, d)) {
         directions.push(d);
       }
     }
 
     return directions;
   }
 
   // moveMinotaur sets the new location of the Minotaur.
   moveMinotaur() {
     // const dirs = this.openDirections(this.minotaur);
     // if (dirs.length === 1) { // Deadened
     //   this.lastPosition = this.minotaur;
     //   this.minotaur = this.coordinateAtDirection(this.minotaur, dirs[0]);
     //   return;
     // }
 
     // const randomDirections = dirs.sort(() => Math.random() - 0.5);
     // for (const d of randomDirections) {
     //   // Don't go to the last position.
     //   const next = this.coordinateAtDirection(this.minotaur, d);
     //   if (this.lastPosition.x === next.x && this.lastPosition.y === next.y) {
     //     continue;
     //   }
     //   // Go to the new direction.
     //   this.lastPosition = this.minotaur;
     //   this.minotaur = next;
     //   return;
     // }
 
     const { path } = this.solve({ start: this.minotaur, end: this.theseus });
     // Move the Minotaur to the next cell in the path.
     if (path && path.length >= 2) this.minotaur = path[1];
   }
 
   // moveTheseus moves Theseus in the provided direction, if it is valid.
   moveTheseus({ d }) {
     const next = this.coordinateAtDirection(this.theseus, d);
     const hasDir = this.hasDir(this.theseus, d);
     const inBounds = this.inBounds(next);
 
     if (hasDir && inBounds) this.theseus = next;
   }
 
   // randomCell returns a random cell in the maze.
   randomCell() {
     return {
       x: Math.floor(Math.random() * this.width),
       y: Math.floor(Math.random() * this.height),
     };
   }
 
   // render draws the maze onto the canvas.
   render() {
     const ctx = this.canvas.getContext('2d');
     const pad = Math.floor((this.canvas.width - (this.width * this.side)) / 2);
     const thickness = Math.floor(this.side / 5);
 
     // cellX and cellY track the top-right edge of the current cell to draw.
     let cellX = pad;
     let cellY = pad;
 
     // Clear the canvas.
     ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
 
     // Draw the bottom and right edges.
     // The top and left edges will be drawn per cell.
     ctx.strokeStyle = '#000000';
     ctx.lineWidth = thickness;
 
     // Bottom
     ctx.beginPath();
     ctx.moveTo(
       cellX - Math.floor(thickness / 2),
       cellY + (this.side * this.height),
     );
     ctx.lineTo(
       cellX + (this.side * this.width) + Math.floor(thickness / 2),
       cellY + (this.side * this.height),
     );
     ctx.stroke();
     // Right
     ctx.beginPath();
     ctx.moveTo(
       cellX + (this.side * this.width),
       cellY - Math.floor(thickness / 2),
     );
     ctx.lineTo(
       cellX + (this.side * this.width),
       cellY + (this.side * this.height),
     );
     ctx.stroke();
 
     // Draw the cells.
     for (let y = 0; y < this.height; y += 1) {
       for (let x = 0; x < this.width; x += 1) {
         const cell = this.layout[y][x];
 
         // Draw the cell borders.
         // A top edge will work as a bottom edge, except on the bottom row.
         // A left edge will work as a right edge, except on the right column.
         // We've handled the special cases above.
         ctx.strokeStyle = '#000000';
         ctx.lineWidth = thickness;
 
         // Top
         if ((cell & direction.up) === 0 || y === 0) {
           ctx.beginPath();
           ctx.moveTo(cellX, cellY);
           ctx.lineTo(cellX + this.side, cellY);
           ctx.stroke();
         }
 
         // Left
         if ((cell & direction.left) === 0 || x === 0) {
           ctx.beginPath();
           // Extend the edge on the upper-left cell to draw in the corner.
           if (y === 0) {
             ctx.moveTo(cellX, cellY - Math.floor(thickness / 2));
           } else {
             ctx.moveTo(cellX, cellY);
           }
           ctx.lineTo(cellX, cellY + this.side);
           ctx.stroke();
         }
 
         // Fill the cell area.
         ctx.beginPath();
         if (this.solution !== null && this.solution.cells[`${x},${y}`]) {
           ctx.fillStyle = '#4271ae';
         } else {
           ctx.fillStyle = '#efefef';
         }
         ctx.lineWidth = 1;
         ctx.rect(cellX, cellY, this.side, this.side);
         ctx.fill();
 
         // Extend the bottom right edge on cells connected down and right.
         // This needs to be done after the cell area is filled, or this
         // line will be drawn over.
         if ((cell & direction.down) !== 0 && (cell & direction.right) !== 0) {
           ctx.lineWidth = thickness;
           ctx.beginPath();
           ctx.moveTo(
             cellX + (this.side - Math.floor(thickness / 2)),
             cellY + this.side,
           );
           ctx.lineTo(cellX + this.side, cellY + this.side);
           ctx.stroke();
           ctx.lineWidth = 1;
         }
 
         // Draw special cell states -- exit, Theseus, Minotaur.
         // The order matters here -- if these overlap, they are drawn over
         // each other.
         if (x === this.exit.x && y === this.exit.y) {
           ctx.beginPath();
           ctx.fillStyle = '#718c00';
           ctx.rect(
             cellX + Math.floor(this.side / 4),
             cellY + Math.floor(this.side / 4),
             Math.floor(this.side / 2),
             Math.floor(this.side / 2),
           );
           ctx.fill();
         }
 
         // Draw Theseus.
         if (x === this.theseus.x && y === this.theseus.y) {
           ctx.beginPath();
           ctx.fillStyle = '#8959a8';
           ctx.arc(
             cellX + Math.floor(this.side / 2),
             cellY + Math.floor(this.side / 2),
             Math.floor(this.side / 4),
             0,
             Math.PI * 2,
           );
           ctx.fill();
         }
 
         // Draw the Minotaur.
         if (x === this.minotaur.x && y === this.minotaur.y) {
           ctx.beginPath();
           ctx.fillStyle = '#c82829';
           ctx.arc(
             cellX + Math.floor(this.side / 2),
             cellY + Math.floor(this.side / 2),
             Math.floor(this.side / 4),
             0,
             Math.PI * 2,
           );
           ctx.fill();
         }
 
         // Increment to the next cell.
         cellX += this.side;
       }
 
       // Increment to the next row.
       cellX = pad;
       cellY += this.side;
     }
   }
 
   // setEscapePath sets the solution for the maze.
   setEscapePath() {
     this.solution = this.solve({ start: this.theseus, end: this.exit });
   }
 
   // solve uses breadth-first search to find a path between start and end.
   solve({ start, end }) {
     const q = [{ path: [start] }];
 
     while (q.length > 0) {
       const search = q.shift();
       const { x, y } = search.path[search.path.length - 1];
 
       // If we've reach the end, we're done.
       if (x === end.x && y === end.y) {
         return {
           path: search.path,
           cells: search.path.reduce((acc, v) => { acc[`${v.x},${v.y}`] = true; return acc; }, {}),
         };
       }
 
       // Find the next cell.
       // If the cell is in bounds and not a backtrack, add it to the path.
       // Then, add the candidate path to the queue.
       const cell = this.layout[y][x];
       let previous = { x: null, y: null };
       if (search.path.length > 2) previous = search.path[search.path.length - 2];
 
       for (const d of direction.clockwise) {
         if ((cell & d) !== 0) {
           const next = this.coordinateAtDirection({ x, y }, d);
           const inBounds = this.inBounds(next);
           const notPrevious = !(next.x === previous.x && next.y === previous.y);
           if (inBounds && notPrevious) q.push({ path: [...search.path, next] });
         }
       }
     }
 
     return null;
   }
 }