Maths, No Man's Sky, and the problem with procedural generation

Features

Maths, No Man’s Sky, and the problem with procedural generation

This isn’t a review of No Man’s Sky, nor is it a critical teardown of what is (and isn’t) in it. This is a discussion about maths and procedural generation.

Published

6 years ago

31st August 2016

Tom Baines

Disclaimer: This isn’t a review of No Man’s Sky, nor is it a critical teardown of what’s in it and what isn’t. This isn’t an expose on Hello Games or their development practises, and it certainly isn’t a litany of complaints about the things Sean Murray may or may not have said to the press in his unchecked enthusiasm. We might touch on those things occasionally, but there have already been more than enough think pieces and hot takes on No Man’s Sky the finished product versus No Man’s Sky the expectation; probably around 18 quintillion, at last count.

What this is, however, is a discussion about mathematics and – more specifically – the mathematics of procedural generation.

Additional disclaimer: There’s also some swearing. For emphasis.

Good at Maths

When I was at university, we lived next door to a bunch of lads from Northern Ireland, in our first year in student housing. Long story short, and I don’t remember the exact details of who broke into whose kitchen via the fire escape to play Pro Evo… in any case, we all got like a house on fire; ironic really, as the fire escape door was broken in doing so. Stick with me folks, there’s a point to this sentimental rambling.

The Northern Irish chaps, all friends from school who had travelled to England together, often had an interesting turn of phrase that the English (and to be fair, the Scottish and Welsh) would need explaining. An example:

Brian came home one morning, still wearing the clothes he had on the night before, having done the walk of shame across campus. Paul and Ryan asked Brian (yes, these are their real names) about who he’d hooked up with the night before, but rather than immediately show us a photo on his phone or wax lyrical about the girl he’d just met, he was rather cagey and quiet.

“Ah, she must be good at maths then, is she Brian?” Came the inquest from his oldest friends. The rest of us, unaware of this expression, asked for an explanation.

“It’s basically, if you’re going out with a girl and she’s not much of a looker or she comes from a rough area or whatever, and you’re a bit embarrassed,” they explained, “then you figure she must have something else going for her, you know? So like at school, you’d go out with a girl, even if she wasn’t very attractive, if she could help you with your maths homework. So, you know, they’re good at maths.”

Sean Murray and Hello Games – and ultimately, No Man’s Sky itself – are very good at maths.

‘Superformula’

There’s an algorithm used, in No Man’s Sky, that sits at the core of everything the game promises. Over 18 quintillion planets, all birthed randomly out of pure mathematics by procedural generation; it’s a fairly serious undertaking by a small development studio.

There was a concern, following the game’s initial delay and the secret legal wrangling with the ~~Sith Lord~~ owner of Sky Media Rupert Murdoch (over their permission to use the word ‘Sky’ in the name) that another hiccup could interfere with No Man’s Sky’s release: the suggestion by a Dutch botanist Johan Gielis that Hello Games has used his patented ‘superformula’ without permission in the creation of their near-infinite universe. Sean Murray quickly nixed those qualms with a tweet stating that the Dutch ‘superformula’ wasn’t used in No Man’s Sky, and asked that “everybody chill”.

I bet he’s wishing for those days of people agonising over a potential name change or a mathematical patent right about now, incidentally, and everybody really does need to chill.

But there is a formula used to create the 18 quintillion planets in No Man’s Sky, and while we don’t know the details of the algorithms Hello Games used – and Sean, if you ever want to get together and discuss hardcore maths, then please get in touch – it must be pretty a pretty super formula to do it.

18 quintillion planets. Just take a moment to stop and think just how big that is. No, seriously. Stop flinging your excrement at Sean Murray and Hello Games on Twitter and Reddit for one sodding minute to think about just how brain-meltingly, calculator-crushingly large a number that really is. To put that in a little – or rather, very large – bit of context, our home galaxy, the Milky Way, upon whose sweeping spiral our insignificant blue speck drifts giddily through the universe, is thought to have at least 100 billion planets. “At least” means it could well be more, but that’s a good low-ball estimate.

No Man’s Sky contains over 18 quintillion planets. That’s over 180 million times larger than the Milky Way, and the install is about 6GB in size. Those are utterly bewildering numbers. It’s one of the technical achievements of the century.

Speculation time: As I said earlier, I don’t know any details of the formula that Hello Games used in the procedural generation in No Man’s Sky (and they’re more than welcome to enlighten me) but I’d be willing to bet there’s a healthy amount of just-in-time instantiation – that is, only creating objects when called upon by the algorithm, i.e. things popping in as you fly towards them – combined with some prodigious deduplication.

Deduplication, in the world of information technology, is a method of reducing storage usage by marking pieces of data as duplicates of one another and only keeping one master copy (with pointers to where it can be found in place of the deduplicated data). On a really basic level, that’s like only keeping one version of a Word document even though you might have the same thing stored in ten places. In reality, that happens at the block level – as small as 4KB in size, the storage equivalent of atomic particles – which probably explains how No Man’s Sky is able to fit so much into so little. It builds the universe on the fly, and it’s really efficient in only storing deduplicated copies of the absolute base components, the atomic building blocks it needs to build said universe.

But when you’re building 18 quintillion planets from shared building blocks, that level of procedural generation and hardcore deduplication is going to show. Unfortunately in No Man’s Sky, it can show pretty early on.

Attack of the Clones

One of the chief concerns being levelled at No Man’s Sky – and certainly one of the more founded ones that, isn’t just teen angst and base internet rancour – is that it can be somewhat repetitive. Though to some, that’s entirely the point.

Anybody who spent years of their life trading commodities in the original Elite can tell you that there was no real aim to that game; the joy was in Littlest Hobo-ing your way around the galaxy, occasionally getting into scrapes and adventures, but mostly just wondering in the vast black expanse of an infinite universe. If that’s your interpretation of No Man’s Sky – as it is ours, here at Thumbsticks towers – then you’re probably the ideal person to play No Man’s Sky, and will get the best out of it in the long run. You should also read Keith Stuart’s piece over on The Guardian on that very subject; it’s really rather good.

But No Man’s Sky is repetitive, nonetheless. I’ll concede that the inventory is too small, and managing it is a constant juggling exercise. I’ll concede that resource mining is a bit of a grind, and can be tedious and frustrating in equal measure. I’ll concede that the trading posts and alien encounters are cookie cutter, and may as well just be text-based menus after you’ve seen the animation once (like the interminable, un-skippable guardian summon monsters in Final Fantasy VIII).

And while I will also concede that the planets can be a bit samey and ultimately repetitive, I’m afraid I’ll have to step in at this point if you’re using that as one of your many slings and arrows with which to attack Sean Murray and Hello Games. The planets have to be similar, or at the very least repeatable or formulaic, because if they weren’t? We’d never be able to get anywhere.

Let’s take a look at those 100+ billion planets in the Milky Way again for a moment. Do you know how many of them are habitable or hospitable? To our precise knowledge, exactly one: Earth (though there has been a good candidate for a second found orbiting Proxima Centauri very recently). And never mind whether they’re actually hospitable; do you know what percentage of them would even have a crust, mantle or surface that you’d be able to walk on, or land a dinky little starship on? The percentage is probably stupendously tiny.

If Hello Games had, with their formula for procedural generation, allowed the galaxy of No Man’s Sky to form in any old way it wanted, then there would be no game, kids; or at least, it would barely be playable. Here’s a fictional diary extract of what would happen if the game were truly random:

Day 1.

I awoke on an alien planet, stranded with my stricken ship, unable to escape this bizarre world. After some time wandering, it seemed that I could scavenge the resources I needed to repair my ship, and set about the task. After several hours of shooting rocks and trees to garner mineral deposits, I was able to craft the requisite parts and fuel up my ship for departure. I only hope the next world I find is friendlier than this one.

Day 287.

I have died so many fucking times it isn’t even funny any more. The first eighteen planets I tried to land on were all gas giants, and my ship simply sank to the core of the planet and, if I wasn’t burned up by whatever hellish gas composed the planet’s surface, I was crushed by its gravity at the centre. The next dozen or so were so hot that my ship melted and I was boiled alive before I even touched the surface. Then the next few months have been spent in a vicious cycle of the two; of finding a new planet, attempting to land, dying, and reloading my fucking save. I’m going to try planet 13,722 now. Wish me luck.

Day 288.

I’ve made a massive fucking error. Planet 13,722 is even worse than all the others! I’ve finally found a planet I can land on, but there’s literally nothing here. It’s just a fucking rock, floating in space like a giant, frozen turd. There’s a relatively hospitable atmosphere and a stable mantle, so it didn’t insta-kill me when I landed, but there’s literally nothing here. There’s no fuel. There’s no minerals or resources. There isn’t another living creature or useful thing on here, and my ship is out of fuel. I spent months wanting to land on a fucking planet that wouldn’t fucking kill me, and now I finally have, I can’t get off the fucking thing. Ever.

Doesn’t sound like much fun, does it? Anyway, back to the maths.

Sean Murray is a Generous God

Hello Games have had to create the procedural generation algorithm for No Man’s Sky with a number of parameters and variables locked in, to result in an actual, playable experience.

Think of it like generating a random world map for a game of Civilization: You pick the size of map you want, you pick what percentage of water, what density of forest, what global temperature range, what distribution of resources, and the game builds you a random world based on those parameters. Do that a thousand times and you’ll never end up with the same map, but you might get some that are very similar if you punch in comparable starter variables. That’s procedural generation at work, folks, and it was foolish of people to expect anything different from No Man’s Sky.

Yes, there’s a hell of a lot more variables, and yes, the results are a hell of a lot stranger than anything we’re used to – and the created universe is still unimaginably large and entirely unfeasible to even comprehend – but it’s still just procedural generation. It’s like one of those children’s games where you can jumble up the face, legs and torso of different characters to produce some comical results, but on a bewilderingly large scale.

I’m willing to bet that the procedural generation algorithm behind No Man’s Sky does the same thing as Civilization’s map builder, just hidden in the back end and with a truckload more variables. Here’s some to get you started:

Planet’s radius.
Percentage of water.
Density of foliage.
Temperature.
Resource distribution.

Thus far, all pretty similar to Civ, just a bit more spacey. But No Man’s Sky goes a lot further than that, delving into the funky and the fantastical:

Monoliths.
Artefacts.
Alien races.
Colour of ground.
Colour of foliage.
Colour of water.
Atmosphere.
Toxicity.
Radioactivity.
Types of plants.
Types of animals.

There’s probably several hundred variables for each planet – and consequently some components like plants and animals will have their own sub-procedural generation and their own individual base variables, based on the planet they inhabit – and the formula will be incredibly complex, but they all have to stay within a liveable set of parameters, because to leave a player stranded on a planet they’re unable to leave would be unforgivable.

That’s ultimately why No Man’s Sky feels repetitive, and it’s also why it feels easy (bordering on the mundane) at times: there’s a benevolent deity, in the form of Sean Murray’s mathematical formula for procedural world-building, watching over you at all times, making sure that you’re always able to progress and keep on trucking with your interstellar gap year. No Man’s Sky is not a hardcore game with procedural generation attached (as you’ll see in other survival roguelikes The Long Dark and We Happy Few), rather it’s a procedurally generated universe with a game attached, and there’s a finite limit to how challenging that game can be while also remaining playable for all possible eventualities (of which there are also quintillions, most likely).

No Man’s Sky is a an astonishing mathematical algorithm for procedurally generating 18 quintillion worlds in 6GB of space, created by a tiny team of enthusiastic coders in a meagre office in Guildford – which in itself is remarkable enough – but it’s not the pillars of fucking creation. It’s a mathematical framework, a complex formula for spitting out odd planets and weird life-forms, but it’s still just procedural generation. Stop treating it like it should be an entire living, breathing universe, with a history of billions of years of evolution and chaos theory in action, because that’s simply not possible.

I’ll repeat that point in case you missed it, because it’s really important and I think some people out there aren’t fully taking it on board: No Man’s Sky does not contain the pillars of fucking creation. It’s still just maths – enormous, staggering, overwhelmingly clever maths, admittedly – but at the end of the day?

No Man’s Sky is just really, really good at maths.

How did we do?

We hope you found this article useful, or informative, or thought provoking, or maybe even a little entertaining. Perhaps it was a guide that helped you through a tricky bit, or we even saved you some money? Lovely stuff! If you'd like to say "thanks" you could always buy the team a cup of coffee.