In prepping to teach a workshop on recursion I wrote this code that uses a maze-building algorithm. In doing so I found it really natural to use generators a lot. I feel pretty happy with how the code turned out but its also pretty unusual and I wonder what yall think of it.
This is meant to run on latest chrome (partial es2015 support, no destructing assignment, no modules yet)
<style>
* {
box-sizing: border-box;
}
body {
background-color: red;
min-height: 100vh;
padding: 0;
margin: 0;
display: flex;
}
main {
flex: 1;
display: flex;
flex-direction: column;
}
.row {
display: flex;
flex: 1;
}
.row:first-child .cell {
border-top: 2px solid red;
}
.row .cell:first-child {
border-left: 2px solid red;
}
.cell {
display: flex;
background-color: yellow;
width: 2%;
border-bottom: 2px solid red;
border-right: 2px solid red;
transition: background-color 1.5s;
}
.cell.clear-right {
border-right: 0;
}
.cell.clear-down {
border-bottom: 0;
}
.cell.visited {
background-color: grey;
}
fieldset {
position: fixed;
bottom: 0;
right: 0;
background-color: beige;
max-height: 5px;
transition: max-height .25s;
overflow: hidden;
}
fieldset:hover {
max-height: 3em;
}
</style>
<main></main>
<fieldset>
<label>Speed:
<input type="range" name="speed" min=1 max=500 value=10 >
</label>
<button name="finish" title="Might take a few seconds">Finish</button>
</fieldset>
<script>
(function(){
'use strict'
var speed = document.querySelector('[name=speed]')
var runLater = fn => setTimeout(fn, speed.value)
document.querySelector('[name=finish]').addEventListener('click', () => runLater = fn => fn())
const board = createBoard(50, 50)
const cell = pos(randomInteger(board.width), randomInteger(board.height))
run(createMaze(board, null, cell))
function run(iterator, prev) {
if( (prev||{}).done ) return
runLater( () => run(iterator, iterator.next()))
}
function* createMaze(board, fromCell, toCell) {
// console.log(`moving from ${fromCell} -> ${toCell}`)
board.move(fromCell, toCell)
yield
yield* createMazeOnUnvisitedNeighbors(board, toCell)
}
function* createMazeOnUnvisitedNeighbors(board, cell) {
const surroundingCells = board.surroundingCells(cell)
const surroundingUnvisited = surroundingCells.filter(c => !board.isVisited(c) )
const nextToVisit = selectRandom(surroundingUnvisited)
if(!nextToVisit)
return
yield* createMaze(board, cell, nextToVisit)
yield* createMazeOnUnvisitedNeighbors(board, cell)
}
function createBoard(width, height) {
document.querySelector('main').innerHTML = Array.from(getTableHtml(width, height)).join('');
const cells = Array.from(cells2D( Array.from(document.querySelectorAll('main .row')) ))
const visited = new Map()
const cellAt = (pos) => cells[pos.y][pos.x]
const move = (from, to) => {
visited.set(JSON.stringify(to), true)
cellAt(to).classList.add('visited')
if(!from)
return
if(from.x < to.x) //→
cellAt(from).classList.add('clear-right')
else if(from.x > to.x) //←
cellAt(to).classList.add('clear-right')
else if(from.y < to.y) //↓
cellAt(from).classList.add('clear-down')
else if(from.y > to.y) //↑
cellAt(to).classList.add('clear-down')
}
return {
surroundingCells: (position) => [...getSurroundingCells({width, height}, position)],
isVisited: (position) => !!visited.get(JSON.stringify(position)),
move,
height, width,
}
}
function pos(x, y) { return {x,y, toString: () => `[${x}, ${y}]`} }
function* getSurroundingCells(dimensions, position) {
const x = position.x
const y = position.y
if(x > 0) yield pos(x-1, y)
if(x < dimensions.width-1) yield pos(x+1, y)
if(y > 0) yield pos(x, y-1)
if(y < dimensions.height-1) yield pos(x, y+1)
}
function selectRandom(items) {
return !items.length ? null : items[randomInteger(items.length)]
}
function* cells2D(rows) {
if(rows.length <= 0)
return
yield Array.from( rows[0].querySelectorAll('.cell') )
yield* cells2D( rows.slice(1) )
}
function* getCellsHtml(width) {
if(width <= 0)
return
yield '<div class="cell">'
yield '</div>'
yield* getCellsHtml(width-1)
}
function* getRowsHtml(height, width) {
if(height <= 0)
return
yield '<div class="row">'
yield* getCellsHtml(width)
yield '</div>'
yield* getRowsHtml(height-1, width)
}
function* getTableHtml(height, width) {
yield* getRowsHtml(height, width)
}
function randomInteger(maxExclusive) {
return Math.floor(Math.random() * maxExclusive)
}
})()
</script>
I'm curious especially about the following
- I wanted to demonstrate that loops are just specialized recursion so I wrote this on purpose with no loops whatsoever. Would loops in places here be clearer (assuming the reader is equally versed in either)?
- Generators seem to be is a really neat way of generating a state machine where the invoker can control when the next step is invoked, but not the order or implementation of either. This is super cool, but also seems like not as flexible as it can be. Is this just always going to be better with some sort of library?
- A css one! I don't like that I have to set
width: 2%
. where width should be a calculated value100% / widthOfGrid
. I would rather doflex: 1
but when I do, often lines don't line up. I can't quite figure out why. - I don't like having to json-ize the keys into my
Map
as it defeats a lot of the point, but I see no good way around that since{x:1,y:2} !== {x:1,y:2}
. Could I do something else? - This seems to be preforming quite well but I'm pretty bad at interpreting profiler tooling
- ...except for where it says that yield is not optimized. Is this a temporary bug or a limitation of yield?
- Are we all agreed that function-declaration hoisting in javascript is a good thing?
- Assuming I abstract away the generators stuff, how good is the maze-building concept for teaching (intermediate-advanced) recursion?
- How good is this for teaching (advanced) generators?
- Other thoughts?