Herringbone Tiles

Summary

This is an unfinished paper that I wanted to get out there. Currently 2011-10-22, originally written in 2010. Herringbone Tiles Sean Barrett Silver Spaceship Software In this paper I'll describe a method for expanding on the technique of Wang Tiles for generating large 2D regions from smaller ones. I call the technique "Herringbone Wang Tiles" or just "Herringbone Tiles". It is also of particular relevance to the map system used in Infamous by Sucker Punch. For an unreleased indie CRPG I worked on in 2010, I used an extremely simple method of dungeon map generation. It involves assembling a large map out of small rectangular tiles. Each tile is chosen from a set of 128 pre-authored tiles (each tile is itself made out of small image sprites that are normally called "tiles" as well, but to avoid confusion here I'll call them sprites). The map algorithm is extremely trivial: every tile is selected at random, with no constraints from neighboring tiles or constraints chosen to enforce map connectivity. The primary technique that made this a viable approach is a novel method for synthesizing large 2D regions from small 2D tiles which I call herringbone tiles, which involves laying out tiles using a herringbone tiling pattern. This technique helps to reduce the obviousness of a regular tiling, and allows better-than-naive connectivity without any computation. A second technique which I didn't use I call jigsaw colors. Here, we allow the edge shapes of the tiles to vary in certain ways to help break up the long straight edges of a normal tiling. I shall say no more about this in this paper since I didn't try it. Wang Tiles The core idea is based on Wang Tiles. It's straightforward to make many small tiles with various edge constraints, and randomly generate a map, placing tiles so that they satisfy the existing edge constraints. (Edge constraints are domain specific; for example, when generating a mostly-solid map with constrained connectivity (e.g. a dungeon), you might sa...