Randomized Depth-First

100%

Randomized Depth-First

✓ Published0🌍 Public

Last edited Feb 9, 2016

Created on May 9, 2014

A randomized depth-first traversal generates a maze on a black canvas, with the active frontier of possible extensions highlighted in magenta. The algorithm starts in the bottom-left corner and repeatedly pops a frontier edge, carving passages in random directions while ensuring no cycles form. It renders to a 2D canvas using `d3.v3` and a `d3.timer` loop, drawing cells and corridors as white rectangles and spacing gaps. Each step redraws affected cells and frontier edges, with a shuffle applied to the frontier array to randomize the next choice.

AI-generated description

This maze generation algorithm uses randomized depth-first traversal. Starting in the bottom-left corner, the algorithm keeps an array of the possible directions the maze could be extended (shown in pink). At each step, the maze is extended in a random direction from the previous cell, as long as doing so does not reconnect with another part of the maze.

Compare this algorithm to random traversal, Prim’s algorithm on a randomly-weighted graph, and Wilson’s algorithm for a uniform spanning tree. The global structure of the maze can be more easily seen by flooding it with color.

gpl-3.0 Licensed

Similar vizzes

Loading thumbnail…

Randomized Depth-First III

A spanning tree of the canvas is generated using randomized depth-first traversal and then flooded with color, where hue encodes Manhattan distance from the root. The animation runs in a web worker, with each frame painting new frontier cells via Canvas `putImageData` and `createImageData`. The visualization uses D3’s `d3.timer` and `d3.hsl` for color cycling, while the maze structure is built incrementally by shuffling frontier edges in the worker’s `generateMaze` function.

Mmbostock

87% match

Loading thumbnail…

Random Traversal

A black canvas displays a maze being generated cell by cell via a random traversal algorithm. White cells mark the growing maze structure, while magenta highlights the current frontier of possible extensions. The animation progresses in steps, using the Canvas API to draw rectangles for cells and connections. The code implements the algorithm with a frontier array and popRandom selection, using d3.v3's timer for animation control.

Mmbostock

87% match

Loading thumbnail…

Randomized Depth-First II

A maze is generated using randomized depth-first traversal, then flooded with color to reveal its structure. Hue encodes the Manhattan distance from the starting cell, making the maze’s branching patterns visually comparable. The animation is rendered on a Canvas 2D context, drawing cells and passages incrementally as the flood expands. The code uses D3’s `d3.timer` to drive the animation loop and `d3.hsl` to cycle hue over time, while a custom `generateMaze` function builds the maze and `fillRect` calls paint each cell and connecting corridor.

Mmbostock

87% match

Loading thumbnail…

Random Traversal II

A maze is generated by random traversal and then flooded with colored light. Hue encodes the Manhattan distance from the starting cell, creating a vibrant gradient that reveals the maze’s branching structure. The animation uses a canvas, with `d3.timer` driving the flood fill, while `context.fillRect` paints each cell and corridor. The maze itself is built from an edge-bit array, and the color progression cycles through the HSL spectrum via `d3.hsl`.

Mmbostock

83% match

Loading thumbnail…

Randomized Depth-First IV

A maze is generated on a 40x40 grid using a randomized depth-first traversal, then converted into a tree structure. The tree layout from D3 is applied to position the nodes, and SVG paths draw the links between parent and child nodes. The code uses `d3.layout.tree`, `d3.select`, and SVG path elements to render the final hierarchical visualization. The tree’s branching pattern visually reflects the maze’s corridors and dead ends, with each node representing a cell and each link a passage.

Mmbostock

82% match

Loading thumbnail…

Random Traversal IV

This example shows a tree layout applied to a recursively generated maze, producing a branching structure of connected cells. The maze is created using a randomized depth-first traversal that records edge connections, and the resulting tree is rendered as a set of black link paths. The code uses `d3.layout.tree` to compute node positions from the maze’s traversal tree, then draws each link as an SVG path with `M` and `L` commands. The visualization is built with D3 v3 and SVG, with the maze generation logic implemented in plain JavaScript.

Mmbostock

81% match

Loading thumbnail…

Random Traversal III

A canvas spanning tree floods with color as an animation, where hue represents Manhattan distance from the root. A Web Worker generates the maze using random traversal, and the main thread colors it via a d3.timer loop, writing pixel data with Canvas `putImageData`. The code uses d3.v3 for color and timing, with bitwise direction flags to track tree edges.

Mmbostock

81% match

Loading thumbnail…

Random Search

This visualization animates a random search algorithm solving a maze, which was itself generated via random traversal. A magenta path highlights the best-known route from the top-right corner to the bottom-left, updating as the search progresses. The code uses D3 v3's timer API to drive the animation and a Canvas context for all drawing. The underlying maze and search logic are implemented directly with JavaScript arrays and bitwise operations to represent cell connections.

Mmbostock

80% match