Future City: Update 1 - Divide And Conquer

Top Down

A key consequence of the Apparance detail management system is that each stage of refinement must be possible independently from any other.  The upshot of this is that the content within a block (in a particular tier) must only depend on the content of its parent (higher tier) block.  It can't depend on the content of any neighbouring blocks.  If this were allowed, then you introduce many cases where long chain dependencies and circular dependencies occur causing no end of problems.  It is also easy to see that approaching a block from one direction leads to neighbouring blocks being refined in a different order to approaching from another direction, again causing problems if you depend on them.

Vertical (downwards) dependency = Good :)
Horizontal (sibling) dependency = Bad :(
Circular dependency = Really Bad :( :(

The Price We Pay

For a lot of structures and models we may want to build, this constraint isn't a problem. For example, refining a wall into individual bricks is straightforward as the bricks and their positions can be generated deterministically from the more general wall shape representation above.  There are however many cases where we cannot model in this way, for example; building a dungeon of interconnected rooms and corridors.  Many procedural dungeon generators are effectively image processing systems, applying several passes to the dungeon 'image' (cells or otherwise) to build up, interconnect, and validate the space.  This is illustrated well in this nice dungeon generation write-up.  Since Apparance doesn't have any image processing (yet) with which to drive this sort of generation, and is effectively a purely functional programming system, we have to use the sub-division approach and work out how to circumvent the horizontal inter-dependencies we meet when neighbouring rooms need to be connected.  More on this later/next time.

City Size

As an initial starting point I think a 10 km x 10 km* city is a good mixture of being both an impressive size and suitable technology show-case.  Since we are always sub-dividing, we also need to start with an outer frame for the city that is big enough to house the tallest building we want.  To put this another way; setting the starting height of the city frame defines what the maximum height a building can be.  (It's a mindset that we need to really get into to).  A height of 200 m* is a good starting point; here's what it looks like:

Bounds of our 10 km x 10 km x 200 m city

*The engine is generally unit agnostic but I am going to stick to 1 Unit = 1 m for sanity's sake.

Space Filling

As stated previously, we are limited to rectangular sub-division of the city at the moment so it will all be a bit angular, but hopefully arbitrary splitting and plenty of adjacent zones with the same type will create interesting shapes none-the-less.

An algorithm I've used before to divide up a rectangular area is as follows:

1. If too small to subdivide, instance a zone and return.
2. If we aren't forced to subdivide (because we are too big), optionally instance a zone and return.
3. If we are too small in one direction then subdivide in the other direction, otherwise choose a direction.
4. Choose a split point such that no sub-regions are too small to instance.
5. Split into two parts and recurse into each part in turn.

This works well and was basically what was used in some early dungeon generation experiments.

Here is this algorithm implemented as a procedure in the Apparance Editor:

Recursive city zone subdivision procedure

This one is mostly fundamental operators (grey block), but the three white blocks are procedures; 'Content' is where we instance a zone, and the 'Zones' procedures are instances of the procedure itself and where the recursion happens.  There are two, one for each side of the split point.  It's a fairly complex procedure as they go, so if you have specific questions about it let me know in the comments below.  The longer lines crossing over behind other operators make it a bit messy but I have ideas about how this UI could be improved (another story).

Setting up the content procedure to just render a randomly coloured inside-out box and choosing suitable minimum and maximum zone sizes gives us a nice visualisation of the resulting zone layout.

City zone procedure output. Zone sizes from 500m to 2,500m.

City Structure

To model an interesting city layout I decided that some familiar planning approaches should be used.  We will start with some basic city district types and a mechanism for loosely specifying where they should be located in the overall city.  This can then be used to drive the classification of each zone as we divide up the city.

• 1 business zone (offices, skyscrapers)
• 1 commercial zone (shops, restaurants, tourist attractions)
• 1 industrial zone (chimneys, factories, and storage facilities)
• 1 space port zone (space ship docking and handling)
• Leisure zones (parks, monuments, and recreation areas)
• Residential zones (housing)

The last two are to be used to in-fill the remainder of the map and don't have any specific location.

Zones are going to form the highest level of city structure, and eventually each one will have many buildings and areas within it (probably called 'blocks', like city blocks).  For now, we are laying out the general plan.

Zone Distribution

For each instanced zone, we need to weigh up the various factors that affect what it could be:

1. Distance from each district centre.
2. Size of each district.
3. Weightings of the non-centralised district types.
4. A random factor to introduce variation and avoid clean district boundaries.

This is embodied in the following procedure:

Main zone type calculation procedure

Here, we use the zones location (centre point) to calculate weightings for the four centralised districts and then perform a weighted selection between them to generate a zone type (an index, 0 to 5).  We'll dig into each of these in turn:

Design Parameters

I've found it useful to group design-time constants into their own procedures.  These are effectively global variables, but with the option of making them parameterised later too.  Doing this makes it easy to find major control points by just looking for procedures named 'Design' in the procedure browser when it comes to tweaking the project later on.

Zone design parameters wrapped in their own procedure

Here we have grouped the zone min/max sizing values as well as all the location, size, and weighting parameters used in zone type selection.  For convenience, I have encoded the district size in the Z value of the Vector3 as only the X and Y are needed to specify a centre.  (Structure support is on the wish-list, but a long way off).

Zone Weighting

This is a fairly simple procedure that just takes a zone location and a district definition (labelled Zone Centre & Size here) and generates a weighting value.  The convention here is that you get a weight of 1 at the centre and a weight of zero at a distance of 'Size' from the centre.  This will generate negative values outside of that but this doesn't affect the weighted selection process.

Zone weighting calculation

Distribution

The distribution process is a general one and hence the procedure was created under the 'Maths' category (for want of a better location).  This is implemented as a chain of tests to see if each weighting value should replace the previous one.

Distribution evaluation via chained tests

Several outputs feed into the next test in the chain, with the final result being available at the output of the last test.

Individual distribution test procedure

The test procedure performs a weight adjustment according to the dithering parameter, randomly offsetting the weight a little to introduce artificial successes and failures when comparing against similar weights.  This introduces an amount of overlap between the district types.  The weight is compared with the previous 'best' weight and this selects whether its own index and weight are passed on, or the previous stages index and weight.

The Results

Updating the Content procedure to colourise the zone according to district type and putting all the above procedures into action produces the following, rather satisfying, result:

City zones classified into district types

Here you can clearly see four of the colours (red, yellow, green, and cyan) are centred around specific points in the map and the other two (blue and magenta) are mixed in around them.  The dithering has been adjusted to break up the zone boundaries and we can see some impinging of the residential and leisure district types on the centralised ones.

As the procedures were constructed, any element of random choice is driven from seed values passed down through each procedure.  This means that the seed value passed into the root procedure can be changed to affect the whole city.  Here are a series of district layouts from a series of seed values:

Varying the seed to produce different cities with similar structure

Each one still has the general layout desired, but introduces interesting variations on the same theme.  Later on we can experiment with parameterising the design parameters so that the locations, sizes, and weightings of the districts themselves can change from city to city.

Next

The next step is to look at how these zones are going to be connected, what sort of interfaces there will be (free travel, steps, ramps, barriers, etc.), and how we are going to break these blocks up further and start to introduce actual buildings.