2b:null 2c:["$","title",null,{"children":"Maze Solver | Northeastern University John A. Guerra Gomez classes | Observable"}] 31:T424,### [Observable youtube Click Me](https://www.youtube.com/watch?v=2x2-F4EF3G0) ## Objective This notebook provides two types of maze: the markdown maze and the canvas maze. The maze generator facilitates learning matrix operations, dynamic programming, DFS, and BFS algorithms by visually illustrating step-by-step changes in the matrix. ## How it can be used ~~~ import {makeMaze, visit, renderMaze, mazeSolver} from "b34a8911dc26c518" ~~~ Rerun the generateMaze to regenerate the maze. This provides function to create maze, mark the maze cell visited, and render the maze. The mazeSolver solve the maze using bfs. ## Interaction Input the start and the end position, drag the step to view the change steps. ## The markdown matrix The wall is marked as '#', walkable cells are marked as 'o', and the current step is marked as '*'. This visualizes the BFS way of solving the matrix from the start point to the end point. ## The Canvas Maze Visualize the maze in canvas and the steps from start position to the end. The user can click refresh to restart.32:T68f,function* mazeSolver(matrix, start, end) { let M = matrix; yield M; const queue = [[start, []]]; // Initialize queue with start position and an empty path const visited = new Set([start.toString()]); // Keep track of visited positions while (queue.length > 0) { const [current, path] = queue.shift(); const [x, y] = current; M = markCur(current, M); yield M; // Check if is the destination if (x === end[0] && y === end[1]) { return path.concat([current]); // Return the shortest path } const neighbors = getNeighbors(matrix, current); for (const neighbor of neighbors) { const [nx, ny] = neighbor; if (!visited.has(neighbor.toString())) { visited.add(neighbor.toString()); // Mark the neighbor as visited queue.push([neighbor, path.concat([current])]); } } } M.explanation = "No path is found." // If no path is found, return null return null; function getNeighbors(matrix,[x,y]) { const neighbors = []; const directions = [ [-1, 0], [1, 0], [0, -1], [0, 1] ]; // Up, down, left, right for (const [dx, dy] of directions) { const nx = x + dx; const ny = y + dy; // Check if the neighbor is within the bounds of the matrix and is not a wall if ( nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length && matrix[nx][ny] === 'o' ) { neighbors.push([nx, ny]); } } return neighbors; } function markCur(cur, matrix) { let newM = deepCopy(matrix); const [row, col] = cur; newM[row][col] = "*"; return newM; } }33:T70f,aStarFunc = { async function* aStar(start, goal, grid) { const openSet = new PriorityQueue(); const cameFrom = {}; const gScore = {}; const fScore = {}; gScore[start] = 0; fScore[start] = manhattanDistance(start, goal); openSet.enqueue(start, fScore[start]); while (!openSet.isEmpty()) { await Promises.tick(1000) const current = openSet.dequeue(); if (current.x === goal.x && current.y === goal.y) { return reconstructPath(cameFrom, goal); } visit(grid,current.x,current.y); yield grid; for (const neighbor of getNeighbors(current, grid)) { const tentativeGScore = gScore[current] + 1; // Assuming edge weight of 1 if (tentativeGScore < (gScore[neighbor] || Infinity)) { cameFrom[neighbor] = current; gScore[neighbor] = tentativeGScore; fScore[neighbor] = gScore[neighbor] + manhattanDistance(neighbor, goal); if (!openSet.elements.find(el => el.element.x === neighbor.x && el.element.y === neighbor.y)) { openSet.enqueue(neighbor, fScore[neighbor]); } } } } return null; // Path not found } function reconstructPath(cameFrom, current) { const totalPath = [current]; while (cameFrom[current]) { current = cameFrom[current]; totalPath.unshift(current); } return totalPath; } function getNeighbors(node, grid) { const neighbors = []; const directions = [ [1, 0], [-1, 0], [0, 1], [0, -1] // Assuming 4-connectivity ]; for (const dir of directions) { const newRow = node.x + dir[0]; const newCol = node.y + dir[1]; if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid[0].length && grid[newRow][newCol] === 0) { neighbors.push({ x: newRow, y: newCol }); } } return neighbors; } return aStar; }34:T5cc,function renderMaze(maze, context) { let size = width < height ? width : height let sideLength = size / maze.length for (let y = 0; y < maze.length; y++) { for (let x = 0; x < maze[y].length; x++) { const padding = 4 if (maze[y][x].visiting) { context.fillStyle = 'rgba(0, 0, 0, 0.2)' context.fillRect( x * sideLength + padding, y * sideLength + padding, sideLength - 2 * padding, sideLength - 2 * padding ) } if (maze[y][x].visited) { context.strokeStyle = 'rgba(0, 0, 0, 1)' context.strokeRect( x * sideLength + padding, y * sideLength + padding, sideLength - 2 * padding, sideLength - 2 * padding ) } context.beginPath() if (!maze[y][x].north) { context.moveTo(x * sideLength, y * sideLength) context.lineTo((x + 1) * sideLength, y * sideLength) } if (!maze[y][x].south) { context.moveTo(x * sideLength, (y + 1) * sideLength) context.lineTo((x + 1) * sideLength, (y + 1) * sideLength) } if (!maze[y][x].east) { context.moveTo((x + 1) * sideLength, y * sideLength) context.lineTo((x + 1) * sideLength, (y + 1) * sideLength) } if (!maze[y][x].west) { context.moveTo(x * sideLength, y * sideLength) context.lineTo(x * sideLength, (y + 1) * sideLength) } context.stroke() } } } 35:[] 2f:{"id":"b34a8911dc26c518","slug":null,"title":"Maze Solver","thumbnail":"4a6f37307afe8ceb9a065e9590b36351608afe1943ec7d7525624361d55b5cff","access_level":"public","create_time":"$D2024-04-22T02:16:25.441Z","update_time":"$D2024-04-25T07:38:22.174Z","view_time":null,"first_public_time":"$D2024-04-26T16:08:23.979Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"afbaa6d30585fd36","login":"nujguerra","name":"Northeastern University John A. Guerra Gomez classes","avatar_url":"https://avatars-next.observableusercontent.com/04e5ef72b3edcda1296894b5d1ecaa9c92ef5d52d69e65e4c115de5534928fe9","tier":"education_2026","bio":""},"version":201,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"2cd043ecf07b70d7","login":"william-qiao","name":"William Qiao","avatar_url":"https://avatars-next.observableusercontent.com/f0d51d96cdd46b1dd35f603a9bd82d25dfe270500c839e9cc382c1f7b44e78c1","tier":null,"bio":""}],"members":[{"type":"team","id":"afbaa6d30585fd36","login":"nujguerra","name":"Northeastern University John A. Guerra Gomez classes","avatar_url":"https://avatars-next.observableusercontent.com/04e5ef72b3edcda1296894b5d1ecaa9c92ef5d52d69e65e4c115de5534928fe9","tier":"education_2026","role":"editor"},{"type":"individual","id":"2cd043ecf07b70d7","login":"william-qiao","name":"William Qiao","avatar_url":"https://avatars-next.observableusercontent.com/f0d51d96cdd46b1dd35f603a9bd82d25dfe270500c839e9cc382c1f7b44e78c1","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Maze Solver","cells":[{"id":189,"value":"md`# Maze Solver`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"$31","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":52,"value":"viewof startRow = Inputs.number({label:\"start X\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"viewof startCol = Inputs.number({label:\"start Y\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"viewof endRow = Inputs.number({label:\"End X\"})\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"viewof endCol = Inputs.number({label:\"End Y\"})\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"viewof step = Inputs.range([0,mazeHistory.length-1],{step:1,label:\"Maze solver step\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"showMatrix(mazeHistory[step])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"## Generate Maze","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":29,"value":"matrix = {\n const mazeSize = Math.max(endRow,endCol);\n return generateMaze(mazeSize,mazeSize);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"## Maze History","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":39,"value":"mazeHistory=[...mazeSolver(matrix.slice(1),[0,0],[matrix.length-1,matrix[0].length-1])];","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"function generateMaze(rows, cols) {\n const maze = [];\n maze[0] = new Array(cols).fill(\"\");\n for (let i = 0; i < rows; i++) {\n const row = [];\n for (let j = 0; j < cols; j++) {\n row.push(Math.random() < 0.7 ? 'o' : '#'); // Adjust the probability to control the density of walls\n }\n maze.push(row);\n }\n return maze;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"function showMatrix(m) { \n return md`\n${m.slice(0, 1).map(row => row.map(d => \"\").join(\" | \")).join(\"\\n\")}\n${m[0].map(d => \" --- \").join(\" | \")}\n${m.slice(1).map(row => row.map(d => d).join(\" | \")).join(\"\\n\")}`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"function deepCopy(m){\n return m.map(row=>[...row.map(d=>d)]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"# Maze Visual","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":183,"value":"viewof rerender = htl.html``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"{\n rerender\n const context = DOM.context2d(width, height);\n\n const maze = makeMaze(grid);\n renderMaze(maze, context);\n const start = { x: 0, y: 0 };\n const end = { x: 10, y: 0 };\n\n // for await (let cur of aStarFunc(start,end,maze)){\n for await (let cur of crossMaze(maze)) {\n renderMaze(cur, context);\n yield context.canvas;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"async function* crossMaze(maze){\n for(let i =1;i a.priority - b.priority);\n }\n\n dequeue() {\n return this.elements.shift().element;\n }\n\n isEmpty() {\n return this.elements.length === 0;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":151,"value":"function manhattanDistance(node1, node2) {\n return Math.abs(node1.x - node2.x) + Math.abs(node1.y - node2.y);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":154,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"## Generator","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":109,"value":"function makeMaze(grid){\n const maze = []\n for(let i=0;irow.map(col=>({...col})));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"height = 720","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1"}} 30:"$2f:body"