[h1]Forms of Randomness[/h1]
[h1]I. Random Number Generators[/h1]
[h2]i. Introduction[/h2]
Random number generators create a sequence of random bits. The client to a random number generator class can request the raw bits directly or interpreted data derived from the bit sequence (floats, doubles, values between two other values, values with a certain distribution, etc.) Random number generators produce bits in a sequence and have a state. It may not be possible to achieve random access to a number in the sequence produced by an RNG. Random numbers are also not be suited for applications with data in multiple dimensions stretching to infinity or finite grids that are too large to store in RAM. If you need random data as a function of one or more variables, you can use a hash function or an RNG seeded from the value of a hash function.
[h3]1. RNG Seed[/h3]
A value called a seed can be used to derive the initial state of a Pseudo Random Number Generator. If you provide the same seed to a PRNG, it will produce the same sequence of numbers every time (but only for the same algorithm). This is useful for creating reproducible procedurally created content, synchronizing random number sequences between multiple computers, or any other scenario require consistency or reproducibility.
[h3]2. RNG State[/h3]
The state of a PRNG is normally hidden to the user of the object. You can create a PRNG that lets you copy it’s state into a different object, so you can create identical sequences starting from the middle of a sequence (instead of just the beginning using a seed) and so you can save and restore the state of the PRNG in the middle of a sequence. All pseudo random number generators have a state. PRNGs are deterministic and do not return truly random sequences.
[h2]ii. Cryptographic Random Number Generators[/h2]
Cryptographic random number generators have special properties useful for security related applications. They exploit properties of number systems that can be used for private communication, authentication, and zero knowledge proofs. They work with large numbers and may be too slow for applications that do not require them, such as simulations or games. If you think you need one in your game but don’t know how it works or what it’s used for, then you probably don’t need one.
[h2]iii. Non-Deterministic Random Numbers[/h2]
You don’t need true random number generators for the same reason you don’t need cryptographically secure random number generators. Cryptographic PRNGs may benefit from keys derived from real world noise in order to prevent some attacks, but a game won’t have to worry about such attacks. To get this type of randomness, computers use input from the physical world that can be considered random. The “state” of this RNG is the state of the real world. It does not have the useful properties of PRNGs other than the appearance of randomness. Computers might utilize this source of randomness or user inputted key to seed a cryptographic PRNG instead of a timer to prevent certain side channel attacks. If you’re not using cryptography, don’t look for this type of randomness.
[h1]II. Hash Function[/h1]
[h2]i. Introduction[/h2]
Hash functions take a sequence of bits and transform them to a new sequence of bits, usually of some fixed length. The [icode]hashCode()[/icode] function for Java Objects produces a 32 bit output. Hash functions are sometimes (that is, very rarely) referred to as compression functions because they take a sequence of bytes and shorten it to a smaller sequence. One way to do this is to simply truncate the sequence (for example “Java Gaming” could be hashed to “Java”), but it’s generally better to have some type of random output. This way “Java Gaming” and “Java Programming Language” don’t create a hash collision. One good reason to never call a hash function a compression function is that it can easily be confused with a compression algorithm. A compression algorithm also shortens a sequence of bits, but in a way that is meant to be reversible.
In a way, hash functions work the opposite of a random number generator. A random number generator may take a 32 bit seed and be used to create a much larger sequence of random numbers. A hash function takes a long sequence of bytes and can convert it to a “random” 32 bit hash. A PRNG always produces the same output sequence given the same seed. And a hash function always produces the same hash given the same input.
This article uses H(X) = Y to represent a generic hash function. X is the input and Y is the output, or “hash,” or “hash value.”
[h3]1. Cascade Effect and Relation to PRNGs[/h3]
The cascade effect says that if you change one bit of the input to a hash function, then about half the bits of the output should change, too, on average. This means that H(“StringA”), H(“StringB”), and H(“StringC”) all produce very different output. A random number generator where each output bit had a uniform probably of being zero or one will produce a similar outcome. One way a cryptographic PRGN can be created is to take the hash of a counter using a cryptographic hash function, although this would be too slow to use in a video game. Some general purpose PRNGs operate in the form [icode]state = f(state);[/icode] where f(x) is a one-to-one hash function. Special care must be taken to ensure that f(x) has a long enough period for all valid states and that its sequence still appears random.
[h2]iii. Randomness, collisions, and Hash Tables[/h2]
Hash tables take advantage of hash functions to make make fast searches for key values. Java’s hashCode() function compresses the data represented by an Object (such as a String, which can be much longer than 32 bits) so that it can be manipulated as an int. The first location the hash table looks for an object is at array index [icode]key.hashCode() % arraySize[/icode] If different values map to the same array index (or hash value if not further compressed using %, then those two values are said to cause a collision using that hash function, which makes look up slower. Collisions in hash functions used in procedural content generation may create visual artifacts. Good hash functions are unpredictable, have the cascade effect, and are statistically as likely to produce one value as any other, so that the chance of collision is minimized.
[h2]iv. Procedural Content, Salting, and Spatial Hashing[/h2]
Hash functions are useful for generating random values that can be found without sequential access or a look up table. For example, if I had a randomly generated RPG world but if I wanted the same people to appear, I could combine a hash function and RNG to generate similar characters with the same name in alternate realities. In this example Bob may be a character with brown hair, a green shirt, blue pants, black shoes, and no glasses. In other save file, he might look the same but have brown hair. Or have glasses in a third save file.
public static Character createCharacter(String characterName, String worldId)
{
// Seed RNG by NPC name
Rng rng = new Rng(characterName.hashCode());
Character c = new Character(characterName);
// Set basic characteristics of NPC
c.setHairColor(rng.nextInt(0, MaxHairColorId));
c.setShirtColor(rng.nextInt(0, MaxShirtColorId));
c.setPantsColor(rng.nextInt(0, MaxPantsColorId));
c.setShoeColor(rng.nextInt(0, MaxShoeColorId));
c.setGlasses(rng.nextBoolean);
c.setGlassesColor(rng.nextInt(0, MaxGlassesColorId));
// Reseed RNG
rng.reset((characterName + ":" + worldId).hashCode());
// Modifiy character slightly in this alternate reality
switch(rng.nextInt(0, 5)
{
case 0:
c.setHairColor(rng.nextInt(0, MaxHairColorId));
break;
case 1:
c.setShirtColor(rng.nextInt(0, MaxShirtColorId));
break;
case 2:
c.setPantsColor(rng.nextInt(0, MaxPantsColorId));
break;
case 3:
c.setShoeColor(rng.nextInt(0, MaxShoeColorId));
break;
case 4:
c.setGlasses(!c.hasGlasses());
break;
case 5:
c.setGlassesColor(rng.nextInt(0, MaxGlassesColorId));
break;
}
return c;
}
Another way to use hash functions is to hash x-y coordinates. Separate your game world into grids and randomly generate content in a grid one grid at a time. You can generate them all ahead of time, or you can generate them on the fly by using a hash function H(x, y) to seed the RNG in that grid location. When the player leaves that area, you can forget about that grid cell and recreate the exact same area the next time the player goes to that area.
One potential problem with this approach is that if a person replays the game, all maps will be the same. This may be desirable. (And it may be helpful. Procedurally created worlds may let you distribute a small binary file and no extra resources (Java4k?) and still have consistent user experience.) One way to change the output of a hash function is to add a “salt” value. You could store the salt in the player’s save file or derive one from their username. Modifying the salt is like modifying the RNG seed. Utilizing String’s hashcode function again, you could have a salt-less version of a hash function that returns [icode](x + ", " + y).hashCode()[/icode] and a salted version that returns [icode](playerName + “…” + x + ", " + y).hashCode()[/icode].
Spatial hashing is one you take a point in multidimensional space, determine what grid cell (square, hexagonal, cubic, or whatever) it is in, and convert the position of that cell to a value.
[h1]III. Other sequences[/h1]
Other sequences may be used that look random to humans and provide certain properties, but aren’t actually. Halton and Sobol sequences are examples of low discrepancy sequences and are also called quasi-random sequences.
[h1]IV. Noise[/h1]
Noise combines one or more of the above forms of randomness and algorithms to produce a desired affect. Perlin noise, for example, requires a grid of random values, which can either be derived ahead of time using an RNG (for small grids) or on the fly at any point using a hash function (for large or infinite grids,) and interpolates between those values for other locations.
White noise in the real world represents a signal with many many frequencies present over an entire spectrum of frequencies. The intensity of the noise is completely random. You could convert the output of an RNG to a PCM sound data to produce (1D) white noise sound or set the brightness of each pixel in a black and white image to the output of an RNG to produce a (2D) white noise image. White noise generally isn’t very useful.
Noise may be generated with specific aesthetic, frequency spectrum, or structural properties instead. See other articles for descriptions of types of noise, noise algorithms, and applications of noise.