- Populating a game world;
- Modelling the change from rural to urban;
- Modelling rural to urban, take two.
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 |
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
No comments:
Post a Comment