Many dungeon games generate random dungeon maps, and a good dungeon map is aesthetically pleasing; The generation of mazes is simpler than the generation of dungeons, do not need to consider the place of the room, the generation of mazes can be said to be the basis of the generation of dungeons (but also a reference) the common algorithm of the generation of mazes have recursive backtracking, recursive divide and rule and so on; The maze generated by spanning tree algorithm is a beautiful perfect maze. The so-called perfect maze is that there is only one path between any two reachable points; This property naturally fits well with spanning trees, so we’re going to use Kruskal’s minimum spanning tree algorithm to generate a perfect maze

Kruskal algorithm

Spanning tree: traversing a connected graph, the combination of edges and vertices passed in the process can be regarded as an ordinary tree, usually called a spanning tree; A spanning tree must meet two conditions: 1) contain all vertices in a connected graph; 2) Minimum spanning tree with and only one path between any two vertices: The edge weight of an undirected connected graph and the minimum spanning tree are in good agreement with the characteristics of the visible spanning tree and the perfect maze (there is and only one path between the reachable points), so the spanning tree algorithm can be used to generate the maze Kruskal algorithm: A common minimum spanning tree algorithm. The basic idea of the algorithm is to maintain a bunch of sets, query whether two elements (nodes) belong to the same set, and merge the two sets until a tree is formed

#### Kruskal algorithm describes #### 1. Input: a weighted connected graph where the set of vertices is V and the set of edges is E 2. 3. Sort E, take the smallest edge in E, if the nodes on both sides do not belong to the same set, then merge the nodes and add the edge to E'; Otherwise ignore 4. Repeat Step 3 until the number of edges in E' reaches n-1(the total number of nodes is N), then the spanning tree is completed 5. Use E' to describe the minimum spanning treeCopy the code

Check and set

Set and lookup: An attribute data structure that supports two operations: 1) determining which subset an element is in; 2) Merge two subsets into one set. There is a popular metaphor about the query set: several families have a party, but the family is generally long, so there are many people. Due to the long separation and the growth of age, these people gradually forget their relatives, only remember who their father is, and the oldest (called the “ancestor”) father has died, he only knows himself as the ancestor. To find out which family they belonged to, they came up with a way to simply ask if their father was an ancestor, layer by layer, until they got to the ancestor. If you want to determine whether two people are in the same family, you just have to look at whether their ancestors are the same person and the idea of looking up sets is similar to this, layer by layer, path compression: Obviously, there is a problem here: when the family chain is too long, it is obviously a waste of time to look up layers of ancestors; The information about fathers and grandfathers, which has nothing to do with ancestors, can be completely ignored and only need to record who someone’s ancestors are. The merge operation is simple. For example, merge A and B, because it does not care whether the ancestor fa or Fb is merged, as long as there is one set, so just hang one set under the other. In some cases, the number of subset nodes may affect the efficiency when merging. In this case, merging by rank can be considered, that is, the final ancestor fa or Fb can be selected according to the number of nodes of A and B or the height of the tree

Reference implementation
fa = [0] * MAXN                  # Keep track of who someone's father is. Specifically, the ancestor's father is himself

# Without path compression
def find(x) :
    if fa[x] == x:               # return if x is the ancestor
        return x
    else:
        return find(fa[x])       If not, then X's father asks X's grandfather
    
# with path compression
def findEx(x) :
    ifx ! = fa[x]:# x is not its own father, i.e. x is not a representative of the set
        fa[x] = find(fa[x])      # Search the ancestor of x until it finds the representative, so the path is compressed accordingly
    return fa[x]
    
# merger
def union(x, y) :
    x = find(x)
    y = find(y)
    fa[x] = y                    # Turn x's ancestor into y's ancestor's son
Copy the code

The basic idea

  1. Both the wall and the reachable points occupy one map grid
  2. Initialize the map as the interval between the wall and the reachable point. Any two reachable points are not connected
  3. A path is formed by removing the wall on the planned path and making it a reachable point
  4. The barrier walls are treated as the edges of the undirected graph, because there is no weight to consider, just random selection
  5. To run Kruskal algorithm, it is necessary to confirm whether the query reachable points belong to the same set, and optimize the efficiency by using and querying the set

Refer to the following figure: The black block is the wall, the white block is the reachable point, and the wall on the path (red line) needs to be removed to become the reachable point (in Kruskal’s algorithm, is the edge set of the selected spanning tree).

implementation

class Maze() :
    def init(self, width, height) :
        Initialize.
        self.wt = width           # Width, the initial number of reachable points per row
        self.ht = height          Height, the initial number of reachable points per column

        self.fa = {}              # is used to look up sets
        self.mp = []              # map
        for i in range(0, height * 2 + 1):
            self.mp.append([1] * (width * 2 + 1))
        for i in range(1, height * 2.2) :for j in range(1, width * 2.2):
                self.mp[i][j] = 0
                self.fa[(i, j)] = (i, j)

    def show(self) :
        Output map (special symbols affected by console font)
        for i in range(0, self.ht * 2 + 1.1) :print(' '.join('■' if j else ' ' for j in self.mp[i]))

    def gen(self) :
        Generation algorithm implementation
        # Count all edges (obstacles)
        wait = []
        for i in range(1, self.ht * 2.2) :for j in range(2, self.wt * 2.2):
                wait.append((i, j))
        for i in range(2, self.ht * 2.2) :for j in range(1, self.wt * 2.2):
                wait.append((i, j))

        while len(wait):
            idx = random.randint(0.len(wait) - 1)
            e = wait.pop(idx)
            p1, p2 = self.arround(e)
            ifself.find(p1) ! = self.find(p2): self.union(p1, p2) self.mp[e[0]][e[1]] = 0

    def arround(self, e) :
        Get the reachable points on both sides of the barrier
        if e[0] % 2:
            return (e[0], e[1] - 1), (e[0], e[1] + 1)
        else:
            return (e[0] - 1, e[1]), (e[0] + 1, e[1])

    def find(self, p1) :
        "And look up the set to find" "
        ifp1 ! = self.fa[p1]: self.fa[p1] = self.find(self.fa[p1])return self.fa[p1]

    def union(self, p1, p2) :
        "And look up the collection and" "
        pp1 = self.find(p1)
        pp2 = self.find(p2)
        self.fa[pp1] = pp2

maze = Maze()
maze.init(19.19)
maze.gen()
maze.show()
Copy the code

The generated effect is as follows:

Resources: spanning tree https://oi-wiki.org/graph/mst/ and search set https://oi-wiki.org/ds/dsu/