C#实现4种经典迷宫生成算法和迷宫寻路算法（五） |
您所在的位置：网站首页 › 迷宫生成算法和迷宫寻路算法 › C#实现4种经典迷宫生成算法和迷宫寻路算法（五） |
C#实现4种经典迷宫生成算法和迷宫寻路算法（五）
|
使用递归切割算法生成迷宫
要说明递归切割算法，我们先来看下图：
（1）在r1到r2这段线上面，随机地点3个点，分别是rd1、rm、rd2。c同理。 （2）通过rm和cm两根线，矩形被分成了4块。 （3）我们看红圈的地方，总共有4个，分别是(rm,cd1)、(rd2,cm)、(rm,cd2)和(rd1,cm)。 （4）4个红圈，只要打通任意3个，四块区域就能连通起来。 （5）我们把这个过程复制到4块区域中的其中一块，不断递归循环下去，直到不能再分为止。 递归切割算法就是这样了！代码如下： public override void Build() { InitM(); int r1 = 0; int r2 = room_row - 1; int c1 = 0; int c2 = room_col - 1; RecursiveDivision(r1, r2, c1, c2, M, new Random()); ParseM(); } private void RecursiveDivision(int r1, int r2, int c1, int c2, int[,,] M, Random rand) { if (r1 < r2 && c1 < c2) { int rm = randint(r1, r2 - 1, rand); int cm = randint(c1, c2 - 1, rand); int cd1 = randint(c1, cm, rand); int cd2 = randint(cm + 1, c2, rand); int rd1 = randint(r1, rm, rand); int rd2 = randint(rm + 1, r2, rand); int d = randint(1, 4, rand); switch (d) { case 1: M[rd2, cm, 2] = 1; M[rd2, cm + 1, 0] = 1; M[rm, cd1, 3] = 1; M[rm + 1, cd1, 1] = 1; M[rm, cd2, 3] = 1; M[rm + 1, cd2, 1] = 1; break; case 2: M[rd1, cm, 2] = 1; M[rd1, cm + 1, 0] = 1; M[rm, cd1, 3] = 1; M[rm + 1, cd1, 1] = 1; M[rm, cd2, 3] = 1; M[rm + 1, cd2, 1] = 1; break; case 3: M[rd1, cm, 2] = 1; M[rd1, cm + 1, 0] = 1; M[rd2, cm, 2] = 1; M[rd2, cm + 1, 0] = 1; M[rm, cd2, 3] = 1; M[rm + 1, cd2, 1] = 1; break; case 4: M[rd1, cm, 2] = 1; M[rd1, cm + 1, 0] = 1; M[rd2, cm, 2] = 1; M[rd2, cm + 1, 0] = 1; M[rm, cd1, 3] = 1; M[rm + 1, cd1, 1] = 1; break; } RecursiveDivision(r1, rm, c1, cm, M, rand); RecursiveDivision(r1, rm, cm + 1, c2, M, rand); RecursiveDivision(rm + 1, r2, cm + 1, c2, M, rand); RecursiveDivision(rm + 1, r2, c1, cm, M, rand); } else if (r1 < r2) { int rm = randint(r1, r2 - 1, rand); M[rm, c1, 3] = 1; M[rm + 1, c1, 1] = 1; RecursiveDivision(r1, rm, c1, c1, M, rand); RecursiveDivision(rm + 1, r2, c1, c1, M, rand); } else if (c1 < c2) { int cm = randint(c1, c2 - 1, rand); M[r1, cm, 2] = 1; M[r1, cm + 1, 0] = 1; RecursiveDivision(r1, r1, c1, cm, M, rand); RecursiveDivision(r1, r1, cm + 1, c2, M, rand); } } private int randint(int start, int end, Random rand) { return rand.Next(end - start) + start; }使用递归切割算法能到的迷宫如下图所示：
特点是很明显的，就是直路特别多，但找路比较难。 4种生成算法介绍到这里，最后一篇会讲解A*寻路算法。 |
【本文地址】
今日新闻 |
推荐新闻 |