Mine Sweeper：改进我的随机定位算法？

Question

这是我创建一个随机生成地雷的网格的代码。问题是地雷太分散了，所以当我计算非地雷单元的地雷时，它主要有值 1、2 而几乎没有值 4、5、6、7。如何改进这个算法？

假设列数、行数和地雷数不变。

var r = new Random();
int columns, rows, TotalMine;
int[,] grid = new int[columns, rows];

int MineCount = 0;
int X = 0;
int Y = 0;

// Add Mines (This is so simple, it cause the problem)
while (MineCount++ < TotalMine)
{
    do
    {
        X = r.Next(columns);
        Y = r.Next(rows);
    }
    while (grid[X, Y] == -1);

    grid[X, Y] = -1; // -1 = have mine
}

Answer 1

您的算法非常好，会随机生成地雷（假设 RNG 足够好）。

我能想到的一种改进方法是使用 生命游戏 算法来消除极端情况，例如杂乱的田地，其中一个田地被 7 或 8 个地雷包围。

只需遍历所有字段并计算周围的地雷（即计算字段数）。如果它是 7 或 8，移除它旁边的一个随机地雷。

作为替代方案，您可以使用 perlin 噪声来创建 "clouds"，然后只在您至少有给定 "density" 的区域随机放置地雷。这样你就可以很容易地创建更大的区域，中间没有任何东西。

您也可以将这两种想法稍微混合一下：

创建一个 table 或与您的比赛场地一样大的棋盘，数值随机分布（true 或 false）。
使用生命游戏算法进行多次迭代以创建一些模式（您最终应该得到"islands"或随机结构）。
仅将地雷放置在设置为 false（或 true - 无论您选择什么）的区域内。

Mine Sweeper：改进我的随机定位算法？

Mine Sweeper: Improve mine random locate algorithm?

c#

algorithm

minesweeper