Idraluna Archives

The Great Antarctic Hexcrawl Pt. 1 - This Train Is Bound for Idraluna (Planning, Prefectures, and Road Networks)

This post is a submission to the January 2024 blog carnival and, after a fashion, the start of my own version of lore24.

The Vision

A while ago I used real-world data (with some finagling) to make a quasi-realistic map of a post-ice Antarctica with believable biomes. Later, just for the hell of it, I overlaid the whole thing with approx. 128,000 six-mile hexes. (See here for how.)

It would be impossible to stock by hand, but I want to see if I can procedurally fill it with interesting locations. My ultimate goal is to write code that exports a GIS hex map along with a LaTeX or Markdown file containing a key with terse hex info, dungeon outlines, landmarks, and settlement descriptions. Nothing as ambitious as Hex Describe, but vaguely similar. For example, I envision entries something like this:

23456: Forest, hilly lowlands: Misty, aspen, rich soil. Dungeon: Murdicog's Manse (Crashed starship (military), 13 rooms & 3 levels) -- page 225.

I'll freely grant that campaigns that lovingly detail a smaller number of hexes are usually more fun and rewarding than a wide-but shallow world. But I'm mostly doing this for its own sake. Part of the fun here is figuring out how the hell do I make this work?

Here's the hex map I'm starting with:

(This is a hex map, the hexes are just really small!)

Lore Conceits

Antarctica in the year 102,024 is called 'Antibor'. It has a temperate climate due to ancient geo-engineering (the status of the rest of the planet is unknown).

There are three main culture groups on Antibor:

The key conceit for this project is that cyber-agronomy districts in the citadels produce enough nutrient cubes to feed residents, so the most technologically advanced stratum is concentrated in 'points of light' (much as I dislike that metaphor) in a vast wilderness with minimal pressure to clear farmland or develop the countryside. Thus, a map full of danger and mystery for players to explore.

Bottom-up vs. Top-down

Antibor is an ad hoc creation. I like simulation & procedural generation and have tried to use it where possible, but I've imposed some higher-level lore by fiat. Anything established in my ongoing Worlds Without Number campaign is canonical, and I want to keep the list of region and city names I dreamed up. Accordingly, I'm trying to implement the procedural elements in a way that fills in the gaps between my fiat decisions.

Similarly, I want to leave space for flux: restocking dungeons, re-placing wilderness lairs, adding in more fiat ideas, etc.

Working Backwards

Populating 128,000 hexes introduces competing pressures: making them distinct requires maximal random generation, but the resulting descriptions must be ruthlessly parsimonious to be even remotely useable. So I'm trying to anchor my efforts in a (relatively) clear idea of the end product, starting from what I most need to know when players enter a new hex. I've broken this down into five key 'user points of contact' that any underlying generative process will need to serve: general needs, mapping needs, at-a-glance Hex key info, regional info (more on that below) and detailed info for settlements, dungeons, etc.

General Needs:

Mapping Needs:

With GIS, there's a lot of potential for ad hoc mapping as long as I store information about the world in a consistent and machine-readable way (i.e. csv files).

At-a-glance Hex Key Needs:

Regional info needs:

Points of Interest Needs (the Gordian Knot that has so far stymied me at every turn):

I don't have all the answers yet, but I've decided to move forward with the parts I feel confident about. In this post, I'm going to allocate some sub-regions, place their main population centers, and plot the major road networks connecting them.

Prefectures

When the Alabaster Potentate landed in the 97,000s they imposed rational administration, decreeing that the continent be divided into (roughly) hexagonal prefectures with a center-to-center distance of 180 miles, further subdivided into ~900 hexagonal tracts of six miles. It was ordained that each Prefecture should be given to an Exultant house with the power to settle and lease tracts as they saw fit.

When the Archons were installed after the Epoch of Heresies, these divisions remained largely intact, but strict controls on population growth, travel, and settlement were imposed. This, combined with widespread resource and soil depletion, the invasion of the Swallowed Ones in the 99,000s, tighter galactic sanctions, and perennial Exultant rebellions led to a substantial gulf between the technologically advanced but stagnating Alabastrine culture and the depopulated hinterlands of Antibor.

In terms of procedural generation:

Making the Prefectures

GIS Workflow

Prefecture Borders

I used the create grid tool in QGIS to make a 180-mile hex grid (note: some images are from an initial attempt with a 144-mile grid, was too lazy to take new screencaps). Then I use the centroids tool to create a point layer of hex centroids and deleted the hex grid. I used the translate tool to ensure that a point was precisely aligned with the South Pole. Then I used select by location to delete all hexes not on land. (This prevents the creation of tiny prefectures with only like 3 coastal hexes).

Then, I ran the Voronoi Polygons command to create nearest-neighbor regions around each centroid. The Voronoi algorithm creates zones such that if a point is in a given zone, it is closer to the centroid corresponding to that zone than any other centroid. This mostly recreated the old Hexes but allowed coastal hexes to blob onto the shorelines.

I then used R to spatially join the hexes to the prefectures, with the following result:

Placing Capitals

I was initially going to try to calculate some kind of suitability score to place capitals, but eventually decided to just do it randomly. (I also considered using the centroid locations, but that felt a little too inorganic.)

I wrote a short loop in R to check if a prefecture already had a fiat-placed city, and if not place a new one & give it a placeholder name. In this loop, I also assigned a random Exultant house as the overlords. I didn't worry about fairness; after 5000 years they probably changed hands a bunch.

# loop through prefectures
for (prefec in na.omit(unique(hexes$prefecture_id_2))){
  print(prefec)
  prefec_hexes <- hexes[hexes$prefecture_id_2==prefec,]

  # grant to an Exultant house
  Prefectures$Ruling_house[Prefectures$prefecture_id_2 == prefec] <- r_gen('Exultant_house')

  # place capital
  # is there a citadel here?
  if (14%in%prefec_hexes$Biome||15%in%prefec_hexes$Biome){
    print(paste('Prefecture', prefec, 'has', nrow(prefec_hexes[prefec_hexes$Biome%in%c(14,15)]), 'urban hexes.'))

  }else {  # place a random capital city and name it randomly
    cap_hex <- sample(prefec_hexes$id, 1)
    hexes$Biome[hexes$id == cap_hex] <- 14  # assign to urban
    hexes$Hex_name[hexes$id == cap_hex] <- paste('Prefecture', prefec, 'capital')
  }

  # calc habitability
  prefec_hexes <- prefec_hexes %>% left_join(Biome_map, by=c('Biome'='Code'))
  print(paste(prefec, 'hab score is', mean(prefec_hexes$Hab_score)))
  Prefectures$Habitability[Prefectures$prefecture_id_2 == prefec] <- mean(prefec_hexes$Hab_score, na.rm=T)
}

Habitability Score

I used population density estimates by biome (not the best source, but I'm not trying to be scientific) to assign relative habitability scores to each region.

My plan is to use this (and possibly mean terrain roughness index) to weight likelihood of ruins and settlements.

Roads (and rail)

This one was a bit tricky. I want the Antiborian elites to be able to jet from arcology to arcology on elevated maglev trains while the plebians lead horse- merychip-drawn carts through the mud below. For mapping purposes, I envision a three-layer hierarchy:

AFAIK there isn't a great way to do hex pathfinding in GIS, so I opted for doing path optimization on a raster, converting the resulting roads to line vector files, and then snapping those lines to hex centers.

The Rail Network

To draw high-speed maglev tracks between the citadel arcologies, I did a least-cost path analysis using the leastcostpath R package. To make the 'friction surface' for the algorithm to optimize around, I assigned a friction score to each biome (high for jungle & xenoformed, extremely high for water, lower for steppe and savannah) and added that to the terrain ruggedness index. This probably overemphasized the effect of terrain (especially for a space-age civilization like the Alabaster Potentate) but I really wanted terrain to matter and stand out.

After A LOT of trial and error the algorithm ended up producing a pretty nice map. The black lines are the generated routes, overlaid against a map of pathfinding priority (higher values are easier to traverse).

I manually pruned it to remove redundant routes:

Prefectural roads

With the main rail lines in place, I still had a bunch of minor cities to link up. I discovered the roads package for R, which seems to be designed for planning optimized forestry roads but essentially fits my use case of 'connect a bunch of random points to an existing network as efficiently as possible'.

I placed roads using the 'dynamic least cost paths' algorithm which incorporates newly generated roads into future friction calculations, cutting down on redundant and parallel pathing. This resulted in a branching network toward the perpiphery. I actually like this -- it will hopefully induce players to do more off-roading, and it makes it easier to name major roads. It also subtly emphasizes the frozen, stagnant incuriosity of the Alabastrines, for whom the only routes that matter are those to the comfort and safety of the nearest Citadel.

Here's the code I used to make these:

######################## leastcost path ----
hexes <- vect(file.path(mapdir, 'Full_hexes.gpkg')) %>% distinct()
r <- rast(TRI)
water <- vect(file.path(mapdir, 'land_water.gpkg')) %>% filter(land==0)

friction_reclass <- data.frame(
  'Is' = Biome_map$Code,
  'Becomes' = Biome_map$Friction
)

### create a rail friction raster based on TRI and biome
rail_friction <- (1/(rasterize(hexes, r, field='Biome') %>% classify(friction_reclass) + (TRI))) %>% trim() 
rail_friction[is.na(rail_friction)] <- 0.0001
rail_friction <- aggregate(rail_friction, fact=9)
plot(rail_friction)

rail_cs <- create_cs(rail_friction)
plot(rail_cs)

destination_hexes <- hexes %>% filter(!is.na(prefecture_id_2), Biome%in%c(14,15)) %>% mutate(burn=1) 
dest_pts <- destination_hexes %>% centroids()
citadel_pts <- dest_pts %>% filter(Biome==15) %>% rowwise() %>% 
  mutate(citadel_name = strsplit(Hex_name, " ")[[1]][1]) %>% ungroup() %>%
  group_by(citadel_name) %>%
  slice_head(n=1)  # citadels are multi-hex, but we'll stick with only one transit hub per.
plot(rail_cs); plot(citadel_pts, add=T)

rail_network <- create_FETE_lcps(rail_cs, locations=citadel_pts)
plot(rail_network, add=T)

## Prune connections:
rail_network_pruned <- rail_network %>% rowwise() %>% mutate(connection = paste0(min(origin_ID, destination_ID), max(origin_ID, destination_ID))) %>%
  ungroup() %>% group_by(connection) %>% slice_head(n=1) %>% ungroup() %>%
  filter(!connection%in%c('26', '14', '47', '27', '56', '12', '13', '37', '36', '38', '35', '46', '78'))

plot(rail_cs); plot(rail_network_pruned, add=T); plot(citadel_pts, add = T)
text(citadel_pts, col='red', cex=3)

### Ok... it's a start.
writeVector(rail_network_pruned, file.path(mapdir, 'Rail_nework.gpkg'), overwrite=TRUE)
## PRUNE AFTERWARDS


######################## roads package -----
# now we branch provincial capital roads off the rail network.
rail_network <- vect(file.path(mapdir, 'Rail_nework.gpkg')) %>% mutate(burn=1)
destination_hexes <- hexes %>% filter(!is.na(prefecture_id_2), Biome%in%c(14,15)) %>% mutate(burn=1) 
dest_pts <- destination_hexes %>% centroids()
landings <- dest_pts

friction_reclass <- data.frame(
  'Is' = Biome_map$Code,
  'Becomes' = Biome_map$Friction
)
trail_friction <- ((rasterize(hexes, TRI, field='Biome') %>% classify(friction_reclass) + (TRI))) %>% trim()  ## I think it goes the other way for this package????
trail_friction[is.na(trail_friction)] <- 2000
plot(trail_friction); plot(landings, add = T); plot(rail_network, add = T)

roads <- projectRoads(landings=sf::st_as_sf(landings), cost=trail_friction, roads=sf::st_as_sf(rail_network), roadMethod='dlcp', roadsOut = 'sf', roadsInCost = FALSE)

plot(trail_friction)
plot(roads$roads, add=T, col='red')
plot(landings, add=T)

road_vect <- vect(roads$roads)

writeVector(road_vect, file.path(mapdir, 'Prefec_roads.gpkg'))
Prettification

Currently, the rail and road networks exist as lines created by 'connecting the dots' of raster cells selected by the pathing algorithms. So, they don't align perfectly with the hexes.

I ended up buffering the roads to filter hex centroids within 3 miles of the road, then used densify and snap to geometry to snap the road geometries to the hex centers. I'm pretty sure this resulted in some weird geometries and some sections are overly zig-zaggy but it got the job done insofar as the next hex along a road is unambiguous.

Similarly, for the rivers I had generated when I did the biomes (blue in the screencaps above), I wanted them to run along hex edges so that they'd serve as a clear obstacle when moving from hex to hex (you're either on one side of the river or the other). I found this QGIS Python script on Stack Exchange to snap lines to the edges of a hex. Unfortunately, it was for an older version of the QGIS Python API and was maddeningly difficult to get working in QGIS. But I managed to rewrite it in R to get much the same effect.

### Network snapping
river_hexes <- vect(file.path(mapdir, 'River_hexes.shp'))

geom(river_hexes[1,])
nrow(river_hexes)

test_cent <- centroids(river_hexes[1,])

# for the record, I do know how to spell 'triangle'
test_trangle <- rbind(geom(river_hexes[1,])[1:2,], geom(test_cent))
test_trangle <- vect(test_trangle, crs = crs(river_hexes), type='polygons')

segment_list <- vect(geom(river_hexes[1,])[1:2,], crs=crs(river_hexes), type='lines')

for(i in 1:nrow(river_hexes)){
  print(paste('Hex', i, 'of', nrow(river_hexes)))
  hex <- river_hexes[i,]
  centroid <- centroids(hex)

  for (j in 1:6){
    cat(j)
    trangle <- vect(  # make triangle
      rbind(geom(hex)[j,], geom(hex)[j+1,], geom(centroid)),
      crs = crs(hex),
      type = 'polygons'
    )
    cat('...')
    #plot(trangle, add=T)

    # test if the river overlaps this polygon
    if(!is.empty(intersect(Rivers, trangle))){
      print('edge_detected')
      edge <- vect(  # make triangle
        rbind(geom(hex)[j,], geom(hex)[j+1,]),
        crs = crs(hex),
        type = 'lines'
      )
      segment_list <- rbind(segment_list, edge)
    }
  }
}

plot(segment_list)

# Remove dangling segments (if one vertex has only one segment and the other has three)

segment_list_pruned <- segment_list

for (i in 1:nrow(segment_list)){
  print(paste('Segment', i, 'of', nrow(segment_list)))
  seg <- segment_list[i,]
  v1 <- geom(seg)[1,]
  v2 <- geom(seg)[2,]

  # proune out duplicates
  if (i < nrow(segment_list)){
    for (j in (i+1):nrow(segment_list)){

      seg_to_check <- segment_list[j,]

      v1b <- geom(seg_to_check)[1,]
      v2b <- geom(seg_to_check)[2,]

      if((sum(v1==v1b)==5&&sum(v2==v2b)==5)||(sum(v1==v2b)==5&&sum(v2==v1b)==5)){
        print('Removing duplicate edge.')
        # remove duplicate rom segment list and segment list pruned
        segment_list_pruned <- segment_list_pruned %>% filter(id!=seg_to_check$id)
        segment_list <- segment_list %>% filter(id!=seg_to_check$id)
        cat(paste('...new total:', nrow(segment_list)))
        break  # don't loop all the way to the end, as there are only two hexes sharing an edge, so at most one extra segment
      }
    }
  }

  # for each vertex, we grab the list of all other segments that incorporate that vertex
  v1_connections <- geom(segment_list)[geom(segment_list)[,'x']==v1['x']&geom(segment_list)[,'y']==v1['y'],]
  v2_connections <- geom(segment_list)[geom(segment_list)[,'x']==v2['x']&geom(segment_list)[,'y']==v2['y'],]

  if('numeric'%in%class(v1_connections)){v1_connections <- t(as.matrix(v1_connections))}
  if('numeric'%in%class(v2_connections)){v2_connections <- t(as.matrix(v2_connections))}

  if (nrow(v1_connections) == 3 & nrow(v2_connections) == 1 || nrow(v1_connections) == 1 & nrow(v2_connections) == 3){
    # remove
    print('dangler')
    segment_list_pruned <- segment_list_pruned %>% filter(id!=seg$id)
  }
}

writeVector(segment_list_pruned, file.path(mapdir, "rivers_snapped_pruned.gpkg"), overwrite=T)

Basically, the algorithm divides each hex into six triangular wedges. Each wedge gets checked for intersections with a river. If there is an intersection, the face of the hex corresponding to that wedge gets appended to the output.

This creates some dangling edges that stick off at a y-intersection, like this:

To get rid of them, the code loops through each segment. It checks for a) another identical segment overlapping it, removing it if found, and b) if the segment meets the condition that one vertex only belongs to one segment and the other vertex belongs to 3, removing it if true. Note: it runs extremely slow, there's definitely a better way to do this (though I had weird issues getting some of the built-in terra geometry equivalence functions to work), but thankfully I'm not trying to automate multiple Antibors at a time, so I'm willing to just let my brute-force solution run overnight.

Here's what the output looks like:

That's where I'll stop this post for now; lots remains to be added, but at least I have regular sub-regions and major roads to work with.

The full map, as it stands currently:

Remaining Tasks

Discuss this post on Reddit

#DIY #GIS #antibor #lore24