使用随机算法生成迷宫

随机算法的思路是这样的：

（1）把起点S放到一个列表里面。

（2）随机地从列表里取出一个格子，把它标记为1。如果跟它相邻的格子没有被访问过，则标记为2，放到列表里。如果已经访问过，随机挑一个，打通墙。

（3）重复第一步。

其流程如下图所示：

随机算法代码如下：

public override void Build()
{
    InitM();

    int r = 0;
    int c = 0;
    List<Position> history = new List<Position>();
    history.Add(GetPosition(r, c));

    Random rand = new Random();
    while (history.Count != 0)
    {
        int index = rand.Next(history.Count);
        Position current = history[index];
        r = current.row;
        c = current.col;
        M[r, c, 4] = 1;
        history.RemoveAt(index);

        List<char> directions = new List<char>();

        if (c > 0)
        {
            if (M[r, c - 1, 4] == 1)
            {
                directions.Add('L');
            }
            else if (M[r, c - 1, 4] == 0)
            {
                history.Add(GetPosition(r, c - 1));
                M[r, c - 1, 4] = 2;
            }
        }
        if (r > 0)
        {
            if (M[r - 1, c, 4] == 1)
            {
                directions.Add('U');
            }
            else if (M[r - 1, c, 4] == 0)
            {
                history.Add(GetPosition(r - 1, c));
                M[r - 1, c, 4] = 2;
            }
        }
        if (c < room_col - 1)
        {
            if (M[r, c + 1, 4] == 1)
            {
                directions.Add('R');
            }
            else if (M[r, c + 1, 4] == 0)
            {
                history.Add(GetPosition(r, c + 1));
                M[r, c + 1, 4] = 2;
            }
        }
        if (r < room_row - 1)
        {
            if (M[r + 1, c, 4] == 1)
            {
                directions.Add('D');
            }
            else if (M[r + 1, c, 4] == 0)
            {
                history.Add(GetPosition(r + 1, c));
                M[r + 1, c, 4] = 2;
            }
        }

        if (directions.Count != 0)
        {
            int direction_index = rand.Next(directions.Count);
            char direction = directions[direction_index];
            switch (direction)
            {
                case 'L':
                    M[r, c, 0] = 1;
                    c = c - 1;
                    M[r, c, 2] = 1;
                    break;
                case 'U':
                    M[r, c, 1] = 1;
                    r = r - 1;
                    M[r, c, 3] = 1;
                    break;
                case 'R':
                    M[r, c, 2] = 1;
                    c = c + 1;
                    M[r, c, 0] = 1;
                    break;
                case 'D':
                    M[r, c, 3] = 1;
                    r = r + 1;
                    M[r, c, 1] = 1;
                    break;
            }
        }
    }

    ParseM();
}

用随机算法生成的迷宫如下图所示：

其特点是：分支特别多。