A dream of a town growth algorithm - MatthewForrester/simutrans-extended GitHub Wiki

Not a serious proposal but some notes of how town growth might work one day, that will almost certainly never be implemented because I don't have the skill or the persistence to implement them.

0. Prolegomena

0.1 Analysis of current town growth & associated systems

Strengths

• Produces fairly realistic looking towns, with clusters of similar buildings and high-value, high-density buildings in town centres.
• Players can easily see on the minimap where there is demand for workers or unemployed workers needing connection to jobs.
• Many, but not all, buildings are gradually replaced as the timeline progresses, resulting in a realistic mixture of old & new.
• You can clearly see in the Town Info Window whether a town has unemployment or a surplus of workers, on a class-by-class basis.
• Most player buildings create jobs, so player investment immediately improves a town's economic prospects.

Weaknesses

• Automatically generated cities are always square (built on almost every tile to the city limits) and no one knows why.
  • Probably the most embarrassing current bug because it's always obvious on screenshots and when the game starts and we inherited the correct behaviour from Standard until we broke it.
• The level of individual citybuildings and the placement of Attractions takes no account of connectivity at the tile level, so providing good service at one station might result in buildings being levelled up 50 tiles away—potentially benefiting your rivals instead.
• If you manually grow cities, particularly on non-default settings, then they just don't grow.
• The Increase Industrial Density button doesn't do what it says on the tin.
• The relationship between town growth and Factories is somewhat opaque.
• The multitile building system incorporated from OTRP isn't used and Prissi reports it's broken.
• The multitile building system doesn't take into account building rotation, so you can't be sure gates or doors will face the road.
• The vast majority of journeys (80%+) take place by walking or private car, so players' actions only have a marginal effect on town growth.
• Only the lowest level of town hall is ever built, perhaps because simcity.cc:L5545 specifically blocks the renovation of town halls:

if (!gb->is_city_building())
				continue; // Definately not a building we want to renovate

Opportunities

• Standard has its own multitile building system that Prissi says fixes the problems with the OTRP one.
• The passengers_succeeded_... variables already recorded detailed local connectivity data on a per-building basis that just needs to be exploited.
• The available_jobs_by_time system already records some employment data on a per-building basis and more could be made of this if helpful.

Threats

• Extended relies on volunteer coders with varying skill levels, so everything needs to be as simple and maintainable as possible.
• Most players are likely to be playing on the largest maps they can, so changes should not have major performance implications, including memory consumption.

0.2 Aims

• To fix the bug that means cities are always square.
• To ensure that city buildings which have good passenger connections level up more quickly than those with poor passenger connections, so that density naturally grows around stations and players are rewarded for providing good service to the right places.
• Simplicity, which will aid code maintenance in the future, in an already complex game.
• Minimal impact on performance.

0.3 The Railroad Not Travelled

1. New variables

• There is a new or repurposed global/world variable, perhaps growth_factor
• Each world or possibly city has a vector (or similar container) of tiles suitable for new/re-developments, which we will call developlist.
  • This list is discussed in more detail in part 4.
• Each citybuilding (RES/COM/IND) has a new sint variable, which we will call capital. For new buildings (including game start), it is initialized at 0.

2. Recording capital: changes to the Passenger Generation Algorithm (PGA)

• As part of the Passenger Generation Algorithm, every time a RES succeeds in making a Commuter journey, both the RES and the destination citybuilding increases capital (let's assume by 1).
  • "Making a journey" for this purpose must be when the passenger packet is generated, rather than when the packet reaches its destination, because packets don't record their origin tile IIRC.
  • RES to Factory commutes will increase capital for the RES; we assume Factory growth is a separate system and ignore it here.
• If the journey fails because the destination citybuilding in unreachable (either totally or within the time limit), then the origin RES' capital is reduced (again, let's assume by 1).
  • In practice, the logic guarantees that more journey attempts fail than succeed, so a final implementation couldn't increase & decrease by 1: the failure reduction needs to be less than the success bonus. This might need to be calculated empirically by keeping a running total of successes or failure in the individual save, or it may turn out to be pretty universal across save games.
• Visitor journeys between RES & COM, COM & COM, IND & IND or COM & IND citybuildings, which represent economic activity, also increase the capital of both origin & destination if they succeed and reduce it if they don't.
• RES to RES Visitors journeys do not affect capital, because they represent leisure travel which does not affect the economic success of the household.
  • RES & Attraction journeys are also considered leisure travel & ignored.
  • The 'economic activity vs leisure' principle can also be followed be made for Town Halls and any other possible permutations.
• None of this would apply to Mail, as Mail searches are not time-limited.

3. Upward renovation or redevelopment

• If capital is higher than (the level of the citybuilding + growth_factor), then the citybuilding is ready for growth.
  • I think this check is very cheap, so could be carried out every time a tile is picked as an origin tile by the Passenger Generation Algorithm. But that is an optimization decision; this proposal works just as well if this check is carried out monthly or annually or whatever.
  • Growth_factor will obviously need to be set by pakset, because AFAIK some paksets might use level 1,2,3 and others might use 10,20,30. In the future, as an extension of this proposal, this could also be used to add economic cycles (i.e. growth_factor is lower in boom years and higher in bust years).
• The existing renovation check is applied. If the citybuilding is going to be renovated, then that happens, and the tile's capital is reset to begin the cycle again.
  • A simple implementation would reset capital to 0.
  • A more complex implementation might deduct ((new level + growth factor) - old level) from capital, so capital is actually spent on the renovation.
• If the citybuilding fails the renovation check, then we carry out a 'migration' process:
  • A building from the developlist is randomly chosen as the destination.
  • Check whether the redevelopment of the destination building is affordable.
    • Calculate the difference between the destination building's current level and (its redeveloped level+growth_factor). This is the redevelopment_cost.
    • If (origin capital>redevelopment_cost), then continue.
    • Otherwise, look for another target building.
    • In §4.1.1 below, we explain some additional steps that apply in certain cases.
  • Check whether the building is reachable, using the same function that's used for the Passenger Generation Algorithm.
    • This step and the one above can be swapped later if that's better for optimization.
  • If the destination is affordable and reachable, then:
    • Redevelop the destination building using the existing renovation code.
    • In a simple implementation, reset the origin and target buildings' capital levels to 0.
    • In a more complex implementation, deduct redevelopment_cost from origin capital then copy origin capital to the target building and reset origin capital to 0.
    • For extra fun, you could spawn passenger packets from the origin building to the destination building. I say packets plural because you'd need different packets if the origin building had more than one class. These could be Visitors or we could even have a new Migrant class of passenger so players could watch the migration happening across their network (if the packet ends up being routed by public transport rather than walking or private car).

4. The developlist

The developlist is a list (technically, a container) of development sites that are suitable for redevelopment by migrants from other citybuildings. Development sites are a new group of citybuildings on certain tiles. Some of them will be chosen from the existing COM/RES/IND citybuildings that we know (and love) already. Others will be of a new type (introduced in §4.2). For each entry, the developlist would store at least three things: the tile's co-ordinates, what is currently built there, and what would be built there if it s redeveloped. We'll call that third thing "the Possible New Building".

4.1 Sources of development sites

Development sites would come from three sources, which we will call greenfield sites, demolition sites, and brownfield sites.

4.1.1 Greenfield sites

At the moment, when a city expands (moving its city limits outwards), it adds roads. And due to a bug in Simutrans-Extended, it usually immediately fills the sides of those roads with citybuildings, creating square cities. In Standard, the roadsides are gradually filled up, so that cities' edges look naturally ragged. Either way, it is proposed that the game would no longer add any of the existing city buildings at this stage. Instead, it would construct placeholder 'dummy citybuildings' (explained in §4.2 below) on each tile and add them to the developlist as being currently built on that tile.

The program will still semi-randomly choose a suitable citybuilding (taking into account climate, region, clustering, etc.), but it instead of constructing it immediately, it will store it in the developlist as the Possible New Building. If and only if this tile became a destination for migrants, using the algorithm described in §3, then the Possible New Building would be constructed and this tile would be removed from the developlist.

4.1.2 Demolition sites

In a similar fashion, these are tiles that become empty when players (including the public player) demolish Ways, Station Extensions, Factories, etc. — any object that would prevent a citybuilding being constructed on a tile. The demolition process (apparently in the various remove() member functions) would conclude by creating a placeholder 'dummy citybuilding' and adding it to the developlist.

However, it would be very annoying if players get dummy citybuildings popping up every time they temporarily delete a Way tile or Station Extension building in order to reconfigure their track layouts or bus stations. So it would be essential to add some kind of timer or safeguard around demolitions by human players, perhaps by adding them to a temporary buffer list until the end of the month.

4.1.3 Brownfield sites

These are existing citybuildings that have been identified as suitable for redevelopment (e.g. in pak128.Britain-Ex, it might be "the Warehouse at tile 123,456"). However, what criterion should be used to choose them? The new capital variable provides us with a convenient metric to assess which tiles are well-connected, but if we consider the options, I think random selection ends up being the least worst option.

NOTE: For each of the algorithms below, need to consider both per-town and mapwide effects.

Bad algorithm: high capital, well-connected citybuildings

Bad algorithm: low capital, poorly-connected citybuildings

Least bad algorithm: randomness

.

4.2 Dummy citybuildings

There would actually be three dummy citybuilding types, for each of RES, COM or IND. They would behave like normal citybuildings in most respects, but their level and class_proportion population statistics would be set to zero, and they would have the following special features.

Use the Passenger Generation Algorithm to assess development potential

If a dummy citybuilding was picked by the PGA (either as an origin or destination), then it would be handled a little differently from other buildings. We would still carry out the PGA searches, as if a passenger was going to travel from/to here, and use them to adjust the capital of the dummy citybuilding in such a way as to reduce the cost to potential migrants to the tile. I know it seems slightly counter-intuitive to make the sites with the best connections 'cheaper', but the effect would be exactly what we want and what would happen in the real world: well-connected greenfield and demolition sites would be more likely to be redeveloped than poorly-connected ones. If you build a station on the edge of town and run frequent services , then you have a good chance (never a certainty!) of seeing development grow up around it.

But we wouldn't necessarily actually generate any Passenger packets for travel. It would be possible to actually generate Visitor packets travelling from the dummy citybuilding (representing potential migrants & investors checking out their potential new home/office/warehouse), but that's not necessary for this proposal to work. Likewise, it might be possible to set some class_proportion_jobs for COM and IND buildings to represent construction workers, but that's not necessary for this proposal. In both cases, I would start by making the bare minimum of changes here. Dummy citybuildings should not send or receive or Mail, both for performance and to model real-world economic decision-making.

UI

If a player clicks a tile holding a dummy citybuilding, then then would get the normal Citybuilding Info window, and they would be able to see that has level=0.

Target citybuilding type already decided

Graphical representation

The graphical representation of the dummy citybuildings is a matter for pakset maintainers. Most (all?) of the Extended paksets currently have a construction-site graphic that is displayed during map generation ( pak128.Britain-Ex, pak128.Sweden-Ex, possibly this for pak192.comic-Ex), which would be highly suitable. At a minimum, even I could make a citybuilding graphic that was transparent except for pastel-coloured borders, similar to the graphics that Cities:Skylines and SimCity use to mark development zones on their maps.

4.3 What should be the extent of a developlist?

Should there be a mapwide developlist, one per city, or a

4.4 Technical considerations

Would replace City Demand, so that means UI changes

The type of entries in the developlist

5. Downward renovation or destruction

6. Technical considerations

6.1 Rotation considerations

6.2 Multitile considerations

6.3. Multithreading considerations