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.

Guildford Game Jam 2016 - Follow-up

Tidy Up

After finishing the game-jam there were a few things I needed (wanted) to do before uploading it for anyone to play.

1. Rendering stutter - performance on lower spec machines was terrible.
2. Collision and physics - so you could walk around the maze, confined to the rooms.
3. Additional detail - the walls were a bit plain and were supposed to be brickwork.
4. Difficulty tweaks - The maze size should have been linked to difficulty and I wasn't sure if it was fair.

I didn't think it was unreasonable to try and polish off these issues as they were either a bit of a show-stopper or had already been started during the jam.

Render Performance

It seemed that slower machines and particularly ones with only a couple of CPU cores suffered badly from low frame-rate and bad stalls whilst moving around the maze.  I had a few ideas where this could be, but really needed to gather more intel.  There were several avenues of investigation I could use:

1. I started with the Remotery integration already in Apparance, to get some ideas what was going on.
2. Running the GPU and CPU profiling tools in Visual Studio.
3. Adding hard coded timing and logging to suspect areas of the engine.

I wasn't having much luck and after a few red-herrings I wondered what else I had changed or added in the past that could be causing such issues.  It was a tricky issue to diagnose as there are various systems between the camera movement and the rendering that could be at fault.  Performance on my main dev machine (many cores) was fine so I suspected something to do with the threaded-rendering or main message loop could be to blame.  To resolve this I tried a few things out of desperation:

1. Boost the priority on render thread.
2. Boost the priority on the main thread.
3. Run the renderer on the main thread (single-threading model).
4. Switch message look to non-blocking (needed for 3).

I made these command-line switchable so I could try different combinations on a couple of machines.

The priority boosts made no noticeable difference, but running the renderer on the main thread did help on machines with only a couple of cores.

My investigations eventually lead to two things that seemed to explain my woes.

1. My slightly hacky camera smoothing system was completely broken.
2. I was logging synth errors to debug output.

The first one was only showing up on slower machines so I just disabled it (something to revisit later).  The second should have only affected development and debug builds of the engine or when running under the debugger, however I disabled it anyway.

Once all these had been fixed and tweaked, performance was much better and so I moved on to collision.

Collision and Physics

Aware that implementing a physics engine is no light-weight task, I tried to keep it focused and simple.  I have implemented this sort of collision successfully before for an experimental Quake clone built in .Net and set in a cube based world.  The collision requirements there were sufficiently constrained that it wasn't too difficult to do.  Based on this previous experience I decided I could get it done quickly.

After an initial late-night foray into hacking together a solution during the jam itself I decided to try and finish this implementation.

My proposed design went like this:

1. Meshes can be tagged with a special material that signifies collision properties.
2. The material will normally be hard wired not to render anything, but can be enabled to visualise the collision surfaces.
3. The engine will gather together any meshes tagged in this way that are within a certain bounds around the camera.
4. A custom camera controller (similar to the free-cam one) will handle FPS style player movement.
5. This controller will hook into the engine to request collision information.
6. Based on this information, collision tests and simulation will be performed to give the impression of solid walls and floors.
7. A Sphere-Triangle Swept collision test would be used to implement this.

I had most of this working during the game-jam, but didn't get the actual motion sim and collision working well enough.  This is what I spent most of the follow-up time on.  I got quite close, with floor and wall collision generally holding up smoothly, but the wall collision was still jittery and there were plenty of failure cases where you could fall though the geometry.  I also found it was going to need the collision geometry to be handled quite a bit differently with regard to detail levels than regular geometry.  This would be a lot of work.

In the end I decided that I was flogging a dead horse and should leave it out.  I didn't want to spend the additional time at this stage.

Additional Detail

The walls I had used to build the maze rooms were using a brick wall procedure written ages ago, and did include additional brickwork detail, even down to modelled bricks and mortar between them.  However, they were implemented before the current detail management system was in place and I was still working out how detail was controlled.  The wall procedure had a manual detail level control that you had to drive at the top-level.  Unfortunately this didn't integrate well with the block based detail control and couldn't be used.  I would have had to re-do the brick wall procedures from scratch and I just didn't have the time.

Difficulty Tweaks

This was one thing I did manage to have a go at, and the maze size now increases with difficulty setting.

Release

I had already set up the release build generation process so it was simple to package up a build for upload.  The final zip file was almost exactly 1 MB which was a nice size to show the compression at play with procedural generation.

The game is available to play via:

https://apparance.itch.io/guildford-game-jam-2016

I also submitted it to The Procedural Generation Jam that was going on at the time:

https://itch.io/jam/procjam/rate/96003

It even got included in a Let's Play of all the entries by Jupiter Hadley.

https://www.youtube.com/watch?v=-NtPCzF2mZI (it's the first one at 00:54)

Download it and have a play!

(Oh, but don't forget to pretend the walls are solid :O)

Guildford Game Jam 2016

Jam

This weekend I attended the Guildford Game Jam organised by @Kilo_bytes and hosted at the new offices of the lovely @RocketdeskUK. There were about 15+ people in teams of one to four with a few floating jammers creating audio and art assets for multiple teams.  I took my creaky old laptop and managed to build a game using Apparance in the two (and a bit) days.  

Guildford Game Jam: 2 Choices

Here's how it went...

Idea

Given the limitations of the Apparance tech at this stage in its development I constrained to something that was non-interactive, i.e. with no moving parts.  I couldn't even rely on collision to build any form of physical puzzles.

The main theme for the event was 'two choices' so I was thinking about exploration of a branching space where each choice led you towards one of many final destinations.  Each split would have some clues as to the kind of outcome you were heading towards.  You would have to fly through the rooms and doors pretending that you couldn't collide with anything.  At the very least I needed my stand-alone player app to support camera controls (mouse/keyboard, and ideally game-pad) for this to be possible.

Pre-production

In anticipation of the jam I worked on tidying up the Apparance Player a bit and adding support for the following that I was going to or probably going to need:

• Command line option support - to select the level of control (I still wanted the house viewer to work, but also free-cam).
• Mouse and keyboard control of camera - for flying round environments (this would also be good for demonstrating the Future City scene).
• Game-pad support - I really wanted to be able to try navigating using a game-pad, it should be much more accessible.

Once I had all this up and running it meant I could run the Old House demo, fly around Future City, and support the game jam all with one player, each using different command line options to launch.

Command line options now supported by the standalone Apparace Player application.

Day 1

Setup

The first day (just Friday evening really) was an opportunity to meet the jammers and catch up with some friends.  We all set up, and started discussing ideas.  I was open to the idea of working in a team, but within the short time-scale I don't think it would have been possible to get someone up to speed using the Apparance tools (particularly as they aren't 'consumer ready' yet).  As it was I worked solo.

Dungeon Reuse

I had intended to start pretty-much from scratch, building an new world to navigate, but once I got playing around with some of my old test scenes I realised I could get a long way with the room-subdivision work I'd already done.

Early dungeon generation experiments.  A good starting point for a maze.

Playing with this and re-thinking my goal I decided that a simple maze of rooms with clues in to some final decision would work well and I had the room network to support it.  I was thinking that the puzzle should be finding your way through the maze and clues leading you towards the correct exit (one bad, one good), for example, bones or treasure scattered on the floor.

To Collide or Not To Collide

At this point I was starting to think that having to manually fly round the level with user-implemented collision was really going to spoil the experience.  I decided that, back at home, I'd try to implement some simple physics for the player controller.

Day 2

Early Hacking

Up early, I started hacking in some collision systems before I headed back to the Rocketdesk office for the 10 am start.  I got to the point where I could tag generated triangles with a material the engine picked up as collision and passing off to the camera controller each frame.  A bit messy but it would work, as long as I could actually do the collision and simple motion sim.  I found a neatly encapsulated bit of sphere-triangle sweep collider code that I was going to use.  But first, a 'day at the office'.

Beginning & End

Back at the Jam I set about building start and exit rooms that bolted onto the generated 'dungeon' space.

Basic level structure test, start room (blue), maze, exit rooms; bad (red) and good (green).

This meant that I had a basic level design that I could fly through from start to (a choice of) finish.  A good start.

Doors

The original dungeon work just had open doorways so I quickly stuck the doors from the Old House project in them to divide up the rooms a bit more.

We can use the door procedure from the old house experiment

Doors in place, double for wider opening.

As it stands Apparance doesn't have an moving object support so there was no way to animate the doors opening.  Instead I had the cheeky idea of switching between open and closed doors based on the detail level and letting the detail blend system provide the transition.

Door opening hack in action; high LOD open, low LOD closed.

This is very hacky, but just the sort of things you try and get away with at a jam.  It adds a lot to the feel of the rooms.

Late Hacking

Back at home (after an evening out at the local Nov 5th fireworks display) I set about integrating the collision test code into the engine.  It's a piece of code I found written by Igor Kravtchenko, which does exactly what I wanted.  For simple environment collision and movement simulation, all you need is sphere-triangle swept collision testing.  Basically, the player (camera) sits on top of a ball which is moved around by the controller.  Each frame you do a sweep test as you attempt to move the ball a bit and adjust the new position according to the collision results.  There are lots of edge cases that would break, but this should have been enough for me to move round a 'boxy' level.  After much coding late into the night I managed to get a rough version working.  Things were looking promising.

Collision testing against tagged triangles.

This wasn't to last though...

Day 3

In the cold light of day, my physics experiments from the previous night started unravelling (too many edge cases, falling through the world, etc) and I decided to abandon the idea as I didn't have enough time to sort them out.  Back to fly-cam.
The game at this stage wasn't much of a game as there were no clues to help you choose your final room.  Puzzles were needed, so I headed out to the jam room again for the final day.

Puzzles

Mulling over the puzzle mechanics the previous night I came up with the idea of mysterious symbols in each room providing clues to the final rooms outcome.  It would work like this:

1. A set of symbol design are available.
2. This set is split into three sub-sets 'good', 'evil', and 'neutral' symbols.
3. Each room in the maze will be clearly distinguishable as either a good clue room or an evil clue room.
4. Each clue room has a few symbols in it, some selected from the good/evil symbols according to the room type, and some from the neutral set.
5. The two final rooms will have a similar set of clues, from which the player must infer the exit type.

Difficulty

The difficulty of the game can be adjusted by varying a number of elements of the game:

• Number of symbols.
• Number of symbols shown in clue rooms.
• Proportion of neutral symbols shown in clue rooms.
• Size of maze.

To simplify the level authoring, the difficulty level is chosen at random based on the game seed in effect.  This means that you choose difficulty by changing the seed until you find a difficulty you are happy with (more on this later).  Most of the difficulty modifiers above were easy to hook up, but unfortunately I didn't have time to implement maze size changing (it would be simple to add though).

Symbols

So I set about implementing the symbol set manipulation (as a bit-field) for generating the sets, and extracting sub-sets, driving symbol generation, etc.  As I worked I quickly set up unit tests to make sure each step worked properly.  I needed to be sure it was correct as any inconsistency would break the puzzles.

Test rigs for bit-field operations: Pick, Split, and Count

Symbol (glyph) generation was a quick mixture of base shapes, colour, scaling, distribution, and variation.

Sample glyph family.

Combining these gave a generation step where from a game seed we could generate a consistent set of symbols for use through a given level.

Glyph sets and choosing example

From these it is possible to then generate a set of symbols for use in each room, good+neutral and evil+neutral, the choice randomised by a varity seed (different for each room).

Example glyph panel for clue rooms

I chose to always show four symbols in each room, with each room being designated good clue/evil clue from the room seed.  This could be varied by difficulty if desired.

Glyphs on the walls of good/evil clue rooms.

I intended for the symbols to be more subtly placed around the room and built into the decoration of objects, but this was far too much given the time constraints and I ended up just plastering them on the walls.

Exits

The two exit rooms needed to be clearly different to the other rooms and also the way you make the final choice needed to be 'no return'.  By colouring the room a neutral colour and making the final exit a hole in the floor it nicely fulfilled both of these requirements.  Under the two exit rooms (which by the way are switched at random) I constructed suitably rewarding and punishing environments to indicate whether the player chose the right room or not.  You will have to play the game if you want to see what they are.  :O]

Start Screen

I managed to squeeze in game seed and difficulty indicators above the starting door to provide a bit of a start screen/menu/front-end to the game.

Game start room with seed/difficulty indicator.

The controller support I added earlier included a key/button to select the seed value going into the top-level procedure.  By driving the difficulty off this seed (at random) it doubles as a difficulty select too.

Postpartum

The final 'game' was playable and enjoyed by a few of the fellow jammers so I'm happy to have met that criteria at least.  It did have the 'two choices' element, and maybe even the 'the player cannot win' modifier as you can't actually escape the dungeon.  I was a bit disappointed that I didn't manage to get the physics working as this would make the game easier to play and overall experience more claustrophobic, as well as the ending drop to doom/glory more dramatic.  I had an ongoing issue with the rendering engine struggling on laptops which really got me down and is something I really need to diagnose.

This week I'm going to try and resolve the rendering issues, finish the physics, and wrap it all up in a package for release on itch.io so you can have a play.  It's quite exciting that this will be the first release using the Apparance technology, and I look forward to your feedback.

Coincidentally this week is also Procedural Generation Jam 2016 week and since my game meets the requirements for that I will look to release it into the proc jam circuit too.  Watch this space for an update!

ProcJam is also going on this week.

As for the jam experience, I found the environment an odd one working solo and would have maybe got more done at home in my own office, but I would have missed out on the creative and collaborative atmosphere.  It's good to meet and interact with people, especially those with similar interests and passions, and I endeavour to continue doing things like this as I work to get Apparance more exposure.  At this stage the tools and tech isn't ready for collaboration at such a short notice, and I continue to realise that it's still a very technical process to build procedures.  It strikes me as very much 'geometry programming' than sculpting of assets, which may or may not be a problem long-term.  I think it's 'just different'.  Thanks to everyone involved and it was great to see everyone's projects played at the end.

Me pointing as a willing victim plays through my game.