Ok, this one is really best explained with a visualiser:
Continue readingDungeon Generation in the Gnomish Mines of NetHack
procgen
Mesh Welding with Spatial Hashing
Recently I’ve been looking at Mesh Welding algorithms.
Mesh Welding is when you have a a mesh, i.e. a collection of vertices, edges and faces, and you merge any vertices which are close enough together.
This is a common operation in procgen, as it’s often convenient to generate several things completely independently, then join them together afterwards. I’ve had to re-implement it several times.
Continue readingOatmeal Spice
Say you’ve written a little procedural generation program. Say it’s some art, music or level generator. It looks kinda cool, but after a few generations, you are already bored with it. Somehow, for all your careful design, all your generated results look samey, boring. This is Kate Compton’s ten-thousand bowl of oatmeal problem: every bowl of oatmeal is unique, but that does not make them interesting or valuable.
What can you do about it? In this article, I want to talk about how we can improve the interestingness of the results, not by adding more content, but by taking things away.
Continue readingLogarithmic Spirals
I got interested in logarithmic spirals recently after learning of the connection between periodic grids and the complex exponential transform.
I made a fun explorer for you to try out, and made the trippy looping animation below.
Continue readingInfinite Random Rectangles – the Poisson Rect process
Previously, we looked at how to sample points randomly at a given density across an infinite plane.
It’s harder than it sounds, as I was looking for an algorithm that was not biased by the size/shape of the chunks used to calculate it.
Today let’s extend that to filling the infinite plane with random non-overlapping rectangles. As before, that means finding a deterministic chunked algorithm that we can prove is unaffected by the choice of chunking.
Continue readingDealing With Infinite Grids
I’ve added an article on handling infinite sized procedural generation to the Sylves documentation. It’s probably of interest to readers of this blog as the techniques are fairly general.
Infinite Random Rhombus Tilings
Everyone loves the Townscaper grid. It’s got a a nice organic look, while still being quadrilateral tiles, somewhat regular, and reasonably easy to implement. But it has some annoyances. I’ve finally managed to find my own design of grid that has a very similar look, but fixes these problems.
Continue readingFiddling Weights with Temperature
In procedural generation, the absolute simplest, most common technique is randomly picking an item from a list. More often than not, it is a weighted random choice, where each item is selected with a frequency proportional to its “weight”, a numerical value that can be tweaked by the designer.
def random_choice(items: list, weights: list[float]):
total_weight = sum(weights)
random_value = random.random() * total_weight
# Find the item that corresponds to the random number
for i, weight in enumerate(weights):
random_value -= weight
if random_value <= 0:
return items[i]I wanted to share a technique from the Machine Learning community that is simple enhancement to this routine that gives a lot of convenience over tweaking weights directly, called temperature.
Continue readingExploring Rectangle Subdivisions
Last week, I saw a talk on Vuntra City, a procedurally generated city with a fully explorable city. Developer Larissa Davidova explained that she settled on using Recursive Subdivision for the city blocks, as she wanted some level of organicness, while still only having to deal with rectangles. But she didn’t like having indefinitely long roads that cause implausible sightlines.
One way Vuntra City handles this is by subdividing a rectangle into 5 blocks, a pattern I called “whirl” in my previous article on recursive subdivision. You can see that it has no internal roads that stretch across the entire map.
But Larissa’s talk got me thinking. The whirl pattern is interesting because it cannot be made from simple cuts. What other ways of subdividing a rectangle into smaller rectangles1, are out there?
Continue readingRunning Tracery bots with LLMs
Tracery bots were a fun, simple, way of making generative texts. They are basically an easy way to specify generative grammars via a simple JSON file format. There used to be a horde of fun little tracery bots on twitter until API changes shut them all down.
Nowadays, you can prompt a chatbot to get whatever you want. But that lacks the same charm, and it doesn’t give you the control you’d want for something unleashed on the internet. Let’s do something about that.
Continue reading