在平面地图上随机生成方块
Randomly generate blocks on a flat map
我正在尝试在平面地图上随机生成方块并使其不相互重叠。
我制作了一个地图大小 (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 个可能的修复方法
- 我应该根据块的位置来设置块的大小。
- 我应该使用另一种随机化算法。
- 我做的不对。
你认为最好的主意是什么？
更新
我的代码运行得更好了。如果需要，我现在尝试多次实例化这些块（目前最多 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);
}
if (elementFound) continue; 将跳过当前循环迭代。你需要包装 int x=Random..; int y=Random()..;参与条件为 while(/* position x/y already occupued*/) { /* generate new valid point */} 的 while 循环，例如：
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<ObjectInterface>();
}
}
}
这很难做好。
这里有一个您可能会喜欢的快速解决方案...取决于您的场景。
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
只需从前面取下您需要的内容：so, 3, 8, 6 等等
举个例子，假设您想要从 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);
简而言之，当您想要在 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);
检查结果
我只是详细解释一下，因为这个问题经常被问到“如何获得唯一的随机数”。这是一个“古老”的编程技巧，答案很简单，就是 随机播放 一个包含所有相关整数的数组。
有趣的是，如果您 google 这个问题（“如何获得唯一的随机数”），那是 google 没有太大帮助的罕见情况之一，因为：每当这个问题被问到时，你就会遇到大量敏锐的新程序员（他们还没有听过正确地做这件事的简单技巧！！）写出大量冗长复杂的想法，导致进一步的混乱和复杂化。
这就是生成没有重复的随机数的方法，幸运的是它是微不足道的。
你不应该遇到那么多碰撞。
假设您的块都是 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<Block> PlaceNonOverlappingBlocks(int count, int maxBlockSize, int mapX, int mapY)
{
var map = new bool[mapY, mapX];
var rng = new Random();
var result = new List<Block>(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;
}
}
}
}
我正在尝试在平面地图上随机生成方块并使其不相互重叠。 我制作了一个地图大小 (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 个可能的修复方法
- 我应该根据块的位置来设置块的大小。
- 我应该使用另一种随机化算法。
- 我做的不对。
你认为最好的主意是什么？
更新
我的代码运行得更好了。如果需要，我现在尝试多次实例化这些块（目前最多 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);
}
if (elementFound) continue; 将跳过当前循环迭代。你需要包装 int x=Random..; int y=Random()..;参与条件为 while(/* position x/y already occupued*/) { /* generate new valid point */} 的 while 循环，例如：
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<ObjectInterface>();
}
}
}
这很难做好。
这里有一个您可能会喜欢的快速解决方案...取决于您的场景。
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
只需从前面取下您需要的内容：so, 3, 8, 6 等等
举个例子，假设您想要从 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);
简而言之，当您想要在 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);
我只是详细解释一下，因为这个问题经常被问到“如何获得唯一的随机数”。这是一个“古老”的编程技巧，答案很简单，就是 随机播放 一个包含所有相关整数的数组。
有趣的是，如果您 google 这个问题（“如何获得唯一的随机数”），那是 google 没有太大帮助的罕见情况之一，因为：每当这个问题被问到时，你就会遇到大量敏锐的新程序员（他们还没有听过正确地做这件事的简单技巧！！）写出大量冗长复杂的想法，导致进一步的混乱和复杂化。
这就是生成没有重复的随机数的方法，幸运的是它是微不足道的。
你不应该遇到那么多碰撞。
假设您的块都是 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<Block> PlaceNonOverlappingBlocks(int count, int maxBlockSize, int mapX, int mapY)
{
var map = new bool[mapY, mapX];
var rng = new Random();
var result = new List<Block>(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;
}
}
}
}