June 4, 2018

Stars and Bars

I have been thinking way too far ahead about dividing my large hexes into much smaller ones. Normally, these would be 6 miles or so - perhaps 2 mph if the mood strikes. But I have the potential to examine 1 mph...that is no simple task. Each 20 mile hex becomes 400 subhexes. How do I determine what's here? The real danger is that once that is done, I'm still not satisfied...but I should really stick to things I can accomplish right away.

Alexis has laid some excellent groundwork tying the effects of civilization to wilderness plotting. There are three posts here I'm standing on here: Groups, Features & Groups, and World Plotting. These posts deal with the generation of random subgroups of the 7 subhexes possible in a 20 mile hex. In particular, he presents a table with the odds of generating different combinations (I won't copy it here - if you want it, go there instead). A comment caught my eye, where someone considered whether this would be extendable (as I am now attempting) into larger numbers of subhexes, and hence greater detail.

I can now answer that question, a mere seven years later. This type of problem is dealt with by the combinatorics branch of mathematics, and specifically is called the Stars and Bars. The question asks, given $n$ objects, how many ways can I choose $k$ multisets? A multiset here refers to the fact that you can choose a sequence of objects that is distinct but looks the same - in Alexis's system, this is why there are only 2 distinct Type II hexes despite 7 total choices. The language here is very similar to the binomial coefficient $n\choose k$, and they are mathematically related:

\[\left(\!\!{n\choose k}\!\!\right) = {n + k - 1 \choose k} = {(n + k - 1)! \over {k! (n - 1)!}}\]

So: if we have $n = 7$ total hexes, and $k = 1$ is wilderness, then:

\[\left(\!\!{7\choose 1}\!\!\right) = 7\textrm{ total options}\]

Now that we have an abstracted model, let's return to the original equation. Fortunately, you can skip all the fancy math and just use Excel's COMBIN function. Boring (understanding the fundamentals helps with design). Here is where we encounter problems. In the 7 subhex example, the number of categories and the total number (128) of combinations are both manageable numbers. The cumulative sum is a nice, gentle slope.


Not so with 400 subhexes. There are only (let me grab my calculator) 2,582,249,878,086,908,589,655,919,172,003,011,874,329,705,792,829,223,512,830,659,356,540,647,622,016,841,194,629,645,353,280,137,831,435,903,171,972,747,493,376 total combinations. That curve is much steeper:

Hmm.

On the bright side, that pretty much guarantees that each hex will be unique (my ultimate goal), since the odds of the same layout occurring twice in 108,000 hexes (a laughably small number now) is astronomically small.

So what now?

The x-axis is tied to the infrastructure number. 7 is less than a typical infrastructure number. In the original post, the bell curve is scaled to 100. For 400 hexes, we have to compress it (assuming 100 is the max). For now, the easiest thing to do is just divide 400 by 100 and say that each point of infrastructure is worth between 1 and 4 extra hexes of not-wilderness.

These thoughts are still a bit incoherent, so I apologize. I'm trying to wrap my brain around the rule-defined system. Nobody tell Jeremy Crawford that someone is trying to use rules in D&D.

No comments:

Post a Comment