游戏优化对象放置在2D游戏 [英] Optimizing of game objects placement in a 2D Game

问题描述

我克隆蜈蚣的比赛，但现在我在电脑上写它。

I'm cloning a centipede game, but for now I'm writing it on a PC.

我想送$ P $垫在蘑菇中的随机位置在屏幕上，但他们不应该彼此重叠。

I would like to spread the mushrooms over the screen in a random position, but they shouldn't overlap with each others.

最坏的情况做了复杂度为O（N ^ 3）的算法，你检查一个蘑菇对方的蘑菇，然后检查了距离或路口，又取最好的随机位置。 一个伪code在这里使用ActionScript：

The worst case for doing that is an O(N^3) algorithm where you check for one mushroom for each other mushrooms and then check the distance or intersection, then take another best random position. A Pseudo code is here using 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上是好的，但我将它移植到小功率微控制器）游戏机。

This is of course on a PC is fine, but I'm going to port it to a game console with small power a microcontroller).

我知道了解决方法是使用一个tilemap的，但有一个更好的策略实现了吗？

I know that the solution is to use a tilemap, but is there a better strategy for achieving that?

推荐答案

您可以用线性同余做到这一点发电机（LCG），这是一个有限的范围内产生明显的随机数的长序列的简单方法。

You can do this with a linear congruential generator (LCG), which is a simple way of generating long sequences of apparently random numbers within a limited range.

其基本公式为 X <分> N +1 =（ A · X <分> N + C ）模 M 。

The basic formula is x_n+1 = (a·x_n + c) mod m.

它的被显示，这个过程会产生一个序列，其包括每一个从0到的米的-1只要一定满足条件（ C 和 M 的互质， A -1是除尽的所有质因素的米的，并且如果米的是4的倍数，那么的一的-1也必须的倍数4）。

It's been shown that this process will generate a sequence that includes every number from 0 to m–1 as long as certain conditions are met (c and m are relatively prime, a–1 is divisible by all the prime factors of m, and if m is a multiple of 4, then a–1 must also be a multiple of 4).

如果你做的 M 等于你的游戏区域（宽×高），那么这会为您提供一系列坐标的大小，不会重复，直到整组的可能性已经覆盖。这意味着，这将是完全没有必要的检查碰撞与其他蘑菇。你可以简单地通过启动LCG具有不同的种子值 X <子> 0 （0≤ X <子> 0 <随机的游戏/分>＆LT; M ）

If you make m equal to the size of your game area (width×height), then this will provide you with a series of coordinates that will not repeat until the entire set of possibilities has been covered. That means it would be completely unnecessary to check for collisions with other mushrooms. You can randomize the game play simply by starting the LCG with a different "seed" value x₀ (0 ≤ x₀ < m).

因此​​，举例来说，如果你的游戏区由200×200个细胞，你可以设置 M = 40000， A = 14081和 C = 15207。在C语言中，你的code会是这个样子：

So for example, if your game area consists of 200×200 cells, you could set m=40000, a=14081 and c=15207. In C, your code would look something like this:

/** 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;

这篇关于游戏优化对象放置在2D游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！