clock menu more-arrow no yes

Filed under:

In the beginning, No Man’s Sky was flat

New, 9 comments

GDC presentation reveals the mathematical complexity of making “planet-sized” worlds

Hello Games

I remember sitting in a hotel room a few years ago at E3, shortly after the team at Hello Games unveiled No Man’s Sky. Sean Murray was there, showing me one of the many worlds he and his team had created using procedural generation.

He made the task seem so effortless, as if conjuring up billions of tiny worlds just happened at the touch of a button.

“But really, how did you do it?” I asked. There was a long pause while he looked at the floor.

“It’s mostly maths,” he replied, shrugging.

At the time, I wondered if the reason he didn’t want to tell me was because it might spoil the illusion. But, after a presentation at this year’s Game Developers Conference, I’m ready to entertain another possibility. Lead programmer Innes McKendrick finally let everyone in on the secret, and now I know I think that if Murray had tried to explain it to me in that hotel room the complicated process would have boiled my tiny brain.

“Everyone has an opinion about how we should have done this,” McKendrick said. “But our primary design goal was that you can fly off the planet and fly to another planet, and then fly back.”

Simple enough. But Hello Games also wanted the simulated distances in No Man’s Sky to have meaning. They wanted players to marvel at the scale of it all, and to feel small by comparison.

No Man’s Sky screenshot Hello Games

“We needed to simulate space where someone walking around a planet, if they wanted to walk around to the other side, that would feel like a really weighty and significant thing for them to do,” McKendrick said. “We wanted our players to explore, and to feel alone, and that meant that those distances needed to be large.”

The first technical solution that McKendrick tried was to make those worlds flat. At ground level, the terrain would extend infinitely in every direction. When players wanted to take off in their spaceship, the game would capture an image of where they were now and then wrap it artfully around the sphere. Any distortions or overlaps would be hidden on the backside of the planet, sort of like folding up the wrapping paper and taping it down on the ends of your Christmas presents.

But that failed to create the kind of permanency that Hello Games was looking for. How do you tell someone to visit a place that you’ve been to when that place is tucked up underneath a fold of terrain on the backside of the planet?

Hello Games

“The really significant problem for us,” McKendrick said, “was that you end up with some impossible places on your flat terrain that you can’t possibly map in a useful way to the sphere. So, if you have these points of interest, maybe you want to share them with other players … then they can’t possibly have the same points, because the way your sphere looks depends on where you take off from it or where you come into it.”

Next, McKendrick decided to the study output of experts that had been doing this kind of work for centuries — cartographers. He pulled up a list of map projections on Wikipedia and did a bit of shopping. But here he ran into other problems. Take the Mercator projection, for example. That’s the one that makes Greenland look like a massive continent, bigger than Africa, by pulling and stretching the land around the poles. That could technically be done in a video game like No Man’s Sky, but McKendrick found that it would be very costly to do that kind of transformation in terms of processing power.

For a time, he said, he considered using the obscure Peirce quincuncial projection, which sort of unwraps the surface of the earth and lays it flat like a pressed flower. But, he found that didn’t work for the kind of arbitrary planets his team wanted to create.

The Peirce quincuncial projection of the world. Note that the equator appears as a red square.
Daniel R. Strebe, July 23 2012

“Peirce quincuncial really only works,” he said, “if you have oceans in just the places that Earth has oceans, and becomes pretty useless when you generalize that to the arbitrary planets that we were generating.

“So we moved on from this one as well, and moved on to the scary approach that we had been trying to avoid — making spherical worlds.”

Spherical worlds are anathema to modern programming. Most of the tricks of the trade involve the assumption of a perfectly flat space. So KcKendrick and his team had to get creative. And the solution, just as Murray had first told me, was indeed “maths.”

What McKendrick devised was a system whereby surface data could be stored in a mathematical cube. In-game, that data was then transposed onto a sphere. Mathematical algorithms were curated and tweaked to generate a kind of noise that would simulate height, giving the impression of a natural planetary surface.

“Having edge cases in your world, literal edge cases sounded like a nightmare,” McKendrick said, and for a time they were. But the team soldiered on through trial and error, iterating as they went. Eventually, they made it work.

With the shape of things hammered out, then they had to work on the player experience, things like perceiving light and shadow in worlds constantly orbiting strange new suns. But the only way for the game to know what direction down was, from the player’s perspective, to constantly reference the center point of each world.

“I will be really excited,” McKendrick quipped, “to one day work on a project where I always know where up is.”

In the final phases, they went even further to add detail to the surface of those planets. They injected additional algorithms into the procedural code to create positive space — overlapping cliffs, winding, worm-like stone structures and floating islands. Then, they used another, similar set of “maths” to create negative space — underground caverns, gaping crevasses and deep valleys. All of it had to be folded into their cubic data, and then transformed into a sphere.

It was a delicate balancing act, with many strange permutations. To check their work, they sent out space probes to bring back samples of the worlds they created.

In the presentation, McKendrick never showed precisely what those algorithms are, what the lines of “maths” actually say. It remains the secret sauce that makes No Man’s Sky so unique. But even without those minute details, McKendrick’s presentation opened the door for other developers to conceptually build on his team’s work.