A new city boundary system

[Phystam]

I thought about a new city boundary system. I would like to propose here the generation of city boundaries using a discrete Voronoi diagram.
The Voronoi diagram is a region that represents which of plural points is closest, and it is used in various applications in the real world. A discrete Voronoi diagram, where the area is represented by pixels, fits into the in-game coordinate system. By applying this, if the city area can be determined, it becomes easier to think of a realistic city renovation algorithm than the current rectangular city area. It will also fit well with the recently introduced "regions" feature.

This feature is still a prototype, but I expect it to look like this:

[jamespetts]

This is interesting, but this appears to assume that all land will be occupied by cities, whereas, in reality, much land lies outside the boundary of any city. We also want to have a system that is compatible with the planned feature whereby small towns get absorbed by larger cities and become metropolitan boroughs.

Is there a way of adapting this planned system to allow for there to be land outside any city and to allow for the future city absorption system?

[Ranran(retired)]

If it is allowed that the divided area do not belong to a city, may it help create natural region boundaries?
Sometimes there are boundaries on the parallels for military reasons, but it still seem strange to regional divisions. (About regional division of another thread)

Also it is natural that one island is represented as a region. The picture above looks like a step in what makes it possible. 

[jamespetts]

If it is allowed that the divided area do not belong to a city, may it help create natural region boundaries?
Sometimes there are boundaries on the parallels for military reasons, but it still seem strange to regional divisions. (About regional division of another thread)

Also it is natural that one island is represented as a region. The picture above looks like a step in what makes it possible. 

That is an interesting idea, but as I understand it, the boundaries are set on the basis of the mid-point between areas defined as having a city at the centre of them, so I am not entirely sure how this would work for regions.

[Mariculous]

Imho city boundaries, as currently, are rather a bounding box than actual city borders.
The issue with current city growth is that cities do always attempt to build up each single tile within the boundings and will never build outside of it. That leads to strictly rectangular cities. rivers or coasts that cannot be crosses are the only exception where cities will not be strictly rectangular.

Your suggested city borders do look nice indeed and in terms of regions that might be a good idea, although I'd expect such regions to follow mountains or valleys. Looking at the united states, that might be an European expectation, however.

[Ranran(retired)]

Generally, open land is preferred for towns and villages. It is often at a low altitude and on the water side.
If city halls and houses can be easily built in such places, I think that a more natural city will be created in combination with this division.

That leads to strictly rectangular cities.

Yes, it looks weird like an ancient Chinese city. I think that many old European cities are circular.

[jamespetts]

Generally, open land is preferred for towns and villages. It is often at a low altitude and on the water side.
If city halls and houses can be easily built in such places, I think that a more natural city will be created in combination with this division.

I am not entirely sure how I follow how this would fit in with the idea of regions, which will each contain a great many different towns.,

Yes, it looks weird like an ancient Chinese city. I think that many old European cities are circular.

Unless forced into a particular shape by geography or defensive requirements, towns will tend to grow on the basis of local transport, additional growth being the shortest transport time away from the centre of all available land. This will give rise to circular cities when the main form of transport is walking, but cities of varying shapes once steam trains become prevalent for local transport, and cities of much wider, less dense circles once private cars become prevalent. It is this patterning that the planned city growth system intends to replicate.

[Ranran(retired)]

We also want to have a system that is compatible with the planned feature whereby small towns get absorbed by larger cities and become metropolitan boroughs.

I don't know how it determines the boundaries, but what is needed is to determine the boundaries after placing the city. And ceding and joining will be necessary. If the preferred land is a wilderness, new towns may be born there.
If many cities were built in the preferred habitable areas, they could be one in the future. It is a reproduction of reality.

If it decide the area first and it is fixed, it won't match. (´・ω・｀)

This will give rise to circular cities when the main form of transport is walking, but cities of varying shapes once steam trains become prevalent for local transport, and cities of much wider, less dense circles once private cars become prevalent. It is this patterning that the planned city growth system intends to replicate.

I'll look forward to it.

the boundaries are set on the basis of the mid-point between areas defined as having a city at the centre of them, so I am not entirely sure how this would work for regions.

Even if the boundary is not a straight line, it may be able to judge the belonging by the center of which region the cityhall is close to. But setting an entire island with several cities as a region can be difficult.

[Phystam]

In the real world, there are several village generation types, like cluster, scattered, and linear. In the early years, as James mentioned, mainly cluster villages are generally established in Europe. However, in the east Asia area, the scattered settlements are also established since they need large rice fields around their houses. And "hotel town" along the main road connecting large cities are established like a linear settlement. Nowadays Shinjuku and Shinagawa are the famous biggest capital cities in Tokyo, but the origin is such a small hotel town.
And I would like to mention about the city area. As I imagine, the European villages have the city boundaries that divide the inside and the outside of the city. It is clearly seen in the yellow board sign which shows the city name when we go inside the city. On the other hand, in the sense of Japan, even if they are outside the village, they belong to one of the cities, so the entire area on the ground is filled with the city area. With this method, it may be possible to introduce a system in which a new village naturally occurs.

This is a difference between the eastern and western senses, and you don't have to choose one or the other. In some cases, it may be necessary to use the recently introduced regions feature to separate systems.

At the very least, it's clear that there is a need to implement free-form city boundaries.
The current specification requires two values, the upper-left coordinate, and the lower-right coordinate, to determine the city limits. On the other hand, planquadrat_t already contains data on which city the grid belongs to. Probably to make it easier to access, but in reality, the former is not necessary and the latter is sufficient. Also, I would like to implement the "city merger" function that is planned to be implemented flexibly by having a hierarchical structure such as states, provinces, counties, cities, and towns.

[Qayyum]

I thought Phystam's system is fine, unless Jamespetts mentioned about land outside any city boundary, which should be called Common land-.-

[Mariculous]

We got quite huge disperse settlements in Europe too.
Ruhr area, Germanys largest urban area area and 5th largest urban area in Europe is of that kind
As a result, Ruhr area does not have a single megacity in the center, but instead multiple cities that grew on a rather large space. When I first saw an actual city exit sign, that simply stated the end of the city, I was quite confused that areas not part of a town do even exist. In Ruhr area you can drive 50km from Dortmund to Duisburg without ever being outside of a town, if you continue to Cologne from there on, you can drive anotheer 80km without ever being outside of any town.

Anyways, back to topic.
I am not quite sure how that could properly be simulated and if it's worth to implement such differences?

[jamespetts]

Thank you all for your thoughts. There are a number of quite complex issues that have been raised, and it is useful to give careful consideration to each of the issues. I will deal with some of the separate issues under different heads.


Region boundaries

There is a possible and relatively straightforward way of making this proposed feature work with region boundaries: if it is possible to use the idea of a Voronoi diagram to draw a median line between sets of points rather than individual points, then the Voronoi diagram algorithm could be used to determine region boundaries by the following process:

(1) generate square regions as at present;
(2) generate towns at random points as at present; and
(3) use a Voronoi diagram algorithm to determine which tile is in any given region by taking the set of all cities in each region as the point between which distance is measured.

This relies on a Voroni diagram being able to determine median lines between multiple sets of points rather than among a number of individual points, and I do not know whether a Voroni diagram can do this. If it can, however, it might lead to more realistic region boundaries.

Care must be taken, however, to ensure that the algorithm for this is not too resource intensive. It is unlikely to be feasible to store the region in a tile as this is likely to take excessive memory (albeit this can be tested). Likewise, any algorithm to determine to what region that any given tile belongs and that is called frequently in a large and well developed game needs to be very efficient to avoid adding excessive computational load. This will need to be tested in a profiler when developing such a feature.


Ceding and joining

Ranran writes of "ceding and joining"; I had not envisaged a process of ceding, as it is difficult to imagine what mechanism in the game might lead to this, and this is not something that tends to happen in reality so far as I am aware. Can I ask what mechanism that you had in mind for this, Ranran?


New towns arising

There is currently no mechanism for the generation of new towns automatically, but players may (at great cost) found new towns. The current system of founding new towns allows the act of founding a town to increase the global population, which does not make much sense.

I am not sure what mechanisms would be ideal for town founding in future and whether there is any need to have a system whereby towns be automatically generated during the game, but certainly any system, whether automatic or manual, for generating towns, must respect the planned realistic mechanism for calibrating population growth over time.


Town shapes/generation mechanics

The actual mechanism for growing towns needs to be changed significantly from the present in order better to reflect reality. The fundamentals of what makes it optimum for people to build a building in one place rather than another are likely to be universal rather than specific to any one place or time, but the operative factors that bear on those fundamentals may differ. We need to have a system that simulates those fundamentals in order to make the system work.

There has been extensive discussion of the current and proposed city growth algorithms here. I do recommend that these be read and that any further discussion of actual city growth mechanics be added there so that the discussion can be kept together.


The concept of boundaries and boundaries at different levels

I am not sure that I fully understand Phystam's description of how Japanese city borders work. We do want a system to be as universal as possible, as I know that Simutrans is popular in Japan, so it would be best to avoid a system that is specifically European; but I need to understand how the Japanese system works in order to understand what is universal and what is regionally specific.

Is it the case that there is no concept at all of a boundary of a city at all in Japan such that there is no sense in which open countryside that is nearer one city than any other city is considered not part of the city in question; or is it the case that there is an area that is understood to be the city proper, and a surrounding area, which may or may not be urban in character, that is considered to be part of a larger metropolitan administrative area of which the city is the centre?


The practicalities and implementation of city boundaries

We do need to consider what we want city boundaries to do in Simutrans-Extended. They currently have a number of specific functions:

(1) they limit where a city may attempt to grow - this will at least partly be to reduce computational overhead of trying to iterate over all map tiles (is this the function that the Voronoi diagram was intended to serve?);
(2) they determine land value, as land value inside a city will be higher than that outside a city (although the long-term plan is to replace this with a more sophisticated system that will not rely on city boundaries);
(3) they determine whether any industry needs to have an independent connexion to the electricity grid provided by the player, or whether it is sufficient that the player has provided electricity to the city generally as is the case when any industry is located inside the city;
(4) they are the primary nodes in the private car routing network; private cars inside city boundaries route using a heuristic system, whereas private cars cannot leave cities unless they are on a defined route to a destination outside the city;
(5) they determine whether player built roads are adopted by the city authorities (and given a lower speed limit); and
(6) they determine whether player built road stops must be able to be shared with other players irrespective of the choice of the player owning the stop.

Thus, we may well need multiple different types of city boundaries to serve different functions. Functions 2, (probably) 3, 4, 5 and 6 need to be served by a system that determines where in practical terms that boundaries of the built-up area really lie. Function 1, however, may be better served by a different system that draws a wider boundary. Perhaps one might call this a "district"?

However, until we have a more sophisticated system for deciding where buildings should actually be built, the problem is that a wider boundary may cause city buildings to grow randomly a long way from the centre of town for no good reason and where there is plenty of space for buildings to be constructed in a more desirable location closer to the centre of town. I do strongly recommend reading the earlier technical discussions of the city growth system in order for such discussions as we may have about the boundaries, which is one aspect of city growth, to be fully integrated into the planned revision of city growth at a more fundamental level.


City mergers and hierarchies

The hierarchical system suggested of states, provinces, counties, cities and towns is interesting, but I am not clear what each of those levels would entail in a practical sense, nor how those would fit into the concept of regions.

The concept of regions as we have now seems to be the approximate equivalent of states and/or provinces. I am not sure that we need to distinguish in gameplay terms between the two. We currently have no implementation of anything like counties, and the current system has no distinction between towns and cities. In the UK, the difference between towns and cities is very peculiar, as a city is defined as any town that has either a cathedral or a Royal charter. In most places in the world, the difference between a town and city is simply size; one would not generally have a town inside a city, so I do not think that the terms "cities" and "towns" are apt to describe a hierarchical system. I generally use the terms "town" and "city" interchangeably when discussing Simutrans, as, in the UK sense, the word "town" is generally more apposite, but "city" is the word traditionally used in the UI and is also used in the code.

The city merger system that I had proposed was one in which a large city would take over smaller cities/towns when the boundaries of the two touched; the smaller town would become a borough of the larger town, and the larger town would become a metropolitan area. The original part of the town would retain its original name, but the wider area would become "Greater [X]", where [X] is the name of the original larger town/city.

This system has the technical advantage of not needing to destroy the memory structure of the smaller town (which simply becomes a borough and retains its separate identity, town hall, statistics, etc.; it would remain a "city" in game code terms, and just have a data member which indicated that it had the status as a borough), which avoids having to track down pointers to non-existent city objects scattered across large and unknown parts of the code. It also preserves continuity (so new stops placed inside the old town boundaries are named after the old town), is more realistic (as this is what happens in reality) and makes the game more interesting (as players can see the results of the gradual historical growth of towns). A Voronoi diagram algorithm might be an effective way of drawing the boundaries between boroughs in such a system.

Some thought would need to be given to how to deal with town statistics in such a case. However, all 6 of the functions listed above would probably have to be based on the larger metropolitan area's boundaries.

So, if we are to have a hierarchy, we might have something like this:

(1) regions;
(2) (possibly) districts (although I am not entirely sure how these would work in game mechanics terms - this would need to be considered);
(3) towns/cities; and
(4) boroughs.

We will need in due course to give consideration as to how best to integrate these features with the planned town growth features.

[Mariculous]

This relies on a Voroni diagram being able to determine median lines between multiple sets of points rather than among a number of individual points, and I do not know whether a Voroni diagram can do this. If it can, however, it might lead to more realistic region boundaries.

That's actually the same as determining borders between individual points and then removing borders between points of the same point set again, so I gues it's not a Voroni anymore but should be a rather simple adaption.

It is unlikely to be feasible to store the region in a tile as this is likely to take excessive memory

If we restrict the number of regions to 256, it's actually an additional 8 bit per tile, which is 64mb on an 8192x8192 map. Doesn't sound too excessive, although not too few either.
These could be stored much more memory efficient as polygons i.e. a list of corner koords, plus a bounding box to speeed up "is within" checks.

I am not sure what mechanisms would be ideal for town founding in future and whether there is any need to have a system

I'd argue it's a nice-to-have admin tool, e.g. when creating real-world map from heightmaps. I do usually generat real-world terrain from heightmaps and then use a mix of generated towns to fill the map and manually placed capitals of the real-world.
I do not think players should ever be allowed to do this, as a transport company founding cities does not make much sense to me.

(6) they determine whether player built road stops must be able to be shared with other players irrespective of the choice of the player owning the stop.

Do they? From my understanding so far any road stop on unowned road can be used by everyone, no matter if in city boundaries or not.

The city merger system that I had proposed was one in which a large city would take over smaller cities/towns when the boundaries of the two touched;

And finally, James merged 70% of the population of Northrhine westphalia into a single 10 million megacity, starting at the 1 million city of Cologne merging Leverkusten, Bonn and some smaller towns of the surrounding districts, creating a new 2 million city that's now unstoppable merging towards me. I don't want to get merged with one of our heavily in debt neighbors :(

[Vladki]

Just a note how town borders and hierarchies work in CZ:

- every piece of land belongs to some town. So it is somewhat similar to Phystam's original suggestion, although the borders are set historically, and are quite far from ideal voronoi diagram.
- the area of town is administratively divided to built-up area, and countryside. Building a house in the countryside requires extra official approval (fertile land is protected) or a new town plan that expands the built-up (or buildable) area. So this border between built-up area and countryside is similar to current town borders in simutrans. And it makes more sense to me this way, just if the growth algorithm would not create rectangles.

- funding new villages - I don't know about any truly new village or town being funded in last 200 years. I think it was mainly medieval thing that people came to some lonely place and funded a new village. Or that a king founded a new town. Now - given the population density, there is no "unowned" piece of land suitable for that. Any new settlement would be in area of some existing town. Maybe a split is possible, but mergers are more common.
- there are also villages that disappeared long ago (or ghost towns in USA). Perhaps towns without jobs could gradually lose population (people moving to other towns).
- merging towns does not necessarily make them a "hierarchical" city. We have examples of nearby towns or villages, that were merged and now have only one town hall.
- hierarchical cities - what would be the difference in simutrans? Apart from station names, it does not really matter now if people travel over the town border or not.
- do not merge cities automatically when they touch. It should be a admin tool, similar to funding new city.

[jamespetts]

That's actually the same as determining borders between individual points and then removing borders between points of the same point set again, so I gues it's not a Voroni anymore but should be a rather simple adaption.

This is an interesting point - I had not thought of that - so this should be possible without too much additional work from the basic algorithm for anyone interested in implementing this.

If we restrict the number of regions to 256, it's actually an additional 8 bit per tile, which is 64mb on an 8192x8192 map. Doesn't sound too excessive, although not too few either.
These could be stored much more memory efficient as polygons i.e. a list of corner koords, plus a bounding box to speeed up "is within" checks.

My concern is more memory bandwidth than gross memory usage, as memory bandwidth is the real limitation for Simutrans-Extended on larger maps. Polygon systems are likely to work much better: a very simple version of this (i.e. rectangles with the data stored as two opposite corners) is used in the current regions system.

I'd argue it's a nice-to-have admin tool, e.g. when creating real-world map from heightmaps. I do usually generat real-world terrain from heightmaps and then use a mix of generated towns to fill the map and manually placed capitals of the real-world.
I do not think players should ever be allowed to do this, as a transport company founding cities does not make much sense to me.

That players can do this is a legacy from Standard. Players should certainly be able to build settlements to be served by their transport routes so that we can simulate Metro-Land and also what I understand is the common Japanese practice of railway companies owning and renting out land near railways (which becomes more valuable as they build the railways and the land becomes more useful). However, this is likely to require more of a system of building individual city buildings and being able to act as a landlord to buildings; there is already an interface for buying city buildings and for building them, although the latter is restricted to the public player and the former may be little known judging by the number of reserving markers placed in town centres on the Bridgewater-Brunel server. What is ultimately needed to add to this is the economic layer of rent income, maintenance and occupancy simulation, as well as better simulation of the capital costs.

We then have to decide what the relationship should be between players building these buildings outside established town boundaries. Should players have to found a new town; or will Phystam's idea of a village inside what I have called a district suffice? How will this system interact with the automatic town growth algorithm? What tiles should be considered for town growth? Should there be villages outside towns that have no townhall or separate statistics? How should they be generated - should building new buildings be done on a global basis, using a weighted random system based on local desirability all over the map? Should we perhaps allow automatic generation of buildings, but not town roads, to take place outside towns, to allow villages to develop by these means along existing roads but not to create their own network of roads (i.e. have a global town growth system but not allow the building of city roads outside the boundaries of a town/city, as opposed to the possibly wider boundaries of a district if we have such a thing as districts)?

Do they? From my understanding so far any road stop on unowned road can be used by everyone, no matter if in city boundaries or not.

I have checked the code for this, and you appear to be correct, although, because towns will always adopt roads built by a player, the behaviour is functionally equivalent to this.

And finally, James merged 70% of the population of Northrhine westphalia into a single 10 million megacity, starting at the 1 million city of Cologne merging Leverkusten, Bonn and some smaller towns of the surrounding districts, creating a new 2 million city that's now unstoppable merging towards me. I don't want to get merged with one of our heavily in debt neighbors :(

The idea of town merger is based on the way in which small towns and villages are usually merged into neighbouring larger towns, such as the way that places such as Highgate, Stratford, Hammersmith and Dulwich were once villages but are now part of Greater London. Is your concern that multiple very large towns will merge with one another where this is not what happens in reality? Might this be abated by the expedient of not allowing merger where both of the towns to be merged are in the top X% of towns by population?

- the area of town is administratively divided to built-up area, and countryside. Building a house in the countryside requires extra official approval (fertile land is protected) or a new town plan that expands the built-up (or buildable) area. So this border between built-up area and countryside is similar to current town borders in simutrans. And it makes more sense to me this way, just if the growth algorithm would not create rectangles.

These sorts of regulations are very new in terms of our Simutrans-Extended timeline, generally 20th century, and mostly in the latter part of the 20th century. Before this, there were no such restrictions, and towns grew on the basis of demand. Simulating these regulations, which vary nationally and with time, is likely to be very difficult, and it is better to default to the pre-regulated position than produce a poor proxy of complex modern regulatory structures.

- there are also villages that disappeared long ago (or ghost towns in USA). Perhaps towns without jobs could gradually lose population (people moving to other towns).

The town growth thread (linked above) does discuss the importance of having a system in which it is possible for buildings to be under-occupied or abandoned; and this is especially important if players are to be able to make a rental income from them as is planned.

merging towns does not necessarily make them a "hierarchical" city. We have examples of nearby towns or villages, that were merged and now have only one town hall.
- hierarchical cities - what would be the difference in simutrans? Apart from station names, it does not really matter now if people travel over the town border or not.

For technical reasons, as discussed above, it is much, much easier to code a hierarchical system. This is how at least most town mergers work in practice, so it seems sensible to do it this way.

- do not merge cities automatically when they touch. It should be a admin tool, similar to funding new city.

As a server admin., I should prefer not to have this responsibility for hundreds of towns. We may want to set a threshold of overlap rather than merge as soon as one town marginally touches another, but I do not see any reason not to automate this. If there be some real objection to the possibility of town mergers in some games, it might be better for this to be able to be disabled in simuconf.tab.

[Mariculous]

I don't know about any truly new village or town being funded in last 200 years.

https://de.wikipedia.org/wiki/Liste_deutscher_Stadtgr%C3%BCndungen/21._Jahrhundert

Seems to be a quite long list in only the last 20 years
These did not come out of nowhere for sure. It had been villages before, now these are towns.

Is your concern that multiple very large towns will merge with one another where this is not what happens in reality? Might this be abated by the expedient of not allowing merger where both of the towns to be merged are in the top X% of towns by population?

My concern is rather Larger cities merging their surroundings and casciding to megacities that will merge in everything they touch.
That percentage depends on how large that percentage is, but might work. Imagining Rhine-Ruhr area in simutrans, 20% will already cause huge parts of the are to merge and it's only a matter of who starts first to determine which city will be the "main" city in the end. All of the larger cities in that area could potentially merge in their surroundings to become an unstoppable megacity. When that 9 million megacity finally reaches cologne, it will just merge these 1 million inhabitants into a district.

i.e. have a global town growth system but not allow the building of city roads outside the boundaries of a town/city

As mentioned elsewhere, I do not think actual global citygrowth is a good idea.
Citygrowth is a rather local thing, although that does not mean that growth should always be restricted to the same city which "caused" the growth, nor should it be impossible for a settler to decide moving from one end of the world to the other side. It should just be very unlikely.
Most people will simply not move to the other side of the world just because they have a better transport service or something like this.
Even better jobs (whatever that means in simutrans) will not cause all people to move to the other side of the world.

Thus people should always prefer to settle to a specific, semi-randomised and rather local location, searching for a good housing candidate around that prefered location.
What exactly that "rather local" means, which factors might affect the decision where to settle and how the actual settlement location will be selected should not be discussed here.
One very short thought is just that the availability of jobs for the class of our settler should be an important factor in his decision where to settle.

[Ranran(retired)]

Ranran writes of "ceding and joining"; I had not envisaged a process of ceding, as it is difficult to imagine what mechanism in the game might lead to this, and this is not something that tends to happen in reality so far as I am aware. Can I ask what mechanism that you had in mind for this, Ranran?

It means that a new town will not be born if it cannot ceding.
My "ceding" means, in a sense, the birth of another city center. As a result of them they divide.

In reality, that kind of thing happened a lot.
For example, there are towns that were born from coal mines, towns that were created as transportation hubs, settlements for food, and reclamation.

Originally it was not suitable for people to live in, but in some cases it was newly pioneered.
The large island on the north side of Japan is called Hokkaido and is a land like Russia of Japan.
That poor large island wes pioneered in the late 1800s, and railways have contributed significantly. The discovery of the coal mine accelerated the development. Several towns were created for coal mines. (But in the end it was almost ruined.)
American goldrush and railroad might be similar examples.

There are many blank areas when you look at server games, but there are many cases where non-city areas are important points of transportation.
For example, a port on the edge of the island. In the real world, a city may be born in such a place. Because there will be demand for hotels, dining out, port management, and business. The people involved in it will live there.

However, intentionally easily creating a city may adversely affect the game balance.
In the real world, the people who live there migrate from another location, which reduces the population at the source. Therefore, it is balanced as a whole.
simutrans does not simulate decline, so it may only benefit.
The coal mine town which example above, eventually died, but many of them went to the city.

Even if there is no such fact in Britain, there are many in the world, and I don't think the system should make it impossible.
Currently we can found a city, but without the ceding, that function will be lost.

Naturally, the new towns mentioned above will be created in the original towns. It means that there is a new center. I think it will be a ceding.
I don't know if it is right for a big city to swallow around. In the case of Japan, what was once a "village" was merged little by little into a big city.
As a result, the city can grow, but it does not necessarily have a single center. Currently there is only one city center in simutrans, but if the new city can have multiple centers in new city growth system, I don't think it matters.

[jamespetts]

I see what you mean now - that is an interesting thought. This does again raise very complex issues that require very detailed consideration to ensure proper balance.

First of all, as discussed here, the plan is very much that (1) decline in population of towns and buildings should be possible; and (2) that population growth should be calibrated on a global basis. This should prevent the construction of new buildings/towns from actually increasing overall population and therefore overall levels of transport related economic activity, ensuring that balance be maintained. (We may want to allow a variable in the advanced settings dialogue to be altered if players in single player games want to edit this population figure).

Freahk writes of the locality of population growth, although the reality is more complex than this, as, where jobs are scarce, people did, even in centuries past, travel long distances to find work; this is what enabled the industrial revolution, as large numbers of people moved from the countryside to the towns to seek better employment in the new industries. Purely local growth would not permit population to be calibrated globally and would thus prevent sensible game balancing. A mix of local and global growth might in theory be workable, but an algorithm for this is likely to be highly complex and I cannot at present think of any sensible and workable algorithm for this (especially as such an algorithm would specifically need to be able to simulate some towns declining in population and others growing as a result when economic conditions that would in reality cause this, e.g. a loss of local jobs (and "local" here means by reference to travel time, not distance), occur in game).

Secondly, what this envisages, from what I understand, is similar to what Phystam suggests, which is permitting what is now called city growth (and what one might better term settlement growth) to occur beyond the edges of cities, unconstrained by any city boundary at all. These new settlements would at first be villages, without any town hall and without an independent statistics; if we adopt a district system as discussed above, they might be considered to be in the district of their nearest town on the basis of a Vonoroi diagram, although the exact implications of this would need careful consideration. It might then be that when such settlements reach critical mass that a new administrative unit of a town be formed around them, although devising a workable algorithm for this is likely to be fiendishly difficult, not least because what counts as a single settlement where the data would simply comprise the whole world's map grid, some of whose tiles are occupied by buildings, is very hard to define in a meaningful way.

There are also other quite significant problems to overcome in dealing with what are now classed as "city buildings" outside towns. First of all, electrification: it would be absurd for each individual cottage outside a town to have to have its own substation, yet, currently, buildings can only be electrified by either (1) being inside a town; or (2) having a substation immediately adjacent to them. Some alternative, algorithmically workable, coherent and reality based means of electrifying small settlements would have to be found; perhaps a catchment area for substations outside city (as opposed to district) boundaries. The coding for this could well be complex, and care would have to be taken not to place excessive strain on memory consumption and memory bandwidth, especially considering that electricity grid identifiers are pointers, so storing a vector of electricity grid identifiers in each tile (as would be necessary to allow multiple substations to be within each other's coverage) would require all the overhead of a vector of 64-bit pointers for each individual grid tile (unless someone can devise a more efficient way of doing this). Whole new code for calculating the demand and load balancing of electricity for city buildings outside towns would have to be written, as well as new code for identifying when individual city buildings outside towns are connected to electricity, as this needs to be able to be used as an important factor for demand/occupancy when electricity becomes prevalent.

There is also the issue of private car routing. Currently, private car routing works using whole cities as nodes. Everything inside the city (apart from industries and attractions) is treated as a single node and no routing calculations take place between points within a city, cars instead being routed heuristically. Cars only use calculated paths outside cities. This could not work for settlements that are not part of towns/cities. The only other possibilities would be: (1) not allowing these buildings to use private car transport at all (but this is unacceptable as it creates intractable and serious anomalies); (2) routing to each of these buildings individually (which is likely to be unworkable owing to the extreme level of computational overhead; or (3) creating a new village abstraction for these settlements to treat them as individual nodes in the same way as towns, but then we run into the same problem discussed two paragraphs above of defining these; and that also means that it is necessary to have these abstractions created for every single "city building" on the map, at which point one might as well just have individual towns in any event.

One could in theory treat the whole district (as I use the term, being the area defined by a town's Vonoroi diagram as introduced by Phystam) as a node rather than just the town, for the purposes of private car routing, but this is not workable, since the current system relies on cars being not able to leave the boundaries of the city unless they are on an existing private car route. If districts were treated as the nodes and cars could travel anywhere in the district, then there would be nowhere on the map where cars not on an actual route could go, and heuristically routed cars would end up using long distance road routes and inexplicably turning back half way between towns as soon as they crossed district boundaries. If districts were used as nodes but cars were not allowed to leave the more narrowly defined town boundaries, then heuristic private car routing would not work for buildings inside the district but outside the town, which would create intractable anomalies for the local use of roads outside towns by private cars.

I do not think that it is likely to be possible to permit city building growth outside town/city, as opposed to wider district, boundaries unless these problems be fully resolved in a way that is:

(1) coherent;
(2) realistic in simulation of reality; and
(3) not so computationally intensive as noticeably to reduce the size or intensity of map on which any given level of hardware can run the game at an acceptable level of performance without sacrificing features currently in the game.

These are formidable challenges; whilst I cannot be certain that they cannot be overcome, and whilst it would be splendid if somebody were to implement a means of overcoming them, I cannot think of any means of overcoming these challenges, especially in relation to private car routing, at present.

[Mariculous]

although the reality is more complex than this, as, where jobs are scarce, people did, even in centuries past, travel long distances to find work

This is not conflicting with local growth preference. It is indeed true, that people will move long distances if their essential requirements cannot be fullfilled locally, but if those can be fullfilled locally, the vast majority of people will still prefer local settlement.

I see two different "levels" in settlement decisions:
1. Selecting a rough area where the essential requirements can be fullfilled:
In the first place this means the availability of jobs (specific to citisens class) in a fairly large area.
Such data could be stored in cities, attractions and industries.
From all these possible areas, citisens will randomly select any, weightened by locality, i.e. a local destination is more likely than one on the other side of the map.


2. Selecting an exact location to settle, within the see considering comfort requirements:
That step is a topic on its own, in huge parts discussed in citygrowth thread already. Consider succes rates, land values and whatever.

One and two should be mixed up a little, selecting multiple candidate areas and selecting the best exact location from multiple areas.
That's because there might be areas with jobs available somewhere, but any "comfort" criteria being excessively bad.
People usually don't want to move there, except if they have no choice.


It does not immediately conflict with global population either:
Instead of immediately growing cities when cities internal population counter increases, such increases could be stored to a more abstract growth rating instead.
That rating in relation to the summed up rating of all cities then determines how many percent of global city growth each single city will cause in the next growth batch. Afther the batch, all ratings are reset to 0 again.
So you got your global population figure combined with a local preference for relocations.
Again, that local preference does not stop people from moving much further away if they cannot find a job nearby and there is a chanche to move far away even if there is a job available nearby.

To simulate decreasing populations of some cities, an additional kind of relocation could be used:
Frequently, a percentage of cities inhabitants will relocate without a new inhabitant being generated.
That means the population of a housing is decreased and then the same relocation logic as above is used.
In effect, the citizen will leave that area and move to an other one.

[jamespetts]

This is not conflicting with local growth preference. It is indeed true, that people will move long distances if their essential requirements cannot be fullfilled locally, but if those can be fullfilled locally, the vast majority of people will still prefer local settlement.

A local growth preference is what I described above as a complex mixed algorithm; it is not a pure local growth algorithm. The current city growth algorithm is a pure local growth algorithm.

I see two different "levels" in settlement decisions:
1. Selecting a rough area where the essential requirements can be fullfilled:
In the first place this means the availability of jobs (specific to citisens class) in a fairly large area.
Such data could be stored in cities, attractions and industries.
From all these possible areas, citisens will randomly select any, weightened by locality, i.e. a local destination is more likely than one on the other side of the map.


2. Selecting an exact location to settle, within the see considering comfort requirements:
That step is a topic on its own, in huge parts discussed in citygrowth thread already. Consider succes rates, land values and whatever.

There is a fundamental problem with splitting it in this way, at least to the extent that the algorithm conclusively determines the first before considering the second, which is that the availability of suitable exact locations to settle is precisely the thing that determines (and, indeed, constitutes) any given area being one in which there are places where essential requirements can be fulfilled. The availability of jobs means the availability of places that one could live where it is likely that there would be a high probability of commuting success, inferred from the commuting success of nearby buildings.

Thus, to know whether any given unit of intended growth determines that any general area potentially fulfils the essential requirements for growth, one of which is local job availability (and, again, local measured in time, not distance), it is necessary to determine whether there are any specific places where growth could in fact take place where it is likely that there will be a high commuting success percentage. That the area in question has a large number of places that already have a high commuting success percentage is not a reliable indicator of this, since all the available spaces that have good transport/walking access to jobs might already have been taken, leaving only places on the edge of a city that have much worse access to jobs than available places elsewhere, even if those available places elsewhere have lower overall average commuting success percentages.

It is not necessarily impossible to have an algorithm of growth that has some sort of local weighting, but it cannot be a simple two stage process as suggested above.

One and two might be mixed up a little, selecting multiple candidate areas, as locality to the familiar surroundings is also comfort criteria, so a much closer location with slightly worse transport and the same further comfort criteria might be prefered over a far-away destination with perfect transport.
Keep in mind that in both cases areas that cannot fullfull job requirements are not considered.

Selecting an area where the demands of the citizen can be fullfilled.
In the first place that means there are enough jobs (specific to citisens class) available at a fairly long distance.

This would demonstrate the anomalies suggested above to a slightly lesser degree than the simpler system, but any two step process of this sort would still demonstrate these anomalies.

The only way that I can think to make a semi-localised system of growth to work is for each town to have its own independent global weightmap of desirability for settlement of people from that town, taking into account locality, and then actual settlement would take place on the basis of a weighted average using that weightmap. I am not sure whether this would consume too much memory/memory bandwidth to be workable, however.

Edit: Also, there is a fundamental problem with the per town weightmap idea: such a per town weightmap would have to take into account locality: indeed, this would be the only purpose of having a per town weightmap. But locality here must mean journey time, not geographical distance; yet there is no memory structure in the game from which average journey times from a town to individual tiles are stored, and any means of generating these data would require such heavy access to the path explorer dataset as to be too computationally intensive to be workable on a larger game.