jeremy's neglected site

Procedural World Generation

2014.01.17 01:45:42

Summary

I have been working on making a video game, and wanted an excuse to do some procedural world generation. Procedural generation of some kind is a part of a lot of the games that I like to play, and it seems to be what the cool kids are doing nowadays. This is a collection of links on procedural programming, and how I'm working through my ignorance to better understand it.

Details

I'm never ignorant while I'm still ignorant. That's probably why, absently mindedly, I spent ~2 hours searching the internet for "procedural world generation" and not finding the tools or the code I needed. I was asking the wrong question, and it dawned on me I was ignorant. Good to get that out of the way early.

I asked the almighty Google slightly different questions, like "perlin noise" and "procedural world generation with noise functions" and "voronoi diagrams." Refining my search I ran into some links that were immensely helpful for getting my going in the right direction. While all of the links below were useful for me, the order of the links represent the chronological usefulness of the articles in descending order.

  • Perlin Noise: This site makes me love the internet. This would have been enough, and I wish I would have found this site first. Includes easy to understand pseudocode.
  • libnoise Tutorial #3: Down at the bottom of this page are two images, side by side, that helped the "why" of procedural world generation click for me.
  • Ken Perlin's "Making Noise" talk: After working with code, I found this talk really useful for putting more of the "why" pieces together.
  • Ken Perlin's Noise and Turbulence: History is good, and the code is great should you wish to take and tweak a C implementation.
  • Polygonal Map Generation for Games: I found this article fascinating and am looking to find a way to integrate Voronoi Diagrams into something that I work on. I haven't touched this technique yet, and I include this here as a "tip of the iceberg" article about what else lies out there beyond the well known techniques discussed above.

For those of you that just want code (I know you exist, I'm one of them), here's my very first, very simple experiment in Python with Pygame. It's okay to laugh at my code, you won't hurt my feelings, but if you have some good ideas, feel free to comment on github. I'll try to remember to update this link if I move/change the location of the code.

If you read the articles above and mess around with code examples you can find on the internet, you likely don't need to read anything that I'm going to write about. I consider myself a n00b in this area. However, if reading someone else's learning process helps you, then read on.

Wrong Assumption #1: I'm not generating a world, I'm generating numbers

This one should have been obvious, and it was, but it also wasn't. Thinking of my world as a grid is obvious. Generating random terrain for my world was obvious. Getting the numbers to act like a world was not. I quickly learned the error of the following Python code:

from random import random
from pprint import pprint

# Generate a grid of "terrain"
coords = [[random() for i in range(2)] for i in range(2)]
# Fail to make sense of the grid.
pprint(coords)

# Output from pprint (you will get different numbers).
# [[0.35353647466830207, 0.03712863075423578],
# [0.4205671728924276, 0.8831232619764249]]

My clue phone started to ring:

  • I needed something that was easily reproducible and tied to a specific coordinate system (or coordinate at a specific time, or other dimension).
  • I wanted something that took an input on each call that acted as the seed.
  • The most obvious terrain that I would be creating represented elevation or a Heightmap, and that would require giving meaning to the numbers within the range of values produced.
  • I needed some way to get those numbers to not be so drastically different.

Last bullet point above, biggest problem to tackle. Using the random number generators I always used, in the way I used them, I might end up with a water grid next to a sheer, snowy cliff, followed by desert, followed by another cliff, all within a range of 4 pixels.

This is where the articles that I read (and continue to find and read) helped make sense of the situation. The "noise" was the random number, but it was only a piece of the procedure. The way the number was processed, and the way in which the number was related to nearby noise coordinates was not some static, set in stone, one way to do things process. There was no "is right noise" or "is wrong noise."

I know for people reading this, if this is the world that you swim in, this was probably a "no duh." For me it was a relief because it took the mystery out of the "how" part of the process and just left the "what to do with the process" and "why do this." As the days pass (I delved into this 2 days ago before writing this up) this feels as cool as when I figured out "how/why functional programming" or "how/why async/multiprocess programming." Just like these other tools, it's merely one tool out of many and this tool alone will not solve all of my "world generation" problems, but it's a great start.

I love programming!

Time to code

Okay, enough elation. Here's a few thoughts that I've had after playing around with some code:

Different number generators for different jobs

I wonder, and have not yet tested:

  • What if I wanted rolling hills, would a sine or cosine wave influenced generator be useful in certain areas of a game?
  • Would a random number generator that had a small period of randomness before repeating itself be useful for creating a procedural texture paintbrush?
  • Can I get away with using the same number generator for 1d, 2d, or 3d noise or do I need something that is slightly different or different coordinate systems?
Different processing for different situations

Relating each individual number to its neighbor played a huge role in the world that resulted on my screen. Some of the links above do a good job showing how unfiltered noise works for generating believable textures: unfiltered noise is not usually useful.

With a bit of tweaking, I am just beginning to see the potential of using this to create the baseline terrain for a game world.

  • I can lower every number creating more water.
  • I can force each number to be more influenced by its neighbors and create a world that ends up flatter and closer to sea level.

For every believable dungeon/world/town/planet that I've seen there is likely a patient programmer working on and tweaking how the world generation works for their specific needs.

Procedural generation comes at a cost: CPU time

My first attempt at generating a simple world using Python and Pygame with cut-and-paste code was for a 600x600 pixel grid. Granted the code wasn't optimized very well, I wasn't expecting to see the beach ball of death on my Mac. Good to see this problem early, as solutions seem pretty straightforward.

  • Generate large chunks of the world and remember them, writing them to disk when needed.
  • Generate small chunks of the world in the background, and on an as needed basis, only saving the deltas to disk.
  • Run the world generation in a background process, and request chunks of the world from the main process when needed.

Right now I like option 3, but I'm too new at this to know what's really the best solution for a game. My gut tells me they're all useful in certain situations.

One routine will not rule them all

One of the articles I read made a good point about a single pass world generation: heightmaps are great for building up a world, but what about rivers that should be drawn flowing down hills?

Or one routine might be good for fires, and another good for clouds.

Perhaps a completely different procedure would be needed to generate caves with stalactites staring down at the stalagmites.

Knowing what I need in my world will determine the sort of routines, and post-processing that I'll need to invent.

Conclusion

It's always nice to have an excuse to learn a new programming technique. Projects, simple they may be, give me a reason to solve the bugs I will end up writing as I learn. And writing a game is a great excuse to learn procedural programming.