使用并查集生成一个迷宫

使用并查集生成一个迷宫

之前在做笔记的时候就想……嗯……大概能写点什么有趣的东西出来加强一下记忆？

于是就整出了这个，然后发现对于 setTimeout 以及 setTimeInterval 的应用还不行啊，晚点继续折腾一下。

并查集部分的笔记在这里：并查集(Data Structure for Disjoint Sets)，LC 解题部分在这里：LC 200, 721,684 并查集解法，总体来说并查集是一个实现非常简单的算法结构，理解起来也不是非常的困难。

并查集的核心代码依旧不变：

export default class UnionFind {
  constructor() {
    this.rank = {};
    this.parents = {};
  }

  makeSet(x) {
    this.parents[x] = x;
    this.rank[x] = 0;
  }

  findSet(x) {
    if (this.parents[x] !== this.parents[this.parents[x]]) {
      this.parents[x] = this.findSet(this.parents[this.parents[x]]);
    }

    return this.parents[x];
  }

  link(x, y) {
    if (this.rank[x] > this.rank[y]) {
      this.parents[y] = x;
    } else {
      this.parents[x] = y;
      if (this.rank[x] === this.rank[y]) {
        this.rank[y] = this.rank[y] + 1;
      }
    }
  }

  union(x, y) {
    this.link(this.findSet(x), this.findSet(y));
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

绘图部分用 CSS 来搞定：

const renderBoard = () => {
  return board.map(([up, down, left, right], i) => {
    const classNames = ["uf__cell"];
    if (!up) classNames.push("uf__cell-up");
    if (!down) classNames.push("uf__cell-down");
    if (!left) classNames.push("uf__cell-left");
    if (!right) classNames.push("uf__cell-right");

    return <div className={classNames.join(" ")} key={i}></div>;
  });
};
1
2
3
4
5
6
7
8
9
10
11

其中数组是一个二维数组 是的我没有用三维数组，当然三维数组也可以用，说不定会更简单一些……？，大概结构如下：

const board = [
  // up,  down,  left,  right
  [false, false, false, false],
  [false, false, false, false],
  [false, false, false, false],
  // ...
];
1
2
3
4
5
6
7

中间的 4 个 boolean 代表的是四个方向是否与其他格子进行联通，如果没有联通那么就使用 css 绘制 border。

绘制之后大概如下：

double border 的问题我倒是有想过解决，但是搜了一下直接使用 margin-left: -1px 不太好用，我就放弃了。2b 项目写多了 css 是真的苦手……

本来如果用定时器重新每隔一段时间渲染一下会比较简单，不过我还在挣扎……嗯……无限循环了……所以这里还是使用手动操作去解决了。

不管怎么说看到 A-Star 的时候自动渲染这部分早晚得解决 OTL，现在就先狗着吧。

这个原理就是随机选取一个结点并且将其移除，这个想法是被 LC684. 冗余连接 启发的，写完这道题之后让我觉得好像画一个迷宫就是这么简单，用这道题的变种就行了。

这部分代码如下：

const getAdjacentNode = (node) => {
  let left = null;

  if (node - 1 >= 0 && node % row !== 0) {
    left = node - 1;
  }

  let right = null;

  if (node + 1 < row * col && node % row !== row - 1) {
    right = node + 1;
  }
  const up = node - row < 0 ? null : node - row;
  const down = node + row >= row * col ? null : node + row;

  return [up, down, left, right];
};

const pickNode = () => {
  while (true) {
    const node = getRandomIntInclusive(0, row * col - 1),
      neightbors = getAdjacentNode(node);

    const i = getRandomIntInclusive(0, 4);

    const neighbor = neightbors[i];
    if (!neighbor) continue;

    if (uf.findSet(node) !== uf.findSet(neighbor)) {
      return [node, neighbor, i];
    }
  }
};

const removeNode = () => {
  // there is a path exist already, no need to remove node anymore
  if (uf.findSet(0) === uf.findSet(row * col - 1)) return;

  const [node, neighbor, i] = pickNode();

  uf.union(node, neighbor);

  setBoard((prevState) => {
    const newBoard = _.cloneDeep(prevState);

    switch (i) {
      case 0:
        newBoard[node][0] = true;
        newBoard[neighbor][1] = true;
        break;
      case 1:
        newBoard[node][1] = true;
        newBoard[neighbor][0] = true;
        break;
      case 2:
        newBoard[node][2] = true;
        newBoard[neighbor][3] = true;
        break;
      case 3:
        newBoard[node][3] = true;
        newBoard[neighbor][2] = true;
        break;
      default:
        break;
    }

    return newBoard;
  });
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

为了创建一种伪随机性，这里 随机 抽取了两个元素：

1. 数组中的元素

2. 被选中元素的邻居

   因为没有使用二维数组，所以这里的检查会稍微多一点，否则会出现某行最后一个元素与下一行第一个元素被打通的情况

如果二者不相连的话，那么就返回，否则就继续在 while(true) {} 这个循环里面继续呆着。移除结点就是进行 union 的操作，并且进行 CSS 的修正。

实现后的效果如下：

省略 n 步后：

一些可以做的优化

大概是提速……？如果结点很多的话可能会卡到白屏，50x50 的渲染还挺快：

100x100 的就容易崩，当然，等个几分钟还是能出来的：

主要是 React 还是在网页条件下跑的，直接就把浏览器给 block 了。

其次是目前没有加 cycle detection 的检查

大概是样本太小了，10x10 的图画了好多个没画出一个有圈的，大的图大概有，不过我……不太想找。

感兴趣的源码可以在这里巴拉：https://github.com/GoldenaArcher/algo-visualization，具体可视化的做多少就……有一个做一个了……？