TL;DR the demo visualizes the circle-packing algorithm I talk about here
I'm a big fan of procedural generation. I'll proudly claim to be among the first to be let down by v1 of No Man's Sky, but funnily enough, whenever I do return to No Man's Sky I only engage with the parts of the game that were available in the first version anyway.
In v1, the game was almost exclusively about exploration because there just wasn't that much else to do, and that aligns perfectly with the particular beauty of experiencing those algorithms at work. People will complain that procedural art isn't handcrafted, but I don't think that's exactly true.
The handcrafted piece is the algorithm which bounds the infinity of possible output. Good procedural art, like that of Minecraft, No Man's Sky, or Caves of Qud, manages to be flexible but to always or (ideally, in my opinion) almost always result in something legible. Most significantly, I appreciate procedural art that isn't precious about curating its output.
When I can re-roll a map, a planet, or an entire world with no friction, I begin to appreciate exploring each roll much more—if the possible output is so vast, any beauty I might find some a tiny corner is that much more special. Would it have gone unappreciated if I hadn't been there to notice it?
That balance of consistency and chaos can give a real sensation of looking into infinity. Ridiculous as it is, I accidentally stumbled across an elemental version of that feeling when I was creating the demo for the hover bubbles post.
Shifting vs popping
I wanted to create a field of bubbles, but I didn't want to place them by hand, so I decided to create a circle packing algorithm that looks something like this:
- Make a central circle of a constrained random radius
- Push it to a stack, then, as long as there are circles remaining in that stack
- Take a circle from the front of that stack (shift)
- Look for any surrounding circles or edges to identify free space
- Fill the remaining free space with circles which are pushed to the stack after creation
This fills a space very efficiently, because it effectively can be visualized as adding circles in layers around the center, so that every layer is as full as possible within the provided constraints before we move onto the next.
I wondered, though, what would it produce if I were to take circles from back of the stack (pop)? I made the change, and suddenly the algorithm was spitting out branching limbs and gestural sweeps.
The difference is essentially a depth- vs breadth-first distinction. Rather than filling the space layer by layer like the shift strategy, the pop strategy goes quite literally as far out on a limb as it can before returning to the first layer, bounded on that initial limb only by the edge of the available space.
On settings with small ratios between the largest and smallest possible radius, it's clear that this branching and swooping comes from the placement algorithm essentially spiraling around the center as it continuously pops the clockwise-most circle to build on.
This spiraling effect could still result in a tight pack, except my algorithm to check whether a sector around a given circle is occupied is very basic—looking for pie slices with the maximum possible radius to avoid overlaps without doing any additional geometry (this is hard to describe, more easily visualized in the demo).
That makes it perform pretty terribly as a circle-packing algorithm, but all of the empty space creates breathing room for the hungry pattern-matching part of my brain to latch onto. For some reason, this one kind of reminds me of a jumping spider:
It's especially distinct because of the concentration of large circles around the edge. Radii are chosen pseudo-randomly like so:
- If the available space can fit at least two circles regardless of random choice, choose at random
- Otherwise, if it's possible to fill the available space with at least one circle, do so
- Otherwise, limit the maximum random choice to ensure that the available space can be filled with two circles
Sampling from uniforms distributions causes the available space constraint to dominate, resulting in radii consistently getting smaller closer to the edge as the available space decreases, leading to some degree of sameyness between seeds. Breaking up that tendency has a huge effect on making the generated patterns feel both varied and intentional.
The Pareto distribution is slightly haunted
The exponential distribution tends to create more organic-looking shapes just because small values are so much more likely than large values, leaving space to select large radii on the edges and interrupting the spiral pattern that the pop algorithm wants to converge on.
The Pareto distribution should be an even better fit because of its tendency to choose more extreme values both on the high and low ends. Bizarrely though, there's a large circle that shows up on the upper right that is common to a tremendous number of seeds.
I can't really demonstrate this without a ton of screenshots, but if you're still reading and you have a couple seconds, by all means go to the Hover Bubble demo with the Pareto strategy and click "reroll" a bunch of times. It's kind of uncanny.
In general, rolling on the Pareto distribution produces near-identical patterns with a shocking frequency despite the seeds having almost no digits in common.
I'd truly love to know what's going on here, so if you happen to know why this happens, by all means let me know at someone@letsomething.blog.