c# - 在平面 map 上随机生成方 block

Question

我试图在平面 map 上随机生成方 block ，并使它们不会相互重叠。 我制作了一个 map 大小 (500x500) 的矩阵(c# 数组)， block 的比例在 1 到 5 之间。 该代码有效，但如果生成的 block 与另一个 block 重叠，它将被破坏并且不会在其他地方重新生成。

我尝试生成的 1000 个 block 中只有大约 80 个不与另一个 block 重叠。

这是生成了大约 80 个方 block 的 map 图片，绿色方 block 是方 block

void generateElement(int ratio, int minScale, int maxScale, GameObject g) {
    bool elementFound = false;
    for (int i = 0; i < ratio * generationDefault; i++) {
        GameObject el;
        // Randomly generate block size and position
        int size = Random.Range(minScale, maxScale + 1);
        int x = Random.Range(0, mapSizex + 1 - size);
        int y = Random.Range(0, mapSizey + 1 - size);

        // Check if there is already an element 
        for (int j = x; j < x + size; j++)
            for (int k = y; k < y + size; k++)
                if (map[j][k] != null)
                    elementFound = true;
        if (elementFound)
            continue;
        else {
            el = (GameObject)Instantiate(g, new Vector3(x + (float)size / 2, (float)size / 2, y + (float)size / 2), Quaternion.Euler(0, 0, 0));
            el.transform.localScale *= size;
        }
        // Create element on map array
        for (int j = x; j < x + size; j++)
            for (int k = y; k < y + size; k++)  
                if (map[j][k] == null) {
                    map[j][k] = el.GetComponent<ObjectInterface>();
                }
    }
}

我想到了 3 个可能的修复方法

• 我应该根据它所处的位置来设置 block 的大小。
• 我应该使用另一种随机化算法。
• 我做的不对。

你认为最好的主意是什么？

---

更新

我的代码工作得更好了。如果需要，我现在尝试多次实例化这些 block (目前最多 5 次)并修复了这些错误。如果 map 上已经有很多元素，它们将不会总是被实例化，这就是我想要的，我只需要找到它尝试实例化 block 的正确次数。

我尝试在 500x500 map 上实例化 1280 个元素。只用了大约 1.5 秒，它实例化了 1278/1280 个 block (99.843%)。

void generateElement(int ratio, int minScale, int maxScale, GameObject g) {
bool elementFound = false;
int cnt = 0;
// Generate every block
for (int i = 0; i < ratio * generationDefault; i++) {
    GameObject el = null;
    // Randomly generate block size and position
    int size, x, y, tryCnt = 0;

    // Try maximum 5 times to generate the block
    do {
        elementFound = false;
        // Randomly set block size and position
        size = Random.Range(minScale, maxScale + 1);
        x = Random.Range(0, mapSizex + 1 - size);
        y = Random.Range(0, mapSizey + 1 - size);

        // Check if there is already an element 
        for (int j = x; j < x + size; j++)
            for (int k = y; k < y + size; k++)
                if (map[j][k] != null)
                    elementFound = true;
        tryCnt++;
    } while (elementFound && tryCnt < 5);
    if (tryCnt >= 5 && elementFound) continue;

    // Instantiate the block
    el = (GameObject)Instantiate(g, new Vector3(x + (float)size / 2, (float)size / 2, y + (float)size / 2), Quaternion.Euler(0, 0, 0));
    el.transform.localScale *= size;
    // Create element on map array
    for (int j = x; j < x + size; j++)
        for (int k = y; k < y + size; k++)  
            if (map[j][k] == null) {
                map[j][k] = el.GetComponent<ObjectInterface>();
            }
    cnt++;
}
print("Instantiated " + cnt + "/" + ratio * generationDefault);

Answer 1

这很难做好。

这里有一个您可能会喜欢的快速解决方案……取决于您的场景。

actualWidth = 500 //or whatever. assume here is square
// your blocks are up to 5 size
chunkWidth = actualWidth / 5
// it goes without saying, everything here is an int
kChunks = chunkWidth*chunkWidth
List<int> shuf = Enumerable.Range(1,kChunks).OrderBy(r=>Random.value).ToList();
howManyWanted = 1000
shuf = shuf.Take(howManyWanted)
foreach( i in shuf )
   x = i % actualWidth
   y = i / actualWidth
   make block at x y
   put block in list allBlocks

然而…………

---

......你会发现这看起来有点“常规”，所以这样做:

只是随机扰动所有 block 。请记住，视频游戏编程是关于聪明的把戏!

理想情况下，您必须从中间开始，然后逐步解决；无论如何，你不能只是把它们排成一行。洗牌是可以的。所以，这样做..

   harmonic = 3  //for example. TRY DIFFERENT VALUES
   
   function rh = Random.Range(1,harmonic) (that's 1 not 0)
   
   function rhPosNeg
       n = rh
       n = either +n or -n
       return n
   
   function onePerturbation
   {
   allBlocks = allBlocks.OrderBy(r => Random.value) //essential
   foreach b in allBlocks
      newPotentialPosition = Vector2(rhPosNeg,rhPosNeg)
      possible = your function to check if it is possible
           to have a block at newPotentialPosition,
           however be careful not to check "yourself"
      if possible, move block to newPotentialPosition
   }

最简单的方法就是运行 onePerturbation，比方说，运行三次。在每次运行之间查看它。还可以尝试不同的 harmonic 调整因子值。

有很多方法可以扰动不同大小 block 的字段，上面是一个 KISS 解决方案，希望它适合您的情况。

---

编码笔记...

如何获得一组唯一的随机数。

只是解释一下这行代码...

List<int> shuf = Enumerable.Range(1,kChunks).OrderBy(r=>Random.value).ToList();

如果您是编码新手:假设您想这样做:“获取一百个随机数，从 1 到百万，但不重复”。

幸运的是，这是一个众所周知的问题，并且有一个非常简单的解决方案。

获得无重复数字的方法很简单，就是打乱所有数字，然后从顶部取出您想要的数字。

例如，假设您需要 1 到 10 之间的一对随机数字，但没有重复。

所以，这是 1-10 的数字:3,8,6,1,2,7,10,9,4,5

简单地从前面取出你需要的东西:so, 3, 8, 6 etc.

举个例子，假设您想要从 1 到 75 的 12 个数字，没有重复。所以第一个问题是，您想要一个包含最多 75 个数字的列表，但打乱顺序。事实上你是这样做的..

List<int> shuf = Enumerable.Range(1,75).OrderBy(r=>Random.value).ToList();

因此该列表有 75 个项目。您可以通过说 foreach(int r in shuf) Debug.Log(r); 来检查它。在接下来的示例中，您只需要其中的 12 个数字。幸运的是，有一个 List 调用可以执行此操作:

shuf = shuf.Take(12)

就是这样 - 你现在有 12 个数字，没有重复，都是 1 到 75 之间的随机数。你可以再次检查 foreach(int r in shuf) Debug.Log(r);

简而言之，当您想要在 1 和 Max 之间没有重复的“n”个数字时，您所要做的就是:

List<int> shuf = Enumerable.Range(1,Max).OrderBy(r=>Random.value).ToList();
shuf = shuf.Take(n);

等等，你可以用 foreach(int r in shuf) Debug.Log(r);

检查结果

我只是详细解释一下，因为这个问题经常被问到“如何获得唯一的随机数”。这是一个“古老”的编程技巧，答案很简单，就是您打乱一个包含所有相关整数的数组。

有趣的是，如果您用谷歌搜索这个问题(“如何获得唯一的随机数”)，它是极少数情况下谷歌帮不上什么的情况之一，因为:无论何时问这个问题，你会遇到大量敏锐的新程序员(他们还没有听过正确执行此操作的简单技巧!!)写出大量冗长复杂的想法，导致进一步的困惑和复杂化。

这就是你如何生成没有重复的随机数，幸运的是它是微不足道的。