I’m in the midst of doing the MATS program which has kept me super busy, but that didn’t stop me working on resolving the most important question of our time: What Hogwarts House does your chatbot belong to?
Continue readingClaude is a Ravenclaw
Intermediate
Exploring 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 readingWraparound 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 readingQuantum WaveFunctionCollapse
One of my biggest gripes with the WaveFunctionCollapse procedural generation algorithm is that, despite the name, it doesn’t really have anything to do with quantum mechanics. I usually prefer the term Constraint Based Procedural Generation instead.
The name WaveFunctionCollapse is meant more as an analogy. As the algorithm progresses, it resolves a fuzzy, uncertain picture of the output into sharper detail, much as in quantum mechanics, the state of a system is also a range of possibilities, which resolves to something specific when “observed”.
But could we adapt WFC to the Quantum way of thinking, and ran it on actual Quantum Hardware? Well, that’s exactly what is discussed in this new paper Quantum WaveFunctionCollapse by Raoul Heese1 (Youtube summary). Does it work? Is it fast? Let’s find out.
Continue readingInfinite Uniform Point Distributions
Rune’s recent talk on layered procedural generation has got me thinking about procedural generation again, so I wanted to share a technique I found about doing a uniform distribution of points on an infinite plane. I assumed this would be a well known thing, but I couldn’t find any references elsewhere.
Continue readingPublishing An Open-Source Library for Unity
So you’ve got some open source C# code, and you want to publish it for other users in Unity? I’ve explored a few options, here are the pros and cons.
Continue readingOrtho-tiles
Last time, we looked at quarter-tiles. This was an auto-tiling technique for square grids. Each cell in the grid is associated with a terrain (i.e. either solid or empty). Then the squares were split in four, and each quarter was assigned an appropriate quarter-tile.
Otho-tiles extends this procedure to work with irregular grids, even non-square grids. We just have to alter the procedure a little, and be ready to deform the quarter tiles fit in place.
Ortho?
Ortho is a Conway Operator. It can be thought of as the extension of dividing a square into 4. It divides each n-gon into n “kites” or “ortho-cells”. Each kite is a four sided shape containing the cell center, one corner, and the midpoint of the two edges adjacent to that corner.
The appeal of the ortho operation is it can take any polygonal grid, no matter how irregular, and convert it into a grid of 4 sided shapes. And it’s much easier to work with something that has a consistent number of sides.
Continue readingQuarter-Tile Autotiling
Since Oskar posted about it, I see an increasing amount of praise for his Dual Grid proposal for autotiling terrains. It works by drawing tiles at a half-cell offset to the base grid, creating a dual grid, and using marching squares autotiling to select which tile to draw based on the terrains the corners of the dual grid, which is the centers of base grid.
This is a great scheme. It’s simple, only needs a few tiles and can be extended quite easily. It’s used in many games.
But, it does have some drawbacks. The dual grid is difficult to get your head around. You have to worry about ambiguous tiles. And despite being a substantial improvement over the blob pattern, it still requires drawing quite a number of different tiles.
I’m here to explain an alternative, quarter-tile autotiling. Quarter-tiling has also been called sub-tiles, meta-tiles (when doubling instead of halving). I’ve previous described as micro blob, which is the same thing with precomposition. It’s best known for being the tiling built into the RPG Maker engine.
Quarter-tiling is pretty easy to implement, and requires substantially less effort to create tiles for, as it uses fewer, smaller tiles. That does mean it’s not possible to produce as much tile variation as marching squares. But there’s plenty of techniques for adding that back.
Later, we’ll look at ortho-tiles – an extension of quarter-tiles to irregular, non-square, grids.
Continue readingConstrained Text Generation with AI
I was discussing how AI text generation, such as ChatGPT, might end up getting used in computer games. So far, designers are fairly reluctant to adopt the technology. One of the key problems is that you just can’t control the output enough. Language models will break character or respond in inappropriate and toxic ways. Finding a good solution to this is a huge research field, and not likely to get cracked soon.
For the foreseeable future, AI in games is much more likely to be used offline – assets and dialog generation generated up front, so it can be vetted before being integrated into the game.
But it got me thinking, can we vet the AI’s output in advance, but still get the benefits of intelligent decision making at runtime? It turns out, we can! I doubt it’ll be useful in every circumstance, but I can certainly see uses for it, like chatbots, games.
The code and demonstration for this article is available here.
Continue readingInfinite Quadtrees – Fractal Coordinates
A cool technique I’ve wanted to write up for a while is “Fractal Coordinates” described in a paper by Peter Mawhorter. Don’t be scared by the name, it’s essentially a variant on quadtrees that covers the entire 2d plane. Fractal coordinates have some interesting properties that are useful for procedural generation.
But first, let’s catch up on quadtrees.
Continue reading