A grid compiled into logic-programming facts, solved by a recursive depth-first search driven by query, announced with goal, and reported through a solved/unsolved event - generation and solving both run live in this page (compiled to WASM once, no rustc per maze). Pick a size and seed, generate a maze, then watch it solve one visited cell at a time.
# Maze solver: logic-programming + goal-oriented + event-driven paradigms.
# The grid is compiled into `open` facts (a real logic predicate, queried
# rather than re-parsed), a `solve` goal announces intent, a recursive
# depth-first search does the actual work, and `solved`/`unsolved` events
# report the outcome - the same when/emit style used elsewhere in the
# portfolio (build_portfolio.patlang concatenates this after lib/html.patlang).
make a function called coord_key takes x, y returns k
return x + "," + y
end
make a function called path_contains takes path, key returns found
let i = 0
let found = false
while i < path.length do
if path[i] == key then
let found = true
end
let i = i + 1
end
return found
end
make a function called trace_reset returns done
set_var("mz_trace", "")
return true
end
make a function called trace_push takes key returns done
let cur = get("__vars", "mz_trace")
if cur == "" then
set_var("mz_trace", key)
else
set_var("mz_trace", cur + ";" + key)
end
return true
end
make a function called maze_dfs takes x, y, ex, ey, path returns result
let key = coord_key(x, y)
if query("open", key, 0) == 0 then
return []
end
if query("visited", key, 0) > 0 then
return []
end
fact("visited", key, "1")
trace_push(key)
let path = list_push(path, key)
if (x == ex) and (y == ey) then
return path
end
let dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
let i = 0
while i < dirs.length do
let d = dirs[i]
let result = maze_dfs(x + d[0], y + d[1], ex, ey, path)
if result.length > 0 then
return result
end
let i = i + 1
end
return []
end
# grid: list of equal-length strings. '#' wall, '.' open, 'S' start, 'E' end.
make a function called solve_maze takes grid returns path
let sx = 0
let sy = 0
let ex = 0
let ey = 0
let y = 0
while y < grid.length do
let row = grid[y]
let x = 0
while x < row.length do
let c = row[x]
if c != "#" then
fact("open", coord_key(x, y), "1")
end
if c == "S" then
let sx = x
let sy = y
end
if c == "E" then
let ex = x
let ey = y
end
let x = x + 1
end
let y = y + 1
end
goal("solve", coord_key(sx, sy) + "->" + coord_key(ex, ey))
trace_reset()
let path = maze_dfs(sx, sy, ex, ey, [])
if path.length > 0 then
emit("solved", path.length + " steps, " + query("open", coord_key(sx, sy), 0) + " start-cell facts")
else
emit("unsolved", coord_key(sx, sy) + "->" + coord_key(ex, ey))
end
return path
end
make a function called maze_cell_class takes grid, path, x, y returns cls
let row = grid[y]
let c = row[x]
if c == "S" then
return "mz-start"
end
if c == "E" then
return "mz-end"
end
if c == "#" then
return "mz-wall"
end
if path_contains(path, coord_key(x, y)) then
return "mz-path"
end
return "mz-open"
end
make a function called render_maze_grid takes grid, path returns html
let cols = grid[0].length
let b = sb_new()
sb_push(b, "<div class=" + q() + "mz-grid" + q() + " style=" + q() + "display:grid;grid-template-columns:repeat(" + cols + ",1.6em);gap:2px;" + q() + ">" + nl())
let y = 0
while y < grid.length do
let x = 0
while x < grid[y].length do
sb_push(b, "<div class=" + q() + maze_cell_class(grid, path, x, y) + q() + "></div>")
let x = x + 1
end
sb_push(b, nl())
let y = y + 1
end
sb_push(b, "</div>" + nl())
return sb_str(b)
end
# ---- maze generation: randomized recursive backtracker ----
# A tiny LCG (Borland/Turbo C constants, modulus 2^15) kept as global state
# via set_var/get, since threading a PRNG state through recursive carve()
# calls by return value would be far more invasive than this codebase's
# established "hidden global counter" idiom (see lower.patlang's closure_seq).
make a function called rand_seed takes seed returns done
let s = seed % 32768
if s < 0 then
let s = s + 32768
end
set_var("mz_rand", s)
return true
end
make a function called rand_next returns r
let s = get("__vars", "mz_rand")
let s2 = ((s * 1103) + 12345) % 32768
set_var("mz_rand", s2)
return s2
end
make a function called rand_below takes n returns r
return rand_next() % n
end
make a function called shuffle4 returns dirs
let dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
let i = 3
while i > 0 do
let j = rand_below(i + 1)
let tmp = dirs[i]
let dirs = list_set(dirs, i, dirs[j])
let dirs = list_set(dirs, j, tmp)
let i = i - 1
end
return dirs
end
make a function called cell_idx takes cx, cy, w returns idx
return (cy * w) + cx
end
make a function called grid_idx takes gx, gy, cols returns idx
return (gy * cols) + gx
end
make a function called carve takes cx, cy, w, h, cols, visited, grid returns done
vec_set(visited, cell_idx(cx, cy, w), 1)
let gx = (cx * 2) + 1
let gy = (cy * 2) + 1
vec_set(grid, grid_idx(gx, gy, cols), ".")
let dirs = shuffle4()
let i = 0
while i < dirs.length do
let d = dirs[i]
let nx = cx + d[0]
let ny = cy + d[1]
if (nx >= 0) and (nx < w) and (ny >= 0) and (ny < h) then
if vec_get(visited, cell_idx(nx, ny, w)) == 0 then
vec_set(grid, grid_idx(gx + d[0], gy + d[1], cols), ".")
carve(nx, ny, w, h, cols, visited, grid)
end
end
let i = i + 1
end
return true
end
# Generates a perfect maze (spanning tree, exactly one path S->E) of w x h
# cells, returned as a list of row strings compatible with solve_maze.
make a function called generate_maze takes w, h, seed returns grid_lines
rand_seed(seed)
let cols = (w * 2) + 1
let rows = (h * 2) + 1
let grid = vec_new()
let i = 0
while i < (cols * rows) do
vec_push(grid, "#")
let i = i + 1
end
let visited = vec_new()
let i = 0
while i < (w * h) do
vec_push(visited, 0)
let i = i + 1
end
carve(0, 0, w, h, cols, visited, grid)
vec_set(grid, grid_idx(1, 1, cols), "S")
vec_set(grid, grid_idx(((w - 1) * 2) + 1, ((h - 1) * 2) + 1, cols), "E")
let lines = []
let y = 0
while y < rows do
let row = sb_new()
let x = 0
while x < cols do
sb_push(row, vec_get(grid, grid_idx(x, y, cols)))
let x = x + 1
end
let lines = list_push(lines, sb_str(row))
let y = y + 1
end
return lines
end
make a function called split_lines takes text returns lines
let lines = []
let cur = sb_new()
let i = 0
while i <= text.length do
let c = char_code(text, i)
if (c == 10) or (c == -1) then
let line = sb_str(cur)
let cur = sb_new()
if line != "" then
let lines = list_push(lines, line)
end
else
if c != 13 then
sb_push(cur, text[i])
end
end
let i = i + 1
end
return lines
end
make a function called join_semi takes items returns text
let b = sb_new()
let i = 0
while i < items.length do
if i > 0 then
sb_push(b, ";")
end
sb_push(b, items[i])
let i = i + 1
end
return sb_str(b)
end
make a function called maze_css returns css
return "<style>" +
".mz-grid{font-size:0}" +
".mz-grid div{width:1.6em;height:1.6em;display:inline-block}" +
".mz-wall{background:#333}" +
".mz-open{background:#eee}" +
".mz-path{background:#6ab04c}" +
".mz-start{background:#4a69bd}" +
".mz-end{background:#e55039}" +
"</style>"
end