随机化对象的位置放置

本文关键字：位置 对象 随机化 | 更新日期: 2023-09-27 18:35:05

只是附加信息：这是我正在做的一个游戏项目。

我正在尝试制作一种有效的随机化算法，该算法在给定可用空间长度的情况下放置多个对象（彼此排列）。

直接解决问题：给定一个可用空间的长度 = lengthOfArea，并且要定位的对象数量 = numObjects，其中每个对象的长度，lengthObject = （lengthOfArea/2）/numObjects。（这样，对象占用的总空间量是可用长度空间的一半）。

我应该寻找每个对象的中心位置并返回一个数组。

这是我目前的尝试：

public int[] FindObjectPositions(int lengthOfArea, int numObjects, Random random)
  {
    int lengthOfObject = (lengthOfArea / 2) / numObjects;
    int[] positionsPicked = new int[numObjects];
    int minPosition = lengthObject / 2;
    int maxPosition = lengthOfArea - (lengthObject / 2);
    for (int i = 0; i < numObjects; i++)
    {
      int newPosition;
      do 
        {
          newPosition = minPosition + random.Next(maxPosition - minPosition);
        } while (!IsPositionValid(positionsPicked, newPosition, lengthObject));
        positionsPicked[i] = newPosition;
    }
    return positionsPicked;
  }
public bool IsPositionValid(int[] positionsPicked, int newPosition, int lengthObject)
  {
    for (int i = 0; i < positionsPicked.Length; i++)
    {
      if (Math.Abs(positionsPicked[i] - newPosition) <= (lengthObject / 2))
        return false;
    }
    return true;
  }

基本上，我正在做的是不断随机为每个对象找到一个有效位置。我只是想知道它是否效率低下。另外，我想知道这种方法是否会陷入僵局？

随机化对象的位置放置

如果存在

无法容纳更多对象的配置，则可能会死锁。 例如，如果有 30 个空格，并且每个对象长度为 5 个空格，则配置

_ _ _ _ x x x x _ _ _ _ x x x x x _ _ x x x x _

即使有 15 个开放空间，也没有可能容纳另一个物体的地方！

<小时 />

假设有m个开放空间，每个对象都有宽度w。 一种不会死锁的方法是生成m-w+1数字列表1, 2, ..., m-w, m-w+1。 然后随机选择一个 - 这将代表对象的最左侧位置。 然后删除该数字左右两侧的w-1数字 - 这表示对象w宽，并且宽度w的其他对象都不适合其左侧w-1空间。

例如，如果m = 20和w = 3，

创建从 1 到 18 的列表

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

然后随机选择一个。 假设我们选择 10。 然后空格 10、11、12 由我们的对象填充，空格 8、9 不能是另一个对象的最左边位置，所以我们删除数字 8 到 12。

1 2 3 4 5 6 7 13 14 15 16 17 18

假设我们接下来选择 18。 然后我们删除 16-18：

1 2 3 4 5 6 7 13 14 15

依此类推，直到我们没有数字了。

<小时 />上面的方法

不会死锁，但它有另一个问题：可以有一个包含（比如）6 个对象的配置，但上面的方法可能只生成一个包含 4 或 5 个对象的配置，并且没有空间容纳更多。 为了解决这个问题，我们可以计算出 6 个对象应该有多少个空白空间，而不是为我们的对象选择随机位置，并为我们的空白空间选择随机位置（使用上述方法）。

这将为您提供所需的对象数量，随机间隔，没有死锁的可能性。

相关文章：