ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Generating a map of hypothetical countries

For discussion of other cellular automata.

Generating a map of hypothetical countries

Postby Extrementhusiast » March 2nd, 2018, 8:31 pm

(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):
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)
User avatar
Extrementhusiast
 
Posts: 1785
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Generating a map of hypothetical countries

Postby Majestas32 » March 3rd, 2018, 12:07 am

B...but why *don't* you want to have large size disparity...
Please, stop spam searching Snowflakes.
User avatar
Majestas32
 
Posts: 524
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Generating a map of hypothetical countries

Postby Cclee » March 3rd, 2018, 3:05 pm

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
User avatar
Cclee
 
Posts: 56
Joined: October 5th, 2017, 9:51 pm
Location: de internet

Re: Generating a map of hypothetical countries

Postby Macbi » March 3rd, 2018, 3:08 pm

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.
User avatar
Macbi
 
Posts: 685
Joined: March 29th, 2009, 4:58 am

Re: Generating a map of hypothetical countries

Postby Apple Bottom » March 3rd, 2018, 3:26 pm

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!
User avatar
Apple Bottom
 
Posts: 1025
Joined: July 27th, 2015, 2:06 pm

Re: Generating a map of hypothetical countries

Postby calcyman » March 3rd, 2018, 3:46 pm

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!
User avatar
calcyman
 
Posts: 2072
Joined: June 1st, 2009, 4:32 pm

Re: Generating a map of hypothetical countries

Postby 77topaz » March 3rd, 2018, 5:03 pm

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.
User avatar
77topaz
 
Posts: 1345
Joined: January 12th, 2018, 9:19 pm

Re: Generating a map of hypothetical countries

Postby Extrementhusiast » March 6th, 2018, 3:16 pm

Found a fairly good rule table:
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)
User avatar
Extrementhusiast
 
Posts: 1785
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Generating a map of hypothetical countries

Postby A for awesome » March 6th, 2018, 6:19 pm

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:
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
User avatar
A for awesome
 
Posts: 1861
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1


Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 3 guests