January 30, 2019

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.

January 23, 2019

Cities II: Names

Generating cities without names is so impersonal.

So I applied my Markov generator to them.

But I don't want them too similar to real-world names. So I decided to "mix" the models together.

For each race, I used the following recipes, with words taken from Swadesh lists (it's hard to find longer lists of more obscure words, but I'm continuously looking). I tried to pick interesting combinations, but I think this will need a lot more experimentation.

  • Orcish = Arabic + Somali. These might be too similar linguistically to give a good effect, but we will see. Qolim, Ishan, Hailid, Faris, Afalah
  • Elfish = Korean + Egyptian. And these might be too dissimilar. I've already noticed that one meme or another tends to dominate the name. Dohyungminseung, Miunghyun, Daehyeon, Petat, Aprieb
  • Dwarfish = Hmong + Egyptian. Khapet, Ziamakiuwel, Sualmayakam, Tirdjedjedi, Menkhteshi
  • Humanish = Welsh + Polish. Rznardir, Garybatawart, Nosty, Kwieb, Zhciach
  • Halflingish = Bokmal + Russian. Smalt, Ideryy, Flyondel, Mamme, Smannyy
Well, they're pronounceable, at least.

The models can be mixed even further, abstracting it into a second-order chain. So if a city is founded in a kingdom of 50% humans and 50% dwarfs, then I can create a combined chain from all the existing city names of those races.

January 22, 2019

Cities I: History II: Fall and Decline

The basic city growth model is \[\Delta P = B + D + I + E\], where $\Delta P$ is population change, $B$ is births, $D$ is deaths, $I$ is immigration, and $E$ is emigration.

I handle $B$ and $D$ with the logistic equation \[B - D = r P \left(1 - {P \over K}\right)\], where $K$ is the carrying capacity of the city. I want some randomness here also, so I add a bit of random walk. I also add some random walk to $r$ (the maximum rate of increase) and $K$, to account for changing conditions in the city's management, infrastructure, and what-have-you.

This leaves $I$ and $E$, which is a bit trickier. I read a lot of papers on this, which mostly deal with models for modern cities, where people often live in totally different cities. Since permanent immigration is due to many varied non-deterministic reasons, these terms often refer to the flow of workers between cities (who aren't necessarily permanent residents). These phenomena are pretty well studied, but that's not helpful to me.

So I figured that a certain percentage of people from a city would want to move someplace better. The bigger the difference in desirability ($\delta_j - \delta_i$), the more people who would try to move there, as long as the host could bear them. The number of migrants is then defined as \[M = {\delta_j - \delta_i \over 10\cdot \textrm{max}\left(\delta_j, \delta_i\right)} P_i\], where $i$ is the source and $j$ is the destination. This captures reverse flow, so I don't have to worry about which one is nicer. Since $\delta$ is already partially a function of $P$, the dense tend to get denser, to a point.

To make things more interesting, there's also a ~5% chance of a "disaster" striking (or perhaps a series of such) which decrease the population even further.

Here's a city undergoing these processes:

All of this assumes near-perfect growth, not to mention a maximum $K$ that's probably optimistic (around 100k or so, but with magic, who knows?). But more importantly, there is no war here. And that, my friends, will not do.

January 17, 2019

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):

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.

    January 11, 2019

    Desirability IV

    As discussed in previous posts, the presence of cities and infrastructure can make a location more desirable. Shown here for elves:

    without city modifier

    with city modifier
    As with many things, the rich will tend to get richer. Highly desirable locations will only become more so. Can penalties occur naturally? Something to consider.

    Currently, the cities are undifferentiated with respect to race - my end state will be to have more eclectic populations - but for placing initial cities, I may want to change that temporarily.

    The next steps are to put it all together in a coherent whole model.

    January 10, 2019

    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).

    January 4, 2019

    Infrastructure I

    In my discussion on desirability (for population centers), I realized that existing infrastructure is extremely important. Communities can exist in isolation but will inevitably spread themselves out, creating new communities and so on.

    Eventually, I'll split infrastructure out into separate races (at least for the desirability index). Infrastructure, of course, determines what sorts of services and industries could be available in a given hex, so I only need a single (non-racial) number eventually. But as far as settlement placement goes, it would make more sense that an elven village would prefer other elves rather than humans or dwarfs, given the chance. I can also define rough guidelines to racial relations - humans and elves might get along better than humans and dwarfs, and who likes the poor, stereotypically brutal orc?

    However, making this switch is pretty easy, so for now I'll work with a single value. This will make settlements more heterogeneous during these tests.

    To really get an accurate base number for infrastructure, I need a value for the total population in a region (or the whole world, as it may be). This part is tricky when starting from scratch and looking at the entire planet - I don't know how many people there are, and where they live. After all, that's the point of this system in the first place.

    The equation in question is as follows, where $I_{i,0}$ is the base infrastructure index of the $i$th city, $p_i$ is the population of the $i$th city, $p_t$ is the total population (urban and rural), and 346 is the number of square miles in a 20-hex:
    \[I_{i,0} = {p_i \over 346} {\sum_i p_i \over p_t}\]
    Essentially, I am ignoring the ${\sum_i p_i \over p_t}$ term, because I don't (yet) have access to $p_t$. Or I could make up a number. Ignoring it is the more palatable option, but adding a multiplicative factor will make the influence of a settlement "reach" farther.

    Placing a bunch of random cities and applying those rules:

    I'm excited to lay down some roads on this bad boy (and to feed it back into the desirability map).

    January 1, 2019

    Desirability III

    I am working on making the desirability index more parameterized. With this, I can create sets of parameters for each race, because humans, elves, etc will not desire the same climates, terrain, or biomes for their habitations.

    I'll probably be tweaking those recipes for a long time. I haven't looked into details on the races (5e is, of course, deeply unsatisfying). But I'm not worried about that for now.

    Most races avoid the rainforest - the soil is often poor for many types of crops. Dwarves like mountains and avoid the coast - but they're not total loners so they'll utilize rivers for travel. Stuff like that.

    This is a hard map to read - essentially I've layered five races on top of one another; humans: green, elves: red, dwarfs: blue, halflings: orange, and orcs: purple. Why those five? No idea. I wanted the three classics, plus a feature race for ice and desert climates that would be inhospitable for the others. The orcs end up with a lot of territory, but they are not as gregarious (modeled with an infrastructure penalty), so the size of their empires should theoretically be limited. The elves also have a wide distribution thanks to the large amount of rainforest (unless I penalize them for it also).

    All of this is, of course, very modular. It's easy to change the climate models and then propagate those changes to the desirability. This is a far cry from where I was earlier this year, where a map like this would require tons of manual rework.

    Creating this Step 0 desirability map is more or less straightforward (tweaking is, as always, necessary). However, existing infrastructure will also affect the terrain...but I haven't built any of that code, so that will need to be next.