Reason
I’m implementing a game where a city is procedurally generated. It is based on a hexagon grid, and buildings can be placed in any of the six segments of a hexagon. To allow flexibility I imagined that there should be difference in how many segments a building can take. A simple house get’s one segment, a church get’s an entire tile and fields of wheat get one or more.
During implementation of this, it turned out it can be a bit boring to look at. After reading how other games like Enter the Gungeon handle procedural generation, I got motivated to try it for my cities.
What
Enter the Gungeon hand crafts a set of tiles, and slaps the larger tiles together in a level. Combine this with traditional procedural generation and they have some really unique and fun results. So instead of defining single buildings and place them around based on necessity or other constraints, I’m going to create different sets of hexagon tiles that can used to combine into a larger city.
They are going to be handcrafted so it should be easier to make at least some parts of the city be unique. Examples:
- A wheat field spanning multiple tiles with a mill and a few houses
- A wall around a ring of hexagons (no reason the set of tiles can’t have holes in them)
- A set of houses around a church
- A castle with adjecent shops/factories
- A cluster of houses in a set shape
How
To create a set of tiles (from now on called schematic) is not the difficult part.
I imagine it can be tricky to see if a certain tile actually fits the current city.
Rotating a schematic is not as simple as rotating the segments of a hexagon.
And if you look closely you can also draw hexagons by selecting segments of hexagons.
In fact, a single tile can exist on three different horizontal offsets in the hexagon grid.
Vertically such an offset is not possible, it always falls in line with the actual hexagons.
Displayed above is the same hexagon, but displayed in three different positions.
(left: centered on the right side of a hexagon, middle: centered on the center of a hexaong, right: centered on the left side of a hexagon)
Rotation
To rotate a schematic you define a center hexagon that will be the axis around the entire schematic is rotated. That center hexagon not actually shifts position, but the further distance away of the center the shift will be larger (with an amount equal to the distance of the center.) A ring of a hexagon is like a circle around a center hexagon. The further away of the center, the larger the ring is. Apart from the shifting we also rotate the segments inside the hexagon, to keep the segments aligned to their new orientation.
There probably is some smart way to rotate the hexagons using direct manipulation of the coordinates.
For now I walk the rings to find the correct hexagon, and try to refactor into something smart after I write tests.
Three different rotations of the same schematic.
Three different rotations are possible with the same schematic, but don’t make sense as its a symmetric shape.
Pseudo code algorithm:
foreach hex:
if hex = center
rotate_segments(hex)
else
distance = hex - center
ring = get_hexes_on_ring(center, distance)
index = ring.find_index(hex)
const new_hex = ring[index + distance]
rotate_segments(new_hex)
Shifting
Shifting is a lot easier, the only tricky thing is that the result of a single hexagon shifting can result in segments on multiple hexagons. It probably can be calculated programatically but I map every segment in hex to combination of hex & segment. After you end up with an array of arrays, I loop over them to combine every duplicate hexagon in a single hexagon again.
Pseudo code algorithm:
new_hexes = []
foreach hex:
foreach segment:
# map every segment to a hex and segment and add result to list
north: find_hex_neighbor(hex_direction.south_east), segment = southwest
northeast: find_hex_neighbor(hex_direction.south_east), segment = south
southeast: hex, segment = north # stays on the same hex
south: hex, segment = northwest # stays on the same hex
northwest: find_hex_neighbor(hex_direction.north_east), segment = northeast
southwest: find_hex_neighbor(hex_direction.north_east), segment = southeast
result = []
foreach new_hexes:
combined_segments = result.find_hex(new_hex) || create_new
combined_segments.push(new_segment)
Javascript implementation of above algorithm can be found in webapp used to generate screenshots.