src

Go monorepo.
git clone git://code.dwrz.net/src
Log | Files | Refs

maze.js (11327B)


      1 /* eslint-disable no-bitwise, no-continue */
      2 import * as direction from '/static/js/minotaur/direction.js';
      3 
      4 // Maze represents a maze with:
      5 // - A player character, Theseus,
      6 // - An enemy, the Minotaur, which chases the player.
      7 // - An exit from the maze.
      8 export default class Maze {
      9   constructor({ canvas, padding = 1, side = 24 }) {
     10     this.canvas = canvas;
     11     this.exit = null;
     12     this.height = Math.floor((canvas.height - (padding * 2)) / side);
     13     this.layout = [];
     14     this.minotaur = null;
     15     this.side = side;
     16     this.solution = null;
     17     this.theseus = null;
     18     this.width = Math.floor((canvas.width - (padding * 2)) / side);
     19 
     20     // Generate the maze.
     21     for (let i = 0; i < this.height; i += 1) {
     22       this.layout[i] = [];
     23       for (let j = 0; j < this.width; j += 1) {
     24         this.layout[i][j] = 0;
     25       }
     26     }
     27     // Connect the cells.
     28     const stack = [{ x: 0, y: 0 }];
     29     const visited = { '0,0': true };
     30     while (stack.length > 0) {
     31       const current = stack[stack.length - 1];
     32       let found = false;
     33 
     34       const rd = direction.random();
     35       for (const d of rd) {
     36         // x and y are the coordinates of the neighboring cell.
     37         const { x, y } = this.coordinateAtDirection(current, d);
     38 
     39         // Ignore coordinates that are out of bounds.
     40         if (!this.inBounds({ x, y })) {
     41           continue;
     42         }
     43 
     44         // Check if we've already visited this cell.
     45         // If we have, skip it.
     46         const key = `${x},${y}`;
     47         if (visited[key]) continue;
     48 
     49         // If we've found a new cell, mark is at visited.
     50         // Throw it on the stack to continue generating from it.
     51         found = true;
     52         visited[key] = true;
     53         stack.push({ x, y });
     54 
     55         // Connect the cells.
     56         // Set the current cell.
     57         this.layout[current.y][current.x] |= d;
     58         // Set the neighbor.
     59         this.layout[y][x] |= direction.opposite(d);
     60 
     61         break;
     62       }
     63 
     64       // Remove expended cells.
     65       if (!found) stack.pop();
     66     }
     67 
     68     // Set the location of the maze exit.
     69     this.exit = this.randomCell();
     70 
     71     // Set the location of Theseus.
     72     this.theseus = this.randomCell();
     73 
     74     // Set the location of the Minotaur.
     75     this.minotaur = this.randomCell();
     76   }
     77 
     78   // clearEscapePath remove the maze solution.
     79   clearEscapePath() {
     80     this.solution = null;
     81   }
     82 
     83   // coordinateAtDirection returns the coordinates reached with the passed in
     84   // starting point and direction.
     85   coordinateAtDirection({ x, y }, d) {
     86     if (d === direction.up) return { x, y: y - 1 };
     87     if (d === direction.right) return { x: x + 1, y };
     88     if (d === direction.down) return { x, y: y + 1 };
     89     if (d === direction.left) return { x: x - 1, y };
     90 
     91     throw new Error(`unrecognized direction ${d}`);
     92   }
     93 
     94   // escaped returns whether Theseus has reached the exit.
     95   escaped() {
     96     if (this.exit.x !== this.theseus.x) return false;
     97     if (this.exit.y !== this.theseus.y) return false;
     98     return true;
     99   }
    100 
    101   // hasDir returns whether a particular cell has a connection to the
    102   // specified direction.
    103   hasDir({ x, y }, d) {
    104     return (this.layout[y][x] & d) !== 0;
    105   }
    106 
    107   // inBounds returns whether or not the provided coordinates exist in the maze.
    108   inBounds({ x, y }) {
    109     if (x < 0 || y < 0 || x >= this.width || y >= this.height) return false;
    110     return true;
    111   }
    112 
    113   // killed returns whether the Minotaur has reached Theseus.
    114   killed() {
    115     if (this.minotaur.x !== this.theseus.x) return false;
    116     if (this.minotaur.y !== this.theseus.y) return false;
    117     return true;
    118   }
    119 
    120   // openDirections returns the open directions for a cell.
    121   openDirections({ x, y }) {
    122     const directions = [];
    123 
    124     for (const d of direction.clockwise) {
    125       if (this.hasDir({ x, y }, d)) {
    126         directions.push(d);
    127       }
    128     }
    129 
    130     return directions;
    131   }
    132 
    133   // moveMinotaur sets the new location of the Minotaur.
    134   moveMinotaur() {
    135     // const dirs = this.openDirections(this.minotaur);
    136     // if (dirs.length === 1) { // Deadened
    137     //   this.lastPosition = this.minotaur;
    138     //   this.minotaur = this.coordinateAtDirection(this.minotaur, dirs[0]);
    139     //   return;
    140     // }
    141 
    142     // const randomDirections = dirs.sort(() => Math.random() - 0.5);
    143     // for (const d of randomDirections) {
    144     //   // Don't go to the last position.
    145     //   const next = this.coordinateAtDirection(this.minotaur, d);
    146     //   if (this.lastPosition.x === next.x && this.lastPosition.y === next.y) {
    147     //     continue;
    148     //   }
    149     //   // Go to the new direction.
    150     //   this.lastPosition = this.minotaur;
    151     //   this.minotaur = next;
    152     //   return;
    153     // }
    154 
    155     const { path } = this.solve({ start: this.minotaur, end: this.theseus });
    156     // Move the Minotaur to the next cell in the path.
    157     if (path && path.length >= 2) this.minotaur = path[1];
    158   }
    159 
    160   // moveTheseus moves Theseus in the provided direction, if it is valid.
    161   moveTheseus({ d }) {
    162     const next = this.coordinateAtDirection(this.theseus, d);
    163     const hasDir = this.hasDir(this.theseus, d);
    164     const inBounds = this.inBounds(next);
    165 
    166     if (hasDir && inBounds) this.theseus = next;
    167   }
    168 
    169   // randomCell returns a random cell in the maze.
    170   randomCell() {
    171     return {
    172       x: Math.floor(Math.random() * this.width),
    173       y: Math.floor(Math.random() * this.height),
    174     };
    175   }
    176 
    177   // render draws the maze onto the canvas.
    178   render() {
    179     const ctx = this.canvas.getContext('2d');
    180     const pad = Math.floor((this.canvas.width - (this.width * this.side)) / 2);
    181     const thickness = Math.floor(this.side / 5);
    182 
    183     // cellX and cellY track the top-right edge of the current cell to draw.
    184     let cellX = pad;
    185     let cellY = pad;
    186 
    187     // Clear the canvas.
    188     ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
    189 
    190     // Draw the bottom and right edges.
    191     // The top and left edges will be drawn per cell.
    192     ctx.strokeStyle = '#000000';
    193     ctx.lineWidth = thickness;
    194 
    195     // Bottom
    196     ctx.beginPath();
    197     ctx.moveTo(
    198       cellX - Math.floor(thickness / 2),
    199       cellY + (this.side * this.height),
    200     );
    201     ctx.lineTo(
    202       cellX + (this.side * this.width) + Math.floor(thickness / 2),
    203       cellY + (this.side * this.height),
    204     );
    205     ctx.stroke();
    206     // Right
    207     ctx.beginPath();
    208     ctx.moveTo(
    209       cellX + (this.side * this.width),
    210       cellY - Math.floor(thickness / 2),
    211     );
    212     ctx.lineTo(
    213       cellX + (this.side * this.width),
    214       cellY + (this.side * this.height),
    215     );
    216     ctx.stroke();
    217 
    218     // Draw the cells.
    219     for (let y = 0; y < this.height; y += 1) {
    220       for (let x = 0; x < this.width; x += 1) {
    221         const cell = this.layout[y][x];
    222 
    223         // Draw the cell borders.
    224         // A top edge will work as a bottom edge, except on the bottom row.
    225         // A left edge will work as a right edge, except on the right column.
    226         // We've handled the special cases above.
    227         ctx.strokeStyle = '#000000';
    228         ctx.lineWidth = thickness;
    229 
    230         // Top
    231         if ((cell & direction.up) === 0 || y === 0) {
    232           ctx.beginPath();
    233           ctx.moveTo(cellX, cellY);
    234           ctx.lineTo(cellX + this.side, cellY);
    235           ctx.stroke();
    236         }
    237 
    238         // Left
    239         if ((cell & direction.left) === 0 || x === 0) {
    240           ctx.beginPath();
    241           // Extend the edge on the upper-left cell to draw in the corner.
    242           if (y === 0) {
    243             ctx.moveTo(cellX, cellY - Math.floor(thickness / 2));
    244           } else {
    245             ctx.moveTo(cellX, cellY);
    246           }
    247           ctx.lineTo(cellX, cellY + this.side);
    248           ctx.stroke();
    249         }
    250 
    251         // Fill the cell area.
    252         ctx.beginPath();
    253         if (this.solution !== null && this.solution.cells[`${x},${y}`]) {
    254           ctx.fillStyle = '#4271ae';
    255         } else {
    256           ctx.fillStyle = '#efefef';
    257         }
    258         ctx.lineWidth = 1;
    259         ctx.rect(cellX, cellY, this.side, this.side);
    260         ctx.fill();
    261 
    262         // Extend the bottom right edge on cells connected down and right.
    263         // This needs to be done after the cell area is filled, or this
    264         // line will be drawn over.
    265         if ((cell & direction.down) !== 0 && (cell & direction.right) !== 0) {
    266           ctx.lineWidth = thickness;
    267           ctx.beginPath();
    268           ctx.moveTo(
    269             cellX + (this.side - Math.floor(thickness / 2)),
    270             cellY + this.side,
    271           );
    272           ctx.lineTo(cellX + this.side, cellY + this.side);
    273           ctx.stroke();
    274           ctx.lineWidth = 1;
    275         }
    276 
    277         // Draw special cell states -- exit, Theseus, Minotaur.
    278         // The order matters here -- if these overlap, they are drawn over
    279         // each other.
    280         if (x === this.exit.x && y === this.exit.y) {
    281           ctx.beginPath();
    282           ctx.fillStyle = '#718c00';
    283           ctx.rect(
    284             cellX + Math.floor(this.side / 4),
    285             cellY + Math.floor(this.side / 4),
    286             Math.floor(this.side / 2),
    287             Math.floor(this.side / 2),
    288           );
    289           ctx.fill();
    290         }
    291 
    292         // Draw Theseus.
    293         if (x === this.theseus.x && y === this.theseus.y) {
    294           ctx.beginPath();
    295           ctx.fillStyle = '#8959a8';
    296           ctx.arc(
    297             cellX + Math.floor(this.side / 2),
    298             cellY + Math.floor(this.side / 2),
    299             Math.floor(this.side / 4),
    300             0,
    301             Math.PI * 2,
    302           );
    303           ctx.fill();
    304         }
    305 
    306         // Draw the Minotaur.
    307         if (x === this.minotaur.x && y === this.minotaur.y) {
    308           ctx.beginPath();
    309           ctx.fillStyle = '#c82829';
    310           ctx.arc(
    311             cellX + Math.floor(this.side / 2),
    312             cellY + Math.floor(this.side / 2),
    313             Math.floor(this.side / 4),
    314             0,
    315             Math.PI * 2,
    316           );
    317           ctx.fill();
    318         }
    319 
    320         // Increment to the next cell.
    321         cellX += this.side;
    322       }
    323 
    324       // Increment to the next row.
    325       cellX = pad;
    326       cellY += this.side;
    327     }
    328   }
    329 
    330   // setEscapePath sets the solution for the maze.
    331   setEscapePath() {
    332     this.solution = this.solve({ start: this.theseus, end: this.exit });
    333   }
    334 
    335   // solve uses breadth-first search to find a path between start and end.
    336   solve({ start, end }) {
    337     const q = [{ path: [start] }];
    338 
    339     while (q.length > 0) {
    340       const search = q.shift();
    341       const { x, y } = search.path[search.path.length - 1];
    342 
    343       // If we've reach the end, we're done.
    344       if (x === end.x && y === end.y) {
    345         return {
    346           path: search.path,
    347           cells: search.path.reduce((acc, v) => { acc[`${v.x},${v.y}`] = true; return acc; }, {}),
    348         };
    349       }
    350 
    351       // Find the next cell.
    352       // If the cell is in bounds and not a backtrack, add it to the path.
    353       // Then, add the candidate path to the queue.
    354       const cell = this.layout[y][x];
    355       let previous = { x: null, y: null };
    356       if (search.path.length > 2) previous = search.path[search.path.length - 2];
    357 
    358       for (const d of direction.clockwise) {
    359         if ((cell & d) !== 0) {
    360           const next = this.coordinateAtDirection({ x, y }, d);
    361           const inBounds = this.inBounds(next);
    362           const notPrevious = !(next.x === previous.x && next.y === previous.y);
    363           if (inBounds && notPrevious) q.push({ path: [...search.path, next] });
    364         }
    365       }
    366     }
    367 
    368     return null;
    369   }
    370 }