Sunday, September 18, 2016

Random Generation and Determinism

Chaotic Planes Development

Random Generation and Determinism

I've kicked off the first day of the rewrite of Chaotic Planes in Unity 3D.  You can read more about the history of the project on the Chaotic Planes page.

My first day was mostly focused on organization and preparing the project in Unity 3D.  I've also started to port some of the code that was originally designed for Galactic Usurper to this project.  Much of that code was built in a library we were calling "Swugl" for "StepWood Unity Game Library".  That library was getting a bit big and monolithic, so I've taken the time to start to break it down into the parts that Chaotic Planes will need.

Which leads us to the goals of the Chaotic Planes project.  

Our main focus with the game is to generate an action RPG similar to those found in the 1990s (think of Zelda or Alundra or other such games).  Specifically, we are going to be using real time combat but with a focus on puzzle solving and exploration.

To make the game interesting, we want the entire game to be procedurally generated.  This means that everything from the level design itself to the story should be built out of replayable and reorganizable blocks.  

We hope that while this will make the game very replayable and extendable over time.  However, we also know that part of the fun is to share your game experience with others and compete.  In addition, we want people to be able to write "walkthroughs" and "guides" for the generated games.  To facilitate that, we plan on making the game generation sharable.  

We also want to publish the game on multiple platforms so that people can enjoy it where they enjoy playing games.

That puts us in a bit of a quandary.  To support sharable random generation across multiple platforms, we need to be able to have deterministic generation.  While that sounds pretty easy, there are things that we can't rely on:
  • Floating point numbers are consistent only on a particular platform with the same compiler (even a version difference in the compiler may produce different values).  This is due to the fact that different chips do floating point math slightly differently and can result in different values.  To get around this, games typically compile C++ code with a "fp_strict" flag that forces the game code to follow strict IEEE standards.  However, that option isn't available to us in Unity 3d.
  • We don't want true random number generation, but rather pseudo random number generation.  This seems easy, since it is the way that computers do random numbers typically.  However, there are no guarantees across platforms that the same random number algorithms are used to support this behavior.
  • Integer math is typically defined well, but some operations are still undefined as to if they cause an overflow or an exception in C#.
  • Decimal should be deterministic in C#, but we've seen reports where that may not be fully the case.  Plus, it requires 128 bits for each number and is quite slow.  There have been errors in the Mono runtime before surrounding decimals and since Unity 3d is built on Mono, we are loathe to accept that risk.
In short, to support sharable, cross platform generation we need to be in as much control as we can be of how the math works.  There will be a considerable amount of testing written against the generators to catch deviations before they occur.  A single variation will result in the shared generation breaking down.

Today's focus after organizing the new project was to put the foundation of the deterministic code in play.  To do that, we've decided:
  • Integer math is "good enough" deterministically if we limit ourselves to a reasonable range in the integer space. 
  • Decimals are out due to space and speed considerations.
  • Floating Point is preferred, but there are no IEEE implementations in C# that I found.  There is a library called Soft Float that we could spend time porting, but we are holding out on a simpler implementation.
  • Fixed Point has its issues, but it is a well understood format.  With integer math being deterministic, it is possible to use this to produce non integer results in the generation.  We've settled on the "Q" format and have implemented both a 32 bit and 64 bit version with basic math operations.  Our "Q" value is specified during runtime so we can adjust the precision of the values as needed.
  • Random number generation isn't overly hard and there are a few good ones available that can be easily ported.  After looking over the various routines we settled on Mersenne Twister, specifically the port done by stlalv.
That's it for day 1!  While I could bore you with screen shots, they wouldn't show anything you'd be interested in yet.  Hopefully, the next day will have us doing something visible on the screen so that I can post a visual or two.

No comments:

Post a Comment