## Generating a map of hypothetical countries

For discussion of other cellular automata.
Extrementhusiast
Posts: 1817
Joined: June 16th, 2009, 11:24 pm
Location: USA

### Generating a map of hypothetical countries

(This topic isn't strictly about CA.)

For a while now, I've been looking for a method to randomly generate a map of fake (but realistic-looking) countries. Since I haven't had much success yet (even after asking about it online once already), I thought I'd ask this community now.

Here are the principles that I want the final map to follow:
• Borders should be somewhat crinkly (fractal dimension around 1.1).
• Countries should be somewhat disparate in size (ratio of areas of largest and smallest countries perhaps around 1.5-3; I'm not as sure about the specifics of this one, but I can definitely tell when it looks wrong).
• Countries should be relatively contiguous and isthmus-free.
I have found a sufficient method for a single country (written as a Python script):

Code: Select all

import golly as g

# starts from initial pattern

NUMITERATIONS=int(g.getstring("How many iterations?","4"))
DENSITY=int(g.getstring("How dense is the soup (in %)?","25"))
MARGIN=int(g.getstring("How wide are the margins?","16"))
g.setrule("B5678/S45678")
g.autoupdate(True)
for i in range(NUMITERATIONS):
VIOLINIST=g.getrect()
CELLIST=g.getcells(VIOLINIST)
g.new("")
g.setstep(4)
g.select([-MARGIN,-MARGIN,2*(VIOLINIST[2]+MARGIN),2*(VIOLINIST[3]+MARGIN)])
g.randfill(DENSITY)
g.fit()
# eliminate chance islands
CHANGES=""
while True:
# run to stabilization
THISHASH=g.hash(g.getselrect())
while True:
g.step()
NEXTHASH=g.hash(g.getselrect())
if THISHASH==NEXTHASH:
break
THISHASH=NEXTHASH
# check for chance islands
if g.empty():
g.reset()
break
else:
# futility check (very rare but can happen)
if CHANGES==g.getcells(g.getselrect()):
break
CHANGES=g.getcells(g.getselrect())
g.reset()
g.putcells(CHANGES,0,0,1,0,0,1,"xor")
# xor-paste in original pattern at double scale
g.putcells(CELLIST,-2*VIOLINIST[0],-2*VIOLINIST[1],2,0,0,2,"xor")
g.putcells(CELLIST,-2*VIOLINIST[0],1-2*VIOLINIST[1],2,0,0,2,"xor")
g.putcells(CELLIST,1-2*VIOLINIST[0],-2*VIOLINIST[1],2,0,0,2,"xor")
g.putcells(CELLIST,1-2*VIOLINIST[0],1-2*VIOLINIST[1],2,0,0,2,"xor")
# run to stabilization
THISHASH=g.hash(g.getselrect())
while True:
g.step()
NEXTHASH=g.hash(g.getselrect())
if THISHASH==NEXTHASH:
break
THISHASH=NEXTHASH
g.select([])
(This script requires a small starting shape; running 16×16 soups in this rule should generate (at least) one within a few soups.)

However, I haven't been as successful with multiple countries fitting together. Here are some types of rules that I've tried:
• Multi-state rules where each individual cellstate follows B5678/S45678: size of countries becomes way too disparate with few states; simulation gets way too slow with many states.
• Rules where seeds form and grow but resist merging (e.g. B15-knqr6a78/S4-nwz5-kr678): this creates a rather large size disparity between regions.
• Rules where cells naturally settle into a skeleton-like structure (e.g. R20,C0,M1,S167..646,B604..877,NM): while the countries-to-be are placed rather well, their borders are too smooth, and there's even a slight chance of border failure.
• Rules based on crystallographic defects (e.g. B2ce3cn4acknwy5aekry6akn7e/S1e2aei3ciny4jknqry5-cjny6k7c, possibly interesting in its own right): while the result is four-colorable (colors correspond to parities of x- and y-coordinates), it's not very realistic, due to two adjacent regions of the same color effectively being considered as one.
• Multi-state rules where each individual cellstate follows the same explosive rule: this has problems similar to the ones in the other multi-state rule, except that the problem with too many cellstates is that the seeds won't grow.
Here are some other possibilities that are less strictly about CA:
• Voronoi diagrams: these create a pretty good starting point, but their borders are always completely and unrealistically straight.
• Mudcracks: modeling these is only easy via the real thing (which takes a while), and suffers from the straight-borders problem.
• DFS maze-generation algorithm from multiple starting points: this frequently generates one-cell-thick isthmuses.
• Prim's algorithm from multiple starting points: many countries generated this way seem to be long and skinny.
• Kruskal's algorithm from multiple starting points: borders seem to be a bit too crinkly.
This seems like it should be doable at least fairly easily, yet it isn't, apparently.
I Like My Heisenburps! (and others)

Majestas32
Posts: 524
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

### Re: Generating a map of hypothetical countries

B...but why *don't* you want to have large size disparity...

Cclee
Posts: 56
Joined: October 5th, 2017, 9:51 pm
Location: de internet

### Re: Generating a map of hypothetical countries

Majestas32 wrote:B...but why *don't* you want to have large size disparity...
clearly the real world dosent have any
like russia and the vatican are nearly the same size wouldnt you sgree
^
What ever up there likely useless

Macbi
Posts: 713
Joined: March 29th, 2009, 4:58 am

### Re: Generating a map of hypothetical countries

Voronoi diagrams: these create a pretty good starting point, but their borders are always completely and unrealistically straight.
Country borders are sometimes straight; when they meet at a place that isn't a river or mountain range. Perhaps you could try Voronoi cells inside a geography with different terrains.
Last edited by Macbi on March 3rd, 2018, 4:01 pm, edited 1 time in total.

Apple Bottom
Posts: 1027
Joined: July 27th, 2015, 2:06 pm
Contact:

### Re: Generating a map of hypothetical countries

Extrementhusiast wrote:Voronoi diagrams: these create a pretty good starting point, but their borders are always completely and unrealistically straight.
But, well, Wyoming...
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

calcyman
Posts: 2126
Joined: June 1st, 2009, 4:32 pm

### Re: Generating a map of hypothetical countries

Try this process: https://mathoverflow.net/q/76623/39521

It's a good model theoretically (you can think of the occupied squares as containing 'explorers', each of whom is equally likely at any moment to colonise an adjacent uncolonised square) and empirically (it approximates Voronoi diagrams, but with stochastic edges).
What do you do with ill crystallographers? Take them to the mono-clinic!

77topaz
Posts: 1467
Joined: January 12th, 2018, 9:19 pm

### Re: Generating a map of hypothetical countries

Apple Bottom wrote:
Extrementhusiast wrote:Voronoi diagrams: these create a pretty good starting point, but their borders are always completely and unrealistically straight.
But, well, Wyoming...
But you don't see many countries with borders like that, do you? There's a big difference between country borders and US state borders, as the US state borders are all decided by one central government while country borders are decided by separate governments and have a longer historical background.

Extrementhusiast
Posts: 1817
Joined: June 16th, 2009, 11:24 pm
Location: USA

### Re: Generating a map of hypothetical countries

Found a fairly good rule table:

Code: Select all

n_states:4
neighborhood:Moore
symmetries:rotate4reflect

var a={0,1,2,3}
var b={a}
var c={a}
var d={a}
var e={a}
var f={a}
var g={a}
var h={a}
var i={0,2,3}
var j={i}
var k={i}
var m={i}
var n={i}
var p={i}
var q={i}
var r={0,1}
var s={r}
var t={r}

0,1,i,j,k,m,n,p,q,1
0,i,1,j,k,m,n,p,q,1
1,3,a,r,b,s,c,t,d,2
1,1,1,1,1,1,1,1,1,2
1,1,i,j,k,m,n,p,q,1
1,i,1,j,k,m,n,p,q,1
1,a,b,c,d,e,f,g,h,0
2,2,a,b,c,d,e,f,g,0
2,a,b,c,d,e,f,g,h,3
It works a lot like DLA, except that it uses B1/S1 as the driving agent, with new countries forming via S8.

Speaking of which, is there any (possibly non-totalistic) explosive two-state rule with a lower (but non-zero) proportion of any one transition being present than B1/S1 has with S8? (For reference, I ended up with an average of 23 instances in a 1024×1024 torus, after letting it sufficiently settle into its "natural" state.)
I Like My Heisenburps! (and others)

A for awesome
Posts: 1949
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1
Contact:

### Re: Generating a map of hypothetical countries

Extrementhusiast wrote:Speaking of which, is there any (possibly non-totalistic) explosive two-state rule with a lower (but non-zero) proportion of any one transition being present than B1/S1 has with S8? (For reference, I ended up with an average of 23 instances in a 1024×1024 torus, after letting it sufficiently settle into its "natural" state.)
What about something like B25c/S4e5e? S8's only predecessor is this 5x5 pattern:

Code: Select all

x = 5, y = 5, rule = B25c/S4e5e
bobob$obobo$b3ob$obobo$bobob!
I haven't been able to come up with a way for that pattern to arise out of natural-looking junk, but it can form via agar decay. I'm sure further fine-tuning could produce a rule in which there is only one (or at least very few) 7x7 predecessors for S8, although I'm not sure how much longer that could be extended.
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce