Generating a map of hypothetical countries

[Extrementhusiast]

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

[Majestas32]

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

[Cclee]

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

[Macbi]

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.

[Apple Bottom]

Voronoi diagrams: these create a pretty good starting point, but their borders are always completely and unrealistically straight.

But, well, Wyoming...

[calcyman]

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

[77topaz]

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]

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

[praosylen]

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.