A Case Of Non-Randomness - Part 2

The Problem

I was just starting to set up the procedures needed for rows of buildings when I hit a problem.

Bad randomness showing up in row of buildings

These are supposed to be random heights!  I've had a nagging feeling that my random number generation operators weren't working properly and had noticed a few artefacts before, but dismissed them as me being overly sensitive to patterns.  This horrible patterning however tipped me over the edge and I had to investigate.

Visualisation

A great way to sanity check random numbers is to visualise a sequence as a grid of intensity values (see Runes blog post again).  So I put together a couple of nested procedures to build a 2D grid of tiles, each coloured black-to-white according to the random function under scrutiny.

Random number sequence visualisation using geometry

This instantly revealed unpleasant patterns in the number sequences.  Trying different seeds showed that most of them seemed to have regular repeating pattern or clearly be restricted to lower or upper value ranges.

Bad patterning in the random number generation

Investigation

My first avenue of investigation was to reproduce the algorithm explicitly in the test procedure using the same sequence of operations as the random generation library code.

Explicitly implemented random number generator

I hoped that this would allow me to play with the algorithm to find the bug.  However, this version produced very nice random values, with no discernible patterns.  Carefully picking through the implementation I couldn't see any functional difference.

Next I added numerical display of the seed and value for each tile and zooming in on the start of the first row I noticed that they did agree for a few values, before diverging.  This seemed to coincide with the seed (handled as a signed integer) going negative.  I wasn't sure how this would affect the algorithm though so I switched to debug build and stepped through the for this case.

After some debugging runs and breaking open the algorithms a bit I discovered what was going on.

Cause

My entropy extraction macro (see Hash part of Random Value Generation Process in the previous article) uses right shift operations >> to re-align the overlapping bits, but I had forgotten that this will perform a sign extended shift if the operand is a signed value.  That is, if the most significant bit is 1, indicating a negative number, then 1's are shifted in instead of 0's.  This situation caused the extraction algorithm to XOR chunks of 1's into the seed values.  XOR has the interesting (and normally useful) property that successive applications of 1's causes toggling.  This fact combined with shifts used set up a repeating oscillation in some chunks of bits.  It was completely believable that this could produce the heavily striped and range limited results I was seeing.

Fix

The fix here was relatively straight forward as the behaviour of >> on unsigned integers always shifts in zeros into the upper bits, as was actually required.  Interestingly, the reason we didn't see this problem on the explicit implementation was that I had made sure the shift operation always used the unsigned shift.

Casting the operands to unsigned integer prior to each shift fixed this and the two implementations now agreed, AND also produced the randomness they were designed to generate.

Much better random sequences

Slight Red Herring

Going back to the building height problem I discovered that this hadn't fixed it, the result was exactly the same!  So, I had managed to find and fix a real problem, just not the one that was causing my issue.  Oops!

The Real Culprit

Checking the building height calculation I realised that I was relying on the variant parameterisation of the Random Twist operator to generate random values from the building index along the row.  The reason it was designed to work like this is that I needed a way to generate unique seeds for each building from the single seed provided to the row as a whole.  The only distinguishing information the buildings have at this point where they are in the row, i.e. their index.  The twist operation seemed to be perfect here as the variant input was intended for exactly this sort of operation.

Using twist variant input to derive per plot variation in a row of houses

Unfortunately this didn't seem to produce very good results for a sequence of successive variant values.  Adding a visualisation of the twist operation with the tile index driving the variation input again showed up this lack of randomness.

Patterning from the Random Twist operator

In hindsight this is one of the issues Rune talks about in his article; close or sequential seeds don't necessarily produce sequences that are very random relative to each other.  He suggests a decent hash of the input to better seed the sequences.

A Better Twist

This time the patterning wasn't as strong, but it was certainly there.  Looking into the Twist implementation I realised the mixing method of the variant value was far too simplistic and I was relying on small changes in variant input to produce significant changes to the output seed and hence number sequence.  This was obviously not the case and I needed a better mixer.

// jump to another point in the

// random stream (parameterised)

int Random::Twist( int input, int variant ) 

{ 

  return Random::Algorithm::Next_LCG_ANSIC( input^variant ); 

}

After some research, I realised that the property I was after is referred to as 'avalanche', i.e. where small input changes cause large output changes, and was a common desirable feature of hashing algorithms.  Again, rather than investigate and implement my own solution I chose a publicly available integer hashing function that claimed very good avalanche characteristics.

Replacing the mixer generation with this in the Twist operator proved very successful and finally achieved a good random variants again.

Much improved twist variant output

Fixed Buildings

Going back to my row of buildings again, with the above changes produced much, much more satisfactory results.

That's much better

I expect to see improvements throughout my projects as a result of these fixes, some will be more subtle than others.  I'm glad I took the time to investigate this as it's resolved a niggle that I couldn't quite put my finger on.

Epilogue

Procedural generation is typically required to be completely deterministic so that, for example, every time you re-visit a game the world is familiar to you, or that every player of a game sees the same world.  This is an important feature of a game such as No Man's Sky, a vast, hugely varied procedural universe that is the same for every player.

Fixing the bugs in my random number generation operators means I have changed the behaviour of something fundamental to all the generation processes across my projects.  This in turn means that all the content they generate will now be different, the content they generated before has been lost.  Forever.

The deterministic nature of the processes involved in procedural generation, combined with their complexity means they are hugely susceptible to the butterfly effect, that small changes to any part (all parts are effectively inputs) can have huge effects on the output.

I have often wondered how many times Hello Games has made changes to No Man's Sky that have completely invalidated the current universe it is set in.  How many versions of universe have they gone through to get to the one we play?  I dread to think how much of a problem this is for ongoing work where they can't change or even fix bugs in so much of the game for fear of breaking the universe.

“There is a theory which states that if ever anyone discovers exactly what the universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable."

"There is another theory which states that this has already happened.”

- Douglas Adams, The Restaurant at the End of the Universe

A Case Of Non-Randomness - Part 1

In preparation for a post about a randomness bug I found, let's look at some of what's going on behind the scenes in Apparance with random number generation, propagation, and manipulation.

Premise

The random number generation in Apparance is based on two main principals:

1. Generating a repeatable sequence of random values.
2. Branching of random number sequences.

These are embodied in two operators you can build into your procedures, the "Random Value" operator (with Float and Integer variants), and the "Random Twist" operator.

The two Random Value operators and the Random Twist operator

Both take a seed* value as input and produce a new seed value as an output.  The Value operators also take Range inputs and produce a Value output.  Seeds are signed (32 bit) integers and so are compatible with the normal integer connection type.

The Value operators are fairly self-explanatory but the need for the Twist operation will be explained further down.

* I've adopted the convention of using the # symbol at the end of an input or output name to indicate a seed value. 

Random Sequences

When a procedure needs some variation, it will usually be parameterised by a seed value such that it can be recreated in exactly the same way by providing the same seed, or different versions of it created by providing different seed values to each instance.

Seeding a procedure.  Same seed; same output, different seed; different output.

Within the procedure, where multiple values may be needed, these can be obtained by calculating a sequence of random numbers from the given starting seed.  Each Random Value operator takes its seed from the seed output of the previous one.  This way each operation is provided with a different seed from which to generate its output value.

Generating multiple values within a procedure

Multiple Seeds

If you want to create a collection of similar, but varying, objects you would need to instance one procedure multiple times, each with a different seed.  So, how do you generate these seeds?

A simple approach would be to just use the same random generation sequence the Random Value operator uses to get each new seed (discarding the values they also generates).  However, there is a big problem with doing this; if internally your procedure uses several random values from the random sequence, the set for each instance can overlap to some extent.  

The problem with using a single random number generator; a rolling pattern of values

If the values in the procedure are used to drive a similar aspect of the output, e.g. the heights of several sub-elements, then you will see similarities between instances where there should be none.  This may be hidden by the exact nature of a scenario, but there are plenty of cases where this will be horribly noticeable.
Wiring up an instancing example using the procedural symbols from my Proc-jam game and using the normal random operator to generate the seeds we can investigate this effect.

Investigating simple seed sequence generation problems

As the set of symbols within the instance procedure is also created using from the normal random generation operator, the symbols displayed are a window into the LCG sequence, each one shifted along by one value.

Symbol sequence with sequential seeds from same generator showing the 'windowing' effect

The solution here needs some consideration of how random sequences are generated and what a seed is.

Generation Algorithms

The sequence of values produced by a random number generator come from the random number generation algorithm it employs.  The seed is used to set up the internal state of the generator, and each time a random number is generated, the internal state changes ready to provide the next one.  The algorithm is responsible for ensuring that the output is perceived as random.  There are a huge variety of algorithms people have devised, each with different characteristics of randomness, speed, size (internal state), and cryptographic suitability (a common use case).

For procedural generation the requirements are usually just going to be around speed, and maybe storage size.  Randomness isn't normally a problem as there are many good algorithms that are fast and small.  For Apparance, one of the most basic classes of generator is all that is needed; the Linear Congruential Generator (LCG).

LCGs are particularly attractive for procedural generation use since the state can be the same size as the seed, allowing us to effectively pass the state around in the same form as we do the seeds, in fact they are treated as one-and-the-same.  This is important because for a fully deterministic procedural system this state has to be propagated around the system with all the other parameters, and this is indeed what happens in Apparance.

Growing Seeds

A seed is the starting point for a random sequence, start with a different seed and you get a different sequence.  In fact though, what you are getting is just a different part of some larger overall sequence.  For any random number generation algorithm the sequence it generates will repeat itself eventually, but the length of this sequence is dependent on the number of possible configurations of its internal state.  The more state, the longer it can generate values without repeating itself.  For a LCG using a 32 bit integer seed there are 2^32 possible internal states and hence it would have a theoretical repeat period of over four billion values.  However, this theoretical maximum isn't guaranteed with every LCG as the mathematics used is very simple and, consequently, choosing the internal constants used is very important.  For Apparance I chose to use constants from publicly documented implementations to save the investigation and analysis time needed to derive good ones.

Multiple Algorithms

Given that we can choose between different LCG variants, each with its own sequence of states/seeds/values, we could choose to solve our issue by using one algorithm for the inner sequence and a different one for the outer sequence.

Using two different random number algorithms to avoid sequence overlap

Since the sequence of values needed by a procedure is going to be far, far smaller than the total sequence size, what we have here is multiple procedures running along different parts of the same overall sequence. For this to be successful all we needed was to change the seed to one that will not produce the next, expected, value in the sequence.  That is exactly what the other algorithm is doing, it effectively skips the needle from one part of the record to another.

Scalability Issues

This approach has two significant downsides though:

1. This requires either more than one Random Value operator, or the operator needs to be parameterised by the algorithm used.
2. The outer procedure needs to make sure it's not using the same algorithm as the inner procedure.

The first issue here adds to the complexity of the available operators and their use.  The second introduces coupling between procedures; knowledge of the inner one is needed to use it in the outer one.  Both of these also suffer from scalability issues; it's very easy to imagine scenarios where this problem is nested more than two procedures deep, i.e. we may need more than two algorithms, or that two procedures need to be used side-by-side that are already using both algorithms.  A better solution is needed.

Twist Variants

This 'branching' of the random streams is particularly effective, but it turns out that to solve our dependency problem it is necessary to be able to jump multiple ways from a given point in the sequence.
This is exactly what the Random Twist operator does.  It produces a new seed value using a different LCG, and also has a Variant input allowing parameterisation of this process.  This is implemented as a simple bit mangle of the variant value with the new seed value so as to change it parametrically, much like the twist operation itself, and jumping tracks again.

Better use of twist operator to generate sub-seeds

Fundamentals

It's worth summarising the random number generation processes at play here before we move on to the main story next time.

The random generation used here can be broken down into these fundamental operations:

• Generate a New Seed from a Seed
• Generate a Value from a Seed

The first is the function of the random generation algorithm (LCG in our case), and the second is actually a form of hash function.  Hash functions map values of one type or size to values of another type or size.  Commonly used to generate check-sums of large sets of data or used in encryption, they are also useful here.  The random number generation in Apparance uses a set of hash operations to map random seeds to floating point and integer values, with configurable ranges for use in the procedural generation process.

The Random Value operators are composed thus:

The Random Value generation process

The Random Twist operator is composed thus:

The Random Twist seed generation process

This should give you enough of a grounding in Apparances randomness operators.  Next time we'll look at the implementation of these a bit more and the quirky bug I found disrupting them.

See Also

If you are interested in reading up in more depth on random number sequences, in particular with respect to procedural generation, I highly recommend Rune Skovbo Johansen's great primer on the subject.

• Rune's Gamasutra article: A Primer on Repeatable Random Numbers

It covers some of the sequencing and hashing issues with deriving numbers for use in procedural generation scenarios.  There is also a fairly detailed analysis of some of the more practical generation algorithms.

One Million Bytes

A slight aside today while I play with futuristic skyscraper shapes.  I'm not going to talk about cities, instead this post is about an interesting technical aspect of the synthesis engine; the use of the call stack.

The Stack

Typically the stack is something that most programs and programmers don't need to worry about, ever.  Programs tend to rarely have a call graph that goes even remotely near the stack depth limit.  Of course we have all hit stack-overflow situations, but these are usually due to either:

1. A function accidentally calling itself (either directly or indirectly).
2. A recursive algorithm not terminating properly.

Both of these are just bugs you would hit during development, fix, and move on.  Sometimes though you may be explicitly using recursion to solve a problem and need to be wary of how deep the recursion goes.  Usually in this case you would just tweak the code to stop it running out of stack space, or perhaps your data-set is of limited complexity and it just works, so you can ignore it and again just move on.  With Apparance however we have to be a bit more careful.

Tree Evaluation

The synthesis process in Apparance is implemented as an operator-tree evaluation.

Simple tree evaluation example

This means that starting at some root procedure we evaluate its output, triggering this sequence of events:

1. The graph inside the procedure is instantiated and connected up.
2. We find what the procedure output is wired to, and evaluate its output (recurse to step 1).
3. At some point we reach a fundamental operator instead of a procedure.  Evaluating its output results in some code being executed to perform its intended function.  In order for it to be able to do this though it needs input data, which it requests (another function call) as required until it can return with the calculated output result.
4. We find out what the operator input is wired up to (this happened in step 1 for its containing procedure).
1. Usually this will be another output and we will evaluate that (step 2).
2. If our input is actually wired to a procedure input, then in a similar way to 4 we have to see what that is wired up to and recursively follow it until we either reach another operator output (step 2 again), or we reach a constant value.
5. On reaching a constant value we now have data to pass back up the call graph and we can return.  There are a couple of ways constant values can appear in a procedure:

1. Embedded in a procedure itself as a constant input.
2. As an input parameter supplied to the root procedure.
3. Output-only operators that obtain the value from outside systems, e.g. mathematical constants like Pi, or useful synthesis state like the current block size.

The upshot of all this is that as we dig deeper into our procedure graph, and at every step towards some constant data value, we are making deeper and deeper function calls.

Data Driven Code

Normally the execution call graph is largely hard-coded into a program; conditional branching changes the exact shape of this graph, and recursion can cause chains of similar shaped sub-branches to push it deeper, but it is still largely predetermined in behaviour.  During development, the stack usage may increase, but this maximum will largely not change during the execution of the program.  As a consequence, for most programs it is impossible to blow the stack in every-day use.

For a data-driven situation however, you can no-longer make this assertion; we don't know how deep our procedures will end up going when we are building them in the editor.  It is very simple to accidentally create a procedure that recurses for-ever and instantly overflows the stack.

Simplest procedure that overflows the program stack.

This is a problem since these crashes happen at edit time, when the application is in the hands of the end user, and not during its development where a debugger and developer are at hand.

A Walk In The Dark

In some senses, every program is a ticking time-bomb.  Are you really aware of how close your program runs to the stack limit?  Do you just ignore the problem since you've never hit it?  Do you even know how much stack space is available to your program?  It's a bit like taking a night-time stroll on the cliff-tops, everything is fine, until it suddenly really isn't.

It's a bit of an odd situation because languages don't really acknowledge the existence of a stack limit and it seems a little talked about point.  There don't seem to be any ways to query the stack, or work out the current depth, using standard library calls.  This may be because there are ways to hand code this and it's such a rare use case that it's just not worth the effort supporting it, or alternatively it is acknowledging what should be entirely an implementation detail that the programmer should make no assumptions about.  Anyway, I need to know the limit and I need to monitor the depth as procedure evaluation is performed and so in the absence of any library support for this it's down to a hand-rolled approach. 

Get A Tape Measure

First, how deep are we?  A few searches online reveal what I suspected; that the simplest way to measure how deep you are in function calls is to take the address of a local variable (or function parameter) at the start of the program and compare it with the address of a local variable in your current function.  I created a macro to do this:

 #define CURRENT_STACK_LOCATION(a) ((uint64_t)(void*)&(a))

Used like this:

 int a;

 uint64_t stack_pos = CURRENT_STACK_LOCATION(a);

During synthesis this is evaluated each time we dig deeper, and compared to the initial stack position.  If we go too deep, we flag the error and abort the synthesis, unwinding the stack with returns triggered by an error check.

How High Can You Get?

The other important question is "how big is the stack?".  There doesn't appear to be a way to measure this in code and some investigation reveals that this is something you can set in your EXE project settings (for C++ project), or via some EXE fiddling (with EditBin.exe) for C#.  In both cases though, the default seems to be one megabyte.

Assuming this 1 MB is actually 1,048,576 bytes (2^20) I decided a 1,000,000 byte threshold would leave a nice safety margin after triggering an abort of the synthesis run.  This seems to work fine, and you can see the results of this with the simple test case (proposed earlier).

Results of simple stack overflow test procedure running.

We managed to get to an evaluation depth of 15,624 and it was a final stack frame of (at least) 96 bytes that pushed us over the million byte limit.  This is plenty of space for very complex procedure evaluation, but with the safety net of knowing you aren't going to crash.

Engineering

It's quite likely that I have missed some useful API call or technique that could have saved me some time or prevented various assumptions here, but I guess this is an engineer's approach to the problem; measure, try stuff, get something that works, and test it.  It seems to work, and until I find a platform/machine/OS/scenario where it doesn't (or a suggestion to improve it)  I will consider it solved for now.  If you have any suggestions, or concerns, please chip in below.

Thanks

A quick thank-you to those that came up for a chat and see me demo some of Apparance at last weeks Tuesday Night Gamedev Pub gathering in Guildford.  There were many good questions and interesting conversation, and I could see that the whole project was making people think, hard (either that or the beer was making it hard to think).  Your questions and chatter prompted the writing of this post.  I hope to demo again next time for those that missed it.

An Introduction to Procedures

As there is a huge amount to cover I'm going to spread it out over multiple posts.  The first few will describe the technology (engine) and after that I'll cover the tooling (editor).  This will by no means cover all the technical detail, but it should give you a good idea of how it works and what (I hope) it will be able to do.

Authoring

Currently the engine allows building of procedural models; objects formed of triangles (and lines) and rendered in a 3D viewport.  These are expressed as 'procedures'; collections of modelling and calculation operations that feed into each other forming a network or graph.  The 'inputs' to this are various constant values within the graph and the output is a 'value' corresponding to the generated geometry.

A simple procedure and the resulting model

Each node is some form of fundamental operator (like add or subtract) implemented in code, or it can be another procedure, itself made from operators and procedures.  The term 'operator' will be used to mean either in the context of a procedures content as once placed down they can be treated in exactly the same way.

A multiplication operator feeding into a luminance procedure

Each operator generally has one or more inputs and one or more outputs, which can be connected up to other operators.  An input can only be connected to one output but an output can connect to multiple inputs.  There are several fundamental data types available for information to be passed between operators.  So far we have: Integer, Float, Bool, Colour, Vector, Matrix, String, Frame, and Model Segment.  These last two are explained more below.  Unconnected inputs are considered constants and the value can be explicitly specified.

Operator inputs of various data types

When creating a procedure, you get to define it's inputs and outputs, and their names and types, these then become available for connecting-to wherever an instance of the procedure is placed down.

Procedures represent blocks of functionality and can easily be used to encapsulate and re-use groups of operators.  For example you might build a colour blend procedure out of mathematical operators if a dedicated operator wasn't available or didn't meet your needs.

Bespoke colour blending procedure

The new blend procedure in use

Operators

There is a small library of built-in operators implemented already to build procedures from, these are roughly divided into:

• Mathematical operations - all the usual maths functions.
• Comparisons and conditional switching - test and flow control.
• Conversion - e.g. changing type or break-out/re-combine (for multi-element types).
• Constants - operator inputs are editable constants, but constant operators are useful for sharing values.
• Modelling - create and manipulate primitives (cube, cylinder, paint, distort, etc).
• Space defining - subdividing and specifying spaces to be used for containing objects (Frames).

Some of the operators available so far

There are hundreds more of these I need to support (something for a future post), but this is plenty for me to test and prove out the principals.  In fact this current limitation means I have to be inventive and really means I push the capabilities of the procedure system to see what I can achieve.

Modelling

Currently there are only two triangle primitives (Cube and Cylinder) and two line primitives (Line and Grid).  The only reason I haven't written more yet is that I have managed to achieve a surprising amount with just these.  All the screenshots you can see so-far are mostly built with the cube operator and an occasional cylinder.  As we will see though they do provide a fair bit of control over how each can actually be used.

Once I got to the point where the geometry synthesis was basically working and I started building shapes I found that a large part of building up objects is actually splitting up the space it is going to occupy into smaller spaces.  This happens at many depths and in many different ways.  There are parallels here to laying out elements on a page or in a user interface, so many concepts like centring, distribution, and offsetting apply equally to 3D space. To facilitate this in Apparance I found a data type to describe an oriented cuboid in space was ideal for this.  These I call 'frames' and operations on them form a large part of the object construction process.

Space partitioning operators in use (highlighted yellow)

Starting with a frame describing the location, orientation, and dimensions of the object being created, you break it down into sub-frames until you reach a point where a single primitive fits exactly, at which point you feed the frame into it generating the geometry needed there.  This aspect of modelling needs a post to its self really :)

Geometry generated by a primitive operator is passed around the graph using a 'Model Segment' data type.  This rather esoteric type is just a way of remembering where in the modelling buffers the vertex and triangle information for that primitive has been put.  A 'combine' operator is available to merge two segments of geometry together so they can be treated as one.  All modelling should result in a single Model Segment output at the top level and it is the geometry enclosed within it that will be displayed.

Part of the appeal (to me at least) of procedural generation is parameterisation.  Anything we build this way can have any aspect of its form exposed as a tweakable parameter.  This may just be the desired size of the object, it might be the thickness of the frame on window, the colour of a building's roof tiles, or the probability of a wonky brick in a wall.  In order for a given parameter to affect the modelling process its value will usually need to be massaged into some other form by using mathematical, conditional, and logic operators.

Synthesis

The process of turning procedures into models that can be rendered it called 'synthesis'.  Starting with a root procedure to be viewed in a 3D scene the synthesis engine starts by instantiating it in memory with any input values needed and requests the geometry via the appropriate output.  This triggers instantiation of all the operators within and their interconnections.  Following the 'flow' of the data connections back from the required output and digging down into procedure within procedure all the functionality needed to produce it is executed.  Requests for output values from leaf operators, ones with actual code behind them causes that code to be executed.  Procedures and operators also call upon their inputs which then cause the evaluation to elevate back up to the level above and follow the connections already in place when the containing procedure was evaluated.

Evaluation tree for the table example

Because procedures are instantiated as they are needed, it can support recursion, i.e. a procedure can include instances of itself.  As long as there are 'exit conditions' defined to limit the recursion depth this turns out to be a really useful way to build a lot of structures.  I discovered early on that this can be used to implement arrays of objects by progressively subdividing until the required object size was reached.  I thought I would need array support explicitly but so far recursion has served well in its absence.

A recursive procedure called "Recursive" that includes itself.

Output of the recursion example

To help with scalability and performance, multiple synthesis runs can be performed in parallel on several separate synthesiser instances.

Four synthesisers running in parallel, busy building geometry

Each has its own pre-allocated chunk of memory as working buffer, used in a non-freeing manner and only reset at the end of each run.  This makes allocation of parameters, values, operator state, and any intermediate data extremely fast and all values effectively immutable, simplifying the operator graph evaluation logic.

A breakdown of how memory was allocated during synthesis

Next

Quite a lot to absorb I'm sure.  I'm happy to answer any questions.  Next time I'll talk about the renderer, some of the less glamorous code supporting everything, and how the project is set up.