Future City: Update 2 - Get Yourself Connected

This time we look at creating interesting boundaries and useful connectivity information between all our city zones.

We want a city with interesting connectivity between zones

Connections

It is as much the interconnections as the spaces in an environment that make a place interesting. Now the zones are laid out we need to look at how they are connected. As we have a number of limitations in how we implement this I'm going to use a fairly basic connection model similar to one I have used before which was based on having a single connection pathway between adjacent areas, like each side of a room having at most one door. The algorithm had the following rules (expressed in terms of rooms and doors):

1. For your starting 'room', specify a door on each side (as desired).
2. Decide where to split based on door positions (i.e. don't split down a doorway).
3. When you split an area into two, always add a door into the new wall.
4. Recurse (go-to step 2) for both sides.

This produces a map where all the four outer doors are guaranteed to be connected, and you can reach every generated room.

Previous connectivity test, all rooms remain connected, various in-fill rooms.

When is a door not a door?

For our city, the door/wall terminology is going to be used to mean something slightly different:

1. A door corresponds to a region of free travel between areas, be it pedestrian, or vehicular.  This can mean either both sharing the same flat height level at the boundary, or that they both guarantee to match some underlying landscape shape at the boundary.
2. A wall corresponds to a barrier between areas, this can take several forms and may or may not have some sort of minimum barrier height.  This could be a wall, fence, steep drop, ditch, or just allow the back of a building to sit along that edge.

Barrier 'wall' (red) and open 'door' (green) segments along the side of an area.

This has an important effect on the splitting constraints; in that I want to allow splitting the open part in two by a boundary.  This will introduce more interesting topologies and should create greater connectivity than the 'single path to exit' algorithm above.

Splitting the area in two but with splitting of an opening allowed.

This does come at a cost though as the calculations needed to maintain connectivity are in-fact more complicated.  I decided to try and track access back to the four starting sides more thoroughly this time so that when splitting, we can work out if we have the option not to add a door, again increasing the connection graph variety.

Also, remember, we are splitting the city up into zones at the moment, these are fairly high-level, and quite large.  The blocked boundaries aren't going to be massive long walls, but opportunities for the next stages of subdivision to use them in different ways to partition the city up into lots of interesting spaces.  Similarly, a long gap may not imply a continuous connection, only that there be some form of connection along the length of each area.  Different areas may decide to achieve this in different ways, be-it steps, a ramp, a wall with an archway, and so-on.

No Structures

A quick aside about structure support in Apparance.  At the moment there are only a handful of fundamental data types you can pass around.  It is feasible to support arbitrary collections of these wrapped up into custom data types (structures) that can be passed around together more easily using single connection points and wires.  This would make propagating things like the access parameters and connectivity information much, much easier and also allow us to modify and add to this information without the huge amount of rewiring it would otherwise need.  Unfortunately, as it stands, I can stretch what I have and make a few design compromises enough that proper structure support isn't enough of a priority.  Something I have mused over a lot, definitely elegantly implementable, and definitely a future feature.  For now though we will pack out information into existing types.

To door or not to door?

Access

The presence of an opening in an side is represented by two horizontal values, the position of the left edge and the position of the right edge.  The absence of an opening is represented by either it's left edge being past the right end of the side, or the right edge bring past the left end of the side.

Opening specified by position of left and right ends.  Fully blocked side specified by either both at the right end of the wall or both at the left end of the wall.

To pass this information around we'll pack it into a Vector3, one of the fundamental types that is used to represent a 3D vector.  It has three floating point values X, Y, and Z of which we use X and Y to be the left and right edges of the opening.  The Z value isn't used yet, but will be needed when we want to encode some height information into the opening.

Packing of edge connectivity into a Vector3

Each area (or room) consists of four sides, each potentially accessible via openings, and so we need to track and pass around four of these Vector3 access values.  As a convention, these are referred to as West, East, South, and North (or their initial), and in that order (lower X axis, upper X axis, lower Y axis, upper Y axis).

West, East, South, and North sides of an area.

Connectivity

We also need to track connectivity available via each side of an area as we sub-divide.  Since we only need to track whether we can reach each of the four outer sides when we only need four bool values, or four bits of data.  This is much simpler information and rather than passing round a value for each side we can pack the information needed into a single integer as a bit-field.

How we pack information about which side of our area can provide access to which side of the city into a 32 bit integer.  A bit value of '1' means yes, we can get to it, and '0' means no we can't.

We will need add a few new bit-wise operators to support the packing and unpacking logic.  These are bit shift, AND/OR, and maybe a bit test operator too.  We can then build packing/unpacking procedures from these.

Connectivity packing and unpacking procedures

NOTE: I've been playing with clearer labelling of some of the simpler operators.  They can now have either large text, or characters from the Symbol font.  This combined with blank IO names and title suppression produces some nice compact visual representations.  You'll see some more below.

Implementation

We are now ready to implement this new functionality on top of the work we did last time splitting our city into zones. To start with I factored out the splitting process into own procedure, this helps manage the complexity of the already fairly complicated procedure that decides whether we should split and which way.

The newly factored out Split procedure in place

Do the splits

New split point, side calculation, and access logic are all in their own procedure now. To make the splitting logic simpler we abstract away the orientation of the split by 'normalising' the incoming area information and then 'de-normalising' it back afterwards.  This allows us to implement the split logic once and be able to use it for both horizontal and vertical splits.  The four sides are termed Left, Right, Bottom, and Top instead of the W.E.S.N. directions we use normally, to help distinguish normalised from de-normalised.

The split operation.  Mostly consisting of the logic to help us treat either orientation of split the same way.

Where to split

The split itself is broken into two parts, where to split, and then how to split.

First we need to work out where across the area are we going to split.  Since we are allowing splits across openings this is technically only limited by the need to ensure we don't create any area too small (min zone size design parameter).

Neat & tidy, tidy & neat

At this point it would be nice to also limit the minimum feature size we create during a split.  Since an arbitrary split could be any distance from an arbitrary opening edge then we can create very tiny openings and short walls.  It would be good to reduce this effect and we can achieve it in two ways.  One is to snap to some overall grid spacing, and second to snap to the edges of the openings in the two walls we are intersecting. The Split Point procedure handles all this for us.

Deciding on where to split the area and generating access information for either side of the split.

When splitting an area into two halves, the connectivity is going to be affected by whether there is an opening in the new wall.  To decide on this we need to work out where each new area is already connected to and use this as the potential new connectivity across the new divide.  By checking to see if each side of the divide includes the opening from the two sides being intersected and combining their connectivity with the connectivity of the opposite wall we get a connectivity value from each side of the split.

How to split

Deciding on the dimensions of an opening in the new wall is fairly straightforward.   We do however need to check whether we need to force an opening though to maintain connectivity between the city outer walls.

Side splitting and connectivity update.

Results

This update was implemented in two stages, first the access generation (wall/door) for each area, then the connectivity calculation and sub-division side opening decision making.  Here is an example where you can clearly see areas that end up disconnected from each other due to no connectivity management.

Disconnected regions (highlighted) present before connectivity checks were implemented

Once the connectivity system was in place it all started working properly.  Here is a selection of city zone layouts with connectivity information diagnostics display enabled.

Examples of a fully connected city

Next

Next we will start breaking down each of our zones into city blocks.  The process is similar to before, but each district type may have different requirements as the layout of each should differ to keep things interesting.

We will also starting thinking about where significant buildings are going to be placed since we will soon require a skyline silhouette to appear as we approach the lower detail end of our city.  Development is a process of adding detail, top-down, exactly analogous to approaching the city gradually from a distance.  Think about what you expect to see, and when.

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.

The Demo Plan

Milestones

I've reached the point where the technology needs a decent sized scene to stretch and test the features and it is also time to start working towards something stand-alone to show off the technology to the world.

The development of Apparance is an on-going timeline of features for which the term 'finished' has no real meaning.  I need milestones though, points along the way to take stock, gather what we have learned/achieved, and show it off properly.  To this ends I have had a 'Demo #1' entry in my planner for a while, which we have now reached.

We are now at Demo #1

Playing To Your Strengths

During my recent time off I decided to apply my thoughts to what form this demo project will take, what I hope to achieve, what technical adjustments, improvements, and indeed features it will need.  I spent some time thinking about the look and the style of the demo, as well as all the assets, effects, shaders, procedures, and techniques I will need to build it.

As a developing technology, the demo must play to the strengths of the engine, showing them off, whilst avoiding missing or weak areas.  I'd loosely list the key features (or lack thereof), and some of their implications, like this:

• Variable detail levels
• Distant and close objects (requires a large world)
• Get more detailed as you approach (show off detail blending)
• Large scale objects (show off dynamic range)
• Small set of primitives
• Basic surface shapes, e.g. cube, cylinder, sphere
• Angular objects and structures will be easiest to produce.
• May need to implement a few new ones
• Frame based space sub-division
• No support for polygon outlines/regions/sub-div yet.
• Rectangular layout of world, e.g. regular rooms only, lots of right angles
• Procedural generation/parameterisation
• Scene can be unique per view (shows off dynamic nature of engine)
• Could incorporate external input (shows off dynamic nature again)
• Huge variety of content needs to be shown (shows off parameterisation)
• Scalability
• Need a lot to explore/see (scene needs to be large)
• View needs to move round the scene.
• No texture support yet
• Flat surfaces for most of the world
• Have to use geometry to add surface detail (plays to engine strength)
• Pixel shader based surface detail can be used
• No shadow support yet
• Harsh lighting will show this up badly.
• A 'light and airy' scene would work best.
• No lighting support yet
• This is going to limit what will look good a lot.
• I'd like to explore static lighting techniques for local lighting effects (this would open up all sorts of possibilities and potentially be less work than a proper dynamic lighting system)
• No AI or scripting yet
• Will need to be a non-interactive experience.
• Need to hard code some temporary fly-through logic (needs to be dynamic to support variety of scenes)
• Will perhaps make a good screen-saver?
• No transparency yet
• I'd really like to get this in as glass allows transitions into interiors (showing off detail levels attainable)
• Combined with pixel shader effects this would also allow simple water features to be added to the scene.
• Implies a level of reflectivity though so would need to think about how much to support this (probably just single general cube-map reflection or specular rather than captured or true reflection.  May need basic texture support.)
• No fog support yet
• This will be needed to add depth to the scene, but is largely a shader based effect so something we can add relatively easily.
• Sky box
• Not really a technology feature as this can be implemented as geometry or shaders.
• Sun/moon can be shader generated to represent major light source direction.

Decision

Given all this, combined with my love of science fiction, I decided that a utopian science-fiction city would be a good choice of subject.  It is something that aligns with the limitations above:

• Regular (buildings are often angular and regular)
• Large scale (from skyscrapers to industrial zones to residential to space ports, all can be large and small)
• Bright (the utopian aesthetic lends itself well to shadow-less implementation)
• Roads (whilst roads are a nice feature of a city, I fancied avoiding them and making the building interconnections more futuristic, for pedestrians or flying vehicles)
• Surfaces (futuristic, high-tech structures are likely to be clean and smooth, the need for texturing reduced)
• Transparency (glass facades and water features really say 'futuristic' and 'utopia' to me)
• Shaders (general shader support would allow all sorts of polish like fog/sky/sun to be added as well as some simple water surface effects and procedural texturing)

Cities are popular choice when showing off procedural techniques and there are several sources of inspiration that have led me here, these are described below:

Inspiration

It's worth drawing attention to two significant city based works of procedural generation that really excite me:

Pixel City

I fell in love with Pixel City the moment I saw it.  A brilliantly executed exercise in procedural generation.  More pictures and information here:

• Video: Pixel City - Procedurally generated city
• Blog documenting its development: http://www.shamusyoung.com/twentysidedtale/?p=2940

Project Sprawl

Also; There has been some fairly sophisticated procedural modelling tools and tech being built for "Project Sprawl", a cyberpunk role-playing simulation, again an inspiration:

• City generation video: https://twitter.com/delacian/status/698922063675969537
• Scrap-book on tumblr: http://delacian.tumblr.com/

Just searching online for Procedural Cities yields lots of other projects in this vein.  I don't think another one is likely to hurt, and it gives me a good benchmark to aim for.

I've started to collect reference material on a Sci-fi Cities Pinterest page as a 'mood board' and ideas page.

I have previously been using skyscrapers as a test case and thinking about what structural components could appear on them in a traditional large city:

Sketching elements of contemporary skyscrapers

Whilst I was on holiday (sitting in the sun by the pool) I spent some time sketching ideas for more futuristic city elements too.

Sketching elements of a futuristic city

Whilst we were in France we took a day to visit the Futuroscope theme park which was full of examples of all sorts of futuristic buildings, technology, and experiences. It had some really quite interesting landscaping and architecture:

Walkways and water features at Futuroscope

Interesting buildings at Futuroscope

Fantastical architecture at Futuroscope

Features

Some features I'd like to see in the city include:

• Non-conventional skyscrapers
• Lots of 'sci-fi' surface detail
• Open plazas with angular water features
• Docked spacecraft
• Multi-level public spaces, stairs
• Monuments and arenas
• Glass facades revealing interior spaces
• Distant mountain ranges
• Variable time of day/night (static)
• Lots of technology; aerial masts, industrial complexes
• Names in lights on buildings
• Street and window lighting
• Automatic fly-through for use as screen-saver
• Manual control for exploration (fly-cam)

Once I have finished working on the detail blending system (for neat transitions between detail levels) I'll start work on the demo.  This is going to be the focus of the blog for a while, although I still want to mix in other things occasionally.  Next post I'll cover what I have to start with, and how I'm going to break down the work.

Audience Participation

As part of 'Future City' demo development I'd like to gather thoughts and ideas from you.  No matter how long ago this was posted, comments are welcome, please contribute ideas in the comments below.  I look forward to your thoughts :)