Infinite Asteroids!

The whole point of procedural generation is that it allows you to generate your game’s world (practically) endlessly. I’ve had procedural generation working for a while, but just now got around to using it to generate the world.

I divided space into a 2D grid, then used the (x, y) coordinates of each cell of the grid as the seed for the pseudorandom generator. The one tricky part was finding a way to use two values (x and y) to create a single unique seed for each grid cell. If you know that your grid has a fixed size – for example, if it’s 100 cells wide – then you can just do the simple trick:

seed = y * 100 + x

And you’ll get a unique value for each cell. But what if the grid is infinite in both directions? I did a little research and found the Cantor pairing function. It’s an amazing function that does exactly what you need: it generates a unique value for every (x, y) combination. The simple version of the function doesn’t handle negative values, but that’s fairly easy to fix. The complete function I ended up with is this:

function cantor(x, y)
  const a = x >= 0 ? 2 * x : -2 * x - 1;
  const b = y >= 0 ? 2 * y : -2 * y - 1;
  const c = a + b;
  return c * (c + 1) / 2 + a;

With a unique seed for each grid cell, I know I’ll always generate the same stuff in that cell every time the player visits it. Just the player flies into a new grid cell, I generate those new rocks. And as they leave the old cell, I de-spawn those. So, while there are effectively infinitely many rocks out there, there are only a small number actually present in memory.

It’s definitely the coolest thing I’ve built in the game so far. There are still a few loose ends to tie up…

If you fly too far in any direction (roughly 100 kilometers), everything starts to wobble around. This is just the nature of floating-point numbers. I can fix this by moving the player back to (0, 0) at a certain distance, but remembering the “offset” of all the world objects.

If you fly out of a region, then come back to it later, everything just respawns. The problem with that is that if you destroyed a rock or even just partially mined it, that is forgotten and the rock is spawned as if it were the first time. Fixing this means remembering the state of every rock the player has ever touched. This will be a lot tougher to fix, but this is the cost of admission when creating a procedural game.

Play it here!

Leave a Reply

Your email address will not be published.