Tuesday 26 August 2014

Modelling settlement with a cellular automaton

I've written about modelling settlement patterns before; several times, actually:


I had hoped to have the algorithm for Populating a Game World written by now, but I've been ill most of this summer and it hasn't happened. Instead, I've revived a rule-driven cellular automaton which I first wrote back in the 1980s; I've reimplemented it in Clojure, and used it to experiment with settlement. The results have been mixed.

What works

Irish Sea basin after 84 generations
Firstly, it's remarkable how simple it is to model a landscape on a coarse granularity with very few rules. Establishing a basic biosphere with birch/oak succession woodland on lower ground, growing to climax forest in more favoured areas, and fading to birch scrub and then to heath in uplands, takes just sixteen rules.  Adding human settlement, up to the point of establishing permanent markets and urban centres, takes just thirty more. And when you run this on a map of Britain, unsurprisingly urban centres end up in just the sort of place you'd expect to see them - for example, in the map shown, there's an urban centre near Lancaster and another at Derry, with settlement around Belfact Lough, Dublin, and in Wigtownshire - all places where we know, historically, there were important early towns.

Lancaster was an urban settlement from Roman times. Rerigonium, in west Wigtownshire, was one of the only British towns important enough to make it onto Ptolemey's pre-Roman map. Derry was the site of a monastery in the 6th century, and probably an urban centre earlier. There's a settlement on Ptolemy's map called Eblana which may possibly be Dublin, but is at least close to it. Belfast has the oldest claim - it has a five thousand year old henge (although there's also a neolithic monument complex at Dunragit, one of the possible sites of Rerigonium).

So this very simple model of settlement patterns works quite well - at a coarse scale.

What doesn't work

While the results are reasonably good, the cellular automaton isn't fast. The scale shown in the picture uses cells about five miles (eight kilometres) square. At this scale, generating a map of Britain and Ireland on my (very powerful) desktop PC takes about a minute per generation, although optimisation is certainly possible. Settlement patterns don't really start to emerge until after one hundred generations, and I'd really like to run for at least two hundred and fifty to get the patterns stable. But five-mile granularity is nothing like good enough to model settlement. I think what I need is hectare granularity. It's obvious that (optimisation aside), for a given ruleset the time to compute a map scales with the area of the map.

I have a map of Great Britain and Ireland at about one kilometer granularity, but I haven't yet even tried to run the ruleset on it yet. It's sixty-four times the area of the map I'm currently using, and one would anticipate it would take about one hour per generation to compute. But, as I've said, even kilometer granularity doesn't seem enough, and a hectare granularity map would take six thousand four hundred times as long to compute (assuming the memory requirement could be handled, which I believe it could), so about four days per generation or about one hundred generations per year of continuous computation.

Now, that isn't in itself impossible. If one sees this as a one-off pre-computation of the settlement pattern of a game-world, it's a not unreasonable investment. But this mechanism doesn't really support ongoing evolution of settlement patterns while the game is in progress.

Also, the rules I have so far are unsophisticated. I don't have a rule which represents the strategic value of a port, or the strategic value of a river crossing. And to produce rules which would model the development of a hierarchical system of territorial aristocracy - a feudal system - would require much more computationally expensive rules than I have now.

Finally, this map is a grid, and as a grid it inevitably will have visual artefacts in the world. That can be mitigated by the rendering algorithm, but it's bound to show. So I don't think this is an avenue which in its pure form I'll pursue much further; but it is a promising start. A hybrid system based partly on a cellular automaton, partly based on actors (as in Populating a game world) is probably the line I shall follow next.

Addendum: the rules

I hope to be able to publish the full source code for the cellular automaton shortly, but it depends on authorisation from my employers - at present all code I produce, even in my spare time, is their copyright. In the meantime, however, here's a high-level statement of the rules used to model settlement.

# Human settlement

;; This rule set attempts to model human settlement in a landscape. It models
;; western European pre-history moderately well. Settlement first occurs as
;; nomadic camps on coastal promentaries (cells with four or more neighbours
;; that are water). This represents 'kitchen-midden' mesolithic settlement.
;;
;; As grassland becomes available near camps, pastoralists appear, and will
;; follow their herds inland. When pastoralists have available fertile land,
;; they will till the soil and plant crops, and in doing so will establish
;; permanent settlements; this is approximately a neolithic stage.
;;
;; Where soil is fertile, settlements will cluster, and markets will appear.
;; where there is sufficient settlement, the markets become permanent, and you
;; have the appearance of towns. This takes us roughly into the bronze age.
;;
;; This is quite a complex ruleset, and runs quite slowly. However, it does
;; model some significant things. Soil gains in fertility under woodland; deep
;; loams and podzols build up over substantial time. Agriculture depletes
;; fertility. So if forest has become well established before human settlement
;; begins, a higher population (more crops) will eventually be sustainable,
;; whereas if human population starts early the deep fertile soils will not
;; establish and you will have more pastoralism, supporting fewer permanent
;; settlements.

;; hack to speed up processing on the 'great britain and ireland' map
if state is water then state should be water

;; nomads make their first significant camp near water because of fish and
;; shellfish (kitchen-midden people)
if state is in grassland or heath and more than 3 neighbours are water and generation is more than 20 then state should be camp

;; sooner or later nomads learn to keep flocks
if state is in grassland or heath and some neighbours are camp then 1 chance in 2 state should be pasture

;; and more herds support more people
if state is in grassland or heath and more than 2 neighbours are pasture then 1 chance in 3 state should be camp
if state is pasture and more than 3 neighbours are pasture and fewer than 1 neighbours are camp and fewer than 1 neighbours within 2 are house then state should be camp

;; the idea of agriculture spreads
if state is in grassland or heath and some neighbours within 2 are house then state should be pasture

;; nomads don't move on while the have crops growing. That would be silly!
if state is camp and some neighbours are ploughland then state should be camp

;; Impoverished pasture can't be grazed permanently
if state is pasture and fertility is less than 2 then 1 chance in 3 state should be heath

;; nomads move on
if state is camp then 1 chance in 5 state should be waste

;; pasture that's too far from a house or camp will be abandoned
if state is pasture and fewer than 1 neighbours within 3 are house and fewer than 1 neighbours within 2 are camp then state should be heath

;; markets spring up near settlements
if state is in grassland or pasture and more than 1 neighbours are house then 1 chance in 10 state should be market

;; good fertile pasture close to settlement will be ploughed for crops
if state is pasture and fertility is more than 10 and altitude is less than 100 and some neighbours are camp or some neighbours are house then state should be ploughland

if state is ploughland then state should be crop

;; after the crop is harvested, the land is allowed to lie fallow. But cropping
;; depletes fertility.
if state is crop then state should be grassland and fertility should be fertility - 1

;; if there's reliable food available, nomads build permanent settlements
if state is in camp or abandoned and some neighbours are crop then state should be house
if state is abandoned and some neighbours are pasture then state should be house
;; people camp near to markets
if state is in waste or grassland and some neighbours are market then state should be camp

;; a market in a settlement survives
if state is market and some neighbours are inn then state should be market
if state is market then state should be grassland

;; a house near a market in a settlement will become an inn
if state is house and some neighbours are market and more than 1 neighbours are house then 1 chance in 5 state should be inn
;; but it will need some local custom to survive
if state is inn and fewer than 3 neighbours are house then state should be house

;; if there aren't enough resources houses should be abandoned
;; resources from fishing
if state is house and more than 2 neighbours are water then state should be house
;; from farming
if state is house and some neighbours are pasture then state should be house
if state is house and some neighbours are ploughland then state should be house
if state is house and some neighbours are crop then state should be house
;; from the market
if state is house and some neighbours are market then state should be house
if state is house then 1 chance in 2 state should be abandoned
if state is abandoned then 1 chance in 5 state should be waste 


## Vegetation rules
;; rules which populate the world with plants

;; Occasionally, passing birds plant tree seeds into grassland

if state is grassland then 1 chance in 10 state should be heath

;; heath below the treeline grows gradually into forest

if state is heath and altitude is less than 120 then state should be scrub
if state is scrub then 1 chance in 5 state should be forest

;; Forest on fertile land grows to climax

if state is forest and fertility is more than 5 and altitude is less than 70 then state should be climax  
   
;; Climax forest occasionally catches fire (e.g. lightning strikes)

if state is climax then 1 chance in 500 state should be fire

;; Forest neighbouring fires is likely to catch fire. So are buildings.
if state is in forest or climax or camp or house or inn and some neighbours are fire then 1 chance in 3 state should be fire

;; Climax forest near to settlement may be cleared for timber
if state is in climax and more than 3 neighbours within 2 are house then state should be scrub

;; After fire we get waste

if state is fire then state should be waste

;; waste near settlement that is fertile becomes ploughland
if state is waste and fertility is more than 10 and some neighbours are house or some neighbours are camp then state should be ploughland

;; And after waste we get pioneer species; if there's a woodland seed
;; source, it's going to be heath, otherwise grassland.

if state is waste and some neighbours are scrub then state should be heath
if state is waste and some neighbours are forest then state should be heath
if state is waste and some neighbours are climax then state should be heath
if state is waste then state should be grassland


## Potential blockers

;; Forest increases soil fertility.
if state is in forest or climax then fertility should be fertility + 1

## Initialisation rules

;; Rules which deal with state 'new' will waste less time if they're near the
;; end of the file

;; below the waterline we have water.

if state is new and altitude is less than 10 then state should be water

;; above the snowline we have snow.
if state is new and altitude is more than 200 then state should be snow

;; otherwise, we have grassland.
if state is new then state should be grassland

Wednesday 20 August 2014

The West Lothian Question, take two

Tam Dalyell. Photograph: The Hootsmon
Back in 1977 that famous old-Etonian, Sir Thomas Dalyell Loch, 11th Baronet of the Binns, famously asked a question which has troubled his party ever since.

The question, in his own words, was this:
For how long will English constituencies and English Honourable members tolerate ... at least 119 Honourable Members from Scotland, Wales and Northern Ireland exercising an important, and probably often decisive, effect on English politics while they themselves have no say in the same matters in Scotland, Wales and Northern Ireland?
Those 'honourable' members - better known here in Scotland as the 'feeble fifty' - have indeed had a decisive effect on English politics. It was with their votes that Tony Blair imposed tuition fees on English university students, foundation hospitals on the English NHS. I believe that it is true that Labour did not have a majority of English MPs on either of those votes - which affected only England.

This is, as Tam pointed out, an untenable anomaly: frankly, a corrupt practice. And the answer to his question seems to be 'not much longer'.

So, what's the corollary to the West Lothian Question?

Well, suppose the present government were to enact - as it's entirely reasonable that they should - that Scottish MPs may no longer vote on English matters. And suppose - I know it's unlikely - that Scotland votes 'no' in a month's time. And suppose - just suppose - Ed Miliband wins the next Westminster election, but without a majority of English seats.

Who then is the English Secretary of State for Health? For Education? For the Environment? for Transport? for Rural Affairs?

Fully half of the current UK cabinet have portfolios which cover only England. If Miliband wins a majority in the UK but not in England, he will find himself on the horns of a dilemma.

Either he appoints Labour members to head the English departments, in which case they will none of them have a majority in the chamber to pass any legislation; or else he appoints Tories to his cabinet, in which case fully half of his cabinet are from the opposition. In either scenario, England is quite ungovernable.

If Scotland bottles this referendum, the Labour party have not won. They've lost - and lost badly.


A footnote: how did Tam vote on tuition fees and on foundation hospitals? The answer is, I don't know. But it would be interesting to find out!

Sunday 17 August 2014

Syria and Galloway

Tombstone of Barathes of Palmyra in Syria, found at Corstopitum
In these days when we're all listening on the news to the developments in Syria and Iraq, the emergence of the Islamic State, the conflict between Sunni and Shia, the plight of fleeing Yazidis and of the Syrian Christians, I was struck by this powerful essay by Robin Yassin-Kassab, exploring the historic links between Syria and Galloway.

Yes, of course there were Syrians (and also Nubians - people from what is now Libya and Morocco) on the wall. I've mentioned them before on this blog. And we know that at the end of their service, they were not sent home: instead, they were given grants of land locally to where they were stationed at the end of their service. So there were certainly Syrians and Nubians settled on what is now Northumberland and Cumbria, and their descendants are almost certainly still there.

Closer to home, the Romans established a harbour in Orchardton Bay, and a road - most of which is still used today - from there, through what is now Gelston and Threave, to their fort at Glenlochar. The fort at Glenlochar was not garrisoned for very long - from  81 AD, but probably for only about twenty years - and as far as I know we don't know which legions garrisoned it. So I don't know whether there were Syrian archers at Glenlochar, but it's by no means impossible.

Furthermore, if the flag-maker and merchant Barathes mentioned in Robin's essay was trading from Corstopitum, he was probably trading across the wall; in which case it's quite likely that he visited the Kelton Hill Fair, which was an important trading fair from the Bronze Age until the enclosures of the eighteenth century. So Barathes very likely knew the landscapes we're familiar with - with Screel, with Bengairn, with the road up past Taliesin.

But the very name 'Cumbria' - land of the Comry, the people, in modern terms the Welsh - reflects what happened after the legions were recalled in AD 383. The Brythonic kingdom of Rheged, whose caput was at Dunragit in Wigtownshire (shown on Ptolemy's map as Rerigonium), expanded south to include lands at least as far south as Penrith. So at that point, the settled legionaries became citizens of the same state that contained what is now Castle Douglas.

Rheged was heavily defeated at the Battle of Catraeth (what is now Catterick, in Yorkshire. where the Syrian Goddesses you mention were found) in about AD 600 - at more or less the same time as Muhammad started to pray in his cave on Mount Hira - and Northumbrian Angles spread into what is now Galloway, establishing their own villages of Kelton and Gelston close to the long-established Brythonic village of Threave. Through that turbulent period, isn't it likely that some of the descendents of people from south of wall moved north of it, either with the retreating people of Rheged or with the advancing Northumbrians?

Populations have been mixing - and people have been trading - since the first mesolithic settlers arrived here. Galloway was on the trading route which was already well established when Pytheas of Massalia - what is now Marseilles in France, but then a Greek colony - followed it around 325 BCE. The quest for a single, authentic ethnicity for the people either of Galloway or of Scotland has always been a false one. There are Gallovidians of Scots ancestry; yes. But it's also worth remembering that there are Gallovidians of Brythonic, and, let's remember it, also almost certainly Iberian and Syrian and Libyan ancestry, who were here before the Scots; and Anglians who were here at the same time. Ethnicity does not define who we are. What we do, and how we relate to the world, defines who we are.

Creative Commons Licence
The fool on the hill by Simon Brooke is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License