Procedural city block

This uses a procedural method (grid subdividing, random building generation) to create the layout of a city.

A live WebGL version of the code runs at the top of the page.

The whole city comes from one 32-bit number. The program never stores the city: on every frame it runs the generator again from the same seed, and draws each box the moment the generator decides where it goes. Because the seed is fixed, the same city comes out every time.

A ZSystem test program

This is a test program for ZSystem, a design for generating a whole universe from seeds, where every object is a function that builds its parts from a random seed and can be made again whenever it's needed. The source is headed "ZSYSTEM TEST VERSION 0.1", and City, Suburb, Block and Building are object functions in that sense: each one takes a seed and a rectangle, and hands fresh seeds down to the parts it makes.

It's a tidied version of the first city test, ZSystem t2, which drew an extra seed for most of each building's boxes and so grew a different city from the same seed. Let's go through it in the order the program runs.

Window and view

The program opens a borderless window the size of the desktop, so it fills the screen, with a crosshair cursor. It asks for a double-buffered OpenGL pixel format with 16-bit colour and a 16-bit depth buffer:

pfd.dwFlags = PFD_SUPPORT_OPENGL | PFD_DOUBLEBUFFER | PFD_STEREO_DONTCARE | PFD_SWAP_EXCHANGE;
pfd.iLayerType = PFD_MAIN_PLANE;
pfd.iPixelType = PFD_TYPE_RGBA;
pfd.cColorBits = 16;
pfd.cDepthBits = 16;

Whenever the window gets its size, GL_Initialise sets up the view: a 60 degree field of view, a near plane 1 unit away and a far plane at 30,000, the depth test on, blending off and a black background. There's no lighting, no fog and no back-face culling (the culling lines are there, but commented out), so everything you see is flat colour.

glViewport (0, 0, width, height);
...
glMatrixMode (GL_PROJECTION);
glLoadIdentity ();
gluPerspective (60.0, (GLfloat)width/(GLfloat)height, 1.0, 30000.0);
glMatrixMode (GL_MODELVIEW);
glLoadIdentity ();
...
glDisable (GL_BLEND);
glEnable (GL_DEPTH_TEST);
...
glClearColor(0.0f, 0.0f, 0.0f, 0.0f);

The main loop is as simple as it gets. It handles any waiting Windows messages, then calls GameMain to move the camera and draw a frame, as fast as the machine will go:

g_exitflag = FALSE;
while (! g_exitflag)
{
  ProcessMessages ();
  GameMain (g_hWnd);
}

Random numbers

Everything random in the city comes from the program's own generator, ZS_Rand. Its state is four unsigned 32-bit words, and creating one spreads the seed across all four:

typedef struct _ZS_RAND {
  unsigned int a, b, c, d;
} ZS_RAND;
...
ZS_RAND *ZS_Rand_Create(int seed)
{
  ZS_RAND *r = (ZS_RAND *)malloc(sizeof(ZS_RAND));
  if(!r) return NULL;
  r->a = seed + 0x87123631;
  r->b = seed * 3;
  r->c = seed + 0x72319631;
  r->d = seed ^ 0x24121531;
  return r;
}

Two words get a different constant added, one gets the seed times three, and one gets it XORed with a third constant. So even a seed of 0 starts with three of the four words non-zero.

Each call to ZS_Rand does two things. First it stirs the state, then it mixes all four words into the number it returns:

unsigned int ZS_Rand(ZS_RAND *r, unsigned int max)
{
  r->d ^= (r->c<<9) + (r->a>>7) + (r->d&r->a);

  r->a += r->b>>1;
  r->b += r->c^0xF0F0A05;
  r->c += r->d;
  r->d += 0x35136613;

  unsigned int v = ( (r->a*7 + r->c*6)^((r->b<<13)-(r->d>>3)) );

  if(max == 0) return v;

  return v % max;
}

The stirring is a chain. d is XORed with c shifted up 9 bits, plus a shifted down 7, plus the bits that d and a have in common. Then a takes in half of b, b takes in c XORed with a constant, c takes in the new d, and d has a constant added, so it steps along by a fixed amount on every call on top of the mixing. Every sum simply wraps round at 32 bits, which is what C's unsigned ints do.

The value returned isn't any one of the words. It's a*7 + c*6, XORed with b shifted up 13 bits minus d shifted down 3. If you pass a max, it's reduced with % so it falls between 0 and max-1. Passing 0 means no limit, and you get the whole 32-bit number back, which is how the program makes new seeds.

Here's the very first call the city makes, from the seed the program starts with, 0xA749F86C:

That result, 0x2EE8D588, becomes the seed of the first suburb, which covers the whole city.

It isn't one of the well-known generators, and nothing says how long it runs before it repeats. For laying out a city that doesn't matter: the numbers only have to look unpredictable and come out the same every time.

ZS_Rand_Tween turns them into a number in a range. It asks for a whole number below a million and scales it, so the result runs from min up to just under max, in steps of a millionth of the range:

double ZS_Rand_Tween(ZS_RAND *r, double min, double max)
{
  double t = min + ZS_Rand(r, 1000000)*0.000001*(max-min);
  return t;
}

One seed per object

The generator isn't shared. City, Suburb, Block and Building each make their own ZS_RAND from a seed they're given, use it, and free it at the end. When one of them makes something smaller, it takes a full 32-bit number from its own generator with ZS_Rand(rand, 0) and hands that over as the new object's seed.

So the seeds form a tree. The city's seed fixes the seeds of its suburbs, each suburb fixes the seeds of what's inside it, and so on down to the slabs on the roofs. Every random choice in the city traces back to one number, and that number is fixed in GameDraw:

static k=0;
int citysize = 500;
//  k++;

int i=0, j=0;

zs_cubes = 0;
zs_buildings = 0;

//  for(j=-2; j<=2; j++) for(i=-2; i<=2; i++)
  City(0xA749F86C + (i<<17) + (j<<5) + k, -citysize/2 + i*citysize, -citysize/2 + j*citysize, citysize/2 + i*citysize, citysize/2 + j*citysize);

With i, j and k all 0, it makes one 500x500 city centred on the origin from the seed 0xA749F86C. The commented-out lines show where it could go. The loop would lay out a 5x5 grid of cities side by side, each with its seed nudged by its grid position, and k++ would add one to the seed on every frame, so a completely different city would grow on each one.

(There's also a Cube2 routine that would repeat every box in a 9x9 grid, 500 units apart. It's never called, and as written it calls itself rather than Cube.)

The seed is what makes the city repeatable, and here it really matters. The city is generated again from scratch on every frame, so if the generator gave different numbers each time, the buildings would change shape from one frame to the next. With the same seed, it makes the same choices in the same order, and the city stands still. Nothing about it is kept in memory between frames.

Suburbs

City hands the whole 500x500 area to Suburb, and that's where the grid subdividing happens. Suburb looks at the size of its area, and either cuts it into smaller suburbs and calls itself on each, or decides it's small enough to be a block:

smallx = (x2-x1) < 70;
smallz = (z2-z1) < 70;
smallrand = (ZS_Rand(rand, 100) < 20 && x2-x1 < 100 && z2-z1 < 100) || iter > 10;

if(smallrand) {

  Block(ZS_Rand(rand, 0), x1, z1, x2, z2);

} else if(smallx && smallz) {

  Block(ZS_Rand(rand, 0), x1, z1, x2, z2);

} else if(smallx) {

  z = ZS_Rand_Tween(rand, z1+23, z2-23);
  Suburb(ZS_Rand(rand, 0), x1, z1, x2, z, iter+1);
  Suburb(ZS_Rand(rand, 0), x1, z, x2, z2, iter+1);
...
} else {

  x = ZS_Rand_Tween(rand, x1+23, x2-15);
  z = ZS_Rand_Tween(rand, z1+23, z2-15);
  Suburb(ZS_Rand(rand, 0), x1, z1, x, z, iter+1);
  Suburb(ZS_Rand(rand, 0), x, z1, x2, z, iter+1);
  Suburb(ZS_Rand(rand, 0), x1, z, x, z2, iter+1);
  Suburb(ZS_Rand(rand, 0), x, z, x2, z2, iter+1);
...
  Cube(x-1, 0, z-1, x+1, 0.01, z+1, 0.4, 0.4, 0.4);
}

The rules, in the order they're checked:

• If the area is under 100 both ways, there's a one in five chance it becomes a block straight away, so blocks come in a mix of sizes.
• After more than ten levels of cutting, whatever is left becomes a block.
• If it's under 70 both ways, it's a block.
• If it's under 70 in one direction only, it's cut in two across the long way, at least 23 units from either end.
• Otherwise it's cut into four at a random point, at least 23 units from the left and top edges and 15 from the right and bottom.

The cuts are random but kept away from the edges, so the smallest piece any cut can leave is 15 units across. Where a four-way cut crosses, a 2x2 grey square goes down in the middle of the junction.

For our seed, the first suburb's one-in-five roll comes out at 74, which doesn't matter yet since 500 is far bigger than 100. The four-way cut lands at x = -225.6 and z = -158.9. That's only 24.4 units in from the left edge, just over the minimum of 23, which is why the city has a thin strip of empty blocks all the way down its left side.

From straight above, with x to the right and z down the page, you can follow the cutting: a cut runs right across the piece it divides, so the long straight streets are the early cuts and the short ones the late cuts. (This picture is from the WebGL version, with the camera moved high above the centre and given a narrow field of view.)

Blocks and streets

A block puts down a grey base slab 0.1 high, 3 units in from the edge of its area, then puts its buildings on top, 8 units in from the edge:

//  Put base

Cube(x1+3, 0, z1+3, x2-3, 0.1, z2-3, 0.5, 0.5, 0.5);

//  Put buildings

int r = ZS_Rand(rand, 100);

if(r < 10) {

  //  No buildings

  Building(ZS_Rand(rand, 0), x1+8, z1+8, x2-8, z2-8, 0.1);

} else if(r < 40) {

  //  Symmetrical array of buildings

  Building(ZS_Rand(rand, 0), x1+8, z1+8, (x2+x1)/2-4, z2-8, 0.1);
  Building(ZS_Rand(rand, 0), (x2+x1)/2+4, z1+8, x2-8, z2-8, 0.1);

} else if(r < 80) {
...

The comments name four kinds of block, but only one of them does anything different yet. In three blocks out of ten, the plot is split down the middle in x with an 8 unit gap, giving two buildings side by side. The other seven get one building covering the whole plot, including the "No buildings" case, which places a building just like the rest.

There's no code that draws a street. Each block's slab stops 3 units short of its edge, and so does its neighbour's, so between any two blocks there's a 6 unit gap where nothing is drawn and the black background shows through. That's the street. Between the edge of the slab and the building plot there's 5 units of pavement.

A Road routine is written to paint dashed white centre lines and a set of short stripes at one end, and Suburb has calls to it after each cut, but they're all commented out.

Buildings

Building is given a plot and the height to build from, 0.1 for the top of the slab. It makes its generator, picks a number from 0 to 99 for the kind of building, and picks a brightness, lit, between 0.8 and 1.0. Most of the building's colours are multiplied by it, so neighbouring buildings come out in slightly different greys:

zs_buildings ++;

ZS_RAND *rand = ZS_Rand_Create(seed);
...
int r = ZS_Rand(rand, 100);

double lit = ZS_Rand_Tween(rand, 0.8, 1.0);

if((x2-x1) < 10 || (z2-z1) < 10) {

  //  Nothing - too small

} else if(r < 40) {

  //  Basic building

  Cube(x1, y, z1, x2, y+ZS_Rand_Tween(rand, 10, 50), z2, 0.8*lit, 0.8*lit, 0.8*lit);
...

If the plot is under 10 units either way, nothing is built. Otherwise there are four kinds, each made only of boxes:

Roof grid

The roof grid picks a number of columns and rows, from 1 up to one less than a third of the width or depth, and divides the roof into that many cells. Each cell gets a thin slab, 1 unit in from each side of its cell, so there's a 2 unit gap between slabs, and one in twenty is left out at random:

h = ZS_Rand_Tween(rand, 20, 70);
Cube(x1, y, z1, x2, y+h, z2, 0.75, 0.75, 0.75);

ii = 1+ZS_Rand(rand, (int)((x2-x1)/3)-1);
jj = 1+ZS_Rand(rand, (int)((z2-z1)/3)-1);

w = (x2-x1)/ii;
d = (z2-z1)/jj;

for(j=0; j<jj; j++) {
  for(i=0; i<ii; i++) {
    if(ZS_Rand(rand, 100) < 95) Cube(x1+i*w+1, y+h, z1+j*d+1, x1+(i+1)*w-1, y+h+0.5, z1+(j+1)*d-1, 0.6*lit, 0.6*lit, 0.6*lit);
  }
}

Because the plot is at least 10 units across, the limit passed to ZS_Rand here is always at least 2, so it never hits the max of 0 that means no limit. The body of this kind is the one colour that doesn't use lit, so every roof-grid building is the same grey.

Stacked

The stacked building is the recursive one. It puts down a box, picks insets w and d of between a sixth and a third of the width and depth, and calls Building again on its own roof, with the plot shrunk by w at each side in x and d in z, and the base height at the top of the box:

h = ZS_Rand_Tween(rand, 20, 70);
Cube(x1, y, z1, x2, y+h, z2, 0.65*lit, 0.65*lit, 0.65*lit);
w = ZS_Rand_Tween(rand, (x2-x1)/6, (x2-x1)/3);
d = ZS_Rand_Tween(rand, (z2-z1)/6, (z2-z1)/3);
if(d > w*1.5) d = w*1.5;
if(w > d*1.5) w = d*1.5;

Building(ZS_Rand(rand, 0), x1+w, z1+d, x2-w, z2-d, y+h);

The two clamps keep w and d within 1.5 times of each other, so the upper part has a similar margin all round. Without them, the upper part would be between a third and two thirds of the width below; the clamps can only make an inset smaller, so it can come out a bit wider.

The new building has its own seed, so it chooses its own kind. It could be plain, have a roof grid or stripes, or be stacked again, and a tower keeps growing until it rolls a different kind or its plot drops under 10 units. That's where the tallest towers get their height. Every level counts in zs_buildings, so the 213 buildings the program reports include each tier of a tower, and the plots that were too small to build on.

Stripes

The last kind is a low box with strips across it. It works out which way the roof is longer, cuts that direction into a random number of equal parts, from none up to one less than a third of the length, and lays a strip 1 high across each part, 1 unit in from every edge:

h = ZS_Rand_Tween(rand, 10, 40);
Cube(x1, y, z1, x2, y+h, z2, 0.8*lit, 0.8*lit, 0.8*lit);

if(x2-x1 > z2-z1) {

  ii = ZS_Rand(rand, (int)((x2-x1)/3));
  if(ii > 0) {
    w = (x2-x1)/ii;
    for(i=0; i<ii; i++) {
      Cube(x1+i*w+1, y+h, z1+1, x1+(i+1)*w-1, y+h+1, z2-1, 0.7*lit, 0.7*lit, 0.7*lit);
    }
  }

} else {
...

Boxes and shading

Everything in the city is drawn by Cube, which takes two opposite corners and a colour. It draws the six faces as six GL_TRIANGLE_FAN quads, with a glBegin and glEnd round each one:

if(!drawBlack) glColor3f(r, g, b); else glColor3f(0, 0, 0);

glBegin(GL_TRIANGLE_FAN);
  glVertex3f(x1, y1, z1);
  glVertex3f(x1, y1, z2);
  glVertex3f(x2, y1, z2);
  glVertex3f(x2, y1, z1);
glEnd();
...
if(!drawBlack) glColor3f(r*0.95, g*0.95, b*0.95); else glColor3f(0, 0, 0);
...
if(!drawBlack) glColor3f(r*0.90, g*0.90, b*0.90); else glColor3f(0, 0, 0);

With no lighting, a box drawn in one colour would be a flat shape, and you couldn't tell its sides from its top. So Cube fakes the light. The top and bottom get the colour as given, the two faces that face along x get 95% of it, and the two that face along z get 90%. That's enough for the edge between any two faces you can see at once to show.

It's a fixed light, so it doesn't change as you fly around. The drawBlack flag makes every box black instead, and is only used by some commented-out drawing at the end of GameMain.

Two more experiments are commented out at the top of Cube. One gives every box its own colour, worked out from its number, and one darkens boxes with distance from the centre and skips any more than 2,000 units out.

Drawing a frame

GameMain does the whole frame. It moves the camera (see below), clears the screen, sets up the view and calls GameDraw, which runs the city generator. Each Cube call draws its box straight away, so generating the city and drawing it are the same thing:

glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

drawBlack = false;

glLoadIdentity();

glRotatef(-r2*0.2, 1.0, 0.0, 0.0);
glRotatef(-r1*0.2, 0.0, 1.0, 0.0);

glTranslatef(-x, -y, -z);
GameDraw(hwnd);
...
SwapBuffers(gl_dc);

The view is built the usual way for a fly camera, by moving the world instead of the camera. Read the calls from the bottom up, which is the order they apply to each vertex: move the world by minus the camera's position, turn it by minus the yaw about y, then by minus the pitch about x. That brings the camera to the origin, looking down -z, which is the way OpenGL looks.

The city comes to 656 boxes. At six fans of four vertices each, that's 15,744 glVertex3f calls a frame, plus a malloc and free for every generator. The depth test sorts out what's in front, so the order things are drawn in doesn't matter.

Every half second, GameDraw puts the counts in the window title, so you can see the size of the city: "City: 213 buildings, 656 cubes".

static int t = 0;
if(GetTickCount()-t > 500) {
  t = GetTickCount();
  char buf[50];
  sprintf(buf, "City: %d buildings, %d cubes", zs_buildings, zs_cubes);
  SetWindowText(hwnd, buf);
}

The same source file also has a set of Terrain_ functions for a fractal height field, which nothing in this program calls. They're the fractal terrain ZSystem was heading towards, filling in the empty terrain stubs of its zterrain test program, and the ZSystem article explains how they work.

The fly camera

The camera has a position, x, y and z, and two angles kept in mouse pixels: r1 for the yaw and r2 for the pitch, at 0.2 degrees a pixel. It starts 200 units above the centre of the city, turned 20 degrees and looking 50 degrees down:

double r1=20/0.2, r2=-50/0.2;
double x=0, y=200, z=0;
int moving = 0;

Mouse look

Windows only tells you where the cursor is, and the cursor stops at the edge of the screen. So the program keeps putting it back. On every mouse move it measures how far the cursor is from the centre of the screen, turns by that much, and warps it back to the centre with SetCursorPos:

case WM_MOUSEMOVE:
  POINT pt;
  GetCursorPos(&pt);

  if(pt.x != width/2 || pt.y != height/2) {
    r1 += (width/2-pt.x);
    r2 -= (height/2-pt.y);
    SetCursorPos(width/2, height/2);
  }

  return 0;

The warp makes a WM_MOUSEMOVE of its own, but with the cursor exactly at the centre, which is what the check is for. Moving the mouse right turns you right. Moving it down tilts the view up, like the stick of an aircraft.

Flying

Holding the left button sets moving to 1 and the right button sets it to -1. Letting go of either one sets it back to 0. SetCapture makes sure the window gets the button-up message wherever the cursor is:

case WM_LBUTTONDOWN:
  moving = 1;
  SetCapture(hWnd);
  return 0;

case WM_RBUTTONDOWN:
  moving = -1;
  SetCapture(hWnd);
  return 0;

case WM_RBUTTONUP:
case WM_LBUTTONUP:
  moving = 0;
  ReleaseCapture();
  return 0;

Movement is timed, so you fly at the same speed however fast the frames come. GameMain measures the milliseconds since the last frame with GetTickCount, caps it at 200, and moves 0.03 units per millisecond, which is 30 units a second. The cap means that a slow frame, or the very first one, moves you at most 6 units.

static int s = 0;
int t = GetTickCount();

int timediff = t-s;
if(timediff > 200) timediff = 200;
s = t;

{
  double vx = 0, vy = 0, vz = -timediff*0.03*moving;

  double wx, wy, wz;

  wx = vx;
  wy = vy*cos(0.2*r2*3.14159/180)-vz*sin(0.2*r2*3.14159/180);
  wz = -(vy*sin(0.2*r2*3.14159/180)+vz*cos(0.2*r2*3.14159/180));

  vx = wx*cos(0.2*r1*3.14159/180)-wz*sin(0.2*r1*3.14159/180);
  vy = wy;
  vz = -(wx*sin(0.2*r1*3.14159/180)+wz*cos(0.2*r1*3.14159/180));

  x += vx; y += vy; z += vz;
}

The step starts as a vector pointing straight ahead in camera space, (0, 0, -step), and is turned into world space: first by the pitch about x, then by the yaw about y. The first turn stores its z negated, and the second turn negates it back as it uses it, so overall these are two ordinary rotations. Worked through, the direction of flight is:

forward = ( -sin(yaw) × cos(pitch),  sin(pitch),  -cos(yaw) × cos(pitch) )

At the start, with a yaw of 20 degrees and a pitch of -50, that's about (-0.22, -0.77, -0.60): forwards and steeply down, so holding the left button straight away flies you down into the city.

The WebGL version

The WebGL version at the top of the page runs the same generator, ported line for line to JavaScript, so it builds exactly the same city: 213 buildings and 656 boxes, which it puts in the page title just as the original did in the window title.

JavaScript numbers aren't 32-bit unsigned ints, so every step of ZS_Rand folds its result back to 32 bits with >>> 0, and the multiplications use Math.imul so they wrap the way C's do:

function rand(r, max) {
  r.d = (r.d ^ (((r.c << 9) + (r.a >>> 7) + ((r.d & r.a) >>> 0)) >>> 0)) >>> 0;

  r.a = (r.a + (r.b >>> 1)) >>> 0;
  r.b = (r.b + ((r.c ^ 0xF0F0A05) >>> 0)) >>> 0;
  r.c = (r.c + r.d) >>> 0;
  r.d = (r.d + 0x35136613) >>> 0;

  var v = ((Math.imul(r.a, 7) + Math.imul(r.c, 6)) ^ ((r.b << 13) - (r.d >>> 3))) >>> 0;

  if (max === 0) return v;

  return v % max;
}

One thing is done differently. The original generates the city again on every frame, but since the seed never changes, the port only needs to do it once. Its Cube just records the corners and colour, and afterwards every box becomes 12 triangles in one vertex buffer, with the same 100%, 95% and 90% face colours built in. Each frame is then a single drawArrays call, and the shaders just pass the colour through, which is all the original's OpenGL state amounted to.

A page shouldn't take the cursor away, so instead of warping it back to the centre, the port turns by how far the mouse moves while it's over the city, with the same inverted up and down. During a drag it keeps turning even when the mouse leaves the view:

function look(dx, dy) {
  r1 -= dx;
  r2 += dy;
}
...
window.addEventListener('mousemove', function (e) {
  if (over || buttonsDown) look(e.movementX || 0, e.movementY || 0);
});

On a touch screen a finger down flies forwards and dragging turns. The few other differences:

• Esc quit the original, but a page can't close its browser tab, so it has no key.
• The original asked for 16-bit colour, where red and blue have only 32 levels each. The browser gives 8 bits per channel, so the 5% steps between faces come out more exactly.
• The original timed frames with GetTickCount, which counts from when Windows started, so its first frame always hit the 200ms cap. The port uses performance.now(), which counts from when the page loaded. Either way the cap keeps the first step small, and nothing moves until you press a button.
• The original filled the whole desktop. The port keeps its canvas at 5:4 inside its frame.