Week 61: An illustrated explanation of my corner-match autotiling

More progress on autotiling 45° corner-cases.

tl;dr: This week, I wrote an illustrated explanation of how my corner-match autotiling works. And I'm still fixing the last of the 45° corner-cases.

Skip to the bottom to see my normal highlights and laundry-list status updates.

How my corner-match autotiling works

Overall autotiling steps:

1. Calculate which neighbors are present and what their angle types are.
2. Calculate the four corner-types for the cell according to the neighbor-cell topography. Also, calculate the corner-types for neighbor corners.
3. Calculate the best tileset quadrant matches for each corner.
4. Render the four quadrants separately in an inner tilemap.

Calculating a tileset quadrant match

1. Create two image files to represent the tileset

• The first image defines the actual subtile art.
• The second image contains corner-type annotations that define the shape of each subtile quadrant.

• Here is a complete tileset supporting 90° and 45° subtiles.
• On the left is the tileset with the corner-types rendered over top.
• In the middle is the tileset image.
• On the right is the corner-type annotations image.
• (You can click an image to enlarge it.)

2. Create a mapping from corner-type to quadrant position using the corner-type annotations file.

Matching an annotation to its corner-type:

• Each possible corner-type is defined in a long enum list, which looks something like the following:

•     EMPTY,
•     FULLY_INTERIOR,
•     ....
•     EXT_90H,
•     EXT_90V,
•     EXT_90_90_CONVEX,
•     EXT_90_90_CONCAVE,
•     ....
•     INT_90H,
•     INT_90V,
•     ....
•     EXT_45_H_SIDE,
•     EXT_45_V_SIDE,
•     EXT_EXT_45_CLIPPED,
•     ....
•     EXT_90H_45_CONVEX,
•     EXT_90V_45_CONVEX,
•     EXT_EXT_90H_45_CONCAVE,
•     EXT_EXT_90V_45_CONCAVE,
•     ...
•     EXT_INT_45_FLOOR_45_CEILING,
•     EXT_INT_90H_45_FLOOR_45_CEILING,
•     EXT_INT_90V_45_FLOOR_45_CEILING,
•     INT_90H_EXT_INT_90H_45_CONCAVE,
•     INT_90V_EXT_INT_90V_45_CONCAVE,
•     ...
•     INT_INT_EXT_90H_45_CONCAVE_INT_45_H_SIDE,
•     INT_INT_EXT_90V_45_CONCAVE_INT_45_V_SIDE,
•     INT_90H_INT_INT_90V_45_CONCAVE,
•     INT_90V_INT_INT_90H_45_CONCAVE,
•     ...
• There is a separate annotation to represent each corner-type.
• These annotations are defined in a third image file.
• This makes it easy to configure the pixels used for each corner-type.
• And this makes it easy to change the shape used for a given corner-type.

A corner-type annotation key image.

A legend listing corner-types along with their annotations and some example subtile art.

Disambiguating quadrants with the same corner-type:

• Many different quadrants in the tileset can use the same corner-type.
• The art for a corner-type might vary depending on how that quadrant connects to its neighboring quadrants.
• So the corner-type annotations image also includes annotations to represent neighbor-quadrant connectivity.
• And the mapping from corner-type to quadrants also includes optional neighbor-type info in order to query the most specific quadrant match possible for a given neighbor-cell topography.

How a quadrant connects to its neighbors can affect the underlying art.

• There are two ways to annotate neighbor-quadrant connectivity:
• Implicitly:
• This uses a single pixel to indicate that the quadrant should connect to a neighbor in the given direction.
• The neighbor's type is then determined according to the whatever type annotation is rendered in the corresponding cell in the tileset.
• Explicitly:
• An implicit annotation requires the tileset to include the neighbor quadrant next to the connection annotation.
• Unfortunately, this could require adding a lot of extra quadrants to the tileset, just to represent these neighbor types.
• So, the connected-neighbor type can also be represented explicitly by including the entire neighbor-type annotation.

Vertical-exterior neighbor-connection annotations:
Implicit on the left, explicit on the right.

3. Define corner-type fallbacks

• When considering a neighbor-quadrant connection, many corner-types can be interchangeable while still preserving the art transitions between quadrants.

The left-side quadrant needs to connect to a right-side quadrant with the correct shape.
All three of these right-side quadrants could be valid connection fallbacks.

• The tileset author shouldn't need to include separate quadrants for each possible combination of neighbor-type annotations if those combinations all correspond to the same underlying quadrant art.
• So a large mapping is configured to map each corner-type to it's possible fallback corner-types.
• The commutative and transitive properties apply for these fallbacks:
• If B is a valid fallback for A, then A is a valid fallback for B.
• If B is a valid fallback for A, and C is a valid fallback for B, then C is a valid fallback for A.
• Unfortunately, this large mapping is manually encoded.
• So, rather than requiring each reverse and transitive fallback mapping to be included for a given corner-type, these are automatically calculated.
• Additionally, each fallback corner-type could potentially match horizontally or vertically inside or outside of the subtile, so each of these four directions is configured separately.

4. Choose the quadrant with the best overall match

• When drawing a new cell in a tilemap, each quadrant is handled separately.
• Choosing which quadrant from the tileset to render for a given cell, depends on the four corner-types of the cell, as well as the corner-types of its neighbors.
• In order to select the best match, we first iterate through each possible quadrant in the tileset that matches the exact corner-type.
• We then look at whether the actual neighbor corner-types match the expected neighbor corner-types for the potential quadrant in the tileset.
• Connections to neighbor-quadrants within the same subtile have a higher priority than connections to neighbor-quadrants in an adjacent subtile.
• Fallback corner-types are accepted for an expected neighbor corner-type.
• If a given neighbor-connectivity isn't defined for a quadrant in the tileset, then that quadrant is matched with a lower priority than a quadrant that does include a matching neighbor-connectivity annotation.
• We calculate a weight for each possible quadrant based on how well it matches each of the neighboring corner-types, and we choose whichever quadrant has the greatest weight.

Let's calculate which quadrants to use in this subtile.

First, we calculate the corner-type annotations for all nearby quadrants.

Then, we compare possible quadrants from the tileset with the actual corner-types in the tilemap.
We will abandon this quadrant, since its corner-type doesn't match.

This quadrant's corner-type matches!
But it doesn't specify any neighbor-connection types, so it's a weaker match than some other quadrants.

This quadrant's corner-type matches, and also it's two neighbor-connection types match.
The vertical-interior neighbor-connection doesn't match the exact corner-type as specified, but it is a valid fallback.

This quadrant matches along five different corner-types.
These five matches give this quadrant a higher weight than the others, so we'll choose this one to render.

Here is the resulting tilemap with the quadrant we chose.

What happened last week?

Highlights

• Still fixing the autotiling logic and tile-set art for all the various 45° corner-cases.

Laundry list

• Continue debugging 45-degree quadrants.
• Add a few new missing corner-types.
• Add support for toggling debug logging from the Godot inspector panel.
• Add support for encoding inbound-exterior fallback multipliers adjacent corner-type connections separately from the opposite-side-interior multipliers.
• Update all fallback multipliers to work better now that I have more flexibility to encode inbound connections separately.
• Fix a subtle bug with how transitive fallback connection corner-types were being calculated.
• Rename connection directions from “inbound” to “external” and from “opp” to “internal”.
• Rename tile-set and tile-map to be tileset and tilemap.
• Refactor the corner-type annotation image parsing. It is now simpler and more extensible.
• Add support for explicitly annotating all quadrant connections that can be implicitly annotated.
• Add a new feature: CornerConnectionWeightMultipliers.
• This is needed for breaking ties when two quadrants have different connections with equal weight.
• This depends on aspects of the tileset's art. For example, floor art might extend far enough to impact the lower neighbor art, but wall and ceiling art might not.
• If you know that your tileset has certain properties, like above, then you might know that you can essentially ignore, or at least deprioritize, some quadrant connections.
• Otherwise, you might need to change many quadrant connection annotations from the original starting template, and also add many additional subtile combinations to account for various adjacent corner-types.
• Pull-out all of the quadrant-selection logic from CornerMatchTileSet and move it into a separate class.
• This makes it much easier to refresh the editor after making changes to the selection logic.
• Also, this is just better organization of my code.
• Add some useful debugging logic to my recursive quadrant-selection function.
• Add support for parsing the connections annotations for a single one-off quadrant.
• Add support for diagonal fallback-connection weights.
• Add support for using h/v-external fallback weights for h2/v2-external connections.
• Condense a lot of the tileset, by taking advantage of the new support for explicit internal connection annotations.

What's next?

• Finish fixing the final bits of 45° autotiling.
• Write documentation for all the different parts of my corner-match autotiling system.
• Publish my corner-match autotiling system as a stand-alone package in the Godot Asset Library.

🎉 Cheers!