Optimizing of game objects placement in a 2D Game

Question

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

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

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);

                        }
                    }
                }
            }

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).

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

Answer 1

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.

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

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).

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).

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;