Last active
July 2, 2021 06:55
-
-
Save Sheraff/062d97ce1eb34383bc09a2e72f9967a2 to your computer and use it in GitHub Desktop.
Find all reachable cells
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"scripts": [], | |
"styles": [], | |
"showConsole": true | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<canvas height="800" width="800"></canvas> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const canvas = document.querySelector('canvas') | |
const context = canvas.getContext('2d') | |
const grid = [ | |
['', '', '', '', '', '', '', '', '', '', '', '', '', '', 'x', ''], | |
['', '', '', '', '', 'x', '', '', '', '', '', '', '', '', 'x', ''], | |
['', '', 'x', '', '', '', '', '', '', '', '', '', '', '', 'x', ''], | |
['', '', '', '', '', 'p', '', '', 'x', '', '', '', '', '', 'x', ''], | |
['', '', '', '', '', '', '', '', '', '', '', '', '', '', 'x', ''], | |
['', '', '', 'x', '', 'x', 'x', '', '', '', '', '', '', '', 'x', ''], | |
['', '', '', '', '', 'x', '', 'x', '', '', '', '', '', '', 'x', ''], | |
['', '', 'x', '', '', 'x', 'x', 'x', '', '', '', '', '', '', 'x', ''], | |
['', '', '', '', '', '', '', '', '', '', '', '', '', 'x', '', ''], | |
['', '', '', '', '', '', '', '', '', '', '', '', '', '', '', ''], | |
['', '', '', '', '', '', '', '', '', '', '', '', '', '', '', ''], | |
['', '', '', '', '', '', '', '', '', '', '', '', '', '', '', ''], | |
['', '', '', '', '', '', '', '', '', '', '', '', 'x', 'x', 'x', 'x'], | |
['', '', '', '', '', '', '', '', '', '', '', '', 'x', '', '', ''], | |
['', '', '', '', '', '', '', '', '', '', '', '', 'x', '', '', ''], | |
['', '', '', '', '', '', '', '', '', '', '', 'x', '', '', '', ''], | |
] | |
const directions = [ | |
[0, -1], | |
[0, 1], | |
[-1, 0], | |
[1, 0], | |
] | |
const playerY = grid.findIndex(row => row.includes('p')) | |
const playerX = grid[playerY].indexOf('p') | |
draw(grid) | |
let foundOne = true | |
let loops = 0 | |
const list = [[playerX, playerY]] // list of current cells of interest | |
const tested = new Set([`${playerX},${playerY}`]) // list of already tested cells | |
;(async function () { | |
while (foundOne && list.length) { | |
await new Promise((resolve) => setTimeout(resolve, 100)) | |
foundOne = false | |
list.forEach((cell, index) => { | |
if(!cell) { | |
return | |
} | |
const [x, y] = cell | |
let foundNeighbor = false | |
directions.forEach(([i, j]) => { | |
loops++ | |
if (x + i < 0 || y + j < 0 || x + i === grid[0].length || y + j === grid.length) { | |
return | |
} | |
const key = `${x + i},${y + j}` | |
if (tested.has(key)) { | |
return | |
} | |
tested.add(key) | |
if (isReachable(grid, x + i, y + j)) { | |
foundNeighbor = true | |
grid[y + j][x + i] = 'r' | |
list.push([x + i, y + j]) | |
} | |
}) | |
list[index] = null | |
if (foundNeighbor) { | |
foundOne = true | |
} | |
}) | |
draw(grid) | |
} | |
console.log(`found in ${tested.size} tests (${loops} loops), for a grid size of ${grid.length * grid[0].length}`) | |
})() | |
function isReachable(grid, x, y) { | |
return !grid[y][x] | |
} | |
function draw(grid) { | |
const width = canvas.width / grid[0].length | |
const height = canvas.height / grid.length | |
const colors = { | |
x: 'red', | |
p: 'green', | |
r: 'blue' | |
} | |
const strokeColor = window.getComputedStyle(document.body).getPropertyValue('color') | |
context.clearRect(0, 0, canvas.width, canvas.height) | |
context.globalAlpha = 0.7 | |
context.strokeStyle = strokeColor | |
grid.forEach((row, y) => | |
row.forEach((cell, x) => { | |
if (cell) { | |
context.fillStyle = colors[cell] | |
context.fillRect(x * width, y * height, width, height); | |
} | |
context.strokeRect(x * width, y * height, width, height); | |
}) | |
) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
body { | |
margin: 10px; | |
} | |
canvas { | |
border: 1px solid currentColor; | |
width: calc(100vmin - 20px); | |
height: calc(100vmin - 20px); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment