algorithm - 优化 2D 游戏中的游戏对象放置

Question

我正在克隆一款蜈蚣游戏，但现在我正在 PC 上编写它。

我想将蘑菇散布在屏幕上的随机位置，但它们不应相互重叠。

最糟糕的情况是 O(N^3) 算法，在该算法中，您检查每个蘑菇中是否有一个蘑菇，然后检查距离或交集，然后采取另一个最佳随机位置。 这里有一个使用 Actionscript 的伪代码:

   for (var i:int = 0; i < m_bricks.length - 1; i++)
            {
                for (var j:int = 1; j < m_bricks.length; j++)
                {
                    if (i != j)
                    {
                        while (m_bricks[i].hitTestObject(m_bricks[j]))
                        {
                            m_bricks[i].x = int((Math.random() * 200) + 45);
                            m_bricks[i].y = int((Math.random() * 200) + 45);

                        }
                    }
                }
            }

这当然在 PC 上没问题，但我要把它移植到小功率的游戏机(微 Controller )上。

我知道解决方案是使用瓦片 map ，但是有更好的策略来实现这一点吗？

Answer 1

您可以使用linear congruential generator来做到这一点(LCG)，这是一种在有限范围内生成明显随机数的长序列的简单方法。

基本公式为x_n+1 = (a·x_n + c) mod m。

事实证明，这个过程将生成一个序列，其中包含从 0 到 m–1 的每个数字，只要 certain conditions满足(c 和 m 互质，a–1 可以被 m 的所有质因数整除，如果 m 是 4 的倍数，则 a–1 也必须是 4 的倍数)。

如果您使m等于游戏区域的大小(宽度×高度)，那么这将为您提供一系列坐标，这些坐标在整个可能性集都被确定之前不会重复。覆盖。这意味着完全没有必要检查与其他蘑菇的碰撞。您只需使用不同的“种子”值x₀(0 ≤ x₀ <m)。

例如，如果您的游戏区域由 200×200 个单元格组成，您可以设置 m=40000、a=14081 和 c=15207。在 C 语言中，您的代码将如下所示:

/** LCG parameters for m = 40000: **/
#define LCG_MODULUS    40000  /* m */
#define LCG_MULTIPLIER 14081  /* a */
#define LCG_INCREMENT  15207  /* c */

int lcg(int arg) {
  static int x = 0;
  if (!arg) return x;      /* arg=0: return last value */
  if (arg < 0) x = -arg;   /* arg=-n: seed with value of n */
  x = (LCG_MULTIPLIER * x + LCG_INCREMENT) % LCG_MODULUS;
  return x;
}

  :

/* Get new random coordinates */
r = lcg(1);
x = r % 200;
y = r / 200;