Beginner’s Procedural Generation
At first when I was creating the blog, I figured that I would be writing mostly about graphics or using game development tools since I tend to work with both a bunch. Instead I am just going to make my first few posts about random computer science related topics that I happen to find myself exploring during my free time. So without further ado, here is my first blog post and probably not my last on procedural generation.
Recently, I found myself going down the rabbit hole of procedural generation, and I have to say at least where I have looked there isn’t a lot out there to help give you an idea where to start. But the places that I have found do have some great information to give you the information needed and point you in the right direction, namely the Procedural Content Generation Wiki (http://pcg.wikidot.com/).
What I am looking to cover in this post is a simple algorithm that creates a procedurally generated cave map. This is just done with text to start off so that we can see that the algorithm will work correctly and as I make more posts where we will create a display where we can create a convincing 2D cave that we look at from top down and be able to explore the cave with a character.
Once again this is a simple algorithm that you can probably do on your own. With subsequent posts, I hope to improve upon this algorithm and explore other options in procedural generation, so we can get the desired structure of the generated map.
The CaveMap Class
The first thing we are going to do is create our CaveMap class. The idea of this class is to create an X by Y map that will have tiles that are initially randomly generated as either a wall or an empty space.
Simply enough right now all the CaveMap class holds is the width and height of the map as well as the map itself which is a vector of size width*height that holds chars. To represent a wall, the entry at position (x,y) in the vector will be ‘#’ and an empty space will just be represented as an empty space ‘ ‘.
The functions that the class has are EvolveMap, EvolveTile, and PrintMap. EvolveMap and PrintMap are both public so we can both see the current state of the map (PrintMap) and evolve the map on to its next step based on our algorithm (EvolveMap). We may want to make EvolveMap private if we were to use this in a game, since all that would matter is the final evolution of the cave but for the sake of this first demo, we will leave it public so we can step through each iteration of the EvolveMap function on our CaveMap. EvolveTile on the other hand is private, since nowhere outside of our CaveMap class should a single tile need to be evolved and we avoid that from happening by accident by doing this.
procMap.h
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#ifndef PROCMAP_H #define PROCMAP_H #include <vector> class ProcMap { private: std::vector<char> theMap; int width; int height; char EvolveTile(int x, int y); public: ProcMap(); ProcMap(int w, int h); void EvolveMap(); void PrintMap(); }; #endif |
We have a default constructor, which will just generate a 10 x 10 map for us to evolve. We also have our other ProcMap constructor which will construct a map of the desired size, randomly choosing if a tile will be a wall marked by the # character or an empty space to mark an empty navigable space on the map. Finally, before we move onto meat of the functions of the class, we have the PrintMap function which will run through our 2D array and print the character corresponding to the tile’s type.
Here is procMap.cpp where we will add EvolveMap and EvolveTile
|
1 2 3 4 5 6 7 8 9 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 41 42 43 44 45 46 47 48 49 50 51 |
#include "procMap.h" #include <time.h> #include <iostream> //default constructor, creates 10x10 map ProcMap::ProcMap() { ProcMap(10, 10); } /*creates map based on width and height provided # is a wall... ' ' is empty space */ ProcMap::ProcMap(int w, int h) { width= w; height= h; srand(time(NULL)); theMap.resize(width*height); for(int i= 0; i < height; ++i) { for(int j= 0; j < width; ++j) { int num= rand() % 2; if(num == 0) { theMap[i*width + j]= '#'; } else { theMap[i*width + j]= ' '; } } } } //prints the map void ProcMap::PrintMap() { std::cout<<"MAP: "<<std::endl; for(int i= 0; i < height; ++i) { for(int j= 0; j < width; ++j) { std::cout<<theMap[i*width + j]; } std::cout<<std::endl; } std::cout<<std::endl; } |
The EvolveMap Function
The EvolveMap function runs over our current map and evolves each tile individually. Evolving individual tiles will be discussed in the next section. What we are concerned with right now is our map as a whole. There isn’t much to the function. The one thing that we need to be careful about is that we need to make sure we don’t change tiles in our map as we are evolving. Only after we have fully evolved our map, do we replace the old tiles with our new tiles. This is done through creating a temporary vector of the same size and placing our evolved tiles in there as we iterate over our map.
EvolveMap function
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/*evolves the map to procedurally generate the cave checks each tile for the number of walls next to it uses evolveTile function for each tiles result */ void ProcMap::EvolveMap() { std::vector temp; temp.resize(width*height); for(int i= 0; i < height; ++i) { for(int j= 0; j < width; ++j) { temp[i*width + j] = EvolveTile(j, i); } } for(int i=0; i < height; ++i) { for(int j=0; j < width; ++j) { theMap[i*width + j]= temp[i*width + j]; } } } |
The EvolveTile Function
This is where most of our work to procedurally generate our map is done. What we are going to do is use what is called the Cellular Automata Method to randomly generate our cave. This essentially is the Game of Life. Remember we have already randomly generated a map with tiles that are either walls or empty space for our cave. What the EvolveTile function does is take a 3×3 square centered on the tile we are looking to evolve and counts how many wall tiles are in that 3×3 square. If 5 or more are walls, then the tile becomes is a wall in the next map iteration, otherwise it is empty space in the next iteration. Even more simply put, the tile type in the 3×3 square that there is the most of(in this case either empty or wall) will be the type of tile that the center tile of this 3×3 square is in the next iteration.
EvolveTile function
|
1 2 3 4 5 6 7 8 9 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 |
/*checks tile if there are 5 or more walls in the area surrounding the tile... if there is then the tile is a wall, else it is an empty tile */ char ProcMap::EvolveTile(int x, int y) { int numWalls= 0; for(int i= -1; i <= 1; ++i) { for(int j= -1; j <= 1; ++j) { if(j + x < 0 || j + x >= width) { ++numWalls; } else if(i + y < 0 || i + y >= height) { ++numWalls; } else if(theMap[(i+y)*width + (j+x)] == '#') { ++numWalls; } } } if(numWalls >=5) { return '#'; } else { return ' '; } } |
Now all we have to do is implement a main function for us to create an instance of the procMap class in and evolve the map we create. What I have done is setup an instance of the class that is 50 x 50 so it can evolve into a large cave structure, that you can evolve as long as you continue to respond ‘y’ to the prompt of “Do you want to evolve the map?”. You will notice that parts of the cave will be fragmented and this does become more of a problem the larger our map grows. In a future post, I hope to fix this issue.
main.cpp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include "procMap.h" int main() { char a; ProcMap* theMap= new ProcMap(50, 50); theMap->PrintMap(); bool stop= false; char ans=' '; while(!stop) { std::cout<<"Do you want to evolve the map? (y/n)"<<std::endl; std::cin>>ans; if(ans == 'y') { theMap->EvolveMap(); theMap->PrintMap(); std::cout<<std::endl; } else { stop= true; } } std::cout<<"Goodbye!"; std::cin>>a; return 0; } |