September 20, 2010 12:00 AM |
['@ Play' is a monthly column by John Harris which discusses the history, present and future of the Roguelike dungeon exploring genre. This time, he continues his coverage of his roguelike-inpired game Mayflight by examining how he implemented key facets of the title.]
This is the second half of our coverage on Mayflight, an algorithmically-generated exploratory platform game of interest to this column due to the roguelike game borrowings made by its creator and developer. That person is myself, John Harris. The first half, which contains download links, appeared here.
This time we focus on some of the under-the-hood aspects of the game: the room and area builders, the random seeding system that makes the seemingly-infinite game world possible, and the algorithmic background generator. The first article covered some aspects borrowed from or inspired by roguelikes; this one is my attempt to give back to the genre, listing some elements of Mayflight's design that might be interesting to the community. Chief among them are the background generator, which turned out surprisingly well, and the room builder routine, which utilizes a system, to my knowledge, that has never been used in a computer game before.
This article is probably most interesting to developers. I apologize to the more general roguelike enthusiast audience, and assure you that we'll be returning to @Play's more traditional stomping grounds next time.
Mayflight's world consists of an overstructure made of areas, each of which contains multiple scrolling units called rooms. When an area is generated, it produces a set of graphics and room-building parameters that give each area a consistent appearance that applies throughout. (There is code in place to allow for multiple sets of such parameters in each area, but it is old, dusty and not used.) In this version of the game each area isn't large enough to need much variety in appearance within a zone; if a substantially-improved version of the game is created, this code will certainly be cleaned up and pressed into service.
One of Game Maker's most unfortunate quirks is its lack of native support for arrays of greater than two dimensions. There are ways around this, such as using very large arrays and a functional interface to convert coordinates or making clever use of hashes (called “maps” in Game Maker), but a couple of other limitations further restrict what is possible in the system. Even one-dimensional arrays are limited to a maximum index of 32,000, there is no such thing as a “struct” in GM, and even objects and classes are mutated enough from their traditional forms that one must think hard about their use. Considering that it essential to hold more than one piece of data about each screen-sized unit of each area map, I ended up using both parallel arrays, same-sized arrays that held related data across indexed cells, and bit-manipulation to squeeze as much information into the game's arrays as possible.
Each area consists of a region nine by nine screens in size. There is an array that holds the connection data between each screen as a set of bit fields. It contains extents, which adjacent screens are considered part of the same room, openings, places where a screen at the edge of a room connects to an adjacent room, and area openings, which are the same but for rooms at the edge of an area. Openings between rooms are always across the same stretch of blocks vertically or horizontally, which means not having to pass around extra data about passage sizes. Similarly, areas connect with each other only in the middle of each side of the between-area border. Areas are not generated until needed to by the game, so something like this was necessary to make sure the player wouldn't emerge into the next area inside a wall. (There is probably another way around this problem. Maybe later....)
Rooms are placed first by randomly placing rectangles from 3x3 to 5x5 screens in size, then, when enough attempts have been made that have failed due to being blocked by already-placed rooms, to go in and try to place a room in every possible place starting from the upper-left corner, until the whole area is covered. It is not a perfect system; in fact, it is purposely imperfect. A better system would create a less-biased array of rooms. As it is, the edges of each area are more likely to contain one-screen wide or tall rooms, which are desirable exploration targets due to their greater likelihood of containing items. This gives an observant player an edge he can utilize to get a leg up on the game. As described last time, the design of the game is intended to be such that all games are naturally doomed, by the ever-decreasing supply of sparks*. While the player may not be able to overcome the diminishing spark count, by devising strategies to further his progress in the game, he can make greater headway against it over successive games.
*Note: this is the plan. But there may actually be a way around the diminishing spark count. Defeated enemies grant a small time bonus. While sparks become less common throughout the game, enemies become more common. There are a couple of ways to become invincible for a limited time. It's possible for a really really good player to possibly take advantage of them to maintain a positive time income even in situations that offer no sparks at all. I've not done this yet, and it would require stellar skills and presence of mind, but it's theoretically possible. It would only happen late enough in a game that certainly 95% of players will never get to a state that allows them to make effective use of it.
The room builder uses an algorithm I discovered a couple of years ago that, to my knowledge, has never been used for terrain construction in a computer game. I describe it here. For illustration purposes, it would be useful to start up a copy of GIMP right now. (People with Photoshop can probably find similar operations.)
Take an empty image document. Using the appropriate filter or plug-in, fill it with random noise pixels. It doesn't really matter if they're only 0/255 or a range between the two, although I prefer the former. In GIMP, you can do this by selecting Filters > Noise > RGB Noise, then turning off Independent RGB and turning on Correlated Noise. The result should look not dissimilar to television static. Now, go back into the filters and select Gaussian Blur at a value of, say, 5 pixels radius. In GIMP, make sure horizontal and vertical are set to the same amount. Now, go under Colors > Brightness & Contrast and turn Contrast all the way up. This effectively posterizes the image, setting values 128 and up to white, and those below to black.
The result should look a fair bit like gurnesy spots on cows. What has happened is that the blurring has given the random noise some structure, which the contrast operation brings out. The size of the spots is directly related to the radius of the blur operation. If you had made the horizontal blurring greater than the vertical blurring, the spots would naturally be elongated horizontally, and vice versa. Gaussian Blur uses a round pattern in spreading out each pixel's color to the surrounding areas; what would happen to the spots if the pattern were shaped differently? And as playing with the Brightness slider and watching the live preview will show, you can control how much of the image is white or black simply by adjusting where along the scale the cut-off value lies, and the resultant blobs maintain a sort of similarity of detail even as you add or subtract white from the image. And what if you started from an image that wasn't pure noise? What if important features were drawn on the grid beforehand? What would happen to them?
Mayflight room builder uses a processes similar to this. Instead of starting with a field of random garbage, it begins with a zero'd grid. There are a number of special codes which are then drawn onto the grid. Many of these codes, most importantly for the outer walls of the room, are “hard coded” walls, that can influence the surrounding area but can't be changed away from walls themselves. A pass is made over the grid and for every “zero” cell, a shaped pattern around it is added to the adjacent cells in the result grid, randomly chosen to be either 128 or -128. To ensure all the exits can be reached, some mandatory spaces are laid down too. When it comes time to render out the map another pass is made: hard-set cells have priority, but those that are not set so solidly get walls or spaces depending on whether their values are greater or less than a center value, usually 0 but possible to be more or less if needed. Then another pass yet is made, which “smooths out” the map a bit, removing some troublesome kinds of terrain situations that proved annoying in playtesting. (In a future version of the game, more interesting tile types like slopes could be added here.) Finally comes the spark and item placement pass.
Thanks to Game Maker's generally rapid execution speed (one of its greatest strengths in my opinion) these four passes usually take less than a second and so can be done on-the-fly, upon room change. Game Maker's data type support, only available in the “pro” version, contains one type that it calls “grids.” Grids are like arrays, but of a generally-fixed sized, less flexible, and accessed only through a functional interface. In trade for all these drawbacks, grids are somewhat faster than arrays, and they also support bulk math operations, such as adding all the cells in a grid to the cells in another grid. Utilizing these both increased the speed of, and helped simplify, my code by allowing me to avoid iterating through still more nested for loops in applying each space's “influence” around its neighbors.
The core of Mayflight's gigantic world comes from using some of the fundamental properties of a pseudorandom generator to provide a source of reproducible arbitrary values. Other games have used such a system to make for reproducible adventuring worlds in the past; notably, Stormfront/SSI's Dungeon Hack used such a system, and took advantage of it to allow players to re-play dungeons by entering a specific dungeon seed value.
A brief primer on some concepts of pseudorandom number generation is called for here.
Pseudorandom number generators work by applying an obfuscation function to a seed value. The result of the function is usually a number from 0 to 1. This value is returned from the call, but is also retained by the generator to serve as the seed value for the next call. Thus, each value is directly determined by the value that produced it. Pseudorandom generators thus produce set sequences of numbers. They follow a pattern, but the obfuscation function uses various mathematical operations to attempt to reduce the predictability of the sequence that us exposed to the program. One consequence of this system is that, if two seed values produce the same output, their sequences essentially “merge,” and become identical from that point on. Thus, pseudorandom generators strive to iterate through many non-repeating values. The results that your program sees may well have repetition in it because what you see often has information that has been discarded from the seed values, but internally these mechanisms strive to maximize their periods.
Computer software usually goes through this convoluted method to provide an appearance of randomness because computer systems, being deterministic machines by design, find it difficult to produce randomness. Often, to introduce true uncertainty into a generator, a program will seed it with a number derived from the system time-and-date clock, or use a hardware source of randomness (such as the white noise generator on the old Commodore 64 microcomputer), or, in the case of Linux operating systems, even maintain a system “entropy pool,” a collection of odd data noted by the system, such as the low-order bits of the timing of user keypresses, which being disassociated from their original sources makes for a useful source of unpredictable bits.
But to return to the subject under discussion, the take-away points are: if you supply a given seed value to a pseudorandom number generator, you always get the same value out; that value will appear to have nothing to do with the value provided to it; and the generator is automatically re-seeded with the result. It is these properties that make possible Mayflight's near-infinite game world.
When the player begins a game, the game seeds the generator with system time and generates a number to serve as the game seed, a large integer* that applies to the whole game. This is saved, and it also serves as the area seed of the starting area. Areas are identified internally by their global coordinates, which are its distance from the starting area. These coordinates are linearized by multiplying the global area Y coordinate by 1,000,000, adding it to the global X coordinate, adding the result to the global seed, then adding and mod'ing the result by a value I call “verylargenum,” a value determined experimentally to be an extremely large number that works well with Game Maker's math routines. (I discovered, the hard way, that no matter how large a value you ask for, Game Maker will never produce numbers greater than a certain quantity, and that its modulo operator also sometimes breaks on huge values.) For the record, verylargenum in Mayflight is set equal to 10,000,000,000. (Note that, since the Y coordinate offset divided by verylargenum is just 10,000, if Aurora were to explore 10,000 areas above or below the start location, the world would cycle. If the Y offset were 100,000 instead it would probably be better, since it'd be longer before the world cycled, although probably no player will ever go even 10,000 areas away in a single game.)
When the area builder is invoked, right at the start the area seed is determined and the pseudorandom number generator is seeded. Area generation proceeds in a way that it doesn't rely on outside information, other than the random generator, to construct the maze, so it builds the same way every time the player enters it. From this a name for the area is picked. In the current version of the game the area name isn't visible to the player, mostly because often it doesn't end up describing the area that gets produced, but it does influence which basic template values are used for the graphics and room layouts. Each room also has its own seed, derived from area seed + (room number * 77,777). (That number chosen to make it less likely that adjacent areas will have similar rooms.)
Using this system, every area and room has its own seed, used when generating it, and which produces the same layout of rooms/walls upon every visit. Effectively, the game universe is 10 billion areas in size, so large that it's unlikely that a player will ever see the same zone more than once. Some other factors come into it as well; certain types of difficult room generation are never used two or fewer areas away from the start location in order to give the player a fighting chance in the early game. Since these outside variables used in this check are the same every time the player returns to the area, persistence is preserved.
The background generation system is probably the greatest success in Mayflight's development. I had no idea that it would turn out as well as it did. I just sort of haphazardly hacked it together, patching in ideas as I thought of them. The resulting graphics look a lot better than a quick-develop game project has any right looking, and I think do a lot in providing each area with a unique feel. Here I describe just how the game puts them together, and why I think they work.
First, when an area is created, the game creates the area's name. It then sets all of the background graphics parameters to a boring set of defaults. The game, going from a number of flags attached to each part of the name, selects from a number of preset background templates which customize the boring defaults, and then determines a main color for the area. Also influencing the main color is the color of the tileset used for the walls. From the main color, the base background color is derived by “mutating” the main color a bit. Other major element colors are also made by mutating the main color. Mutation is done by taking the main color as a HSV value and changing one of the three values a bit. (HSV is a much more sensible system for random color permutation than RGB I discovered. If you just change one of the values a bit, you're almost certain to end up with a color that looks good alongside the original.)
After this, the area parameters are run through a function that further mutates all of the variables that go into background creation. The way this works is, the Cartesian distance of the current area from the start is multiplied by 15. Let's call this value the loop score. Then a massive random switch statement is run until that value reaches zero. Each entry in the switch randomly permutes one of the many variables that go into background creation and reduces the loop score a bit. “Bigger” changes reduce the loop score by more than little ones. In this way, the further the player travels from the start, the further the graphics drift from the boring base values, which provides a subtle extra reward for getting far into the game. It also makes “uglyzones,” my name for areas with unappealing backgrounds, less of an aesthetic flaw and more of a kind of easter egg for players to find, e.g., “I got so far the game's graphics started going weird!” It must be said, however, that the current iteration of the graphics routine produces uglyzones surprisingly rarely, even after exploring 3,000 meters.
So, how are the graphics actually produced? Well....
One of the things determined in the background presets and mutation steps is which background sprite to use in this area. 21 of these are included in the game. They're all pretty abstract, intended to be more impressionistic than representational, although there are exceptions to this. In addition, a “backsprite” is also chosen that may or may not be used. This is usually the same as the background sprite, but the mutation function can make it something different. Also an “erasesprite” is chosen.
Backsprites are drawn “behind” the background sprites as part of a separate step. They're drawn a bit bigger, but a bit faded compared to the background sprite. The “erasesprite” is similar, but it's drawn in front of the background sprite, a bit smaller, and its default is the same color as the background. The scaling, rotation and color factors of each of these sprites are exposed to the mutator function, and may end up subtly diffferent, changing the effect.
The object of all this is to create interesting negative-space shapes between the background sprites and backsprites, which are further enhanced by the erasesprites. Each step of sprite drawing is made using the same draw color, so the sprites of each step tend to merge together into a large shape. This drawing is done once behind every foreground tile, so the result is large, continuous, abstract structures that seem to follow the foreground. The human mind tends to look for patterns even where they don't exist, and thus the abstract graphics sometimes match up with things from its experience. All of these factors do their part in producing interesting background effects for each area.
When a room is entered a graphics surface of the same size as the room is created. It's filled with the background color. Three passes are made through the room's tile array. (Mayflight doesn't use individual tile objects, which is the “official” Game Maker way of making maps, by the way; for speed's sake, it handles all collisions by comparing them with an array of tiles.) The first pass covers the backsprite drawing, so they all seem to be on the same “layer,” one covers the primary background sprites, and one draws on the erasesprites. It's possible for either the backsprite or erasesprite steps to be skilled, again depending on the mutator function's chaotic proclamations.
The mutator function can also change some of the variables used by the room builder, which allows it to produce unusual room superstructures in odd cases. I've seen it create huge boxes, towering spires, floating regular rectangles, large, airy regions and other types besides.
Now that you have some explanation for how the background graphics are created, go to the screenshots in this article, and in the previous column on Mayflight, and see if you can see how the system I described was able to construct them. It's really a simple system, but I'm continually amazed by the visuals it can produce. With a bit more work, it might be turned into something really useful.
Whew! This concludes the implementation description of my random-world platformer, Mayflight. Next time we'll be back on our usual beat. I'll probably cover Dungeon Crawl's challenging new game mode, Dungeon Sprint. Until next time....
Categories: Column: At Play