在平面地图上随机生成块

Question

我试图在平面地图上随机生成块,并使它们不会相互重叠.我已经制作了一个地图大小(500x500)的矩阵(c#数组),这些块的比例在1到5之间.代码可以工作但是如果生成的块与另一个块重叠,它就会被破坏而不会在其他地方重新生成.

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

这是地图的图片,生成了大约80个块,绿色方块是块

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个可能的修复方法

• 我应该根据它的位置设置块的大小.
• 我应该使用另一种随机化算法.
• 我做得不对.

您认为最好的想法是什么？

---

UPDATE

我让代码工作得更好.我现在尝试在需要时多次实例化块(当前最多5个)并修复了错误.如果地图上已经有很多元素,它们将不会总是被实例化,这就是我想要的,我只需找到它将尝试实例化块的正确数量.

我尝试在500x500地图上实例化1280个元素.它只需要大约1.5秒,并实例化1278/1280块(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

但是............

......你会发现这看起来很"正常",所以这样做:

只是随机扰乱所有的块.请记住,视频游戏编程是关于巧妙的技巧!

理想情况下,你必须从中间开始并逐步解决; 无论如何,你不能只是排成一行.洗牌是可以的.所以,这样做..

   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调整因子值.

有许多方法可以扰乱不同大小的块的区域,上面是一个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

只需从前面拿出你需要的东西:所以,3,8,6等.

所以举一个例子让我们说你需要12个数字,没有重复,从1到75.所以第一个问题是,你想要一个列表,所有数字最多为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);

简而言之,当你想要"n"个数字,在1和Max之间没有重复时,你只需要这样:

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

etvoilà,你可以查看结果 foreach(int r in shuf) Debug.Log(r);

我只是详细解释这个问题,因为这个问题经常被问到"如何获得独特的随机数".这是一个"古老的"编程技巧,答案很简单就是你将所涉及的所有整数数组洗牌.

有趣的是,如果你谷歌这个问题("如何获得独特的随机数字")这是谷歌没有太大帮助的极少数情况之一,因为:无论什么时候提出这个问题,你都会得到过多的敏锐的新程序员(谁没有听过这样做的简单伎俩!)写出巨大的复杂思想,导致进一步的混乱和复杂化.

这就是你如何制作没有重复的随机数,幸运的是它是微不足道的.