In 1991, on a DOS machine with a BGI graphics driver, I wrote a small program that draw colored trees on screen. It wasn't meant to generate mazes. It became one by accident. Last weekend, 35 years and two rewrites later, I finally gave it a home in the browser.
How it started: trees, not mazes
The idea didn't begin as "let me build a maze generator." It began with drawing trees.
First came binary trees — each branch splitting into two. Then I moved to trees with three branches instead of two. At some point those three branches were arranged so they met at 45-degree angles from one another, and that's when it clicked: a tree that never crosses itself, that always has exactly one path from the root to any point on it, is a maze. A "perfect maze" is nothing more than a spanning tree with no cycles. I arrived at that property by drawing branches, not by studying graph theory.
What came out of that was a recursive backtracking routine: pick a point, grow a branch in one of several directions, recurse, and if a direction is blocked, back up and try another. This is, in retrospect, a randomized depth-first search — the same family of technique used by what's now widely known as the "recursive backtracker" maze algorithm. I want to be precise about what I'm claiming here, because it matters: I'm not claiming to have invented backtracking, or randomized DFS, or even maze generation via spanning trees. Backtracking as a formal technique goes back to D.H. Lehmer's work in the 1950s, and randomized DFS on a grid is a fairly natural thing for anyone to land on once they're generating trees programmatically. What I am saying is that I arrived at this specific approach independently, through a visual/geometric route rather than an algorithmic one, before I'd ever seen it written up as a named "maze generation algorithm" anywhere. The technique got its wider recognition in the developer community mostly through Jamis Buck's well-known 2010–2011 blog series cataloging maze algorithms — nearly twenty years after I'd written LABYR.PAS. That's the honest version of the story, and it's a more interesting one than a discovery claim: two people, two decades apart, arriving at the same idea from completely different directions.
The original: LABYR.PAS
The 1991 source, LABYR.PAS, is pure Turbo Pascal, built on the crt and graph units, targeting BGI (Borland Graphics Interface) output. A few design choices in it still hold up.
A precomputed permutation table. From any given heading, the algorithm can turn toward three possible directions (never back the way it came). Rather than shuffling those three options at runtime, I precomputed all six permutations of three items into a lookup table and just picked one at random each time a branch needed a direction:
const
dn: array [1..6,1..3] of integer =
((1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1));
It's a small, DOS-era trick for getting randomized turn order without runtime permutation logic — cheap on a resource-constrained machine, and honestly still a reasonable move today if you want to avoid a shuffle allocation in a hot loop.
The canvas as the state. Instead of maintaining a separate grid or graph structure to track which cells had been visited, the algorithm asked the screen itself:
function dotchk(px, py: integer): boolean;
begin
if getpixel(px, py) = backgr then
dotchk := true
else
dotchk := false;
end;
If the pixel wasn't the background color, something had already been drawn there. The rendered image was the occupancy map — an efficient use of memory on a resource-constrained machine, at the cost of tightly coupling rendering to algorithm state in a way I wouldn't design today.
Probabilistic branching. Two tunable parameters — p (probability of continuing to recurse) and plr (probability of turning left or right versus going straight) — shape how organic or how disciplined the resulting tree looks. That's what gives the output its distinctive, hand-drawn character rather than a uniform grid maze.
It ran, it worked, and then it sat untouched for years.
1998: the Delphi rewrite
Later, I ported it to Delphi — same logic, a more structured language, still native, still Windows-era. It was less a rewrite than a translation: the algorithm's bones didn't change, just the syntax and the toolchain around it.
Last weekend: TypeScript, and a chance to actually improve it
I found the old source again recently and spent a weekend bringing it into the present: an Angular component with a <canvas> renderer, running entirely in the browser. This wasn't just a syntax port. A few things needed to be genuinely rethought, and this is where 35 years of engineering practice actually shows up in the diff.
Recursion became an explicit stack. The original relied on native Pascal recursion, which the DOS environment tolerated within its own stack segment. In JavaScript, a recursion depth of several hundred (the depth parameter defaults to 700) risks a stack overflow — browsers don't give you nearly as much headroom. The TypeScript version replaces the recursive call with an explicit stack and a small state machine that reproduces the exact backtracking behavior of the original wall/backstep procedures — just safely:
interface WallFrame {
posx: number;
posy: number;
sel: Direction;
fd: Direction;
dp: number;
dotn: number;
dotnm: number;
initialized: boolean;
needBackstep: boolean;
savedLastHeading: Direction;
}
const stack: WallFrame[] = [/* seed frame */];
while (stack.length > 0) {
const frame = stack[stack.length - 1];
// process frame, push a child frame instead of recursing
}
State and rendering were separated. Instead of asking the canvas "is this pixel drawn," a plain typed array now tracks which cells are occupied:
export class OccupancyBitmap {
private readonly occupied: Uint8Array;
constructor(readonly width: number, readonly height: number) {
this.occupied = new Uint8Array(width * height);
}
isFree(px: number, py: number): boolean {
if (px < 0 || py < 0 || px >= this.width || py >= this.height) {
return false;
}
return this.occupied[py * this.width + px] === 0;
}
}
It's a small change, but it removes a dependency that never should have existed between what's on screen and what the algorithm knows — the kind of coupling that's easy to justify under DOS-era memory constraints and much harder to justify with a few kilobytes of typed array.
The main thread stays responsive. The original's repeat ... until keypressed loop was a blocking native loop — fine for DOS, fatal for a browser tab. The async version yields control back to the browser every 50 iterations:
iteration += 1;
if (iteration % yieldEvery === 0) {
await new Promise<void>((resolve) => setTimeout(resolve, 0));
}
so generating a large, dense maze doesn't freeze the page.
A couple of things also got added along the way that weren't in the 1991 version at all: a curated 18-color palette for the generated trees, and a "toothed" border effect where small random gaps are cut into the frame — details that have nothing to do with the algorithm's core logic, just an extra layer of visual character.
What stayed exactly the same
The interesting part, to me, is how much of the behavior carried over unchanged across three languages and 35 years. The direction logic, the rule preventing a branch from immediately reversing on itself, and the left/right turning bias all map almost one-to-one from the original Pascal case statements to their TypeScript equivalents. The algorithm itself never needed fixing — only the infrastructure around it did. That's a decent argument for getting the core logic right the first time, even on a machine with 640KB of conventional memory.
Try it
The live version is here: Labyrinth Generator — click the info icon on the page to see the original 1991 Pascal source alongside the current implementation.
The source lives at src/app/playground/components/labyrinth-generator in the LKovariHome repository. If you find it interesting, a ⭐ on the repo is always appreciated.
If you remember writing something similar back in the Turbo Pascal / BGI days — or if you've independently landed on the same randomized-backtracking idea from a completely different direction — I'd like to hear about it in the comments.
Top comments (0)