ZSystem

ZSystem is a design for generating a whole universe from seeds. Nothing is stored: every object is a function that builds its parts from a random seed, so any part of the universe can be made again, exactly the same, whenever it's needed.

The problem it solves is size. A universe is far too big to generate in one go and keep in memory, but you never need all of it at once. ZSystem only generates the parts the camera can see, caches them while they're in use, and lets them go when they're not, because any object can be made again from its address: its path down from the top.

Only the design notes and a skeleton of the library were written, and it was never finished as a library. Instead the idea was tried out by hand in three test programs, which all share the same seeded random number generator, ZS_Rand, and the same City, Suburb, Block and Building functions: ZSystem t2, zterrain and the procedural city block. Let's see how it works.

Seeds, params and addresses

The design notes start with a list of terms. Every object has a seed, which is all it needs to make its own random numbers:

The SEED of an object is a random seed which is used to create pseudo-random numbers.

It also has a param list, named pieces of data such as a colour or the region it covers. Its object function takes the seed and the params and makes a list of subobjects, each with params of its own:

An object function creates a set of subobjects from its SEED and PARAMs. This set is cached using the ADDRESS as a key and the object function is only called again if that entry has been removed from the cache.

An object's index is its place in its parent's list, and its address is the string of indexes on the way down to it from the top. So 1.2.0 is the first subobject of the third subobject of the second object in the universe. The address is all you need:

The ADDRESS of an object is a string of INDEXes. This uniquely defines it and its PARAMLIST - object can be generated from this information.

That works because an object function depends only on its seed and its params. To make object 1.2.0 again, run the universe's function and take subobject 1 from its list, run that one's function and take subobject 2, and so on. Every step comes out the same as it did the first time, so you end up with the same object.

At the top of the tree is a single universe object:

You create a ZSystem with a specific entrypoint which is a universe object function. And then you can render this universe from any viewpoint.

The notes end with a sketch of what an object function would look like in C. It reads its region, sets two params for itself, then makes one subobject with the current params and another with a region of its own:

void MySubObject(ZSYSTEM zs)
{

}



void MyObject(ZSYSTEM zs)
{
  ZREGION *r = ZsGetParam("region");

  ZSystem_Param(zs, "colour", 0xFF6699);
  ZSystem_Param(zs, "shape",  5);

  ZsObject(zs, MySubObject);

  ZSystem_Begin(zs, ZSubObject);
    ZSystem_Param(zs, "region", r2);
  ZSystem_End(zs);

  // ...
}

It's a sketch rather than working code: r2 is never set, and it mixes two naming styles, ZsGetParam and ZsObject next to ZSystem_Param, ZSystem_Begin and ZSystem_End. The text above it leaves two questions open, one in a sentence that stops part way: "If a function does not produce an object list then", and "At the lowest level objects give way to primitives. How does this work?"

The skeleton library

ZSystem.h and ZSystem.cpp are the start of the library. Its interface is five functions:

Behind them are a private ZSystem_Render_Recurse, which comes next, and ZSystem_Cache_Create and ZSystem_Cache_Add, which are empty. The types say what an address is and what the ZSystem carries round:

typedef struct _ZSYSTEM_ADDRESS {

  DWORD length;
  DWORD index[1];

} ZSYSTEM_ADDRESS;
...
typedef struct _ZSYSTEM {

  ZSYSTEM_CACHE *cache;          //  The cache for this ZSYSTEM
  ZSYSTEM_PARAMLIST *paramlist;  //  The paramlist for the current object
  ZSYSTEM_ADDRESS *address;      //  The address of the current object

} ZSYSTEM;

The address is declared with one index, the usual C way of putting a variable-length array at the end of a struct: you allocate as much room as the address needs and index past the end. The ZSYSTEM is the "global state" the notes talk about, passed to every function so that it knows which object it's working on.

It's a skeleton in the true sense, and wouldn't compile as it stands. ZSystem.h and ZSystem.cpp each define their own ZSYSTEM and ZSYSTEM_CACHE: the header's ZSystem has a uniproc for the universe function and its cache is a linked list of items, while in the .cpp the cache is an empty struct. The param list is declared with typdef, ZSystem_Render calls a Render_Object_Recurse that doesn't exist, and ZSystem_Param and ZSystem_Object aren't given a ZSystem to work on.

The cache and the cull test

The cache is what makes this fast enough to use. The notes give it two operations, "Given an ADDRESS returns an OBJECTLIST if one is stored for that ADDRESS" and "Can add an OBJECTLIST for a given ADDRESS", and a limit:

The CACHE is a set of OBJECTLISTs stored against their ADDRESSes. The cache is a fixed size and a least recently used scheme will probably be used to expire entries when space is needed.

Each ZSystem has its own cache, so two universes in one program don't share one. Nothing in it is precious. An entry that's thrown away to make room can always be made again from its address, at the cost of running the object functions on the way down to it.

Rendering is a walk down the tree. The render loop in ZSystem.cpp is only an outline, but it shows the plan: make an object's subobjects if they aren't in the cache, then go down into each one that passes a cull test.

void ZSystem_Render_Recurse(ZSYSTEM *zs, ZSYSTEM_OBJECTPROC objproc)
{
  //- Check if this object is still cached

  if(!cached) {

    //- Set environment for rendering this object

    //- Call object function

    objproc(zs);

  }

  //- Render each subobject if it passes a cull test

  ZSystem_Render_Recurse(...);

}

The cull test is what lets the universe be as big as you like. Say the camera can only see object 1, and inside it only 1.1 and 1.2. The walk makes the universe's list of 0, 1 and 2, finds that 0 and 2 are out of view and never calls their functions, makes 1's list, culls 1.0 and 1.3, and goes on down into 1.1 and 1.2. Nothing under 0, 2, 1.0 or 1.3 is ever generated, however much there would be.

Fly somewhere else and different branches pass the test. The ones you've left stop being used, become the least recently used entries and fall out of the cache, so the memory needed depends on the size of the cache, not the size of the universe.

ZS_Rand

The test programs don't use ZSystem.cpp. They do the same thing by hand with plain functions, and the first thing they need is a random number generator whose whole state comes from one seed. C's rand() has one hidden state for the whole program, so the numbers an object got would depend on everything drawn before it, anywhere. A ZS_RAND is something you create from a seed, so every object gets a stream of its own:

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;
}
...
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;
}
...
double ZS_Rand_Tween(ZS_RAND *r, double min, double max)
{
  double t = min + ZS_Rand(r, 1000000)*0.000001*(max-min);
  return t;
}

The seed is spread across four 32-bit words with different constants. Every call stirs them with shifts, adds and XORs, then mixes all four into the result, wrapping round at 32 bits as C's unsigned ints do. Asking for a maximum of 0 gives the raw 32-bit value, which is how a parent makes seeds for its children. ZS_Rand_Tween turns a draw into a number between two values, in steps of a millionth of the range.

Let's make one from the seed 1. ZS_Rand_Create sets the words to a = 0x87123632, b = 3, c = 0x72319632 and d = 0x24121530. The first call stirs them and comes out at 0xEBB93890, which is 3,954,784,400, so ZS_Rand(r, 100) gives 0. Here are the first eight calls of ZS_Rand(r, 100) for the seeds 1 and 2:

Make another generator from the seed 1 and it gives 0, 74, 69, 33 and the rest again, every time. That's what makes an object repeatable. Its function makes the same generator from the same seed, so it makes the same choices in the same order and hands the same seeds to its children.

The order of the draws matters as much as the seed. Add or remove one draw and everything after it changes, and that even includes the order the arguments of one function call are worked out in, which C++ leaves to the compiler. ZSystem t2's plain building draws a seed and its height in the same call:

    BuildingCube(ZS_Rand(rand, 0), x1, y, z1, x2, y+ZS_Rand_Tween(rand, 10, 50), z2, 0.8*lit);

MSVC works out arguments from right to left, so the height is drawn first. Build it with a compiler that goes the other way and you get a different city from the same seed.

Object functions and the seed tree

The test programs build their city the ZSystem way, out of object functions. City, Suburb, Block and Building each take a seed and some params, here a rectangle on the ground. Each makes its own ZS_RAND from the seed, makes its choices, and calls the next function down for each part it creates, with a fresh seed drawn from its own generator:

void City(unsigned int seed, double x1, double z1, double x2, double z2)
{
  ZS_RAND *rand = ZS_Rand_Create(seed);

  //  Place floor poly

//  Cube(x1, -1, z1, x2, 0, z2, 0.1, 0.1, 0.1);

  //  Divide into blocks

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

  ZS_Rand_Delete(rand);
}

A suburb either becomes a block or cuts itself into two or four smaller suburbs, a block puts one or two buildings on its plot, and some buildings put another building on their roof. The seeds form a tree, and every random choice in the city traces back to the one number GameDraw passes to City:

A child's seed depends only on its parent's seed and params and on how many draws the parent made before it, which is fixed by the child's place in the list. That's what an address needs: follow the same path of indexes down from the city's seed and you always arrive at the same seed and the same rectangle.

Here's how the design's terms come out in the test programs:

So the test programs try out the generating half of the design, and leave the cache and the cull test for later. How the suburbs are cut and the four kinds of building are put together is in the Procedural city block article, which goes through the generator step by step.

ZSystem t2

ZSystem t2 is the first test: one 500x500 city grown from the seed 0xA749F86C, made entirely of flat-coloured boxes, which you fly over with the mouse.

The window and OpenGL setup come from a small Windows OpenGL helper library written by Mark Lord at Gremlin Interactive: Winmain.cpp opens the window and runs the main loop, and qe_ogl.cpp sets up the pixel format and the GL state. The window is a borderless popup the size of the screen, cut down to 800x600 on a bigger screen, and centred. It asks for 16-bit colour and a 16-bit depth buffer, with a 60 degree field of view, the near plane at 1 and the far plane at 30,000. The depth test is on and there's no lighting. The shading on the buildings comes from Cube, which draws the sides of each box at 95% and 90% of its colour.

The city functions are an earlier version of the ones in the procedural city block. Most of the boxes a building puts up go through BuildingCube, which takes a seed of its own for features it doesn't have yet, and next to it is the start of a BuildingWindow for window sills, which stops half way through its first line and isn't called anywhere:

void BuildingWindow(unsigned int seed, double x, double y, double z, int orientation)
{
  //- Draw sill

  Cube(x-0.6, y, z, x+0.6

}
...
void BuildingCube(unsigned int seed, double x1, double y1, double z1, double x2, double y2, double z2, double lit)
{
  //- Draw building

  Cube(x1, y1, z1, x2, y2, z2, lit, lit, lit);

  //- Draw features

}

Nothing uses that seed, but drawing it moves every draw after it along by one. So the same seed grows a different city here than in the tidied version: 216 buildings and 597 cubes, against 213 and 656.

The city isn't stored anywhere. Every time GameDraw runs, it calls City with the same seed and the whole city is generated again, straight into OpenGL calls:

void GameDraw(HWND hwnd)
{
  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);

The two commented-out lines show where it could go next: k++ would change the seed on every frame and grow a new city each time, and the loop over i and j would lay out 25 cities in a 5x5 grid, each with its own seed made from its position. Every half second, GameDraw puts the counts in the window title.

Growing the whole city again for a picture that hasn't changed is wasted work, so GameMain only draws when the view has turned or you're flying. The rest of the time it returns straight away and the last frame stays on the screen:

void GameMain(HWND hwnd)
{
  if(oldr1 == r1 && oldr2 == r2 && !moving) return;
  oldr1 = r1; oldr2 = r2;

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

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

One side effect: the timer s only moves on when a frame is drawn. So if the view has been still for a while and you start flying, the first step uses the full 200ms cap, a jump of 6 units, before it settles down to the real time between frames.

zterrain

zterrain is ZSystem t2 turned into the start of a terrain test. Its city functions are already the tidied ones, calling Cube directly with no BuildingCube, but the city is switched off: the City call is inside a comment block, together with the loop that would make 25 of them, which here isn't commented out. Two stubs wait for the terrain: MakeTerrain, with a flag to stop it running twice, and GetTerrainHeight, which for now says the ground is flat everywhere:

bool maketerrain=false;

void MakeTerrain()
{
  if(maketerrain) return;

}



float GetTerrainHeight(float x, float y)
{
  return 0;
}

Instead of the city, GameDraw plots three axis bars crossing at the origin: red along x, green along y and blue along z, each 20 long and 2 thick. They sit inside a commented-out loop that would put a set every 25 units, 21 each way:

    //- Plot axes

    i=0; j=0; k=0;

/*
  for(k=-10; k<=10; k++)
  for(j=-10; j<=10; j++)
  for(i=-10; i<=10; i++) {
*/
    Cube(i*25-10, j*25-1 , k*25-1 , i*25+10, j*25+1 , k*25+1 , 1, 0, 0);
    Cube(i*25-1 , j*25-10, k*25-1 , i*25+1,  j*25+10, k*25+1 , 0, 1, 0);
    Cube(i*25-1 , j*25-1 , k*25-10, i*25+1,  j*25+1 , k*25+10, 0, 0, 1);
/*
  }
*/

Then comes a stand-in for the terrain, a 41x41 grid of yellow 2x2x2 cubes:

  //- Make terrain if necessary

  MakeTerrain();

  //- Draw terrain

  float x1, z1, x2, z2;

  for(i=-20; i<=20; i++) for(j=-20; j<=20; j++) {

    float d = 2*sqrt(i*i+j*j);
    x1 = i*d; z1 = j*d;

    Cube(x1-1, z1-1, -1,   x1+1, z1+1, 1,   1, 1, 0);

  }

The spacing isn't even. Each cube's grid position (i, j) is multiplied by d = 2·sqrt(i² + j²), which is twice its own distance from the middle in grid steps, so it ends up 2(i² + j²) from the centre. Along an axis the cubes sit at 0, 2, 8, 18, 32, 50 and so on, out to 800, and the corners are at (1131, 1131). Near the middle they're packed together, and further out they spread apart:

The loop calls the second coordinate z1, but it goes into Cube's y argument, and the cube's z runs from -1 to 1. So the grid doesn't lie on the ground: it stands upright in the x-y plane, like a wall facing along z.

The camera starts at (-100, 100, -100) with the same angles as the city, which points it away from the wall, so the screen is black until you turn round with the mouse:

The rest of the differences are small:

The procedural city block

The procedural city block is the third test program, and its source is headed "ZSYSTEM TEST VERSION 0.1" just like the other two. It's the same city with the code tidied up: BuildingCube and BuildingWindow are gone, the city is switched back on, and it redraws on every frame. Without BuildingCube's extra seeds, the same seed gives a city of 213 buildings and 656 cubes. It fills the whole desktop, and its mouse look tilts the other way, so moving the mouse down tilts the view up. Its own article goes through the generator in detail, from the first suburb cut to the four kinds of building.

Its source also has what zterrain was waiting for. MakeTerrain and its flag have become Terrain_Startup and terrain_startup, and GetTerrainHeight, which returned 0, has become Terrain_GetHeight, a working fractal height function, with functions to draw the ground beside it. Nothing in the program calls them yet.

Fractal terrain

The terrain is a height field: give Terrain_GetHeight a point on the ground, x and z, and it returns the height there. Like everything in ZSystem it stores nothing. Each height is worked out from scratch from the position alone, so any part of the ground can be made in any order and always comes out the same.

The random numbers come from Terrain_PosRand, which hashes a position into a number from 0 up to 1. Here the position takes the place of a seed:

float Terrain_PosRand(float x, float z)
{
  unsigned int a = x*984729;
  unsigned int b = z*735161;

  unsigned int r = (a^b)-(a*b) + ((a >> 10)&(b << 2)) - ((a << 2)|(b >> 9));

  return (r%18378276)/18378276.0;
}

Each coordinate is scaled up by a large constant and turned into a whole number, the two are mixed with an XOR, a multiply, shifts, an AND and an OR, and the result is reduced to a fraction. At (0, 0) both numbers are 0 and so is the result, so the ground at the origin always has a height of 0. Along the line x = 0 the mixing comes down to b - (b>>9), which simply grows with z for the first 25 units: 0.399 at z = 10 and 0.798 at z = 20.

Terrain_GetHeight starts with the 20x20 cell the point is in, and a random height from Terrain_PosRand at each of its corners. Then it halves the cell, keeping the quarter that holds the point, and makes the corners of the new window from the old ones. Each new point on an edge is the average of the two ends of that edge plus a random bump, and the new centre is the average of two opposite corners plus a bump:

  float scale = 20;

  float sx = scale*((int)(x/scale));
  float sz = scale*((int)(z/scale));
...
  r00 = Terrain_PosRand(sx, sz);
  r01 = Terrain_PosRand(sx+scale, sz);
  r10 = Terrain_PosRand(sx, sz+scale);
  r11 = Terrain_PosRand(sx+scale, sz+scale);

  float hscale = 1;

  for(i=0; i<15; i++) {

    scale *= 0.5;

    //- If it's less than half way then bring the window back else move it forward

    float nr00, nr01, nr10, nr11;

    if(sx+scale > x) {
      if(sz+scale > z) {

        nr00 = r00;
        nr01 = 0.5*(r00+r01) + hscale*Terrain_PosRand(sx+scale, sz);
        nr10 = 0.5*(r00+r10) + hscale*Terrain_PosRand(sx, sz+scale);
        nr11 = 0.5*(r00+r11) + hscale*Terrain_PosRand(sx+scale, sz+scale);
...
    }

    r00 = nr00; r01 = nr01; r10 = nr10; r11 = nr11;

    hscale *= 0.2;
  }

  //- TODO: Bilinear filter to get height

  float r = r00;

  //- Return height

  return 10*r;

The bumps shrink to a fifth of their size at each level while the window halves, so the big hills come first and finer and finer detail is added on top. This is midpoint displacement, the usual way of making fractal terrain, done here for one point at a time.

Let's find the height at (5, 5). It's in the cell from (0, 0) to (20, 20), whose corners hash to 0, 0.483, 0.798 and 0.286. At the first level the window halves to the quarter from (0, 0) to (10, 10), and its three new corners each get a bump of up to 1. At the second level it halves again. The point isn't less than the halfway mark of 5, so the window moves on to the quarter from (5, 5) to (10, 10), and its corner at (5, 5) is new: the average of the diagonal corners 0 and 0.653, plus 0.2 × 0.797, which makes 0.486.

From then on (5, 5) is the window's top-left corner at every level, so it keeps that value, and the height is 10 × 0.486 = 4.86. A point that isn't on a grid line goes down all 15 levels, to a window 20/32768 of a unit across, and takes the value at its top-left corner. The TODO is where the four corners would be blended; at that size it hardly matters.

Every new point gets the same value whichever window makes it. An edge point depends only on the two ends of its edge and its own position, and a centre on two opposite corners and its position, so neighbouring points agree and the ground joins up. The bumps are never negative, so the heights never go below 0. Sampled every half unit over an 80x80 square from the origin, they run from 0 to just under 16.

Two things show it isn't finished. The cell is found with (int)(x/scale), which rounds towards zero, so for a negative x or z the cell starts on the wrong side of the point and the window never holds it. Terrain_DrawSquare simply skips anything below 0. And it's slow: each height takes 49 calls to Terrain_PosRand, four for the corners and three at each of the 15 levels, with nothing cached.

The drawing functions are there too. Terrain_Draw covers an 81x81 patch of 1x1 squares from the position it's given, each one a fan of four corners lifted to their heights, with greys of 0.3, 0.6, 0.9 and 0.6 at the corners. That's 26,244 heights and nearly 1.3 million hashes for each frame. A commented-out version lays the ground out on rings instead, using Terrain_GetPoint:

void Terrain_GetPoint(int i, int j, float xo, float zo, float *x, float *z)
{
  float d = i+i*(i-1)/14;
  float a = j*3.14159/16;

  *x = xo+d*sin(a); *z = zo+d*cos(a);
}

There are 32 spokes, and the rings get further apart the further out they go. i*(i-1)/14 is worked out in whole numbers, so the first four rings are 1 unit apart, then the gaps grow to 2, 3 and 4, out to a radius of 47. Where zterrain's GetTerrainHeight returns 0, this returns a real height.

The fly camera

All three programs fly the same way. r1 and r2 are the yaw and pitch, counted in mouse pixels at 0.2 degrees each. On every mouse move the cursor is put back at a fixed point and the distance it moved is added on, so you can keep turning as far as you like without the cursor reaching the edge of the screen. The buttons set moving to fly forwards or backwards:

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

      if(pt.x != midx || pt.y != midy) {
        r1 += (midx-pt.x);
        r2 += (midy-pt.y);
        SetCursorPos(midx, midy);
      }

      return 0;

    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;

The camera starts at r1 = 20/0.2 and r2 = -50/0.2, turned 20 degrees to the left and looking 50 degrees down. Each frame GameMain takes a step of (0, 0, -s) straight ahead in camera space, where s is the speed times the milliseconds since the last frame, and turns it by the pitch and then the yaw. For pitch p and yaw y the step works out as:

( -s·cos p·sin y,   s·sin p,   -s·cos p·cos y )

The view turns the world by the same two angles the opposite way round, so this is exactly where the camera is looking, and you fly where you look. At the starting angles each unit of travel is (-0.22, -0.77, -0.60): mostly down, and a little to the left.

The WebGL versions

The ports of ZSystem t2 and zterrain are plain WebGL 1 with no libraries. The originals send every face with glBegin and glEnd on each frame, but since the scene never changes, the ports build it once at start-up and record each triangle fan as two triangles in a vertex buffer, in the original order. Each frame is then a single draw call.

ZS_Rand is rewritten to wrap at 32 bits the way an unsigned int does in C, and the plain building draws its height before its seed, as MSVC does, so the city comes out with the same 216 buildings and 597 cubes. A small shader passes the glColor3f colour straight through, and the matrices are built by hand to match gluPerspective, glRotatef and glTranslatef. ZSystem t2's port keeps the redraw check too. A few things can't be the same:

• A page shouldn't take the cursor away, so instead of pinning it with SetCursorPos, moving the mouse over the view turns it by the same amount.
• Escape closed the program, but a page can't close its browser tab, so it has no key.
• The browser chooses the colour and depth buffers, rather than the 16-bit ones the originals asked for.
• The clock is performance.now(), which counts from when the page loaded rather than from when Windows started. The step is capped at 200ms either way, so it doesn't show.
• zterrain keeps the shape of its window's client area once the title bar and border are taken off, 792x573.
• The city counts go in the page title, which you can see when ZSystem t2 is opened in its own window.