Queue implementation used here is published as separate gist queue.js.
When loaded it draws path from top left to bottom right corner. White cells are empty and black -- walls. Clicking on any cell inverts it(empty > wall and wall > empty) and forces path redraw. For now or recreates Adjacency List every time. Sometimes it cannot find path from start to the end, in this case just refresh page.
| const findStartIndex = (cells) => | |
| cells.findIndex(({ type }) => type === "empty"); | |
| const findEndIndex = (cells) => { | |
| for (let i = cells.length - 1; i >= 0; i--) { | |
| const el = cells[i]; | |
| if (el.type === "empty") { | |
| return el.index; | |
| } | |
| } | |
| return -1; | |
| }; | |
| const solve = (start, adjList) => { | |
| const queue = new Queue(); | |
| const visited = new Uint8Array(count); | |
| queue.enqueue(start); | |
| visited[start] = 1; | |
| const result = []; | |
| while (!queue.empty()) { | |
| const curr = queue.dequeue(); | |
| adjList[curr].forEach((sibbling) => { | |
| if (visited[sibbling]) { | |
| return; | |
| } | |
| queue.enqueue(sibbling); | |
| visited[sibbling] = 1; | |
| result[sibbling] = curr; | |
| }); | |
| } | |
| return result; | |
| }; | |
| const reconstructPath = (start, end, prev) => { | |
| const path = []; | |
| for (let pos = end; pos !== undefined; pos = prev[pos]) { | |
| path.push(pos); | |
| } | |
| path.reverse(); | |
| return path[0] === start ? path : [start]; | |
| }; | |
| const breathFirstSearch = (adjList, cells) => { | |
| const start = findStartIndex(cells); | |
| const end = findEndIndex(cells); | |
| const prev = solve(start, adjList); | |
| const path = reconstructPath(start, end, prev); | |
| return path; | |
| }; |
| const createGetIndex = (perRow) => (row, col) => row * perRow + col; | |
| const createGetCell = (getIndex) => (row, col) => cells[getIndex(row, col)]; | |
| const createIsEmpty = (getCell) => (row, col) => { | |
| const el = getCell(row, col); | |
| return el ? el.type === 'empty' : false; | |
| }; | |
| const generateFns = (perRow) => { | |
| const getIndex = createGetIndex(perRow); | |
| const getCell = createGetCell(getIndex); | |
| const isEmpty = createIsEmpty(getCell); | |
| return { | |
| getIndex, getCell, isEmpty | |
| }; | |
| }; | |
| const DIRECTIONS_4 = [ | |
| [-1, 0], | |
| [1, 0], | |
| [0, -1], | |
| [0, 1], | |
| ]; | |
| const DIRECTIONS_8 = [ | |
| ...DIRECTIONS_4, | |
| [-1, -1], | |
| [1, -1], | |
| [1, 1], | |
| [-1, 1], | |
| ]; | |
| const createGridToAdjacencyList = (directions) => (grid, perRow) => { | |
| const { getIndex, isEmpty } = generateFns(perRow); | |
| const { length } = grid; | |
| const result = []; | |
| for (let i = 0; i < length; i++) { | |
| const el = grid[i]; | |
| const { row, col, index } = el; | |
| const edges = []; | |
| directions.forEach(([aRow, aCol]) => { | |
| const pRow = row + aRow | |
| const pCol = col + aCol; | |
| if (pCol >= 0 && pCol < perRow && isEmpty(pRow, pCol)) { | |
| const conn = getIndex(pRow, pCol); | |
| edges.push(conn); | |
| } | |
| }); | |
| result[index] = edges; | |
| } | |
| return result; | |
| }; | |
| const gridToAdjacencyList = createGridToAdjacencyList(DIRECTIONS_8); |
| <!DOCTYPE html> | |
| <html lang="en"> | |
| <head> | |
| <style> | |
| :root { | |
| --grid-cols: 150; | |
| --grid-rows: 100; | |
| } | |
| html, | |
| body { | |
| margin: 0; | |
| padding: 0; | |
| width: 100%; | |
| height: 100%; | |
| } | |
| .grid { | |
| display: grid; | |
| grid-template-columns: repeat(var(--grid-cols), 1fr); | |
| grid-template-rows: repeat(var(--grid-rows), 1fr); | |
| width: 100%; | |
| height: 100%; | |
| } | |
| .cell { | |
| outline: 1px solid #eee; | |
| } | |
| .cell.step { | |
| background-color: #9f9; | |
| } | |
| .cell.wall { | |
| background-color: #000; | |
| } | |
| .cell.empty:hover { | |
| outline-color: #f99; | |
| } | |
| </style> | |
| <script src="queue.js"></script> | |
| <script src="grid-to-adjacency-list.js"></script> | |
| <script src="breadth-first.js"></script> | |
| </head> | |
| <body> | |
| <div id="grid" class="grid"></div> | |
| </body> | |
| <script> | |
| const gridEl = document.querySelector('#grid'); | |
| const gridStyles = window.getComputedStyle(gridEl); | |
| const COLS = parseInt(gridStyles.getPropertyValue('--grid-cols'), 10); | |
| const ROWS = parseInt(gridStyles.getPropertyValue('--grid-rows'), 10); | |
| const ids = {}; | |
| const cells = []; | |
| const showPath = () => { | |
| // FIXME we may update only adjacent cells instead of rebuilding whole list | |
| const adjList = gridToAdjacencyList(cells, COLS); | |
| breathFirstSearch(adjList, cells).forEach((index) => { | |
| const cell = cells[index]; | |
| cell.classList.remove('empty'); | |
| cell.classList.add('step'); | |
| }); | |
| }; | |
| const cellOnClick = ({ target }) => { | |
| document.querySelectorAll('.cell.step').forEach((el) => { | |
| el.classList.remove('step'); | |
| el.classList.add('empty'); | |
| }); | |
| if (target.classList.contains('wall')) { | |
| target.type = 'empty'; | |
| target.classList.remove('wall'); | |
| target.classList.add('empty'); | |
| } else { | |
| target.type = 'wall'; | |
| target.classList.remove('empty'); | |
| target.classList.add('wall'); | |
| } | |
| showPath(); | |
| }; | |
| const getCellId = (row, col) => `cell-${row}-${col}`; | |
| const { getIndex, getCell, isEmpty } = generateFns(COLS); | |
| const count = COLS * ROWS; | |
| for (let i = 0; i < count; i++) { | |
| const row = Math.floor(i / COLS); | |
| const col = i % COLS; | |
| const el = document.createElement('div'); | |
| const id = getCellId(row, col); | |
| const type = Math.random() < 0.3 ? 'wall' : 'empty'; | |
| Object.assign(el, { id, index: i, row, col, type }); | |
| el.addEventListener('click', cellOnClick); | |
| el.className = `cell ${type}`; | |
| ids[id] = el; | |
| cells[i] = el; | |
| } | |
| grid.append(...cells); | |
| showPath(); | |
| </script> | |
| </html> |