Algorithm Field Guide

Maze Generation + Solving Documentation

A practical reference for every algorithm in this visualizer: what it does, why it behaves that way, and when to use it.

Open VisualizerJump to GeneratorsJump to Solvers
22Generators
23Solvers
45Total Algorithms

Generator Algorithms

These construct the maze structure by carving passages between cells.

Generatordfs-backtracker

Recursive Backtracker (DFS)

Grows a maze by walking deeply until stuck, then backtracks.

Time: O(V)Space: O(V)

How It Works

  1. Start at one cell, mark it visited, and push it on a stack.
  2. Move to a random unvisited neighbor and carve the wall.
  3. If no unvisited neighbors remain, pop and continue from the previous cell.
  4. Stop when the stack becomes empty.

Pros

  • Fast
  • Simple
  • Produces long winding corridors

Cons

  • Can create low branching
  • Less uniform than Wilson/Aldous-Broder

Best use: Fast visual generation with dramatic backtracking behavior.

Interesting fact: This is one of the most common textbook maze generators because it is easy to animate step-by-step.

Generatorprim

Randomized Prim

Expands a frontier set by attaching random frontier cells.

Time: O(V)Space: O(V)

How It Works

  1. Start from one cell and mark adjacent cells as frontier.
  2. Pick a random frontier cell.
  3. Connect it to one random visited neighbor.
  4. Mark its unvisited neighbors as new frontier.

Pros

  • Good branching
  • Natural wavefront animation

Cons

  • Needs frontier bookkeeping
  • Can look noisy at high randomness

Best use: Balanced mazes with lots of local choices.

Interesting fact: It is inspired by Prim's minimum spanning tree method, but with randomized edge selection.

Generatorprim-frontier-edges

Prim (Frontier Edges)

Prim-style generation using explicit frontier edge sampling.

Time: O(E) expectedSpace: O(E)

How It Works

  1. Start from one visited root cell.
  2. Push all edges from visited cells to unvisited neighbors into a frontier list.
  3. Pick a random frontier edge; if it connects to an unvisited cell, carve it.
  4. Add new frontier edges from the newly visited cell and repeat.

Pros

  • Classic Prim interpretation
  • Good branching and texture

Cons

  • Frontier edge list can grow large
  • Extra filtering for stale edges

Best use: When you want Prim behavior driven directly by edge randomness.

Interesting fact: Compared with frontier-cell Prim, edge-based Prim can emphasize different local branching statistics.

Generatorkruskal

Randomized Kruskal

Carves walls by joining disjoint sets while avoiding cycles.

Time: O(E α(V))Space: O(V)

How It Works

  1. Treat each cell as its own set.
  2. Shuffle candidate walls (edges) between neighboring cells.
  3. If an edge connects two different sets, carve it and union the sets.
  4. Stop when all cells are in one connected set.

Pros

  • Strong theoretical guarantees
  • Uniform spanning-tree style behavior

Cons

  • Needs union-find
  • Less intuitive than DFS/Prim

Best use: When you want explicit disjoint-set control and predictable correctness.

Interesting fact: Union-find path compression makes practical performance very fast even on large grids.

Generatorbinary-tree

Binary Tree

Each cell carves toward one of two preferred directions.

Time: O(V)Space: O(1)

How It Works

  1. Visit cells in scan order.
  2. For each cell, carve either north or west when available.
  3. Edge cells carve only when the direction exists.
  4. Continue until all cells are processed.

Pros

  • Extremely fast
  • Tiny memory footprint

Cons

  • Directional bias
  • Predictable patterns

Best use: High-speed generation and teaching directional bias effects.

Interesting fact: Its directional rule creates obvious diagonal flow patterns that are easy to recognize visually.

Generatorsidewinder

Sidewinder

Builds horizontal runs and occasionally links them upward.

Time: O(V)Space: O(1)

How It Works

  1. Move across each row while extending a run to the east.
  2. Randomly decide to close the run.
  3. When closing, carve one north connection from a random cell in the run.
  4. Repeat per row.

Pros

  • Very fast
  • Distinct corridor aesthetics

Cons

  • Visible row bias
  • Less organic appearance

Best use: Fast generation with intentional horizontal character.

Interesting fact: It is often paired with Binary Tree to show how tiny local rules create global maze style.

Generatoraldous-broder

Aldous-Broder

Uses a pure random walk and carves only on first visits.

Time: Expected O(V^2)Space: O(V)

How It Works

  1. Start from a random cell.
  2. Walk to a random neighbor each step.
  3. If that neighbor is unvisited, carve the edge and mark it visited.
  4. Stop after all cells are visited.

Pros

  • Uniform spanning tree
  • Conceptually minimal

Cons

  • Can be very slow
  • Many non-carving steps

Best use: Demonstrating random-walk behavior and uniform spanning tree theory.

Interesting fact: Despite being simple, it converges slowly because random walks revisit cells many times.

Generatorhunt-and-kill

Hunt-and-Kill

Alternates random walking with linear hunts for a new branch point.

Time: O(V^2) worst-caseSpace: O(V)

How It Works

  1. Walk randomly until reaching a dead end.
  2. Scan for an unvisited cell adjacent to visited territory.
  3. Connect there and resume random walking.
  4. Finish when the scan finds no valid unvisited cell.

Pros

  • Interesting phase changes
  • Good organic structure

Cons

  • Scanning phase can be expensive
  • Slightly more bookkeeping

Best use: Visual demos where algorithm phases should feel very different.

Interesting fact: The switch between hunt and kill phases is very visible and makes this algorithm great for education.

Generatorgrowing-tree

Growing Tree

Generalized family that blends DFS-like and Prim-like behavior via selection policy.

Time: O(V)Space: O(V)

How It Works

  1. Keep a list of active cells.
  2. Select one active cell using a strategy (newest, random, or mixed).
  3. Carve to one unvisited neighbor if possible; otherwise remove the active cell.
  4. Continue until no active cells remain.

Pros

  • Highly tunable style
  • Good compromise between long corridors and branching

Cons

  • Selection policy impacts style heavily
  • Less canonical than pure DFS/Prim

Best use: When you want one algorithm knob to dial corridor-vs-branch behavior.

Interesting fact: Using newest-only turns it into recursive backtracker; random-only makes it feel close to Prim.

Generatorbfs-tree

Randomized BFS Tree

Builds a spanning tree layer-by-layer from a queue frontier.

Time: O(V + E)Space: O(V)

How It Works

  1. Choose a start cell and enqueue it.
  2. Pop cells in BFS order and inspect neighbors.
  3. For each unvisited neighbor, carve to it and enqueue it.
  4. Continue until queue is exhausted.

Pros

  • Very stable progression
  • Naturally broad, wave-like growth

Cons

  • Can look less organic than DFS variants
  • Needs queue/frontier bookkeeping

Best use: Clear breadth-first generation visuals and predictable expansion fronts.

Interesting fact: Unlike Prim, this variant commits tree parents by discovery order, creating BFS-depth layers.

Generatoreller

Eller

Builds the maze one row at a time using dynamic disjoint sets.

Time: O(V) expectedSpace: O(width)

How It Works

  1. Assign set ids across the current row.
  2. Randomly join adjacent cells with different set ids.
  3. For each set, carve at least one vertical connection downward.
  4. On the final row, force all remaining disjoint sets to merge.

Pros

  • Streaming-friendly
  • Memory-efficient for tall mazes

Cons

  • Row-wise bias can be visible
  • Implementation is more stateful than DFS/Prim

Best use: Generating large mazes where memory proportional to width is preferred.

Interesting fact: Eller is one of the few classic perfect-maze algorithms that does not require full-grid state history.

Generatorwilson

Wilson

Creates a uniform spanning tree using loop-erased random walks.

Time: Expected polynomial; often higher than DFS/PrimSpace: O(V)

How It Works

  1. Start with one cell in the tree.
  2. Pick an unvisited cell and perform a random walk.
  3. Erase loops in the walk as they form (loop-erased random walk).
  4. When the walk hits the existing tree, carve the whole walk into the tree.

Pros

  • Uniform spanning tree output
  • Strong theoretical guarantees

Cons

  • Can be slower
  • Walk-loop bookkeeping is heavier

Best use: When statistical fairness of generated spanning trees matters.

Interesting fact: Wilson and Aldous-Broder both generate uniform spanning trees, but Wilson is usually much faster in practice.

Generatorhouston

Houston (AB + Wilson)

Hybrid that starts with Aldous-Broder then switches to Wilson for speed.

Time: Expected faster than pure AB, near Wilson in late stageSpace: O(V)

How It Works

  1. Run Aldous-Broder random walk for an initial visited fraction.
  2. Use the visited cells as an initial tree.
  3. Switch to Wilson loop-erased walks for the remaining unvisited cells.
  4. Finish when every cell is merged into the tree.

Pros

  • Practical speed boost
  • Retains random-walk flavor early on

Cons

  • More implementation complexity
  • Hybrid behavior is less canonical

Best use: Balancing visual random-walk behavior with practical completion speed.

Interesting fact: Houston is a known optimization strategy specifically meant to mitigate Aldous-Broder's long tail.

Generatorrecursive-division

Recursive Division

Creates a maze by adding split walls with one opening per division.

Time: O(V log V) typicalSpace: O(log V) recursion + patch batches

How It Works

  1. Start from an open field (internal walls removed).
  2. Pick horizontal or vertical orientation per region.
  3. Add a dividing wall and keep one random gap.
  4. Recurse into both child regions until indivisible.

Pros

  • Distinct architectural look
  • Fast wall-adding style

Cons

  • Can look structured
  • Less organic than random walkers

Best use: When you want blocky, room-like visual structure.

Interesting fact: This is the canonical wall-adder among classic maze generators.

Generatorprim-true

Prim (True Frontier Edges)

Prim variant that samples random frontier edges directly.

Time: O(E) expectedSpace: O(E)

How It Works

  1. Seed one visited root cell.
  2. Push root->unvisited frontier edges.
  3. Pick random edge and carve when target is unvisited.
  4. Repeat until frontier is exhausted.

Pros

  • Classic Prim behavior
  • Good branching texture

Cons

  • Large frontier edge list
  • Needs stale-edge filtering

Best use: True edge-frontier Prim demonstrations.

Interesting fact: Edge-frontier Prim and cell-frontier Prim can produce noticeably different local motifs.

Generatorprim-simplified

Prim (Simplified)

Frontier-cell Prim using lighter bookkeeping than edge-frontier mode.

Time: O(V) expectedSpace: O(V)

How It Works

  1. Track frontier cells near visited territory.
  2. Pick random frontier cell.
  3. Connect it to one visited neighbor.
  4. Add newly exposed frontier cells.

Pros

  • Simple implementation
  • Strong maze branching

Cons

  • Less canonical than true edge Prim
  • Can look noisy

Best use: Practical Prim-style generation with less overhead.

Interesting fact: This style is common in visualizers because frontier bookkeeping is straightforward.

Generatorprim-modified

Prim (Modified)

Random-active-cell variant close to Growing Tree random policy.

Time: O(V)Space: O(V)

How It Works

  1. Keep active in-maze cells.
  2. Select one active cell uniformly at random.
  3. Carve to a random unvisited neighbor if possible.
  4. Drop active cells that have no remaining unvisited neighbors.

Pros

  • Flexible texture
  • Simple random policy

Cons

  • Style depends on active-list evolution
  • Not uniform

Best use: Middle ground between Prim-like and DFS-like growth.

Interesting fact: This policy is one endpoint of the broader Growing Tree algorithm family.

Generatorgrowing-forest

Growing Forest

Grows multiple trees in parallel, then merges them into one maze.

Time: O(V + E α(V))Space: O(V)

How It Works

  1. Seed several trees across the grid.
  2. Grow each tree into nearby unvisited cells.
  3. When growth saturates, collect boundary edges between trees.
  4. Union tree components with boundary carves until one tree remains.

Pros

  • Distinct multi-origin growth
  • Good global variety

Cons

  • More bookkeeping
  • Harder to reason about than single-tree growth

Best use: Visualizations emphasizing concurrent growth fronts.

Interesting fact: Forest merge phase is effectively a component-union process similar to Kruskal.

Generatorunicursal

Unicursal

Builds a single non-branching path through the full grid.

Time: O(V)Space: O(V)

How It Works

  1. Create a serpentine Hamiltonian-style ordering of cells.
  2. Carve between consecutive cells in that ordering.
  3. Continue until all cells are connected in one route.

Pros

  • No branch ambiguity
  • Very readable path structure

Cons

  • Not a branching maze feel
  • Low replay diversity

Best use: Labyrinth-style experiences and path-only demonstrations.

Interesting fact: Unicursal structures have exactly one route and no junction choices.

Generatorfractal-tessellation

Fractal Tessellation

Recursively forms quadrant trees and stitches them with three bridges.

Time: O(V log V) typicalSpace: O(V)

How It Works

  1. Split region into quadrants recursively.
  2. Generate subtree edges inside each quadrant.
  3. Sample cross-boundary connector candidates.
  4. Select three connectors that unify quadrants without cycles.

Pros

  • Recursive self-similar texture
  • Strong visual identity

Cons

  • Can look regular
  • More implementation complexity

Best use: Fractal-style maze aesthetics and recursive demos.

Interesting fact: Using exactly three inter-quadrant links preserves tree structure at each merge.

Generatorcellular-automata

Cellular Automata (Cave-Biased)

Uses a smoothed CA mask to bias spanning-tree carving decisions.

Time: O(V) generation + O(V) mask smoothingSpace: O(V)

How It Works

  1. Initialize random binary cave mask.
  2. Run CA smoothing iterations over the mask.
  3. Grow a spanning tree while preferring neighbors with similar cave state.
  4. Backtrack when stuck until all cells are carved.

Pros

  • Organic local texture bias
  • Still deterministic and step-friendly

Cons

  • Not pure cave generation
  • Requires extra precomputation

Best use: Hybrid cave-like style without losing spanning-tree guarantees.

Interesting fact: CA-inspired bias lets one algorithm bridge classic mazes and dungeon-like visuals.

Generatororigin-shift

Origin Shift

Rewires a rooted spanning tree by repeatedly shifting the root.

Time: O(V + S), where S is shift countSpace: O(V)

How It Works

  1. Start from an initial rooted spanning tree.
  2. Pick a neighbor of the current root.
  3. Detach that neighbor from its old parent edge.
  4. Connect old root to the neighbor and promote neighbor as new root.

Pros

  • Unique dynamic rewiring animation
  • Keeps tree connectivity throughout

Cons

  • Less intuitive than carve-from-walls methods
  • Requires parent-edge tracking

Best use: Modern/experimental generator comparisons.

Interesting fact: Each shift performs a local edge swap while preserving a valid spanning tree.

Solver Algorithms

These navigate an already generated maze from start to goal.

Solverbfs

Breadth-First Search (BFS)

Expands in layers and guarantees shortest path in unweighted mazes.

Time: O(V + E)Space: O(V)

How It Works

  1. Push start cell into a queue.
  2. Pop in FIFO order and visit neighbors.
  3. Record each neighbor's parent when first discovered.
  4. When goal is reached, reconstruct path via parents.

Pros

  • Optimal path for unit weights
  • Simple and robust

Cons

  • Can explore many irrelevant nodes
  • Large frontier on wide-open maps

Best use: Reliable shortest path on unweighted grids.

Interesting fact: BFS is equivalent to Dijkstra when every edge has identical weight.

Solverdfs

Depth-First Search (DFS)

Follows one branch deeply before backing up.

Time: O(V + E)Space: O(V)

How It Works

  1. Push start cell onto a stack.
  2. Pop and explore a neighbor branch deeply.
  3. Track discovery parents for reconstruction.
  4. Backtrack naturally when stack unwinds.

Pros

  • Very low overhead
  • Strong step-by-step visual clarity

Cons

  • No shortest-path guarantee
  • Can take long detours

Best use: Showing exploratory behavior rather than shortest paths.

Interesting fact: On tree mazes (perfect mazes), DFS still finds the unique path but may explore much more first.

Solverastar

A* Search

Combines actual cost and heuristic distance to guide exploration.

Time: O(E) to O(E log V), depending on priority structureSpace: O(V)

How It Works

  1. Maintain open set prioritized by f(n)=g(n)+h(n).
  2. Expand the cell with lowest estimated total cost.
  3. Relax neighbors if a better g-cost is found.
  4. Stop at goal and reconstruct via parents.

Pros

  • Usually much faster than BFS
  • Optimal with admissible heuristic

Cons

  • Needs heuristic tuning
  • Bookkeeping heavier than BFS/DFS

Best use: Fast near-optimal routing on grid mazes.

Interesting fact: Manhattan distance is a natural heuristic for 4-directional grids.

Solverastar-euclidean

A* (Euclidean)

A* variant using straight-line distance heuristic.

Time: O(E) to O(E log V), depending on queueSpace: O(V)

How It Works

  1. Score candidates with f(n)=g(n)+h(n), where h is Euclidean distance.
  2. Expand the lowest f-score node.
  3. Relax neighbors with improved g-cost and update parents.
  4. Stop and reconstruct when reaching goal.

Pros

  • Admissible and consistent on grid movement
  • Often smooth directional guidance

Cons

  • Can expand more than Manhattan A* on 4-neighbor grids
  • Still more bookkeeping than BFS

Best use: Comparing heuristic behavior and exploring geometric distance cues.

Interesting fact: Euclidean is tighter for continuous geometry, while Manhattan better matches axis-only moves.

Solverweighted-astar

Weighted A*

Biases A* harder toward the heuristic for more aggressive search.

Time: Often faster than A* in practiceSpace: O(V)

How It Works

  1. Use f(n)=g(n)+w*h(n) with w>1.
  2. Expand the node with smallest weighted estimate.
  3. Continue relaxing neighbors and updating parents.
  4. Return reconstructed path when goal is dequeued.

Pros

  • Lower exploration count
  • Good speed at high grid sizes

Cons

  • Can lose optimality
  • Quality depends on weight

Best use: When responsiveness matters more than guaranteed shortest path.

Interesting fact: Weighted A* is common in games and robotics where near-optimal is acceptable for speed.

Solverdijkstra

Dijkstra

Uniform-cost expansion from the source, optimal for nonnegative weights.

Time: O(E) to O(E log V), depending on queueSpace: O(V)

How It Works

  1. Initialize start with distance 0 and others with infinity.
  2. Expand the currently known minimum-distance node.
  3. Relax each outgoing neighbor distance.
  4. Stop when goal is finalized.

Pros

  • Optimal
  • Generalizes to weighted edges

Cons

  • More work than BFS on unit weights
  • No heuristic acceleration

Best use: Reference optimal solver and weighted-path baselines.

Interesting fact: Dijkstra published his algorithm in 1956 and reportedly designed it in about twenty minutes.

Solvergreedy-best-first

Greedy Best-First

Chooses nodes closest to goal by heuristic only.

Time: Highly input-dependentSpace: O(V)

How It Works

  1. Keep frontier ordered by heuristic h(n).
  2. Expand the most goal-looking node.
  3. Add newly discovered neighbors.
  4. Reconstruct once goal is found.

Pros

  • Very fast in easy layouts
  • Small control overhead

Cons

  • Not optimal
  • Can be misled by local geometry

Best use: Quick approximate solving and heuristic demonstrations.

Interesting fact: Greedy best-first can outperform optimal methods on easy maps but degrade sharply on deceptive ones.

Solverbidirectional-bfs

Bidirectional BFS

Runs two BFS waves from start and goal until they meet.

Time: Often far less than single-source BFSSpace: O(V)

How It Works

  1. Initialize one queue at start and another at goal.
  2. Alternate expanding the smaller frontier.
  3. Detect when a node is seen by both searches.
  4. Stitch both parent chains into one path.

Pros

  • Big practical speedups on long corridors
  • Still optimal on unweighted graphs

Cons

  • More bookkeeping
  • Path merge logic is trickier

Best use: Large mazes with distant start/goal pairs.

Interesting fact: Meeting in the middle can reduce explored states exponentially in branching factor terms.

Solverdead-end-filling

Dead-End Filling

Prunes leaves iteratively until only solution corridor remains.

Time: O(V + E)Space: O(V)

How It Works

  1. Compute each cell degree in the maze graph.
  2. Queue non-start/non-goal dead ends (degree <= 1).
  3. Remove dead ends and update neighbor degrees.
  4. Remaining cells form the final path corridor.

Pros

  • Very different visual style
  • No heuristic needed

Cons

  • Less intuitive to users expecting search waves
  • Best suited to perfect mazes

Best use: Teaching maze topology and pruning-based solving.

Interesting fact: This method solves by elimination, not by explicitly chasing the goal first.

Solverlee-wavefront

Lee Wavefront

Distance-wave flood fill from goal, then gradient backtrace from start.

Time: O(V + E)Space: O(V)

How It Works

  1. Run BFS-like wavefront from the goal and assign distance labels.
  2. Stop once start is labeled (or all reachable nodes are processed).
  3. Trace from start by repeatedly moving to a neighbor with smaller distance.
  4. Mark traced cells as the final path.

Pros

  • Optimal in unweighted mazes
  • Path extraction is simple and deterministic

Cons

  • Needs full distance map storage
  • Can explore broad regions like BFS

Best use: Wave-propagation visualizations and shortest-path extraction via gradients.

Interesting fact: Lee's algorithm is a classic in PCB routing and grid-based shortest-path problems.

Solverwall-follower

Wall Follower (Right-Hand)

Follows one wall consistently to eventually find the goal in simply connected mazes.

Time: Input-dependent, typically O(E) in tree mazesSpace: O(V) with parent tracking

How It Works

  1. Keep a heading and prefer right turn, then straight, then left, then back.
  2. Move through open passages while maintaining wall contact.
  3. Record discovery parents for path reconstruction.
  4. When goal is reached, reconstruct and display the route.

Pros

  • Very intuitive
  • Great for demonstrating local decision rules

Cons

  • Not generally optimal
  • Can fail in non-simply-connected wall topologies

Best use: Educational demos of local navigation strategies.

Interesting fact: In perfect mazes (tree mazes), wall following always reaches the goal because there are no isolated loops.

Solverleft-wall-follower

Wall Follower (Left-Hand)

Left-hand counterpart of wall following with mirrored turn preference.

Time: Input-dependent, typically O(E) in tree mazesSpace: O(V) with parent tracking

How It Works

  1. Keep one hand on the left wall while moving.
  2. Prefer left turn, then straight, then right, then back.
  3. Track visited/discovered cells and parent links.
  4. Reconstruct path after goal is reached.

Pros

  • Simple local rule
  • Useful for comparing handedness behavior

Cons

  • Not generally optimal
  • Same topology limits as right-hand variant

Best use: Educational side-by-side comparison with right-hand wall following.

Interesting fact: In simply connected mazes, left-hand and right-hand rules both solve, but can produce very different traversal traces.

Solverrandom-mouse

Random Mouse

Chooses random moves at junctions with no directional strategy.

Time: Highly variable; can be very largeSpace: O(V) with parent/discovery tracking

How It Works

  1. Start at entrance and pick random open move each step.
  2. Record first-discovery parents for optional reconstruction.
  3. Continue until goal is reached (or fallback solver is applied).

Pros

  • Extremely simple
  • Great baseline for comparison

Cons

  • Unreliable performance
  • No optimality guarantees

Best use: Baseline and educational contrast against informed solvers.

Interesting fact: Random Mouse is often used as the lower-bound benchmark in maze-solver studies.

Solverflood-fill

Flood Fill

Floods distance labels, then follows descending gradient to goal.

Time: O(V + E)Space: O(V)

How It Works

  1. Run wavefront from goal to compute distances.
  2. Once start distance is known, trace to smaller-distance neighbors.
  3. Mark traced route as the final shortest path.

Pros

  • Shortest path in unweighted mazes
  • Clear wave visualization

Cons

  • Needs full distance map
  • Can expand broad regions

Best use: Micromouse-style distance-field solving demonstrations.

Interesting fact: Flood fill and Lee wavefront are closely related formulations on grid graphs.

Solverpledge

Pledge Algorithm

Wall-following with turn accounting to escape loops/islands.

Time: Input-dependentSpace: Low local memory (higher in visualizer for tracing)

How It Works

  1. Pick preferred heading.
  2. Move straight when possible; otherwise follow wall.
  3. Track net turn count while wall-following.
  4. Leave wall when heading and turn count reset conditions are met.

Pros

  • More robust than naive wall following
  • Good local-navigation concept

Cons

  • Still not shortest-path optimal
  • More state than hand-on-wall rule

Best use: Comparing local heuristics in non-trivial topologies.

Interesting fact: Pledge specifically addresses wall-follower failures around detached wall islands.

Solvertremaux

Tremaux

Mark-based exploration that avoids repeatedly traversing passages.

Time: O(V + E) typicalSpace: O(V + E) for marks

How It Works

  1. Mark edges/passages as they are traversed.
  2. Prefer unmarked exits; backtrack on marked branches.
  3. Avoid over-marked branches unless forced.
  4. Eventually reaches exit if reachable.

Pros

  • Guaranteed for finite mazes
  • Human-doable with marks

Cons

  • Not shortest-path optimal
  • Needs marking memory

Best use: Historical human-solvable guaranteed strategy demos.

Interesting fact: Tremaux's algorithm predates modern graph-search terminology but maps well to DFS ideas.

Solverchain

Chain

Global-map style chaining method that links expansion fronts.

Time: Implementation-dependentSpace: O(V)

How It Works

  1. Maintain connected exploration chains from endpoints.
  2. Expand chains while preserving linkage structure.
  3. Detect and connect chain intersections.
  4. Reconstruct resulting route(s).

Pros

  • Global structural reasoning
  • Useful for comparative studies

Cons

  • Less common in mainstream libraries
  • Harder to implement cleanly

Best use: Advanced solver comparison sets.

Interesting fact: Chain-style methods are documented in Think Labyrinth as broad-topology solvers.

Solvercul-de-sac-filler

Cul-de-sac Filler

Extends dead-end elimination to prune cul-de-sac style branches.

Time: O(V + E)Space: O(V)

How It Works

  1. Identify dead-end-like and cul-de-sac candidates.
  2. Iteratively remove non-solution side branches.
  3. Repeat until only core route structure remains.

Pros

  • Topology-first solving
  • Useful structural visualization

Cons

  • Less intuitive than path search
  • Best with full maze map

Best use: Map-analysis style solving workflows.

Interesting fact: Cul-de-sac pruning can be seen as generalized leaf stripping on maze graphs.

Solverblind-alley-sealer

Blind Alley Sealer

Seals blind alleys to reveal viable route corridors.

Time: O(V + E)Space: O(V)

How It Works

  1. Detect blind alley candidates.
  2. Seal candidates and update neighborhood state.
  3. Iterate until no additional blind alleys are found.

Pros

  • Strong structural interpretation
  • Highlights non-solution regions

Cons

  • Requires global map view
  • Less direct than shortest-path search

Best use: Structural maze analysis and elimination visuals.

Interesting fact: Sealer variants preserve structural context while removing navigational noise.

Solverblind-alley-filler

Blind Alley Filler

Fills blind alleys iteratively, leaving only viable route cores.

Time: O(V + E)Space: O(V)

How It Works

  1. Find current blind alleys.
  2. Fill one or more blind alleys.
  3. Update neighboring alley status and continue.

Pros

  • Simple elimination concept
  • Works well in map-view mode

Cons

  • Not a local in-maze strategy
  • Can be slower than direct search

Best use: Comparing elimination solvers with search-based solvers.

Interesting fact: Blind alley filling is conceptually similar to iterative graph leaf removal.

Solvercollision-solver

Collision Solver

Expands from both ends and solves where search waves collide.

Time: Near bidirectional BFS behaviorSpace: O(V)

How It Works

  1. Start simultaneous expansion from start and goal.
  2. Track visited sets and parent links for both waves.
  3. When waves collide, stitch the two partial paths.
  4. Output one or multiple shortest collision routes.

Pros

  • Fast for distant endpoints
  • Natural two-wave visualization

Cons

  • More merge bookkeeping
  • Depends on collision tie handling

Best use: Bidirectional shortest-path comparisons.

Interesting fact: Collision-style solving is closely tied to bidirectional search theory.

Solvershortest-paths-finder

Shortest Paths Finder (All)

Identifies the full set of cells that belong to shortest routes.

Time: O(V + E)Space: O(V)

How It Works

  1. Compute distances from start.
  2. Compute distances from goal.
  3. Keep cells where dStart + dGoal equals shortest distance.
  4. Mark resulting shortest-path manifold.

Pros

  • Shows all shortest alternatives
  • Great for route multiplicity analysis

Cons

  • More data than single-path methods
  • Can look dense in open areas

Best use: Analyzing alternative optimal routes.

Interesting fact: A single shortest path is just one sample from this full shortest-path set.

Solvershortest-path-finder

Shortest Path Finder

Finds one shortest route from start to goal.

Time: O(V + E) on unweighted mazesSpace: O(V)

How It Works

  1. Run shortest-path wave expansion.
  2. Track predecessor for first arrival at each node.
  3. Reconstruct one optimal route at goal.

Pros

  • Deterministic and optimal
  • Low conceptual overhead

Cons

  • Returns one path only
  • Does not enumerate all optimal alternatives

Best use: Practical shortest-route extraction.

Interesting fact: On unweighted grids, this is equivalent to BFS shortest-path recovery.