随机生成平面地图上街区 [英] Randomly generate blocks on a flat map

问题描述

我试图平面地图上随机生成的块，并使其以使它们不相互重叠。
我已取得的地图（500×500）的尺寸的矩阵（C＃阵列），该块具有1和5之间的比例。
在code ++工程，但如果产生块重叠另外一个，它被摧毁，而不是再生别处。

I'm trying to randomly generate blocks on a flat map and make it so that they don't overlap each other. I have made a matrix (c# array) of the size of the map (500x500), the blocks have a scale between 1 and 5. The code works but if a generated block overlaps another one, it is destroyed and not regenerated somewhere else.

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

Only around 80 of the 1000 blocks I try to generate don't overlap another block.

下面生成地图的与大约80块的图像，该绿色方块是块

Here is a picture of the map with around 80 blocks generated, the green squares are blocks

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种可能的修复

I thought of 3 possible fixes

• 我应该设置取决于它的地方的块的大小。


• 我应该用另一种随机算法。


• 我不这样做的权利。

你怎么认为是最好的主意吗？

What do you think is the best idea ?

更新

我得到了code工作要好得多。我现在尝试，如果需要（暂时最多5个）多次实例化的块，我修复的错误。如果在地图上已经有很多的元素，他们不会永远被实例化，这就是我想要的，我只需要找到的时候适量它会尝试实例块。

I got the code working much better. I now try to instantiate the blocks multiple times if needed (maximum 5 for the moment) and I fixed the bugs. If there are already many elements on the map, they will not always be instantiated and that's what I wanted, I just have to find the right amount of times it will try to instantiate the block.

我尝试实例化一个500×地图上1280元。只需约1.5第二和它实例化1280分之1278块（99.843％）。

I tried instantiating 1280 elements on a 500x500 map. It takes only about 1.5 second and it instantiated 1278/1280 blocks (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);

}

推荐答案

这是难以置信的困难做好的

下面是一个快速的解决方案，你会也许像......取决于你的场景中。

Here's a quick solution you'll maybe like ... depending on your scene.

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

但............

HOWEVER ............

......你会看到这个看起来有点正规，所以做到这一点：

...... you'll see that this looks kind of "regular", so do this:

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

Just randomly perturb all the blocks. Remember, video game programming is about clever tricks!

在理想情况下，你必须从中间开始，然后你的出路;在任何情况下，你不能只是做他们在一条线上。洗牌是确定。所以，做..

Ideally, you have to start from the middle and work your way out; in any event you can't just do them in a line. Shuffling is OK. So, do this ..

   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 ，说，三次。让每个运行之间的了解一下吧。也可以尝试在谐波调整系数的值不同。

The simplest approach is just run onePerturbation, say, three times. Have a look at it between each run. Also try different values of the harmonic tuning factor.

有许多方法来扰乱领域的不同大小的块，上面是一个KISS的解决方案，希望看起来好您的具体情况。

There are many ways to perturb fields of differently-sized blocks, above is a KISS solution that hopefully looks good for your situation.

编码记...

只是为了解释这一行code ...

Just to explain this line of code...

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

如果你是新来的编码：说你要做到这一点：得一百的随机数，从1到百万，但没有重复

If you are new to coding: say you want to do this: "get a hundred random numbers, from 1 to million, but with no repeats".

幸运的是，这是一个非常众所周知的问题与很简单的解决方案

Fortunately, this is a very well known problem with a very simple solution.

你没有重复数字的方式，简直就是 洗牌的所有号码的，然后把你想要多少从顶部。

The way you get numbers with no repeats, is simply shuffle all the numbers, and then take how many you want off the top.

举例来说，说你需要一个随机数夫妇从1-10，但没有重复。

For example, say you need a random couple of numbers from 1-10 but with no repeats.

所以，这里的1-10洗牌的数字：3,8,6,1,2,7,10,9,4,5

So, here's the numbers 1-10 shuffled: 3,8,6,1,2,7,10,9,4,5

简单地采取你所需要的关闭前：那么，3，8,6等

Simply take what you need off the front: so, 3, 8, 6 etc.

于是做出了榜样，让我们​​说你要12个号码，没有重复，从1到75。所以，第一个问题是，你想用所有的数字高达75，却拖着一个列表。事实上，你是这样做的。

So to make an example let's say you want twelve numbers, no repeats, from 1 through 75. So the first problem is, you want a List with all the numbers up to 75, but shuffled. In fact you do that like this ..

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

所以这名单是75个项目长。你可以这样的foreach（在SHUF INT R）的debug.log（R）检查; 。接下来的例子中，你只希望这些数字12。幸运的是有一个列表调用，它是：

So that list is 75 items long. You can check it by saying foreach(int r in shuf) Debug.Log(r);. Next in the example you only want 12 of those numbers. Fortunately there's a List call that does this:

shuf = shuf.Take(12)

所以，这就是它 - 你现在有12个数字，没有重复，全部随机1和75之间。同样，您可以用检查的foreach（在SHUF INT R）的debug.log（R）;

总之，当你想N的数字，没有重复，1和MAX之间，所有你必须​​这样是这样的：

In short, when you want "n" numbers, no repeats, between 1 and Max, all you have to so is this:

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

等瞧，你可以检查与的结果的foreach（在SHUF INT R）的debug.log（R）;

我只是在长度解释这是因为经常有人问如何获得特有的随机数。这是一个古老的绝招编程，答案很简单，您随机所有涉及到的整数数组。

I just explain this at length because the question is often asked "how to get random numbers that are unique". This is an "age-old" programming trick and the answer is simply that you shuffle an array of all the integers involved.

有趣的是，如果你谷歌这个问题（如何获得随机数的唯一），这是罕见的场合的谷歌是没有多大帮助的一个的，这是因为：每当这个问题是问，你渴望新的程序员（有没有听说过的简单的一招去做正确的！谁）写出巨大的长期复杂的想法过多，导致进一步的混乱和复杂性。

Interestingly, if you google this question ("how to get random numbers that are unique") it's one of those rare occasions where google is not much help, because: whenever this question is asked, you get a plethora of keen new programmers (who have not heard the simple trick to do it properly!!) writing out huge long complicated ideas, leading to further confusion and complication.

这就是你如何做的随机数字，没有重复，好在它是微不足道的。

So that's how you make random numbers with no repeats, fortunately it is trivial.

这篇关于随机生成平面地图上街区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！