Ex Nihilo II: Routing

I worked the number of total polities down to the low 2000s. This is probably still pretty high, but it takes a while to simulate warfare between so many cities, so I'll call it here.

The next thing is to place roads, according to Higher Path rules. I briefly tried a modification, where the number and type of roads was determined by the total infrastructure, and not the infrastructure category. For example, rather than primary, secondary, and tertiary routes, a hex with an infrastructure of 61 could have 1 low road (35), 1 cobbled road (20), 1 cart track (6), and finish out the 6 total connections with trails (0). This all adds up to $35\cdot1 + 20\cdot1 + 6\cdot1 + 3\cdot0 = 61$ total. However, I didn't much like this as the resultant network was weird-looking, with all routes being pulled towards the local center.

It's got kind of an artsy feel to it, but massive infrastructures would be necessary to make any kind of even network. So I went back to the old way but will continue to think about it.

It's a busy-looking map, but remember that this is primarily DM-facing (more accurately, computer facing). All we need to know for now is that there is a road from A to B of type C. From hence we can apply A* route-finding algorithms to find optimum travel paths between hexes. I'm using the AP weights from here, assuming a normal walking pace. The function will return both the route taken and the cost in AP, so that travel times can be determined for the trade network.

Note that these don't take into account the convenience of river travel if available. A comprehensive model will present the players with a plan involving the cheapest method: a boat from A to B, then overland from B to C, then finally upriver to D. For this, I'll probably rely heavily on the fascinating work by ORBIS. In the same manner, I need to re-address sea travel, so those are next on the list.

Detail V | Roads VIII

Roads are easier than rivers because they do not shape the terrain they "flow" through as rivers do. I thought they would be more complicated but they turned out to be quite simple.

The river ingress and egress hexes are found by doing a transform on the character values of the strings of the names of the hexes. This gives a nice stochastic but repeatable location. For the roads, I simply reverse the inputs. Badabingbadaboom.

The roads (which are defined at the 20-hex level) enter the hex and make their way to the 1-hex with the highest infrastructure, which is located on the river and is assumed to be the settlement center. Where there are no roads, there are trails. Trails may or may not be well maintained, and they are not suitable for significant trade. But they allow transportation of goods and supplies to and from remote outposts such as mines which may not have access to a main trade road. Again, these trails all seek the assumed central hex.

Trails are also defined at the 20-hex level to connect settlements with low infrastructures. Generally speaking, a road will only occur through a 20-hex with $I\geq 50$. An exception is made if the road is being laid (and maintained) from capital to capital. Therefore, trails are used instead to connect lower $I$ settlements as well as provide access to hinterlands.

Darker hexes are less civilized, road in red

As a note on the trade system: only 20-hexes with a road can have a market. If your settlement has no market, you'll have to travel to find one. All goods produced in a 20-hex without a market must find their way down a trail to somewhere they can be sold. Therefore, for the purposes of the system, these goods are credited as being produced in the market settlement, even though their physical location might be different. My trade system engine assigns them to the market which is closest in the network.

This raises interesting gameplay situations. Most people in these remote locations would either make their own tools or carefully guard something they took a specific trip to buy. Very rarely would a merchant make their way down these dangerous and unfriendly trails to sell their wares. Plan accordingly.

Trade IV: Fixing the Seaways

I had a Big Problem with the way the seaways were generated, so I haven't included them in the trade network yet. But this is a shame. So I will fix it.

Mostly, it's good. But occasionally, weird stuff like this happens (the route marked in red). The error happens during the "refueling stops" portion of the code. First, a seaway is found between two cities of appropriate size and infrastructure. These are the anchor points. However, these routes are quite long - I limit it to search within 50 hexes, or around a month at sea. That's not impossible, but for a regular trade route is pretty tough. You want the ability to stop at a friendly port and resupply. So the code will then search along that route for nearby cities. They must have more than 1000 people, but can be much too small to originate a route of their own. So the code will split up the original, long route into manageable chunks.

However, I was getting this weird error where the splitting was rejoining everything back together incorrectly. That should be fixed now, and I can add these into the main trade network. As it is, everything is pretty isolated without access to other continents.

I would also like to determine a "piracy index" based on the frequency of ships passing through a given hex. This is gameable information: stuff that's not just pure numbers for my own enjoyment. Players can make decisions (to pirate, defend, or take the long way) based on this gameable information.

Roads VII: Row, Boys, Row

What I did with the roads, I now do with the seaways (I'm calling them seaways because its a convenient one-word descriptor).

I toyed a long time with the idea of reducing the number of these trade routes between harbors. If there are two routes between two harbors, over time, one will emerge as the dominant one. For my purposes, I can just say that the "shortest" route will be the best. Therefore, why generate all possible routes?

Eventually, though, I decided to take the extra time to generate everything. Well, not everything. Only harbors with a certain infrastructure (50, for now) are eligible, and I only look at harbors within a 50-hex distance. Longer journeys are certainly possible, but not all at once. Certainly not for trade, which will find the quickest and easiest route to transport goods (as mentioned before).

As a result, there are only a few places where you can travel between continents. However, it is theoretically possible to travel to every single continent.

There are also a couple of issues where some of the seaways are drawn as straight lines (a few can be seen in the figure above). Ideally, the lines follow the currents. It's kind of neat to show a straight line diagram, but if I want that, I'll make that. I think this error happens because of the route-splitter.

Let me back up. I'm generating routes between harbors of sufficient size, A to B. But let's say that this route passes just off-shore of a town too small to have its own harbor. Well, it's reasonable to assume that this would be an ideal place (politics aside) to resupply your merchant vessel. So the algorithm will find places such as this (C) and split A>B into A>C and C>B. All three are now connected rather than just the two. This allows a more robust network and lets smaller cities benefit from the commercial activity of larger ones. However, I have a bug in the code that when no C is found, it looks like the algorithm abandons the original path entirely. Should be trivial to fix (the programmers famous last words).

And if a party is interested in a much longer journey, it is trivial to generate it.

At this point, I'm starting to be interesting in taking all this data and condensing it into a trade network. I've already written a bit about this here, but so far all my testing has been done with manual inputs. Now, I can simply run an algorithm over my map data and generate nodes, edges, and weights from the cities, roads, seaways, and river routes. Things are finally coming up Milhouse.

Roads VI: Better Roads and Gardens

Generating a road takes a long time, because there are a lot of things to consider when picking targets, etc.

So it is better to generate them post-hoc, rather than in situ. Still takes a while, but I can blow through a lot more history and get some people on the map to debug.

I really like these results. The basic method here that I select the largest city in a region of continuous infrastructure. Then, a road is placed to every other city in that region if the target city is in the same size class. This generates a main road network artery. For every other city in the region of a certain infrastructure (so not every single village), a road is place to the next nearest road. In this way, all cities of the requisite infrastructure are joined together in a network that makes sense.

I particularly like that not every settlement has a road to it. These are the hinterlands. But if I add resource placement to the history generator, I might need to force high-resource areas to have roads. No sense in having a gold mine if you can't get to or from it easily.

Next, I'll determine the seaways in a similar fashion.

Roads V: Hard to Port

Testing roads is already pretty difficult, since I want to let the population build up organically before placing them. Seaway routes are even more so, because they require a little more infrastructure to generate. They look good, except there are too many and they're not quite long enough.

As pretty as these look, I'd like to add a little intelligence to them. For example, these are really long journeys. Let's say that A, B, and C cities lie along a coast.

Furthermore suppose that an established route already exists between B and C.

Now, if A jumps into the sea-trade game, and wants a route to C, would it be preferable to go straight there, without resupply?

Instead, it's preferable to harbor at B, assuming that B is a friendly city.

So when selecting targets, the code should be able to check if there's already an existing route from B to C (and maybe there are more stops in between?) and reroute through an existing channel. I already kind of do this with the roads, but they're also constrained to a limited number of connections (since roads are physical objects which require maintenance, a trade route is an abstract concept).

This also assumes that a route A>B>C is always preferable to A>C. This might not always be the case. If B fell into enemy hands, then obviously it would no longer satisfy the criteria for a safe harbor. However, I can take this one step at a time and see how things shake out before adding additional constraints and shifting conditions.

Roads IV: Take to the Sea!

Sea routes are essential for trade between people. I suppose you could have robust trade networks if you were confined to land, but it's a lot easier (not without risk) to put a bunch of stuff on a ship, rather than haul it across a dangerous terrain.

So naturally I needed to update my sea current algorithms and make sure everything is peachy there.

Once that's done, I can use my A* algorithms to place "roads" in the sea. Going with the current is easier, but the more you turn against the current, the more difficult it is. This means that a double-edged graph is in hysteresis: the return journey must take a different route.

It takes a while. The roads are by definition close by - sea routes theoretically make shorter work of a much longer journey. In addition, there are too many function calls in the algorithm right now, so I'll have to work on that.

Unlike roads, there is no maximum number of routes that may pass in a certain hex or a minimum score for a hex to support a route. You just sail through it. A higher number of routes might mean a higher risk of piracy, though.

I'd also like to add in a maximum distance that the route can be based on the development or infrastructure level of the originating harbor. A small fishing village will not be launching transoceanic trade routes.

It might also be good to penalize routes that are too far from a coast. It's harder to resupply when you strike out more than a day or two from a large landmass. But not impossible. So I'll work on that. It might make the route take longer but if you can avoid really long, empty routes, that would be desirable.

Even the shortest route here spends about 40 days out of sight of land

Regardless, this will be an interesting addition to the trade network.

History III: Rise of Civilizations

To this point, I've been placing cities more or less randomly. Sure, the presence of a large metropolis will increase the chances a bit, but the new cities are still spawning from nothing, essentially.

With the new changes, cities that are large enough (population at least 2500, for now) have a small chance to spin off a new city into a neighboring hex, if one is available. This should make things a little more procedurally driven. However, this can lead to a steady-state-esque system where all cities are around 2500 in population; every time they got bigger, the excess drained off into a new city somewhere.

Another big change is the way I'm processing the cities and placing new ones. Initially, I'd place all cities, then check all the new ones for birth/death rate, then check road availability, etc, etc. Now, I look at each city in turn and run through each of those functions in a random order. This allows a bit finer control over what's going on down at the local level, and I think it helps with the road generation as well, since I'm adding roads to cities as they become large enough, not waiting until the end of the year to place them.

The slowest parts of the algorithm are the remaining random city placement - I have to have some new civilization seeds - and the desirability/infrastructure algorithms. I mean, it's Python, so everything is pretty slow anyway, but those algorithms have to perform a calculation for each of the 108k hexes, sometimes many times. So there is definite room for improvement. My programming style is usually to hack something together that works inefficiently, and then target those inefficiencies later.

Generally speaking, it takes about 150-200 years for infrastructure to advance to the point of supporting actual maintained roads (keep in mind that the roads I'm generating are not the only way of traveling between settlements, just the only way of moving appreciable quantities of trade goods). A party could still travel along a trail, etc. The roads are looking much better.

Year 1030, halfling kingdom

Humans (green) spread out very quickly along the coasts. To adjust this, I can add some "gravity" to the expansion function to pull things closer together. These empires (if empires they be) would not be very manageable with early tech. Halflings (orange) dominate many areas, since so much of the map is near the southern pole.

Year 1030, human kingdom

Year 1030, halfling and dwarfen kingdoms

In every sim I've run so far, the dwarfs (blue) have about 3 or 4 kingdoms right here in the middle of the continent. This represents the only Dfc climate on the map, which my dwarfs like. So here they all are.

Elves (red) are pretty rare. I gave them a reduced modifier for growth rate (my elves aren't a bazillion years old, but they do live about 150-175 years), and that really tends to hurt.

Year 1030, human, elf, and halfling kingdoms

But what's this?

Year 1030, dwarfen kingdom...mostly

A pretty large elfish city, right smack dab in the middle of the biggest dwarfen empire in the world? How?

This is where the raw numbers can give rise to interesting story. The simulation says that a dwarfen city fell into ruins, through emigration or disease, and not long after, a group of elves moved into and took over, building their own metropolis! No doubt to the chagrin of the dwarfs. Fascinating.

race	urban pop.
dwarf	184646
human	444824
halfling	429106
elf	113819
orc	61150

The total population (cities included) after 1030 years of simulation is 20,517,454. Not bad. Maybe a little much, but I do have five races. Elves grow very slowly, as intended. The dwarfs also lag, but since they are geographically clustered, it's not as obvious. But it might be rare to see a dwarf outside of those areas. Orcs are present on the map, but they rarely form permanent settlement, so their urban population is very low relative to the rest.

The next thing I need to do is figure out how these loosely connected settlements will coalesce into kingdoms and empires. I'd also like to include long-range colonization, not just expansion into an adjacent empty hex on land.

Roads III: Across the Wilds

The building of roads must be more dynamic.

Yes, a certain infrastructure must be in place for a road to start. But it is misguided (as I have tried previously) to require that same level of infrastructure for each intermediate hex. Roads will frequently be built across areas of wilderness. How do I capture this?

The road, after all, merely connects two locations. It is not itself a location. So while we might require an infrastructure index of, say, 50 to begin and end a road, it might pass through many areas where the infrastructure index was much lower, like 5 or 10.

A bridge (generalized river crossing) also should not be a static threshold, but should vary based on the size of the river (measured by drainage $d$). \[I_d = 100 \ln(d)\] Bigger rivers require a large infrastructure to be built to maintain their bridges.

Maintained roads are not the only option for travel. Cart trails or other paths can be available as well. So perhaps the "road system" should be primarily for heavy trade, and not necessarily for point to point movement of a player party.

I could also check if two locations can already be connected before placing a new road between them. This would reduce the total number of roads which need to be placed. However, just having a single connection is not enough. We can easily imagine a scenario in which a road between two distant cities is placed among the most optimal route at the time, but 100 years later, a more favorable route (perhaps through a large intermediate city) is possible. We can't expect our people to shrug because there's already a road there! So perhaps this can be tweaked.

That still doesn't improve things a lot. But - maybe they don't need to be "improved." A country with a road system like this could be a military or industrial power.

Limiting the number of roads by population of a city?

This might work. But I still need to tweak it to generate longer networks.

Infrastructure II: History I

Time to begin placing cities.

There are a few considerations to make when growing populations/cities organically.

• Initial populations of villages are set to $P_0 = 150$. The growth equation at time $t$ then becomes \[P(t) = {K \over {1 + {K - P_0 \over P_0} e^{-r t}}}\] In the future, I'll actually progressively modify the population number, but for now I just evaluate this equation using the age of the city.
• The carrying capacity $K$ is a function of the desirability $D$ of the location. \[K_0 = 5000 \exp\left(10 \left({D \over \textrm{max}(D)} - {1 \over 2}\right)\right)\]
• $K$ is then modified according to Central Place Theory (CPT). One of the tenets of CPT is that cities are spaced according to the product of their populations and inversely to the distance between them. My method for doing this is as follows: the city in question is assigned a level $\ell = \log_{10} K_0 - 1$. $K_0$ is then reduced by a factor of 10 if $2 ^ i > \delta_c$ for all $i < \ell$, where $\delta_c$ is the distance to the closest city of the same $\ell$. So a city of 9500 people cannot be closer than 4 hexes to another similarly sized city. If it is, then $K_0$ is reduced by a factor of 10. This will hopefully ensure an exponential distribution of city sizes, and prevent a concentration of very large settlements.
• $r$ will be a random number with a max of $2\% \cdot D \over \textrm{max}(D)$. This sets the maximum growth rate at 2%, but allows for a lot of variation in between. Maybe the different races should have different growth rates?
• Any given hex which meets all other requirements has only a 5% chance of generating a city. I'll give this a little boost for particularly desirable places.
• I won't force them to obey Zipf's Law, but I'm wondering how the distribution will shake out. Zipf's Law has been demonstrated to hold most true for "small cities" over 100,000 - for a fantasy low-tech world, that might be a "huge city" instead!
• Another thing I need is a mechanism to destroy or stagnate a town - many things can affect a city's growth or longevity. Not every city built in 1000 BC still exists. In fact, most don't. Plague, famine, war, resource depletion, etc can all wipe out even large settlements.
• A dynamic $K$ value might be cool also. That way a settlement might have a bright future, but overcrowding could really hurt long-term. As groups compete for resources, which larger cities need more of, smaller settlements tend to be crowded out. I need to capture that, and that might help my goal of CPT-arranged cities.

Some observations:

• Since dwarfs (blue cities) are not "constrained" to the coast, their cities are placed much faster. This isn't necessarily a problem, but I want to consider how heavily the coast is weighted vs the inland. As a result, non-dwarfen cities are isolated, and have more difficulty coalescing into an entity.

• The desirability map takes a dozen seconds or so to populate. This adds up and makes the year-by-year simulation very slow.
• Similarly, it's expensive to figure out where roads should be placed so that they make sense. I've added some timeout functions to the road placement algorithm to make sure that A* doesn't get stuck somewhere it can't get out, but the constraints need some work. As shown in these images, it's made slower by the fact that eventually, every city gets a full 6 roads coming in and out.

• Some of the orc cities (purple) behave well with roads, but there are no special road considerations for different races.

• River crossings are a problem. They would be easier to implement if I used edges instead of tiles, but that would be a big pain to implement with the drainage code.

After 550 years of simulation, the total city populations are as follows (not including rural population, which is expected to be about 5x urban):

elf	13,552,065
dwarf	5,570,650
halfling	11,144,894
orc	28,884,984
human	14,688,643

Orc growth is much faster because their cities form at great distances from the other, allowing for rapid growth and large carrying capacities from CPT. The opposite is true of the dwarfs: they have many cities, but densely packed, which reduces the maximum carrying capacity.

I could do more analysis of the cities, but I'd like to tackle the road problem first, since it feeds back into the city placement algorithm, and is the current bottleneck for any kind of long-term simulation.

Roads II

With the rough infrastructure map in hand, I wanted to be able to place roads between them. Then both systems could be fed back into the desirability model.

But as usual, there were some kinks to work out. There are a few constraints on the roads, such as climbing distance (too steep? penalty), altitude (particularly above 8000 ft, where the air is thin for those not acclimated), and of course overall length. Additionally, a hex must have a certain infrastructure threshold to even be considered for a road, and it's even higher for a bridge to cross a river.

I don't mind the jaggedness of the line - the hexes are huge, after all. It's the overlapping roads I want to avoid. So I fixed it to seek only the closest city for a road. This is similar to a minimum spanning tree, but not exactly. I want a non-optimal layout - the spread of populations shouldn't always make sense.

These maps also show how the infrastructure (red) is affected by local topography, which constrains it from spreading too far.

Now, I can feed both of these systems into desirability and start building more organic layouts (the cities I used here are just randomly selected).

Roads I: Original Pathfinder

No, not that pathfinder. To be honest, I've never played it.

I'm talking about a real pathfinder.

Where do the roads go? How can I get from Point A to Point B most effectively?

I won't try to give an indepth explanation of how the algorithm I've chosen (A*) works, since others can do that much better. I'll just explain how I implemented it.

def a_star(start, end):
  def g(current):
        z = zip(closed_list, closed_list[1:] + [current])
        return sum(travel(i, j) for i, j in z)
    def h(current):
        return(distance(hexes[current].c, hexes[end].c) / 86.6)
    def f(current):
        return g(current) + h(current)
    open_list = list(hexes[start].neighbors)
    closed_list = [start]
    came_from = {sorted(open_list, key = lambda h: f(h))[0]: start}
    while open_list:
        s = sorted(open_list, key = lambda h: f(h))[0]
        open_list.remove(s)
        closed_list.append(s)
        if s == end:
            break
        for t in hexes[s].neighbors:
            if t not in closed_list:
                if t not in open_list or g(t) < h(t):
                    open_list.append(t)
                came_from.update({t: s})
    path = [end]
    while path[-1:][0] != start:
        path.append(came_from[path[-1:][0]])
    return path[::-1]

Basically, we find the path that minimizes the cost of travel. I've made some custom adjustments to the travel heuristic here. The only modifications so far are for height - I need to work on more specific terrain later. For now, moving up or down 400 feet costs an extra day of travel. If you're moving into or through an area that's above 8000 feet, it costs an extra day for each 1000 more feet you ascend (due to oxygen requirements - 8000 feet is the general baseline I've found, but I'm not a climber, and I'd like some better data to use here).

Here, it is quite obvious that even those constraints are enough to create an interesting pathway. Rather than take the "shortest" path (a straight line), our caravan is compelled to ascend into the foothills, and follow the crests of the mountain chain, until at last a suitable pass is found.

This took about two hours to implement - much better than I was expecting. I think the next steps are to figure out the effects of terrain, and to save the cumulative road score (how many paths are found through this hex), which can affect the desirability index. High traffic roads are good places to start up a village and leech off the resulting trade.

One thing I don't know how to do yet is sea travel. This is an important one, but there are a few problems.

1. I don't save sea hexes as terrain; I leave them blank to save file size
2. Sea travel is highly dependent on winds and currents, which I have, but not in a format that is good for cellular automata

There are ways around these problems, but I have to pick them out of my brain first. Right now they're floating around nebulously and I can't see them very clearly.