Ok, this one is really best explained with a visualiser:
Continue readingDungeon Generation in the Gnomish Mines of NetHack
gamedev
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 readingDihedral Subgroups Explained Via Factorio
The dihedral group is the mathematical formalism behind all the rotations and reflections of a regular polygon. For an n sided polygon, there are always n possible rotations, and n reflections, for 2n possible symmetries.
Combining any two symmetries gives another from the same group, that is what makes it a group in the mathematical sense.
The theory of it is useful to know for gamedev. I was reminded of this when seeing this Factorio devlog, where the developer ran into some trouble because he initially forgot to account for all the cases.
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 readingOuter Wilds Mission Graph
I recently played Outer Wilds and absolutely loved it. But after playing it I realised how little of the game was really on the critical path – most locations fill in lore and deepen your curiosity but don’t actually help you reach any location you couldn’t before. To analyse this, I made a mission graph for the game. Spoilers ahead.
SPOILERS IN FULL ARTICLEWraparound Hex Grids
A user requested adding wrapping hex grids to Sylves. That is, a grid that is a collection of hexagons, and the collection itself is also hexagonal shaped. When you exit from one side, you re-enter on the opposite side.
The maths for this turned out to be surprisingly fiddly, and not listed by RedBlobGames, so I thought I’d share it here.
Continue readingGenerating Tilesets with Stable Diffusion
Recently I’ve been playing around more with gen AI techniques. I thought I’d try to generate a set of tiles that all connect together. It’s harder than it sounds – Stable Diffusion is hard to control, so there’s no easy way to get a set of images that are fully consistent with one another.
I’ve developed a technique for doing it that I’ll call Non-Manifold Diffusion as it involves doing diffusion over a set of patches that interlock to form a non-manifold surface.
Continue reading