The Biomes are pseudorandomly generated via a combination of "Wang tiles" and "Pixel scenes".
Herringbone Wang Tiles[]
These tiles are slotted together. Looking at Horscht's awesome web-based wang tiler gives a clear visual explanation. See this page and this page for technical info about Herringbone Wang tiles.
This example of a single wang tile from the Coal Pits generates the associated structure
Examples of the wang tiles from the Mines (full, and zoomed section) can be seen below.
coalmine.png from the game code
A zoomed-in section
All the guaranteed chest spawns in Mines. One of them being a pixel scene.
A catalog of the HP Up Locations has been compiled.
Pixel scenes[]
Pixel scenes are added to the rendered biome.
Material colors[]
The colors in the wang tiles represent materials, as assigned by data/materials.xml and documented in the image at right.