Revision as of 12:14, 22 April 2012

In PSG228, we tried to extend a single city over the full 512x512-map. The first issue was the road design, which stopped town growth at about 350,000 inhabitants. We got rid of all dead ends, and the town got bigger again. However, after we reached a population of ~1.5 million, the town refused to increase its population. Growth tunnels spread more houses on the outside, but the result were many empty spots closer to the city center, which decreased the total population.

This inspired me to do some research how towns work, and how this can be used to grow towns. The source code of OpenTTD is public and can be accessed at [1]. For towns, the most important file is town_cmd.cpp.

Algorithm of town growth

The algorithm to build new houses works like this:

1) First, calculate how many times the town tries to build a house (which I will call N):

• If the town is founded with "2x2 grid" or "3x3 grid" as road layout, N = 10 + housenumber*1/9
• If the town is founded with "better roads", N = 10 + housenumber*2/9
• If the town is founded with "original roads", N = 10 + housenumber*4/9

This means that the chosen road layout of the town is important - even if we build all roads ourself, which is usually done in coop games.

2) now, begin at the city center (usually the road under the town sign, or a road next to it)

• if there is no road or if there is another, unconnected road, build a road (if allowed by game settings) and always stop the function
• if not, choose a random direction. If the current tile has a road connection in this direction, do nothing. Otherwise, if the neighbor tile in this direction is empty, build a house there and stop the function. There are more checks involved (e.g. "is the tile in water?"), but they are not important here. If towns are allowed to build roads and have a grid layout, no house will be built at tiles reserved for roads.

3) If the function was not stopped for one of the reasons above, follow the road in a random direction, except the one where you came from. For regular roads, this just follows the road. At cross-roads, a random direction is chosen. If the road has a connection to one side only (and therefore is a dead end), the function is stopped.

4) Try to build something there again. Repeat steps 3 and 4, until the number of attempts is larger than the maximal number calculated in step 1.

If the algorithm hits a bridge instead of a regular road, it continues at the other side, independent of the length of the bridge. If a bridge begins at the tile of the city center, the other side is used only half of the time.

For interpretation, it is important to compare N to typical town sizes: A town with 200,000 inhabitants might have something like 2000 houses and therefore N=230 to 900, depending on the road layout of the town. But it fits in a circle with a radius of about 50 tiles. Where does the difference come from? As mentioned in step 3, the town follows roads in random directions at each crossroads. This leads to a pattern which is called random walk in mathematics. I don't want to annoy you with details, but it is important to keep in mind that the resulting path might visit the same roads multiple times and the average distance from the origin grows with the square root of the pathlength. This is fine, as the town radius grows with the square root of the house number, too, if it can grow in all directions.

This town demonstrates the large difference between potential growth radius and usual town sizes. The map shows a single road, 4135 tiles long, with houses on both sides. The central structure is disconnected to enforce town growth in the direction of the long road.

House quality

Towns have four different areas, which can be distinguished by the road layout:

• region 4 with street lights
• region 3 with trees on the roads
• (region 2 is not used)
• region 1 with sidewalks
• region 0 has no special road design

Towns with less than 92 houses use a table to look up the size of these regions, if they have more houses they use the following formulas: m=housenumber/8 (rounded down)

• region 4: range=m*3+5
• region 3: range=m*5-5
• region 1: range=m*9-15
• region 0: range=m*14-40

A tile is within a certain area if its squared distance to the town center is smaller than this range. Region 3 has an area of about pi*5/8*housenumber tiles, which is nearly 2*housenumber. If half of the town tiles can be used for houses, the whole town can be within this area.

An example with a town in PSG218: It has 1171 houses, therefore m=[1171/8]=146 and region 4 has range=146*3+5=443. The tile with street lights is (19,9) tiles away, the squared distance is 19^2+9^2=442 which is smaller than 443. Therefore, the tile is in region 4.

House number and town size

Every house has a (minimal) lifetime. After reaching this time, it is destroyed and might be replaced by another house. If not, the tile gets empty. Large towns spend a lot of their "growth" attempts to fill these gaps again. The best growth rate is 1/day. This gives a natural upper limit of the house number of towns: As soon as the rate of dying houses is equal to the rate of new houses, the town cannot grow any more. I am not sure if NewGRFs change the lifetime of buildings. In addition, different house sizes might have different lifetimes. For a regular town layout and original houses, I think the limit is somewhere around 27000 to 30000 houses and about 2.4 to 3 million inhabitants, where the lower values were reached in my tests and the upper values might be possible somehow. A town of this size needs about 80 years to remove and rebuild the house on each tile once.

Application to town building

• avoid dead ends in populated areas. The town growth algorithm might run into them and stop without building a house. A dead end somewhere outside does not matter - as long as there are no houses, the town does not use this road anyway at the moment.
• a single road tile with an open end does count as a dead end. The town might follow it, try to build a road (and fail) and stop.
  

  A dead end towards east
• avoid having too many road junctions. Every junction is a place where the town might change its search direction, reducing the effective range where it searches for empty spots to build new houses.
• use growth tunnels/bridges if your road layout near the city center is so complex that the outer parts get too few houses. However, let them end within region 3 (roads with trees) until this area is filled with houses.

The "best" road layout

The best road layout is everything where each growth attempt is successful and ends in a new house. Most simple SBahn-grids get close to 100%, you can grow a city with at least 2 millions inhabitants with that. To always get a new house, build a few long roads, going from the town center outwards. The town growth algorithm will follow them and pick one of the nearest empty spots. This results in houses everywhere along the road, and always enough empty tiles after some point.

With just two roads (connected in the town center to get a single long road), each road piece can support ~2 houses, therefore the town has to perform roughly housenumber/4 steps in the searching algorithm. With "original layout", it can do up to housenumber*4/9 steps, which is larger than this number. Therefore, this layout is basically the best you can do without other constraints. These roads can be winded around the town center in some spiral-shape.

A town with a single long road, as described in the text. The town uses every available spot in the inner parts (except some corner tiles) and fills gaps there nearly instantly.

This map has a serious problem with overpopulation. 13 million people live on 512x512 tiles, with a transportation rate of about 80% via transrapid trains.