My Future in Procedural Generation (Procedural Generation 101)
Working on Faerie Tale has been VERY good to me. I've sharpened my coding knowledge a great deal, and I've learned a lot of new tricks and skills.
At this point, I'm pretty certain I could run Faerie Tale on an improved engine that draws its tiles from file, perhaps even drawing the graphics based on its terrain data. This opens up a lot in terms of faster development and more complicated tiles, not to mention I could let other people design tiles to divvy up the work. Cool, no?
But there's more. Faerie Tale is actually capable of reading multiple terrain types with basic tweaking. How it would react to this depends -- the easiest is selectional walls; like floors you can jump up through. (Falling back down through them should also be a fairly simple addition)
And this is just stuff I could modify to Faerie Tale's engine. I have bigger projects in mind down the line. In foremost, I want to escape the horizontal-only scrolling of Faerie Tale. But I'm also interested in making cohesive worlds -- spontaneously.
Let me tell you about my next ambition -- but before that, I want to explain something really awesome that I've developed in the process. This is all theoretical, but I have no doubt I can make it work.
Table 1: The Empty 8x5
So, here we have a big, empty world. It's 5 tiles tall and 8 wide. Think of this as a small stage in a game that has nothing in it. We start the game, and it drops you into void, and you fall till you fall off the bottom and then die. Or maybe wander until you hit an edge and have nowhere else to go. It's big and it's empty. So let's give it the first stage of characteristics.
Table 2: The Simple Landscape
Aha! Now there's something to look at. This world isn't big and empty anymore... but... what is it? This technique can be applied to any 2D (or theoretically 3D , but that's a little beyond me, code wise) games that have a landscape.
Maybe this is Metroid, and the colors are different areas? Or this is Zelda, and the Green is grassland, the Blue is water and the Red is a dungeon. What you need to think of these as are cohesive screens that represent a KIND of place, but not the place itself. Each green piece is a screen that could be potentially identical; think of the color as a theme. Everything that has the same color has the same theme, so they all match each other. But this isn't a landscape yet. And my original designs in Faerie Tale work a lot like what you see here. There's not enough category yet to make something really complicated. So one more time in to the breach!
Table 3: Path Types
┌ ┬ ┬ ─
─ ─ ─ ┐
│ │ └ ┬
─ ─ ─ ┤
│ └ ─ ┼
─ ─ ┐ │
│ ╟ ─ ┼
─ ┐ ╧ │
╧ ╟ ─ ┴
─ ┴ ─ ┘
NOW we have a defined landscape. Now, I see this as a Metroid style map, myself, but what we've defined here is the basic shape of all the rooms. If the lines connect, the rooms connect. The double lines indicate a dead end.
At this point, I bet you're asking why this is exciting to me, as a model. But we've done two important things here.
We've defined LANDSCAPE type and PATH type. As a random level generator goes, these are simple definitions. A Landscape type tells us what kind of colours and images to use; it's about graphics. Faerie Tale only uses one, thought it was meant to use three. The PATH type is the exciting new bit.
See, one of the biggest issues with random generation like in Faerie Tale is time. If we don't narrow down the tiles we're using when matching, it can take forever to find an actual match. The more tiles available, and the more variety between them, the longer it'll take to find a match for that tile, which could render the engine useless at a certain mass.
When we define Landscape and Path type, we're limiting the number of tiles the game has to keep track of when doing any one match.
So what's Path type? Well, it determines which of its edges are open, and which aren't. What it doesn't determine is what the content between those edges are like, or even what the edges are like. It's just a class of tiles with a certain subset of edges. Assuming nothing crazy, there's then six basic Path Types: Box (0 Openings), End (1 opening), Line (2 Openings), L (2 Openings), T (3 openings) and Plus (4 Openings).
Now, for a Zelda-style overhead game, we could probably get away with just the basic 6, but with something like Metroid, we'd need to use 16 types; 1 Box, 4 Ends, 2 Lines, 4 Ls, 4 Ts, and 1 Plus. Sixteen is a bit unwieldy, but it's still a good number when dealing with something very large scale and complex. Our 8x5 is perhaps a tad too small, but that's ok.
Now, this is where database management becomes a really useful asset, and I might have to investigate Oracle or SQL or some other kind of Database, because what we want next is an index of the tiles. It should list a tile ID, that tile's Landscape and Path Type, as well as it's Edge types ( a unique identifier that describes the edge; two tiles with the same Edge type should match seamlessly), and probably any of its Tile Data (the numbers that tell the program what is solid and what is not).
Now, we have to determine how the game builds the map. I'd assume it does it by row, then by column; this way it'd be analogous to writing a sentence in english, in terms of how the characters go down.
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
This would be the order our landscape would need to use generate under my assumption. Easy enough to do.
This is important for sorting, because now we want our database to dump a reference chart that the game will use to find its tile. The chart here would read like this.
Landscape Type
+ Path Type
+ Top Edge Type
+ Left Edge Type
- Tile
Imagine this as ONE branch of a big directory. The root level is all folders of Landscape Types. In our case, that's three folders. The next is the 6/16 path types. Then folders of Top edges, left edges and finally a folder of tiles. This way, it matches all the way down, till it has nothing to match to. The tile will fit its designated landscape, it will fit it's path, and it's two pre-connected edges will be matched. Finally, it picks a tile. If there's only one tile, then that's what it picks. Otherwise, it's random.
Once it has a tile ID, it can place it on a chart of what each room is, in terms of tiles. This means a persistent world, unlike Faerie Tale, but it also means a large, complicated world, right from the get go.
Now; there's two places to go from here. One is procedural generation macro/micro. That is, an algorithm 'paints' the world with Landscape Types, then 'draws' lines through it in Path Types until you get a little landscape chart like we have above -- the macro generation. Then it starts to assign tiles to those macro definitions, making the world in to a specific object -- micro generation. Bare in mind, the micro generation could be done twice with the same macro model and each time it would (likely) be different. There's no guarantee you'd be able to use the same routes, depending on the tiles.
The other option is User Generated Content. You could easily allow a player to 'paint and draw' the map. Then the world could be micro generated randomly. Perhaps that's not interesting enough -- so the player wants more control? After the Macro generation, they could scroll through the tiles one by one to find the ones they liked, and then save the tile table at the end.
In each of these cases, the tile table could be saved when you're done and loaded later. What that a particularly challenging game? Save it and beat your score later, or maybe give it to a friend to try. Post it online, and the most popular worlds could have their own rankings! Because, why not?
I'm gonna stop this here, though. I'm going somewhere with all of this, but I think I'd like to post it separately. So what do you think -- this is Procedural Generation for games, 101, folks!
- Kagirinai
At this point, I'm pretty certain I could run Faerie Tale on an improved engine that draws its tiles from file, perhaps even drawing the graphics based on its terrain data. This opens up a lot in terms of faster development and more complicated tiles, not to mention I could let other people design tiles to divvy up the work. Cool, no?
But there's more. Faerie Tale is actually capable of reading multiple terrain types with basic tweaking. How it would react to this depends -- the easiest is selectional walls; like floors you can jump up through. (Falling back down through them should also be a fairly simple addition)
And this is just stuff I could modify to Faerie Tale's engine. I have bigger projects in mind down the line. In foremost, I want to escape the horizontal-only scrolling of Faerie Tale. But I'm also interested in making cohesive worlds -- spontaneously.
Let me tell you about my next ambition -- but before that, I want to explain something really awesome that I've developed in the process. This is all theoretical, but I have no doubt I can make it work.
Table 1: The Empty 8x5
So, here we have a big, empty world. It's 5 tiles tall and 8 wide. Think of this as a small stage in a game that has nothing in it. We start the game, and it drops you into void, and you fall till you fall off the bottom and then die. Or maybe wander until you hit an edge and have nowhere else to go. It's big and it's empty. So let's give it the first stage of characteristics.
Table 2: The Simple Landscape
Aha! Now there's something to look at. This world isn't big and empty anymore... but... what is it? This technique can be applied to any 2D (or theoretically 3D , but that's a little beyond me, code wise) games that have a landscape.
Maybe this is Metroid, and the colors are different areas? Or this is Zelda, and the Green is grassland, the Blue is water and the Red is a dungeon. What you need to think of these as are cohesive screens that represent a KIND of place, but not the place itself. Each green piece is a screen that could be potentially identical; think of the color as a theme. Everything that has the same color has the same theme, so they all match each other. But this isn't a landscape yet. And my original designs in Faerie Tale work a lot like what you see here. There's not enough category yet to make something really complicated. So one more time in to the breach!
Table 3: Path Types
┌ ┬ ┬ ─
─ ─ ─ ┐
│ │ └ ┬
─ ─ ─ ┤
│ └ ─ ┼
─ ─ ┐ │
│ ╟ ─ ┼
─ ┐ ╧ │
╧ ╟ ─ ┴
─ ┴ ─ ┘
NOW we have a defined landscape. Now, I see this as a Metroid style map, myself, but what we've defined here is the basic shape of all the rooms. If the lines connect, the rooms connect. The double lines indicate a dead end.
At this point, I bet you're asking why this is exciting to me, as a model. But we've done two important things here.
We've defined LANDSCAPE type and PATH type. As a random level generator goes, these are simple definitions. A Landscape type tells us what kind of colours and images to use; it's about graphics. Faerie Tale only uses one, thought it was meant to use three. The PATH type is the exciting new bit.
See, one of the biggest issues with random generation like in Faerie Tale is time. If we don't narrow down the tiles we're using when matching, it can take forever to find an actual match. The more tiles available, and the more variety between them, the longer it'll take to find a match for that tile, which could render the engine useless at a certain mass.
When we define Landscape and Path type, we're limiting the number of tiles the game has to keep track of when doing any one match.
So what's Path type? Well, it determines which of its edges are open, and which aren't. What it doesn't determine is what the content between those edges are like, or even what the edges are like. It's just a class of tiles with a certain subset of edges. Assuming nothing crazy, there's then six basic Path Types: Box (0 Openings), End (1 opening), Line (2 Openings), L (2 Openings), T (3 openings) and Plus (4 Openings).
Now, for a Zelda-style overhead game, we could probably get away with just the basic 6, but with something like Metroid, we'd need to use 16 types; 1 Box, 4 Ends, 2 Lines, 4 Ls, 4 Ts, and 1 Plus. Sixteen is a bit unwieldy, but it's still a good number when dealing with something very large scale and complex. Our 8x5 is perhaps a tad too small, but that's ok.
Now, this is where database management becomes a really useful asset, and I might have to investigate Oracle or SQL or some other kind of Database, because what we want next is an index of the tiles. It should list a tile ID, that tile's Landscape and Path Type, as well as it's Edge types ( a unique identifier that describes the edge; two tiles with the same Edge type should match seamlessly), and probably any of its Tile Data (the numbers that tell the program what is solid and what is not).
Now, we have to determine how the game builds the map. I'd assume it does it by row, then by column; this way it'd be analogous to writing a sentence in english, in terms of how the characters go down.
01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
This would be the order our landscape would need to use generate under my assumption. Easy enough to do.
This is important for sorting, because now we want our database to dump a reference chart that the game will use to find its tile. The chart here would read like this.
Landscape Type
+ Path Type
+ Top Edge Type
+ Left Edge Type
- Tile
Imagine this as ONE branch of a big directory. The root level is all folders of Landscape Types. In our case, that's three folders. The next is the 6/16 path types. Then folders of Top edges, left edges and finally a folder of tiles. This way, it matches all the way down, till it has nothing to match to. The tile will fit its designated landscape, it will fit it's path, and it's two pre-connected edges will be matched. Finally, it picks a tile. If there's only one tile, then that's what it picks. Otherwise, it's random.
Once it has a tile ID, it can place it on a chart of what each room is, in terms of tiles. This means a persistent world, unlike Faerie Tale, but it also means a large, complicated world, right from the get go.
Now; there's two places to go from here. One is procedural generation macro/micro. That is, an algorithm 'paints' the world with Landscape Types, then 'draws' lines through it in Path Types until you get a little landscape chart like we have above -- the macro generation. Then it starts to assign tiles to those macro definitions, making the world in to a specific object -- micro generation. Bare in mind, the micro generation could be done twice with the same macro model and each time it would (likely) be different. There's no guarantee you'd be able to use the same routes, depending on the tiles.
The other option is User Generated Content. You could easily allow a player to 'paint and draw' the map. Then the world could be micro generated randomly. Perhaps that's not interesting enough -- so the player wants more control? After the Macro generation, they could scroll through the tiles one by one to find the ones they liked, and then save the tile table at the end.
In each of these cases, the tile table could be saved when you're done and loaded later. What that a particularly challenging game? Save it and beat your score later, or maybe give it to a friend to try. Post it online, and the most popular worlds could have their own rankings! Because, why not?
I'm gonna stop this here, though. I'm going somewhere with all of this, but I think I'd like to post it separately. So what do you think -- this is Procedural Generation for games, 101, folks!
- Kagirinai