Algorithms

Prim’s starts at a random point and expands the labyrinth by always selecting a random neighboring wall of an already visited cell and opening it. Advantage: Produces very uniform, natural-looking labyrinths with many short dead ends. Visually, it appears like organic growth from a central point. Wikipedia

Kruskal’s considers all walls of the grid as potential paths. It randomly selects walls and opens them only if the two adjacent cells are not yet connected (preventing cycles). Advantage: Produces a very complex labyrinth with many long, winding paths. Visually, it is engaging because the labyrinth emerges simultaneously in many places and eventually merges into a whole. Wikipedia

Original work

• Robert C. Prim (1957): Shortest connection networks and some generalizations
• Joseph B. Kruskal (1956): On the shortest spanning subtree of a graph and the traveling salesman problem

How it works

The grid has 101 × 101 cells. Cells with even coordinates are rooms (51 × 51 = 2,601), the cells between them are walls. Both algorithms first compute the order in which walls are opened; the animation then opens them one by one. The result is a spanning tree: every room is reachable and there is exactly one way between two rooms.

• Prim (randomized): starts in a random room and keeps a frontier list of walls to rooms not yet visited. Each step picks a random wall (swap with the last element, then pop: O(1)) and opens it if the room behind it is still unvisited. Randomness replaces edge weights.
• Kruskal (randomized): all 5,100 walls between two rooms are collected and shuffled with Fisher-Yates. Each room carries a set id. A wall is opened when the rooms have different ids; then all rooms of one set get the id of the other. That is one pass over the grid per union, simpler than union-find and fast enough for 2,601 rooms.
• Start and goal sit in two random corners. Dijkstra and A* then run on the same grid as on the pathfinding page.
• Memory: one node object per cell (10,201) plus the list of cells to open.

Source code:maze-generator.service.ts

Note Both algorithms are based on the principle of the 'Minimum Spanning Tree'. This means for your labyrinth:

• Perfect labyrinth: There are no closed loops – every point is reachable, but there is always exactly one path between any two points.
• Reachability: Since it is a spanning tree, every cell in the grid is guaranteed to be part of the labyrinth; there are no isolated areas.
• Randomness: By weighting the edges with random values, each run produces completely new, unique structures.
• Application: Such labyrinths are the perfect test environment for pathfinding algorithms such as Dijkstra or A*.