Created
June 15, 2025 12:50
-
-
Save PhilippIRL/822d6f682a31fbc1795809c60037647e to your computer and use it in GitHub Desktop.
This file contains hidden or 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
| <!DOCTYPE html> | |
| <html lang="en"> | |
| <head> | |
| <meta charset="UTF-8"> | |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> | |
| <title>Document</title> | |
| </head> | |
| <body> | |
| <canvas id="content"></canvas> | |
| <style> | |
| html, body { | |
| background-color: #000; | |
| margin: 0; | |
| } | |
| body { | |
| overflow: hidden; | |
| } | |
| #content { | |
| width: 100vw; | |
| height: 100vh; | |
| } | |
| </style> | |
| <script> | |
| function addNode(graph) { | |
| graph.push([]) | |
| } | |
| function hasConnection(graph, n1, n2) { | |
| return graph[n1].includes(n2) | |
| } | |
| function addConnection(graph, n1, n2) { | |
| if(graph.length >= 2 && !hasConnection(graph, n1, n2)) { | |
| graph[n1].push(n2) | |
| graph[n2].push(n1) | |
| } | |
| } | |
| function createGridGraph(n) { | |
| const graph = [] | |
| const count = n ** 2 | |
| for(let i = 0; i < count; i++) { | |
| addNode(graph) | |
| } | |
| for(let i = 0; i < count; i++) { | |
| const x = i % n | |
| const y = Math.floor(i / n) | |
| if(x !== n - 1) { | |
| addConnection(graph, i, i + 1) | |
| } | |
| if(y !== n - 1) { | |
| addConnection(graph, i, i + n) | |
| } | |
| } | |
| return graph | |
| } | |
| function dfs(graph, source, randomize) { | |
| let adjList = graph.map(n => [...n]) | |
| if(randomize) { | |
| for(let nodeIndex = 0; nodeIndex < adjList.length; nodeIndex++) { | |
| adjList[nodeIndex] = adjList[nodeIndex].map(node => ({ node, weight: Math.random() })) | |
| .sort((a, b) => a.weight - b.weight) | |
| .map(({node}) => node) | |
| } | |
| } | |
| const visited = graph.map(n => n === source) | |
| const backPath = visited.map(isSource => isSource ? 0 : null) | |
| const stack = [source] | |
| while(stack.length > 0) { | |
| const top = stack[stack.length - 1] | |
| if(adjList[top].length > 0) { | |
| const neighbor = adjList[top].shift() | |
| if(!visited[neighbor]) { | |
| visited[neighbor] = true | |
| backPath[neighbor] = top | |
| stack.push(neighbor) | |
| } | |
| } else { | |
| stack.pop() | |
| } | |
| } | |
| return { visited, backPath } | |
| } | |
| function drawSquareGraph(graph, path) { | |
| const canvas = document.querySelector("#content") | |
| canvas.width = window.innerWidth * window.devicePixelRatio | |
| canvas.height = window.innerHeight * window.devicePixelRatio | |
| const ctx = canvas.getContext("2d") | |
| const vGraphSize = Math.sqrt(graph.length) | |
| const pNodeSpacing = Math.floor((Math.min(canvas.width, canvas.height) * 0.9) / vGraphSize) | |
| const pGraphSize = pNodeSpacing * (vGraphSize - 1) | |
| const pGraphStartX = Math.round((canvas.width / 2) - (pGraphSize / 2)) | |
| const pGraphStartY = Math.round((canvas.height / 2) - (pGraphSize / 2)) | |
| ctx.strokeStyle = "#fff" | |
| ctx.lineWidth = window.devicePixelRatio * 2; | |
| for(let nodeIndex = 0; nodeIndex < graph.length; nodeIndex++) { | |
| const vx1 = nodeIndex % vGraphSize | |
| const vy1 = Math.floor(nodeIndex / vGraphSize) | |
| const px1 = pGraphStartX + (vx1 * pNodeSpacing) | |
| const py1 = pGraphStartY + (vy1 * pNodeSpacing) | |
| const node = graph[nodeIndex] | |
| for(const otherNodeIndex of node) { | |
| if(otherNodeIndex > nodeIndex) continue // the bigger node always draws the connections | |
| const vx2 = otherNodeIndex % vGraphSize | |
| const vy2 = Math.floor(otherNodeIndex / vGraphSize) | |
| const px2 = pGraphStartX + (vx2 * pNodeSpacing) | |
| const py2 = pGraphStartY + (vy2 * pNodeSpacing) | |
| ctx.beginPath() | |
| ctx.moveTo(px1, py1) | |
| ctx.lineTo(px2, py2) | |
| ctx.stroke() | |
| } | |
| } | |
| if(path) { | |
| ctx.strokeStyle = "#f00" | |
| ctx.beginPath() | |
| for(const pathIndex in path) { | |
| const nodeIndex = path[pathIndex] | |
| const vx = nodeIndex % vGraphSize | |
| const vy = Math.floor(nodeIndex / vGraphSize) | |
| const px = pGraphStartX + (vx * pNodeSpacing) | |
| const py = pGraphStartY + (vy * pNodeSpacing) | |
| if(pathIndex === 0) { | |
| ctx.moveTo(px, py) | |
| } else { | |
| ctx.lineTo(px, py) | |
| } | |
| } | |
| ctx.stroke() | |
| } | |
| } | |
| function drawRandowMazeWithPath(n) { | |
| const nodeCount = n ** 2 | |
| const baseGraph = createGridGraph(n) | |
| const graph = [] | |
| for(let i = 0; i < nodeCount; i++) { | |
| addNode(graph) | |
| } | |
| const { backPath: mazePaths } = dfs(baseGraph, 0, true) | |
| for(let nodeIndex = 0; nodeIndex < mazePaths.length; nodeIndex++) { | |
| const relevantNeighbor = mazePaths[nodeIndex] | |
| addConnection(graph, nodeIndex, relevantNeighbor) | |
| } | |
| const pathTo = nodeCount - 1 | |
| const { visited, backPath } = dfs(graph, pathTo, false) | |
| let path = null | |
| if(visited[pathTo]) { | |
| path = [0] | |
| while(path[path.length - 1] !== pathTo) { | |
| path.push(backPath[path[path.length - 1]]) | |
| } | |
| } | |
| drawSquareGraph(graph, path) | |
| } | |
| let size = 2 | |
| setInterval(() => { | |
| drawRandowMazeWithPath(++size) | |
| }, 1000) | |
| drawRandowMazeWithPath(size) | |
| </script> | |
| </body> | |
| </html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment