Something I’ve done a little less than I should have over this series of blog posts is discuss areas in which I’ve been required to do research and expand my knowledge, so I figured I’d make a blog post just discussing some of the various things I’ve been looking up, focusing on the area of procedural generation.
I’ve done randomly generated environments quite a few times in the past, however most of these times the environment was generated as you go, but not revisited (such as a free faller), or generated within a limited area (such as a set size map). Both of these types of random generation are extremely different from what is required from our game. For these sorts of projects there’s been a lot of focus on using random number generation (which isn’t as useful for me currently, as discussed below) as well as some 2D algorithms such as perlin noise.
Random number generation provides a series of (seemingly) random numbers given a seed. Each number is used in the calculation of the next number, therefore, to get the 20th number, the previous 19 must be calculated first (PCGW, 2015). The problem with relying on random number generation for this game is that there is no underlying order in which chunks will be generated or accessed by the player. Although this may be appropriate when working with AI’s or with other behavior which is enclosed, it isn’t for chunk generation. Chunks fundamentally rely on having the same terrain each time you visit them, and for all chunks seamlessly connect to one another.
Hash functions on the other hand, are provided with a set or arguments as well as a seed, and will calculate a result (PCGW, 2015). This result will always be the same whenever those arguments are passed in. A good hash function however will have seemingly no relation between two values generated by extremely similar arguments. To help visualize, I have a hash method which will take in numbers (for example, an X coordinate and a Y coordinate). If this hash function were to be called for every pixel on an image, the resulting image would be (pseudo) random noise.
Apparently creating these hash functions is not an easy task to any extent, and numerous people have tried with varying results. One of the links on the PCGW site took me to a blog post which does an extremely good job of explaining the difference in quality between various hash functions out there (Johansen, 2015). I’ve chosen to go with one called xxHash. Below is an image from the blog post which is showing some difference in quality between 3 different hash functions.
I’ve utilized the hash function in the generating of the caverns to ensure that the same structures form when revisiting chunks, and removing any need to save data about the terrain. It also provides me with the benefit of being able to take note of a seed in the case of an issue in generation, and being able to revisit that exact location to reevaluate the problem, and to see when it’s fixed. If I had to search for a rare problem in the terrain every time I pressed play, there would be a lot of time wasted.
References
Johansen, R. S. (2015, Jan 1) Primer on Repeatable Random Numbers. Retrieved May 5, 2015 from http://blog.runevision.com/2015/01/primer-on-repeatable-random-numbers.html
PCGW (2015) Hash Function. Retrieved May 5, 2015 from http://pcg.wikidot.com/pcg-algorithm:hash-function
PCGW (2015) Pseudorandom Number Generators. Retrieved May 5, 2015 from http://pcg.wikidot.com/pcg-algorithm:pseudorandom-number-generator
