Ortho-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.

Kites for some shapes

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 reading

Quarter-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 reading

VoronatorSharp

I’ve relased a new library, VoronatorSharp.

VoronatorSharp is a C# library that computes Voronoi diagrams. The Voronoi diagram for a collection of points is the polygons that enclose the areas nearest each of those sites.

Voronoi diagrams have applications in a number of areas such as computer graphics.

This library features:

  • Computes Voronoi diagrams and Delaunay triangulations.
  • Voronoi polygons can be clipped to a rectangular area.
  • Uses a n log(n) sweephull algorithm.
  • The implementation attempts to minimize memory allocations.
  • Integrates with Unity or can be be used standalone.
  • Uses robust orientation code.
  • Handles Voronoi diagrams with only 1 or 2 points, and collinear points.

Editable WFC

When I spoke about autotiling, I briefly touched on how it’s possible to use Wave Function Collapse (or other constraint based generators) as a form of autotiling, i.e. user-directed editing of tilemaps.

I’ve usually referred to this technique as “editable WFC“. It’s a combination of autotiling and WFC, and contains the best of both:

  • Being an autotiler, it allows users to easily and interactively make changes to an existing level.
  • Being constraint based, it automatically ensures that those changes are consistent with the predefined rules of the constraints, potentially making further changes to the level to make it fit

This is different from most other autotilers, which either require manual configuration of patterns used to enforce good behaviour, hidden layers, or come with more stringent requirements on what tiles are available.

Continue reading

Infinite Modifying in Blocks

I’m going to share with you a technique I’ve found for doing lazy, reliable, deterministic, constant-time infinite generation of tile based levels using Wave Function Collapse (WFC). But first, let’s cover some background, Modifying in Blocks, and lazy chunk based infinite generation.

Continue reading

Constraint-Based Tile Generators

Last article, we were comparing WaveFunctionCollapse (WFC), and Model Synthesis (MS). These are both similar procedural generation techniques that work along similar lines. Specifically, they generate a grid of tiles (or pixels), using a set of hard constraints, and some generalized solver technique to find a solution, a set of tiles that satisfies all the constraints provided. Let’s call this overall class of thing constraint-based tile generators.

The techniques have been pretty popular in recent years, and part of that is because it’s actually a very easy concept to experiment with and extend. Many of the more practical examples in the wild include their own extensions, as basic WFC tends to produce levels that look a bit repetitive and structureless.

Today I thought I’d do a review of all the different ways that you can customize this generation technique, showing how WFC and MS are subsets of a greater class. The whole family of such algorithms is much larger and I think there’s a lot of potential still to explore.

Continue reading

Model Synthesis and Modifying in Blocks

I’ve written a lot about Wave Function Collapse. Developed in 2016 by Maxim Gumin, it’s an algorithm for generating tilemaps and pixel textures based on the constraint solving with extra randomization . But did you know most of the key ideas come from a paper written a full decade earlier? Today, we’ll be looking into Model Synthesis, the 2007 PhD dissertation of Paul Merrell, and some of the elaborations he’s designed, particularly Modifying in Blocks.

Continue reading