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:

- Calculate which neighbors are present and what their angle types are.
- Calculate the four corner-types for the cell according to the neighbor-cell topography. Also, calculate the corner-types for neighbor corners.
- Calculate the best tileset quadrant matches for each corner.
- 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 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!

## Comments

## Post a Comment