It's possible to create an entire "reality" using nothing but algorithms

June 25, 2015 9:20 AM

Inspired by Dwarf Fortress and No Man's Sky, Josh Newland writes about procedural generation of game worlds at Gamasutra and presents his Unity/WebGL game project.
posted by boo_radley (15 comments total)

As a programmer who has played with procedural generation this error message amused me greatly:

An error occured running the Unity content on this page. See your browser's JavaScript console for more info. The error was: too much recursion

Of course, one cannot have too much recursion... only too small a stack. Silly Firefox. It ran fine in Chrome. YMMV.
posted by samworm at 9:46 AM on June 25, 2015 [10 favorites]

Perlin noise is a very old technique for generating landscapes and other "realistic-looking" topologies. Pretty cool to see that it's still widely used for that purpose.
posted by schmod at 10:15 AM on June 25, 2015 [1 favorite]

Is there a substantive difference between an algorithm and whatever rules physics plays by? Because it seems to me that we live in a procedurally generated universe.
posted by no mind at 10:19 AM on June 25, 2015 [2 favorites]

This guy did it with 50bytes.
posted by jeffamaphone at 10:20 AM on June 25, 2015 [7 favorites]

You need algorithms and also physical computers I think
posted by clockzero at 10:21 AM on June 25, 2015

River Raid and Pitfall used a linear feedback shift register to generate their not-quite-endless levels. (incidentally, this is the same algorithm the Atari 2600 sound chip implemented in hardware to generate random-ish noise).
posted by RobotVoodooPower at 10:26 AM on June 25, 2015 [4 favorites]

Is there a substantive difference between an algorithm and whatever rules physics plays by? Because it seems to me that we live in a procedurally generated universe.

You need algorithms and also physical computers I think

Well, there's the simulation hypothesis...
posted by Rangi at 10:47 AM on June 25, 2015

Sweet! Procedural generation is one of the common threads between many of my favorite games.

I played a dungeon-crawler called Telengard on my Commodore 64, many moons ago. The dungeon is very vast, but is the same every time you play. I learned later that it's procedurally generated, because otherwise it would never have fit into the tiny amount of memory that microcomputers had at the time.

So, there's an unconventional use of procedural generation: not to make the game different every time, but to make it the same every time, within very tight memory constraints.

The diamond-square algorithm is another relatively simple-to-implement algorithm for generating terrain or other heightmaps.

And RogueBasin, a great little wiki about developing roguelike games, has some interesting articles about procedural generation of 2D, grid-based worlds.
posted by escape from the potato planet at 4:03 PM on June 25, 2015 [1 favorite]

Once we implement AI, everything will be procedurally generated.
posted by blue_beetle at 4:32 PM on June 25, 2015

The diamond-square algorithm is another relatively simple-to-implement algorithm for generating terrain or other heightmaps.

Notice the grid-aligned artifacts you can get with diamond square. BUT.

Consider what a generalization of diamond square would look like. Diamond square fixes the order that points are visited in; for each point, it also fixes the points whose average is perturbed. But, if you don't give a shit about performance, you can just get rid of those restrictions. Instead, you generate K seed points, and then thereafter pick any point, anywhere, find the K nearest neighbors that already have a value, and perturb their average. Keep picking points until the image is full. You can retain some of the diamond square flavor by having the magnitude of the perturbation slowly decrease as more points are picked.

I threw together a little proof of concept in C# and I think it (slowly) makes purdy pictures.

And then you think- couldn't that be generalized further? K-nearest-neighbors is just one method among many of predicting the value of a point given a set of other values. The method could really be "for the next pixel, use the existing pixels to generate a predictive model, then perturb the prediction of that model for this pixel", and the method I implemented above would be an instance of this, using k-nearest-neighbors as its model. Other models- other methods of predicting one pixel's value given the set of existing pixel values- could produce completely different images.
posted by a snickering nuthatch at 9:13 PM on June 25, 2015 [2 favorites]

Jpfed: apologies if this is a really stupid suggestion but couldn't you improve performance to near-diamond-square by generating NUMPIXELS guaranteed-unique pseudorandom pixel coordinates using a Linear Congruential Generator with a period of NUMPIXELS? Instead of picking points at random and testing if set, you generate the next pseudorandom coordinate to visit, perturb and walk the grid pseudorandomly with zero repetition. In practice you'd want to use the first N coordinates for your seeds, and subsequent NUMPIXELS-N coordinates for your perturbation points.

Again, apologies if I've misunderstood something here or if that's just a really stupid idea in general. I do a lot of UE4 voxel mesh coding but have only the slightest exposure to the terrain value generation side of things.
posted by Ryvar at 11:25 PM on June 25, 2015

That's a neat idea! My approach didn't involve testing; it was more "here's a list of all the point coordinates in the image; randomly select one to pop from the list". So generating the next point is pretty fast; the slow bit is finding nearest neighbors. Instead of making a proper spatial data structure, I iterate over a list of already-set points if there aren't too many of them, else spiral outward from the point, probing the bitmap-under-construction for already-set points.
posted by a snickering nuthatch at 12:19 AM on June 26, 2015 [1 favorite]

Generated noise doesn't work when you go high fidelity: you need real world samples instead.
posted by andrewdoull at 12:49 AM on June 26, 2015

I'm working on a procedurally generated game, but just to fuck with myself, I wanted it to be scrollable, both up/down and left/right, and tilable, so you could scroll over the entire sphere. Like Civilisation, but there you have a cilinder (you can scroll left/right and end up where you started) and I wanted this to happen when you scrolled up/down as well.

So I needed seamlessly tilable randomly generated terrain. I ended up using 4D Simplex noise, fractally overlaid; Simplex noise is what mr. Perlin came up with after Perlin noise; the 4D part means you're basically looking up circles in a 4D structure (it helps if you think of this as a 3D pointcloud or a cloud of smoke) so the terrain you create is seamless where the edges meet.

To create actual terrain, you add up (let's call it) different frequencies of this noise to create larger and smaller terrain features which, when added up, create mountains and valleys.

I do this once per world generation (at the beginning of the game), but I have since realised I could do this in realtime at runtime, so you could have an endless gamespace (kinda like Minecraft, but pixelperfect and not blocky) you could wander through, meeting new thing along the way.

It does take a long time to generate, though, on Android machines, but I know the class I've implemented to generate this data needs mucho optimising, but it still is quite cool looking.

After all that, you do have to add rain fall /erosion simulation to get decent looking rivers/lakes/seas, not to mention a shitload of other stuff to actually get a game (I'm working on randomly generated, interlocking factions with actual decision based dynamics, so doing stuff for one faction can piss off/eliminate another faction, that kind of thing).

Anyway, I am still working on all of this, but I do have some pretty pics (and apparently a rather technical post) on spiralcode.wordpress.com (am I allowed to do that, self link a relevant subject?) of my WIP. But right now, I'm ghonna dive into all those links! So, thanks, boo_radly, for screwing up my friday night plans!
posted by MacD at 11:14 AM on June 26, 2015 [4 favorites]

You're welcome! Happy to have helped you along the path org magnificent obsessions.
posted by boo_radley at 8:57 PM on June 27, 2015