在平面地图上随机生成块

我试图在平面地图上随机生成块，并使它们彼此不重叠。 我已经制作了一个地图大小（500×500）的矩阵（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(); } } } 

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

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

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

---

UPDATE

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

我尝试在500×500地图上实例化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 && 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(); } 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 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 xy put block in list allBlocks 

但是…………

---

……你会发现这看起来有点像“常规”，所以这样做：

只是随机扰乱所有的块。 请记住，video游戏编程是一个巧妙的技巧！

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

  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 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 shuf = Enumerable.Range(1,75).OrderBy(r=>Random.value).ToList(); 

所以该列表长达75个项目。 您可以通过说foreach(int r in shuf) Debug.Log(r);来检查它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 shuf = Enumerable.Range(1,Max).OrderBy(r=>Random.value).ToList(); shuf = shuf.Take(n); 

etvoilà，你可以用foreach(int r in shuf) Debug.Log(r);检查结果foreach(int r in shuf) Debug.Log(r);

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

有趣的是，如果你谷歌这个问题（“如何获得独特的随机数字”）这是谷歌没有太多帮助的罕见情况之一，因为：无论什么时候提出这个问题，你都会得到过多的敏锐的新程序员（谁没有听过这样简单的伎俩！）写出巨大而复杂的想法，导致进一步的混乱和复杂化。

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

Answer 2

if (elementFound) continue; 将跳过此当前循环迭代。 你需要包装int x=Random..; int y=Random().. int x=Random..; int y=Random().. ; 部分在while循环中，条件为while(/* position x/y already occupued*/) { /* generate new valid point */} ，例如：

 void generateElement(int ratio, int minScale, int maxScale, GameObject g) { for (int i = 0; i < ratio * generationDefault; i++) { GameObject el; // Randomly generate block size and position bool elementFound = false; int size, x, y; do { elementFound = false; 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; } while(elementFound); 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(); } } } 

Answer 3

你不应该得到那么多的碰撞。

假设您的块全部为5个单位宽，并且您正在尝试将它们装入500,500的网格中，那么它们至少可以有100 * 100个空间，这样可以容纳10,000个空间以容纳1,000个块。

尝试使用此代码：

 using System; using System.Collections.Generic; namespace ConsoleApplication1 { class Program { static void Main() { var result = PlaceNonOverlappingBlocks(1000, 5, 500, 500); } static List PlaceNonOverlappingBlocks(int count, int maxBlockSize, int mapX, int mapY) { var map = new bool[mapY, mapX]; var rng = new Random(); var result = new List(count); int collisions = 0; while (count > 0) { int size = rng.Next(1, maxBlockSize + 1); int x = rng.Next(0, mapX - size); int y = rng.Next(0, mapY - size); if (fits(map, x, y, size)) { result.Add(new Block(x, y, size)); addToMap(map, x, y, size); --count; } else { if (++collisions> 100000) throw new InvalidOperationException("Hell has frozen over"); } } // This is just for diagnostics, and can be removed. Console.WriteLine($"There were {collisions} collisions."); return result; } static void addToMap(bool[,] map, int px, int py, int size) { for (int x = px; x < px+size; ++x) for (int y = py; y < py + size; ++y) map[y, x] = true; } static bool fits(bool[,] map, int px, int py, int size) { for (int x = px; x < px + size; ++x) for (int y = py; y < py + size; ++y) if (map[y, x]) return false; return true; } internal class Block { public int X { get; } public int Y { get; } public int Size { get; } public Block(int x, int y, int size) { X = x; Y = y; Size = size; } } } }