Gaming: Generating random world content and some consistency algorithms...
Generating random world content is one of those tasks that gets written off as a trivial matter. It isn't hard to throw some stuff around a virtual space and call it good. However, after trivializing the world content generation during your first game, you'll never make the same mistake twice. You should set aside quite a bit of time to think about your algorithms, employ consistency checks early on, and future proof your algorithms against later enhancements. Exactly how much time you should set aside is a project planning consideration based on how complex your world content is going to be.
Planning Units
The first thing you should do is plan to set aside some time to work with your world units. Depending on the world space you are working in you might be required to take into consideration several dimensions of space. Another feature is whether or not the game-world is broken into consistently sized chunks (aka a grid) or whether it is a free-positioning coordinate system (using floating point numbers to define location). The size of various object should also be considered since allowing multi-square items in a grid system or arbitrarily shaped objects in a free-positioning system drastically changes the next few steps of the process.
Basic Consistency Checks
Consistency checks help keep a given random world playable and even more importantly, believable. They are heavily linked to your units and how your world space is broken down. In fact, most of the values in your game related to world content generation will probably be aggregate values built from more basic variables. Because computations are involved you have to make sure each aggregate value is consistent across the board and consistent with how you expect your game to be played. The means the first type of consistency check is a playability check:
// Terrarium Pseudo Example Code
int EnergySpentStandingStill = 20;
int EnergySpentDuringMinimalMove = 18;
if ( EnergySpentStandingStill >= EnergySpentDuringMinimalMove ) {
// Playability hack since moving uses less energy than standing still
}
Playability checks are most often the result of a broken aggregate chain. Normally, we'd derive our value for movement energy directly from the value for energy spent while standing still. If we do that, and as long as someone doesn't change the constant multiplier to some value less than or equal to one, then we should be safe. But safe should never be taken for granted, and the consistency check should always be there. When tweaking game rules to improve playability, you'll often make mistakes that would create inconsistencies that would be found with playability checks.
Bounding and range checks can be even more important. I've actually played commercial games before where I was required to perform some task that would never be possible. For instance, a mini-game might required that you achieve a score, but not provide enough elements to achieve that score. Another problem are hunt and search games where a required element is inaccessible. Three colored keys and a set of matching doors will quickly show you that the placement of the keys is important to opening the doors in the proper sequence. If the blue door is first and the only accessible key is the yellow key, then you might have a problem.
// A sample bounds check based on a grid
int gridSize = 10; int gridArea = gridSize*gridSize;
int apples = 10; int pears = 80; int oranges = 50;
if ( (apples+pears+oranges) > gridArea ) { // We can't even place our elements }
// A sample accessibility check
bool accessible = false;
if ( Accessible(BlueKey) ) {
Unlock(BlueDoor);
if ( Accessible(YellowKey) ) {
Unlock(YellowDoor);
if ( Accessible(RedKey) ) {
accessible = true;
}
}
}
if ( !accessible ) { // We have a problem! }
Accessibility is almost a section of it's own, but it is a form of spatial boundary check with respect to a given world-state. I'll leave it up there. The primary set of checks are just to make sure numbers are consistent. If you have to get 50 points to win, make sure 50 points are possible. If the player needs to create 50 points in 3 minutes, but it takes 6 minutes to get enough pieces, then that falls under a boundary check and should be caught.
Density Checks
There are checks that are dependent on more than just counts and derived aggregate values. For instance, you may be required to place 50 pieces, and so you do. If you are using a grid system, you can easily find that 50 pieces should fit in a 10x10 grid. What happens when some of the pieces are different grid sizes. Perhaps some take up 2 squares, 3 squares, or even 4 squares. Now you have a density check. You have to add the size or area of each element and check that against the available space.
We had some very important density checks to solve in the Terrarium. For instance, we needed enough room to store up to 250 creatures and plants. On the same note, we couldn't fix the world size because then systems with 60 creatures and plants would be too spread out and they'd run out of energy finding other plants and animals to eat.
Density checks may also help ensure believability in the game. If you find an apple across the screen from an apple tree, you might get confused. You might need to check that all apples are within a certain distance of the tree. Stack these distance checks with some boundary checks to ensure each tree has a range of apples surrounding it and you've created a full on consistency check for one of your game elements.
Density works in reverse as well. You may need to prove a minimum density in order to make elements well dispersed. Take Squirrel .NET and the addition of trees to the game world. A squirrel can only carry a specific number of nuts at a time, and they need to stop by trees in order to store them. If all of the trees are in the same spot in the game world, then making a choice about which tree to go to isn't a big deal or make a big difference to solving the puzzle of collecting the nuts. Ensuring that the trees are evenly spread is really important. A great consistency check is to logically shrink the grid, and ensure that trees don't exist in the same grid space.
// Squirrel .NET Game World Enhancement
int gridSize = 10;
int halfSize = gridSize / 2;
bool[,] used = new bool[halfSize, halfSize];
for(int i = 0; i < trees.Length; i++) {
if ( used[trees.X/2, trees.Y/2] ) { // Inconsistent }
used[trees.X/2, trees.Y/2] = true;
}
// Reversing the consistency check into a generation algorithm
int gridSize = 10;
int halfSize = gridSize / 2;
bool[,] used = new bool[halfSize, halfSize];
Tree[] trees = new Tree[10]; // Place 10 trees
for(int i = 0; i < trees.Length; i++) {
trees[i] = new Tree([1..10], [1..10]); // Pseudo range generator
while(used[trees[i].X/2, trees[i].Y/2) {
// Pre-Consumed, loop
trees[i] = new Tree([1..10], [1..10]);
}
}
The nice thing about consistency checks and generation algorithms, is that they are heavily reusable in many different circumstances. In the abstract the objects you place are just objects, and they take on more specific roles once you label them and apply graphics. A layout scheme for 15 different elements in a 2 dimensional grid is easily reduced to an algorithm that might work for laying out two different types of elements in a completely different program. If you come up with anything impressive, feel free to toss it up in the comments!