Discussion.Cities and Terrain - Ae-2222/pioneer GitHub Wiki

City terrain blending

@fluffyfreak

I was thinking about something RobN said in the the small fixes thread about terrain. I'm sure that this will therefore be redundant but it'd make sense to try and take into account the underlying terrain beneath a city, whilst also making it more suitable for the city which is sitting on it.

The idea is relatively simple, when the game defines a "city" it has a central position and a size, or extent, i.e. how big across the city is. Currently buildings are then placed onto the land directly.

What I suggest is that the city has some extra data in the form of an inner and outer limit used later on. When the city is define it first harvests some low-resolution data from the terrain / or generates it using the same inputs, and uses it as a basis to generate its own "local" heightmap. That heightmap only affects the terrain nodes that touch it rather than the whole planet but when it does the terrain node is affected in one of two ways.

if the node / terrain point is between the inner and outer city extents then it is linearly interpolated between the value that the terrain would have had, and the one in the cities heightmap.
if the node / terrain point is fully within the inner extents then it takes the value directly from the cities heightmap.

Buildings themselves should only ever be placed fully within the "inner" extent by the engine.

Example/explanation image below (i hope):

This way we could control the local city environment using more appropriate/simpler algorithms and avoid situations caused by the terrain changing resolution & height beneath them. One algorithm might be a Voronoi diagram (http://en.wikipedia.org/wiki/Voronoi_diagram) representation to preserve large flat areas but still have some larger stepped change in heights. Another one, interactive too (http://mbostock.github.com/d3/ex/voronoi.html)

The point is that once the basic system is in place people will be able to extend the city heightmap generating methods independently of the terrain whilst still having them blend into it. The system could also be used for finer control over specific areas of the real world if anyone wanted that, or for scripted missions etc.

What do people think? Specifically s2odan and other coders?

Andy

Re: City terrain blending

@robn

I'll click through the links and think a bit more and hopefully provide a better reply, but here's some initial thoughts and musings (some of which you'll already know & understand) based on my experience so far:

As noted, buildings are currently just dropped onto the terrain at the height at that point. Height is based on the centre of the model and the terrain height at that point. This is why on a steep incline part of the building goes into the ground while other parts hover over it.
Selection is mostly random. There is some code to try and choose the right types of buildings for different areas but its rather rudimentary (and right now there aren't any other building types active anyway). I was working on something better with clearly defined zones (starport, power, residential, industrial, etc) and atmosphere types (earthlike, hostile) before I realised...
Zoning is fine, but just dropping buildings is dumb. I want to "grow" cities that follow the terrain so they look a bit more organic. The algorithm I settled on for an initial test (but never implemented) was to give each building an amount of population that it consumed, and then right at the start determine the population of the city. Then we walk out from a point or set of points (eg the starport) in all eight directions, looking at the terrain around it. If the terrain is too steep, is water, already has a building, etc we don't go that direction. We place buildings at all remain points and then recursively walk out to each building we placed and do it again. Each time a building is placed, we consume its amount of population from the total, and stop when we run out. This should create cities with a heavy central area and thinning out the further out you go. It should also follow ridges, rivers, etc in a "natural" way.
I want roads too and bridges too. Maybe roads are just a special type of building? Bridges are - they just have two "bases", which must be on similar heights, and preferably spanning some terrain that is radically different in height (water, ravine, etc).
Looking at the "steepness" of the terrain for placement is fine, but on gentle slopes its still possible to have the building bases do the wrong thing. Placement needs to be able to modify the underlying terrain slightly to flatten it - call it excavation if you like. I don't know what the performance hit will be as we have to compute the terrain height at the four corners of each building instead of just the centre, so naively our height computation during city generation quadruples. There's optimisations that can be done - take the central point for one building and interpolate to the known centre point of the previously-placed building, but its still heavier. It may not be a problem, but I don't currently trust our heightmap generators for speed :)
So now we have a generated, static city heightmap that we have to use in place of the dynamic heightmap. Blending may not actually be necessary. The city heightmap was originally based on the dynamic terrain, so perhaps it can just be used in its place. Probably some blending is necessary though, as its going to be a fairly low-res map compared to the higher detail levels coming from the generator.
Blending on the GPU would be incredible simple - sample two (or multiple) heightmap textures, blend them, adjust mesh positions. I'm not so sure about on the CPU. I guess its the same, its just that GeoSphere.cpp scares me right now. Anxiously awaiting jaj22's rewrite. That said, we could do this on the GPU if we wanted and the non-shader version can just use the regular dynamic heightmap as it always has. Shaderless Pioneer is has to be functional, not necessarily pretty ;)
To avoid the city heightmap being too "steppy", we might want to mix a little noise over the top. A third heightmap, if you like. Might not be necessary if the dynamic terrain is mixed in, as it should have enough variation. Also the city terrain is covered in buildings, so perhaps it won't even be noticable. Possible dumb idea, never mind!
Texturing the terrain would cover all manner of sins, allow more colour variation and let us simplify the geometry in a lot of places. Its not strictly necessary for cities, but since we're talking about some fairly fundamental changes to the way terrain works, it needs to be considered.

That ended up longer than I expected. Blame my morning coffee and toast that I was consuming while I wrote this - it obviously got me progressively more buzzed as I typed! I'll think a bit more about what you wrote today, and you pick this apart. Cheers!

Re: City terrain blending

@Ae:

Fluffyfreak wrote: "What I suggest is that the city has some extra data in the form of an inner and outer limit used later on. When the city is define it first harvests some low-resolution data from the terrain

There has been some work done on algorithms for generating small maps (cylindrical projections) of each planet (hopefully with a way to get terrain type from the get height function as an integer), to be used for a lot of things, including city selection/positioning. It is awaiting some way to visualise it, so it can be developed further (probably after the GUI).

Fluffyfreak wrote: or generates it using the same inputs, and uses it as a basis to generate its own "local" heightmap.

The issue with precomputing heightmaps is that, if you allow for local variation (down to city block level) and have massive urban sprawl (like the common in the USA) let alone an entire city planet, it requires a vast map.

This is both a space and cpu time intensive exercise.
For instance the 30 mb moon map only had points 1.2 km apart (so ~1 sq km blocks) (storing only 16 bit integers as data) and the moon has a radius of 0.273 of Earth's giving about 07% of the surface area. A 300 mb map would be needed just for simple 1sq km height variation.
(If you then add in actual surface details depicting artificial city infrastructure, maps of parameters needed to position buildings/select between styles etc. with variation down to city blocks then straightforward pre-computation of everything becomes impossible, even in theory, due to lack of memory.)

A solution is to use small texture fragments containing height/colour data as needed (along with tables containing building/infrastructure geometry positioning) used fractaly with the assistance of algorithms controlling which textures and how they are used.

Fluffyfreak wrote:

That heightmap only affects the terrain nodes that touch it rather than the whole planet but when it does the terrain node is affected in one of two ways.

if the node / terrain point is between the inner and outer city extents then it is linearly interpolated between the value that the terrain would have had, and the one in the cities heightmap.

if the node / terrain point is fully within the inner extents then it takes the value directly from the cities heightmap.

This is essentially how the region based terrain control system I outlined here works.

It uses points (ideally arranged as a tree so traversal is fast), even for quite high res point distribution, to define a region.
There can be multiple such trees for different properties.
A metric like distance to is then used to identify whether a location belongs to a point.
Once this is done the arbitrary data that can be contained in the point, along with the distance can be used to affect things like height, building types, building layout patterns etc.
The idea is to have a simple point set for economy, military, architectural style that the game can change as planets get invaded, militarised, become poor and so on.
It is possible to either store links to neighbours or just use the 'leaves' in the final division to get cumulative effects based on neighbours (e.g. influences from multiple economic, cultural centers).
Minimal points needed to represent variation at differing areas are used (i.e. multi-resolution map)
Terrain can use:

a mixture of the original terrain
new fractal code describing artificial like city infrastructure
fractally mixed heightmaps
pre-computed large scale maps of properties if needed.

Fluffyfreak wrote: This way we could control the local city environment using more appropriate/simpler algorithms and avoid situations caused by the terrain changing resolution & height beneath them.

The changing of height with time is purely due to the lodding code:). The cities would need higher res geometry generated near them, either separately or using some type of preferential patch division.

Fluffyfreak wrote: One algorithm might be a Voronoi diagram (http://en.wikipedia.org/wiki/Voronoi_diagram) representation to preserve large flat areas but still have some larger stepped change in heights. Another one, interactive too (http://mbostock.github.com/d3/ex/voronoi.html)

It's also possible to do something like round to the nearest 40m height if within city boundaries and, if within 3 meters of a 40m boundary, interpolate with noise added to get a smooth natural looking transition.

RobN wrote: I want to "grow" cities that follow the terrain so they look a bit more organic. The algorithm I settled on for an initial test (but never implemented) was to give each building an amount of population that it consumed, and then right at the start determine the population of the city. Then we walk out from a point or set of points (eg the starport) in all eight directions, looking at the terrain around it. If the terrain is too steep, is water, already has a building, etc we don't go that direction. We place buildings at all remain points and then recursively walk out to each building we placed and do it again. Each time a building is placed, we consume its amount of population from the total, and stop when we run out. This should create cities with a heavy central area and thinning out the further out you go. It should also follow ridges, rivers, etc in a "natural" way.

Growing cities either in time or evolving along terrain boundaries iteratively (feedback based algorithms) is usually done in games where the size of the city is small and has limited detail. The main issue here is time required. This is the reason why pioneer can't 'grow' rivers or simulate erosion, as is done with photo-realistic terrain generators like Vue or Terragen, which have no time constraints.
The Pioneer approach is to look at the properties of evolved systems as well as how those change with differing conditions, e.g. rivers that fan out like ridged noise can be done and, the degree of branching based on some property, like rock type or altitude, can be factored in to change the noise.
For large scale/coarse evolutionary effects it is, of course, possible to have an iterative system of some sort.
Single terrain point feed back, i.e. altering selection of buildings based on type of terrain, height or coarse map data containing closeness to rivers/sea at one point is possible.

Looking at the patterns such evolved systems create and replicating that will work. It is also possible to generate terrain features along with/based on the building patterns e.g. creating holes in the building patterns for water bodies, incorporating an architecture variation pattern to vary from a central point to simulate growth with differing architecture/wealth.

Some properties building generation should have

Not be created with respect to a city center or it's associated starport. i.e. supporting urban sprawl and city planets.

Support variation on the scale of city blocks up till on the scale of continents.

Makes use of heightmaps covering all detail prohibitive.

Allow for dynamic variation as the social/military/economic situation changes (keeping in mind high level factions will play a full RTS/4X game creating almost every situation present in sci-fi literature).

Destruction with war and use of weapons of mass destruction/meteorite strikes.
Occupying forces building different types of architecture to serve their needs.
Abandoning due to threats, economic situation.
Military buildup due to threat of war.
Variation with changing styles and cultural influence from new powers.
Adding military/medical attachments to change existing structure use.
Interface with the higher level RTS/4x game will be through the few state variables it uses..e.g. increasing military structures in a region of space will have ripple effects as it is fed in to the building generation as a parameter or mixed with other relevant parameters and used (local resources, policy, militancy in culture etc.)
A way of keeping a timeline of developments since the game started (military buildup, oppressive forces building structures, freedom to continue as before). Using very coarse maps of an areas' resistance to modification, or not completely fading away influence centers are possibilities. Adding historic influence centers to match the procedurally generated history of a planet is a possibility.

Allow for variation in architecture according to: (Wealth , Military presence ,Economic level, Industrial use, History/archaeology, Terrain type/world type)

Use common procedural content generation pipeline - load building locations as visible (using a simplified algorithms/assets for distant areas), cache nearby areas, prune cache as viewer moves away.

This requires a fast building positioning algorithm. ==> Making the terrain component run using the results of the building algorithm when under influence of city areas (which in turn might use pre-generated maps of the original terrain at a coarse level) would allow decoupling of building positioning and terrain generation for fast building loading.

Have a method for uniquely identifying buildings.

Possibly by rounding off center position coordinates to the nearest meter and creating a 3 integer mt-rand seed component, along with a fast hash (e.g. xor) of the city gen/building type parameters relevant to identify it, when it existed.
This will allow bombing, reconnaissance missions, reporting of buried archaeologically relevant structures, legal penalties for property destruction etc.