One challenge with the old build of the game was instantiating ‘new stars’ for a new player to call home when joining the game. As a designer, you want them to have a little bit of a platform from which they can step up and take on the other players who have been playing a while, and have expanded out among the stars. But how to do that in a way that seems even remotely fair? The first time around, I used an algorithm to choose where the new player’s star would be placed, called the Archimedes Spiral. It took as input the number of previously-registered players, and made a somewhat galaxy-shaped spiral, expanding outward from a ‘galactic center’. But issues arose when it became more and more apparent that the stars were too close together, and there weren’t a lot of “other places” for a player to check out that weren’t already someone else’s homeworld. I could have tuned parameters of the spiral, but ultimately, the new stars were always appearing in a predictable pattern, so an experienced player could camp the end of the spiral arm with a Shipyard or a few heavy warships and make a quick PK on a new player as soon as they joined.
Mostly, I’m attempting to make the first pass at development a 1:1 replacement Ruby for Python and Rails for Django, but this was one area that I knew would be a problem as soon as beta testing began, so I chose to take on the challenge of re-imagining this as I rebuilt the new onboarding path.
This is an issue that has been gnawing at me ever since I put this game away 10 years ago (probably second-only to concocting ways of ‘rubber banding’ the exponential growth advantage of players who joined before you), so I had some ideas on how I might approach it.
I wanted something that would fit the following criteria:
- Evergreen: Usable indefinitely as the game grows, so it can always generate a new location for a player no matter how large the battlespace becomes.
- Stochastic: A existing player can’t “camp” the next spawn point by guessing where it might be.
- “Evenly” Spaced out: Obviously, giving over any part of a player’s initial setup to randomization leads to risks of variable bootstrapping opportunity for a new player, but I don’t want anyone dropped in a total star-desert, nor do I want someone’s star to be so close to another star that they essentially get two systems off the bat.
- Centrally-clustered: While I don’t want the players directly on top of each other, I also don’t want to just generate random points in a 100,000×100,000 coordinate space, and hope they end up finding each other, it could take weeks or months for a new player to encounter adversaries, and that’s not fun either. So I want them all “nearish” the action as they get going.
So here’s what I came up with: First, let’s assume the “center” of the galaxy is at the coordinate origin (0,0) (Don’t worry, when this thing goes live, “0,0” is going to have some juicy planets to fight over, Twilight Imperium style). To start, we choose a random “angle” 0-2π (0-360° if you’re not a math nerd), then, we point in that direction, and we take a walk. Taking steps of 10 distance on the coordinate grid in that direction, we check how far that point is to every Star object in the Universe, and see if they’re all greater than a specific distance that I think is a reasonable amount of space for a new player. If there are stars too close? We take another 10-unit step away from the Galactic Center and we check again. Eventually, no matter how large the finite Universe is, or how many Stars have been generated by this process by previous Players signing up, we’ll get far enough out that we either find a gap, or we’ll expand the outer edge of the galaxy.
“But Woodard!” You may shout from the back of the room — “You have to check every single star every time you take a step, just to find an open spot? That seems really inefficient!”
And you’d be right. Luckily, we can employ a method called “Dynamic Programming” to shortcut the number of checks we need to make at each step of the walk, and minimize the amount of work we need to do to find that perfect spot for a new Empire to take root.
Every time we take a step, we can be certain that if:
- A Star is already outside our ‘minimum distance’, AND
- It is further away after taking this ‘step’ than it was on the previous ‘step’, we know it’s safe to never bother checking again on any subsequent iterations.
This way, after a relatively few loops, the list of Stars we have to check rapidly decreases, focusing into a cone directly in front of us. (Technically a wedge I guess, since it’s 2d, but we’re in space, so let me call it a cone ???? )
Maybe one day I’ll make an animation of this in action or something, but I’m trying to move fast, so I’m going to go back to focusing on building this all out!