0

只是附加信息：这是针对我正在开发的游戏项目。

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

直截了当地说：给定一个长度 = 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;
  }

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

4

1 回答 1

1

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

_ _ _ _ xxxxx _ _ _ _ xxxxx _ _ _ _ xxxxx _ _ _

即使有 15 个空地，也没有地方可以容纳另一个物体！

假设有m开放空间，每个对象都有 width 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 个对象应该有多少个空白空间，而不是为我们的对象选择随机位置，然后为我们的空白空间选择随机点（使用上述方法）。

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

于 2012-05-23T22:05:40.793 回答