City terrain blending
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 it's 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.
1) 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.
2) 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?
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:
[*:3finr69x]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.
[*:3finr69x]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...
[*:3finr69x]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.
[*:3finr69x]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).
[*:3finr69x]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 🙂
[*:3finr69x]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.
[*:3finr69x]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 😉
[*:3finr69x]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!
[*:3finr69x]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!
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).
I don't think that roads make sense as buildings, zoning, population, and following the terrain all seem like parts of the same thing. You can't really consider them in isolation.
Lets take a look at how one other example I've read handles this, I think it's similar to the cancelled "SubVersion" project:
1) generate heightmap,
2) generate habitability map - i.e. water = 0, mountain slope = 1, marsh land = 2, flat solid land = 3, etc.
3) generate population map - starting point is the highest value on the habitabilty map that's nearest to the city centre, add more points based on overall desired city size, then turn these into a Vornoi map with a value dropoff say starting at 255 at the centre to 0 at the edges.
4) generate highways - the above Voronoi map generates a lot of edges around population density points, you can connect these density points directly (as major roads) and then use the edge list from the Voronoi map as smaller roads.
5) generate lots - major population areas have now been nicely divided up, break up the resulting blob areas into smaller building lots of whatever shape you like, a grid based approach is probably ok at this resolution and it's quick.
6) the edges of the lots above can now become minor roads, i.e. one and two way streets,
7) buildings are placed at one corner of each lot facing the road (either) and then the rest of the buildings can be placed around the lot one after the other with a little bit of buffer spacing - the choice of building is based on the habitability and population density maps we created earlier, higher population = taller building but constraints applied by habitability because you can't have a skyscraper on a mountain slope etc.
If you want defined economic type zones or instanced building types then they get injected as other maps or parameters of the vornoi zones etc. Inserting a large spaceport of example would add an extra major highway to be drawn during the "generate highways" process and put a large exclusion area into the lot generation which all naturally filter down into the following stages.
Hmm, I should program more and think less sometimes 😀
Instead of thinking of this as a problem with generating terrain, derive the heightmap from the buildings and the city itself.
We have the heightmap, lets say it's a greyscale heightmap in traditional 2d, we don't need to re-generate anything, we just paint the building footprint into the heightmap plus the centre height. That would have the effect of raising the lower heights and lowering the higher bits without calling the terrain generation.
When the terrain is generated it only _reads_ the information from this heightmap, no additional noise or processing required because all terrain directly under the centre of the city comes _from_ that city heightmap 🙂
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.
Blending is possibly the wrong usage by me, my fault, what I had in mind was something simpler.
Currently we generate the terrain using noise, what I'm suggesting is that near a city the cities local heightmap overrides the terrain generation algorithm. This would be "ok" because of two features: the 1st is that we'd have used the terrain generation as an input for the city heightmap anyway so it wouldn't be too different, the 2nd is that when we generate the terrain mesh we'll linearly interpolate between the height from the planet noise and the city heightmap depending on the distance between the inner and out extent boundaries.
I'll try and write a quite example of the 3 cases:
1) Outside the city entirely, terrain mesh height = planet_noise(x,y,z)
2) 50% of the distance between outer and inner city extents,
pn = planet_noise(x,y,z)
ch = city_height(x,y,z)
// result is a point 50% of the distance between points "pn" and "ch"
terrain mesh height = ((pn) + (0.5) * ((ch) - (pn)))
3) completely within city inner boundary, terrain mesh height = city_height(x,y,z)
No actual "blending" needs to be done anywhere as it's done at mesh generation time.
Of course this is based on thinking about how our current terrain system works 🙂
Right, can't post anymore right now, got washing to do and then going for lunch 😆
What a nice informative valuable article from yours about City terrain blending ! I think your post is related with mileage between two cities. Am I right ? Thanks for your well sharing.