Generate a maze using Kruskal's algorithm

maze.py

import copy
import random
from typing import NamedTuple, FrozenSet

maze_height = 24
maze_width = 48

map_height = 50
map_width = 80

directions = (
    (0, -1),  # north k
    (1, 0),  # east l
    (0, 1),  # south j
    (-1, 0),  # west h
)


class Node(NamedTuple):
    x: int
    y: int


class Edge(NamedTuple):
    nodes: FrozenSet[Node]

    @classmethod
    def connecting(cls, node1, node2):
        return cls(frozenset((node1, node2)))


edges = set()
nodes = set()

for x1 in range(maze_width):
    for y1 in range(maze_height):
        node1 = Node(x1, y1)
        nodes.add(node1)
        for dx, dy in directions:
            x2 = x1 + dx
            y2 = y1 + dy
            node2 = Node(x2, y2)
            if x2 >= 0 and x2 < maze_width and y2 >= 0 and y2 < maze_height:
                edge = Edge.connecting(node1, node2)
                edges.add(edge)

print(len(edges))
print(len(nodes))

# pull an edge from the ones we haven't processed yet
# if it joins node(s) that we haven't seen yet, then we use the edge to connect the
# two nodes
# or it joins two nodes from different groups, also use the edge
# if the edge does neither of those things, throw it away
# assign the connected nodes to the same group (or label them the same, or something)
# remove the nodes from the unprocessed set
# repeat until no edges are left
# assert that there are also no nodes left
# assert that there is only one group of nodes/edges
# walk all of the edges and use them to draw the map

map_ = [['#' for x in range(map_width)] for y in range(map_height)]

x = 40
y = 25

map_[y][x] = ' '


iterations = 10
for i in range(iterations):
    # pick a direction and walk a few tiles
    directions = (
        (0, -1),  # north k
        (1, 0),  # east l
        (0, 1),  # south j
        (-1, 0),  # west h
    )
    dx, dy = random.choice(directions)
    length = random.randint(1, 4)
    for _ in range(length):
        x += dx
        y += dy
        map_[y][x] = ' '


def show_map():
    for row in map_:
        for tile in row:
            print(tile, end='')
        print('')


if __name__ == '__main__':
    show_map()

References:

• https://people.cs.ksu.edu/~ashley78/wiki.ashleycoleman.me/index.php/Kruskal's_Algorithm.html
• http://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm