Digitizing War Room Part 1: Map Generation

Work In Progress / 30 July 2023

If you haven't already, check out the project page for Digital War Room on my website at grantdoney.com for more context on the project, the inspiration, and the current playable!

The first consideration when starting this project was map generation. How do I create a flexible system where tiles can be edited frequently, but retain complexity. Where all this data can be serialized for the game state, with each tile knowing its neighbors, its railroads, and its resources each time the game is launched. I took a feather from Paradox Studio's cap, emulating their map generation technique for games like Hearts of Iron 4, Europa Universalis 4, and Crusader Kings 3. Instead of hand authoring dozens to hundreds of map tiles, each with their own outline, a pixel map of the tiles would be fed into a generator during run time, creating the geometry and linking the tiles together in the data. Paradox offers loose documentation on these features through their Modding wiki pages, so while the general concepts could be understood, the exact implementation would have to be from scratch.

The first step was creating geometry from color blocks. The first test map was a 32x32 bmp file with 3 color blocks, each intending to test a certain element of map generation

The first step was to read the input texture, finding the exterior pixels of each color block. These pixels would later be converted to vertices and fed into a mesh triangulation algorithm. This meant the vertices couldn't only be vertices, they also had to be in order, preferably in the same direction for each tile. Starting with the first pixel of the new frontier color, every neighbor is checked to see if it's the frontier color and an edge color. This was done in East, South, West, North, South East, South West, North West, North East order to maintain a counter clockwise search.

This pixels are then assembled as the main points, visualized here by instantiating spheres at the coordinates of the pixels.

These pixels could then be passed into a triangulator as ordered vertices, creating the first UV'd mesh based on the input geometry.

This method produced a glaring issue: the points in pixel space were integers, centered on the pixel, while the vertices for the tiles would have to meet to form seamless boundaries. The solution was to check each point to see if it was necessary for the geometry, labeling it a "Main Point". To be a "Main Point", the pixel's diagonal neighbors had to be a different color and have their two directly adjacent neighbors be different colors.This main point would be the same on each tile, meaning an average point could be taken between the 2 meshes. This system would be refined a number of times as the pixel map became more complicated. This resulted in the first seamless tiles and the end of the first generation source texture's usefulness (a statue was planned, but the funds never came through).

The second generation map used an "artistic" interpretation of western Europe at 64x64. It revealed a number of flaws in the system, which required further refinement of both the generation code and map authoring techniques.

At this time, the first exploration of Points of Inaccessibility was also started. In cartography, the Point of Inaccessibility is the furthest location form any border for a country or distinct body. This is normally where a label will be put. To label each of these tiles, a Signed Distance Field was calculated using a recursive quadtree search to find, roughly, the farthest point from any border in an irregular concave polygon.This is the load time destroyer.

Further refinement of the main point definition and edge loop extractor resulted in the eventual chubby Europe. Unity's Line Renderer components were used to create the first rudimentary borders, passing vertex positions for the Line and using a Shader which only renderer the interior half (one of the reasons the counter clockwise order was so imperative across all tiles, as the Line Renderers definition of interior UV's changed based on direction).

The third generation of source texture saw an increase in resolution to 128x128 and the use of Google Maps to make sure it actually looked like Europe. This had the adverse effect of increasing the size of the map by 2 fold in each direction (noticeable by the very little labels)

The fourth generation created a much larger map, at 1536x1536 (egads,, it's not power of 2, how could this be). This map spanned the entire world, with roughly 100 tiles. This created a noticeable drop in performance when loading the scene, requiring an asynchronous operation so it didn't seem like the game had died horribly for 15 seconds. With some added camera controls and further refinement of the scripts, the result was the first fully generated map (with infinite side scrolling) and a manager for keeping track of the tiles, unit stacks, and occupations.