Big Robot Games - Indie Dev Blog Edition

Somewhere for me to post my musings on Indie Development, Cryptocurrencies and whatever else strikes my fancy.

Mersenne Twister

This is an implementation of the Mersenne Twister random number generator, written in VB.NET. (I had a C# version laying around at one point, but I may have deleted it. This one works exactly the same, and implements the same algorithm.)

This is what I use in Heroic Adventure! (HA!) and have recently added it to my Cellular Automata project as well. It's a nice fast substitute for System.Random, with a much longer period before predictable repeating patterns.

'
' An implementation of the Mersenne Twister algorithm (MT19937), developed
' with reference to the C code written by Takuji Nishimura and Makoto Matsumoto
' (
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html).
'
' This code is free to use for any pupose.
'

Option Strict On

'''
''' A random number generator with a uniform distribution using the Mersenne
''' Twister algorithm.
'''
Public Class MersenneTwister
 Private Const N As Integer = 624
 Private Const M As Integer = 397
 Private Const MATRIX_A As UInteger = &H9908B0DFUI
 Private Const UPPER_MASK As UInteger = &H80000000UI
 Private Const LOWER_MASK As UInteger = &H7FFFFFFFUI

 Private mt(N - 1) As UInteger
 Private mti As Integer = N + 1

 ''' <summary>
 ''' Create a new Mersenne Twister random number generator.
 ''' </summary>
 Public Sub New()
  Me.New(CUInt(Date.Now.Millisecond))
 End Sub

 ''' <summary>
 ''' Create a new Mersenne Twister random number generator with a
 ''' particular seed.
 ''' </summary>
 ''' <param name="seed">The seed for the generator.</param>
 <CLSCompliant(False)> _
 Public Sub New(ByVal seed As UInteger)
  mt(0) = seed
  For mti = 1 To N - 1
   mt(mti) = CUInt((1812433253UL * (mt(mti - 1) Xor (mt(mti - 1) >> 30)) + CUInt(mti)) And &HFFFFFFFFUL)
  Next
 End Sub

 ''' <summary>
 ''' Create a new Mersenne Twister random number generator with a
 ''' particular initial key.
 ''' </summary>
 ''' <param name="initialKey">The initial key.</param>
 <CLSCompliant(False)> _
 Public Sub New(ByVal initialKey() As UInteger)
  Me.New(19650218UI)

  Dim i, j, k As Integer
  i = 1 : j = 0
  k = CInt(IIf(N > initialKey.Length, N, initialKey.Length))

  For k = k To 1 Step -1
   mt(i) = CUInt(((mt(i) Xor ((mt(i - 1) Xor (mt(i - 1) >> 30)) * 1664525UL)) + initialKey(j) + CUInt(j)) And &HFFFFFFFFUI)
   i += 1 : j += 1
   If i >= N Then mt(0) = mt(N - 1) : i = 1
   If j >= initialKey.Length Then j = 0
  Next

  For k = N - 1 To 1 Step -1
   mt(i) = CUInt(((mt(i) Xor ((mt(i - 1) Xor (mt(i - 1) >> 30)) * 1566083941UL)) - CUInt(i)) And &HFFFFFFFFUI)
   i += 1
   If i >= N Then mt(0) = mt(N - 1) : i = 1
  Next

  mt(0) = &H80000000UI
 End Sub

 ''' <summary>
 ''' Generates a random number between 0 and System.UInt32.MaxValue.
 ''' </summary>
 <CLSCompliant(False)> _
 Public Function NextUInt32() As UInteger
  Dim y As UInteger
  Static mag01() As UInteger = {&H0UI, MATRIX_A}

  If mti >= N Then
   Dim kk As Integer

   Debug.Assert(mti <> N + 1, "Failed initialization")

   For kk = 0 To N - M - 1
    y = (mt(kk) And UPPER_MASK) Or (mt(kk + 1) And LOWER_MASK)
    mt(kk) = mt(kk + M) Xor (y >> 1) Xor mag01(CInt(y And &H1))
   Next

   For kk = kk To N - 2
    y = (mt(kk) And UPPER_MASK) Or (mt(kk + 1) And LOWER_MASK)
    mt(kk) = mt(kk + (M - N)) Xor (y >> 1) Xor mag01(CInt(y And &H1))
   Next

   y = (mt(N - 1) And UPPER_MASK) Or (mt(0) And LOWER_MASK)
   mt(N - 1) = mt(M - 1) Xor (y >> 1) Xor mag01(CInt(y And &H1))

   mti = 0
  End If

  y = mt(mti)
  mti += 1

  ' Tempering
  y = y Xor (y >> 11)
  y = y Xor ((y << 7) And &H9D2C5680UI)
  y = y Xor ((y << 15) And &HEFC60000UI)
  y = y Xor (y >> 18)

  Return y
 End Function

 ''' <summary>
 ''' Generates a random integer between 0 and System.Int32.MaxValue.
 ''' </summary>
 Public Function [Next]() As Integer
  Return CInt(NextUInt32() >> 1)
 End Function

 ''' <summary>
 ''' Generates a random integer between 0 and maxValue.
 ''' </summary>
 ''' <param name="maxValue">The maximum value. Must be greater than zero.</param>
 Public Function [Next](ByVal maxValue As Integer) As Integer
  Return [Next](0, maxValue)
 End Function

 ''' <summary>
 ''' Generates a random integer between minValue and maxValue.
 ''' </summary>
 ''' <param name="maxValue">The lower bound.</param>
 ''' <param name="minValue">The upper bound.</param>
 Public Function [Next](ByVal minValue As Integer, ByVal maxValue As Integer) As Integer
  Return CInt(Math.Floor((maxValue - minValue + 1) * NextDouble() + minValue))
 End Function

 ''' <summary>
 ''' Generates a random floating point number between 0 and 1.
 ''' </summary>
 Public Function NextDouble() As Double
  Return NextUInt32() * (1.0 / 4294967295.0)
 End Function
End Class
 

Cellular Automata

I've been playing with procedural cave map generation lately, and put together a C# class that uses the Cellular Automata technique to fill a grid with true/false noise and apply rules for "growing" the caves (very similar to "Game of Life" rules.)

The rules work like this: 

  1. If you have a "live" cell (value: true) with 4 or more live cells around it, it stays alive (value: true)
  2. If you have a "live" cell (value: true) with 3 or less live cells around it, it dies (value: false)
  3. if you have a "dead" cell (value: false) with 5 or more live cells around it, it becomes alive (value: true)
  4. If you have a "dead" cell (value: false) with 4 or less live cells around it, it stays dead (value: false)

To use it, you'll need to call the constructor to initialize the RNG and CaveMap array, then call the InitializeCaveMap() method once. After that, you'll want to call ApplyRulesToCaveMap() a few times (best/smoothest results for my purposes was about 8 times, but your needs may be different.)

As you can see from the pictures at the bottom, earlier passes show the most drastic change, while later passes have a smoothing effect.

I've cut out the namespace and using statements for brevity, but the class is below. Pretty simple stuff, but feel free to ask any questions in the comments section.

I'd love to hear if and how you might be using it.


class CaveBuilder
{
   public bool[,] CaveMap;
   private System.Random rng;

   public CaveBuilder(int width, int height)
   {
      rng = new Random();
      CaveMap = new bool[width, height];
   }

   public void InitializeCaveMap()
   {
      for (var x = 0; x < CaveMap.GetLength(0); x++)
         for (var y = 0; y < CaveMap.GetLength(1); y++)
            CaveMap[x, y] = (rng.Next(0, 2) == 1);
   }

   public void ApplyRulesToCaveMap()
   {
      for (var x = 0; x < CaveMap.GetLength(0); x++)
         for (var y = 0; y < CaveMap.GetLength(1); y++)
            if (CaveMap[x, y])
               if (CountLiveCells(x, y) >= 4)
                  CaveMap[x, y] = true;
               else
                  CaveMap[x, y] = false;
            else
               if (CountLiveCells(x, y) >= 5)
                  CaveMap[x, y] = true;
               else
                  CaveMap[x, y] = false;
   }

   private int CountLiveCells(int x, int y)
   {
      var total = 0;

      if (CaveMap[Constrain(x - 1,0), Constrain(y - 1,1)]) total++;
      if (CaveMap[x, Constrain(y - 1,1)]) total++;
      if (CaveMap[Constrain(x + 1,0), Constrain(y - 1,1)]) total++;
      if (CaveMap[Constrain(x - 1,0), y]) total++;
      if (CaveMap[Constrain(x + 1,0), y]) total++;
      if (CaveMap[Constrain(x - 1,0), Constrain(y + 1,1)]) total++;
      if (CaveMap[x, Constrain(y + 1,1)]) total++;
      if (CaveMap[Constrain(x + 1,0), Constrain(y + 1,1)]) total++;

      return total;
   }

   private int Constrain(int check, int dimension)
   {
      if (check < 0)
         return 0;

      if (check > CaveMap.GetLength(dimension) - 1) 
         return CaveMap.GetLength(dimension) - 1;

      return check;
   }
}


Random noise, no discernible pattern:


After one pass of rules, still pretty rough:


A couple more passes:


A few more passes, about as smooth as it gets:

Writing and Speaking...

I've been doing a little of both lately, and my newest article on MonoGame is on the stands now in the Nov/Dec issue of CODE Magazine. You can find it here:  http://www.codemag.com/Article/1411081

I've also been selected to speak at Prairie Dev Con in Winnipeg, CA.  I'll be presenting two sessions, both on MonoGame:

XNA Is Dead, Now What?

and

Building a Scrolling Tile Engine with MonoGame

I guess it's time to get that passport. :)

Design in Evernote

I've been using Evernote a lot lately to map out the design for a tactical RPG and so far I'm really liking it. I can paste pretty much anything into it, and it syncs with every device I own (which means any time I get an idea, I can add it... no matter where I am.)

It's also good for grocery lists.

It's been rather quiet here

(Un)fortunately, I've been somewhat busy of late. I'm in the midst of writing a few articles for Code Magazine, and two books: one on MonoGame and the other on Bitcoin. As a result, I haven't had much time for blogging.

As I'm working more and more in MonoGame, I have a number of XNA samples from various demos (such as my Tile Engine one, and the Pathfinding with Waypoints one) that I'm converting to MonoGame, so I'll be posting those up as well.

I just submitted a 20 page article for Code Magazine (on MonoGame), which should see publication in the upcoming issue. I also had an article on CryptoCurrencies show up in the Sep/Oct issue, which you can see here:

http://www.codemag.com/Article/1409091

On Notch leaving Mojang

I am simultaneously jealous and sympathetic.

http://notch.net/2014/09/im-leaving-mojang/

I'm partly kidding about the jealous part. It's no secret that in many people's eyes, Notch is living the dream, but his struggles with depression and disillusionment are also well known. Minecraft had grown well beyond Notch's ability to run, maintain or even enjoy it.

I hope he enjoys the rest of his life. He's free to do whatever he likes at this point.