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 }