new civilization positioning

mysterious space sector map

hello, Internet. I thought it might be interesting to explain how I solved a kind-of-weird problem in Mysterious Space, both to give you an inside look at how the game works, but also, hopefully, to show you at least one way that these kinds of problems can be solved.

first of all, the problem was this: sometimes, inhabited planets would be placed very close together:

bad, bad, civilizations

the reason had to do with how I’d been placing civilizations. my method was something like this:

  1. pick a random, empty system in the map, and “colonize” it
  2. until you have colonized six systems, pick a system you HAVE colonized, and colonize a random, adjacent system
  3. choose three of the colonized systems, at random, and uncolonize them

my thinking was that each civilizations would, “realistically”, tend to control adjacent systems, but I knew I’d want some spaces in between, so step 3 was added specifically to put some holes in a civilization.

besides the fact that step 3 won’t guarantee holes in a civ, it turns out that this “realistic” approach was bad for gameplay in a couple ways:

  1. since civilized systems are safe, having several in a row will let you skip a ton of systems. on the way TO the Mysterious Source, this means jumping up in difficulty level significantly (which maybe you want, but probably not), and on the way BACK, it often lets you skip most of the last systems, granting a cheap victory.
  2. with all the civilized systems clumped up, you don’t have many opportunities to shop. either you encounter a clump, and so get two shopping chances – once on the way in; once on the way out – or you don’t encounter one of these clumps at all, and never get to shop!

and though it was rare, sometimes multiple civs would clump together, compounding these problems!

agh!

I still liked the idea of having each civ in its own general area, but it was clear that my current method was not working.

so how to solve it?

there were a couple issues to solve, but I decided to start with spacing, since that was the problem that was most in-your-face.

I knew I didn’t want two civilized systems to be adjacent; I might even want them to be 2 or 3 systems apart… but I also wouldn’t want them to be TOO far apart, if possible…

it occurred to me that, since the system map itself is randomly generated, that even if I overlayed a repeating pattern of “place a civilized system HERE”, you would probably not be able to see that pattern…

what pattern could I use? I came up with this one:

civilization placement pattern

(you’ve probably noticed that the systems in Mysterious Space tend to fall on a grid. if not: well, they fall on a grid – now you know :P)

using this grid, you could imagine picking a random spot on it, drawing a box around that spot – say a 4×4 box – and colonizing all the planets within that box. that would ensure that the planets are near each other, but not TOO near.

but to do this, I’m going to need to a way to tell whether any arbitrary x/y position can be colonized. like say I position a civilization at (-11, 23), and want to check the squares around it… which ones can be colonized, and which can’t?

looking at the grid, I noticed that when y is 0 and x is 0, then the system can be colonized, and then when y is 5 and x is still 0, it can be colonized again: the pattern repeats every 5 rows (and every 5 columns). so if y divided by 5 has a remainder of 0 (or as mathsy people like to say, “y modulo 5 = 0”, or as programmers like to say, “x % 5 == 0”), AND x % 5 == 0, then the spot can be colonized. but when we look at a y of 1 (y % 5 == 1), it changes… and not in a way that’s immediately obvious. going from y = 0 to y = 4, we have:

  if y == 0, and x % 5 == 0, colonize
  if y == 1, and x % 5 == 3, colonize
  if y == 2, and x % 5 == 1, colonize
  if y == 3, and x % 5 == 4, colonize
  if y == 4, and x % 5 == 2, colonize

we could use that logic pretty much as-is, but surely there’s ONE line we can use to describe the entire grid. the question is how to map the y % 5 values (0, 1, 2, 3, 4, 5) to the x % 5 values (0, 3, 1, 4, 2), so that we can compare the two to each other. after playing with the numbers a little, I discovered the connection, and it’s what’s written on the left of the grid image above: x % 5 == (y * 3) % 5, or if you like: the remainder of x divided by 5 (0, 3, 1, 4, 2) equals the remainder of y times 3, divided by 5 (0 % 5 = 0, 3 % 5 = 3, 6 % 5 = 1, 9 % 5 = 4, 12 % 5 = 2).

OKAY.

fine, so now we have a grid. but how are we going to apply it to the system map, to colonize planets? I wanted to make sure each civilization had its own area of the map, where they wouldn’t overlap… how could I pick three starting places and be sure that they’re fairly-equally spaced?

making a grid by hand seemed pretty successful; why not pick the starting postiions by hand as well? 😛

civ starting areas

the diamond represents the general shape of Sector ZZ-Omega-9. (did you know it was a diamond shape?) the large “+” in the center is the x/y coordinate plane. (the Mysterious Source is always placed at (0, 0).) from there, I kind of drew boxes in such a way that I seemed to have given each box an equal share of the diamond, and then guesstimated at the coordinates of those boxes. for example, the left-most box touches the left edge of the diamond, and ends about 1/3 of the way from the center. each box seems to be 2/3 the “radius” of the diamond, and the left-most box is centered on the x-axis, so it must start at y = -1/3, and end at y = 1/3, and so on.

once I had decided on these general areas, the rest was fairly straight-forward: randomly assign a civ to each area; then for each area, find its center, and move outward, colonizing each system whose x and y coordinate falls on our grid – x % 5 == (y * 3) % 5 – until three systems are colonized.

ta-da!

the picture at the top of this post shows one sector generated using this method.

you might ask, though: “is this method perfect? is it even good enough? those rough guesses at civ areas were pretty rough – are you sure they’re equally sized? – and the areas that the civs take up are the same each time! that, together with the grid, makes it pretty easy for a player to know the positions of civilized systems!”

and those might be very fair points! I think, given the random arrangement of the systems themselves, that the final output is sufficiently random… but it is possible that, in the long run, this system will simply be too predictable.

there are a few ways I could increase the randomness, however:

  1. it would be trivial to “shift” our “you can colonize these spots” grid by a random amount by simply adding some random number to the x and/or y coordinates. for example, rather than x % 5 == (y * 3) % 5, we could use (x + RandomShiftValue) % 5 == (y * 3) % 5. just make sure to use the same RandomShiftValue over the course of the entire colonization process!
  2. it would also be trivial to slightly shift the start position from which we start placing each civ; rather than the dead-center of each area, a point slightly off-center by a random amount.
  3. realize that the “areas” we divided the diamond into are kind of silly; in the end, all we care about is a point from which to start placing a civ, and there are better, more-flexible ways to find three points evenly-spaced around a center point: trig! use the angles 0, 120, and 240, offset them all by the same, random amount, and then use cosine and sine to get x and y values.

and I will very likely do all three of these things! (to be honest, I hadn’t thought of them all until I sat down to write this article!)

I hope this has all been interesting to you, as a player of Mysterious Space, as a designer of your own games, or both!

thanks for reading!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s