Generating Random Starmaps in C++ - Part I: The BasicsStrategy games set in space, especially 4X games, generally require a Starmap. You could create a Starmap in advance, but this limits playability. A better option is to generate Random Starmaps. This tutorial will give you a simple method of doing just that.
In order to generate a random Starmap, we first need to know what information we're going to need. For this example, it's not much. Because this is meant for a 4X game, we'll only need the information about a star that players can see, and later on, the information necessary to generate planetary systems. So we need the stars location, its size, and its stellar classification.
The location of a star is simply its x and y coordinates (or x, y, and z on a 3d map). Note that these x,y coordinates will be tile positions, not screen positions. (So 0,0 will be the top left tile, 0,1 the tile underneath that, etc.) The size of the star will just be a number from 1 to 3, or the number 5 for supergiants.
Stellar Classification takes a little explanation if you know little about astronomy. Astronomers classify stars based on their heat using a series of letters. The order, from hottest to coldest is O,B,A,F,G,K, and M. The mnemonic generally cited to remember this order is "Oh Be A Fine Girl, Kiss Me." Each classification is then further divided in 10 parts, designated from hottest to coldest with the numbers 0 to 9. So you could have for example, a hot star of classification O3, a temperate star of F5, and a very cold star classified M8. Earth's sun, Sol, is a G2. We're not going to get this detailed, though. We'll stick to the seven letters. Note that this classification ignores things like brown dwarfs, quasars, pulsars, black holes, etc. They could be added fairly easily and this is left as an exercise for the reader.
So our first code example is the class for an individual star.
CODE
class Star
{
private:
int x,y; // The stars location on the starmap grid
int classification; // The stellar classification
int size; //The size of the star ranges from 1 to 3, and then 5 for super giants
// char *name; This will be taken care of in another tutorial
// Planet *planets; Again, in another tutorial
Star *next; // The next star
public:
Star(int, int); //constructor
~Star(void); //destructor
void Add(Star *); // Add a star to the list
int here(int, int); // Is there a star at the given coordinates?
Star * GetStar(int, int); //return the star at the given location, otherwise return null
int GetClassification(void); //Get this star's classification
int GetSize(void); //Get this star's size
Star *GetNext(void); // return the next star
int GetX(void); // Get this star's X coordinate
int GetY(void); // Get this star's Y coordinate
};
I implemented the Star class as a linked list. This was a personal choice. You could just use arrays or even vectors in the Starmap class.
So let's look at the methods of the Star Class, we'll start with the constructor and destructor
CODE
Star::Star(int x_a, int y_a)
{
x=x_a;
y=y_a;
int temp; // This variable will be used to determine if the star is a giant
classification=rand() % 7; // This will generate a random number from 0 to 6, for the OBAFGKM classification
temp=(rand() %100); // Generate a random number between 0 and 99
if(temp<PERCENT_GIANTS) // is this a supergiant
size=5; // then it's size is 5
else // otherwise
size=(rand() % 3) + 1; // This will generate a random size from 1 to 3
next=NULL; // There is no next star yet
}
Star::~Star(void)
{
if(next) // If there is a star after this one
delete next; // Delete it first
}
There's a variable used in the constructor that we haven't seen yet. That's PERCENT_GIANTS. It's defined in the header file for the classes. The definitions defined there are as follows:
CODE
// DEFINES
#define PERCENT_STARS .10 // The fraction of the map that has stars
#define PERCENT_GIANTS 3 // The chance that any given star is a super giant
#define STAR_O 0
#define STAR_B 1
#define STAR_A 2
#define STAR_F 3
#define STAR_G 4
#define STAR_K 5
#define STAR_M 6
I chose PERCENT_STARS and PERCENT_GIANTS arbitrarily. Feel free to change them.
To add a star to the list, use the Add(Star *) method.
CODE
void Star::Add(Star *n)
{
if(!next) // If this star doesn't point to another star
next=n; // Then add the passed star to this one
else // Otherwise
next->Add(n); // Let the next star handle it
}
Okay, for those not familiar with linked lists and pointers, a little explanation is probably necessary. The *next pointer points to the next star object in the list. If there is no next star, it is simply NULL. So the if(!next) will be true if the pointer is NULL, ie, if there's no next star. Otherwise, if there is one, we let the next star decide what to do with the object. (ie, pass it on, or add it to itself).
The destructor works the same way. If there is a next star, it has to be deleted first, all the way down the list.
The next two methods work the same way as well. Using the recursive nature of lists, they pass information down the line, and also return information back up the line.
CODE
int Star::here(int x_a, int y_a)
{
if((x==x_a) & (y==y_a)) // Am I at the given location
return 1; // Okay, then return true
else // Otherwise
if (next) // Is there another star?
return next->here(x_a, y_a); // If so, let it handle the request
else // No more stars and no match found
return 0; // return false
}
Star * Star::GetStar(int x_a, int y_a)
{
if((x==x_a) & (y==y_a)) // Am I at the given location
return(this); // Hey, it's me. So return me
else // Otherwise
if(next) // Is there another star?
return next->GetStar(x_a, y_a); // If so, let it handle the request
else // No more stars and no match found
return NULL; // Return NULL
}
The first method, here(int, int), just returns a boolean. It basically answers the question "Is there a star at this x and y coordinate position." This is necessary for the star map generation routine to make sure that no stars are created in the same place.
The second method, GetStar(int, int), works the same way, and just returns a different value. If there is a star at a given coordinate position, it returns a pointer to that star. Otherwise, it returns NULL.
The rest of the methods in the Star class are pretty self explanatory.
CODE
int Star::GetClassification(void)
{
return classification; // Duh
}
int Star::GetSize(void)
{
return size; // Duh
}
Star * Star::GetNext(void)
{
return next; // Duh
}
int Star::GetX(void)
{
return x; // Duh
}
int Star::GetY(void)
{
return y; // Duh
}
Now that we know how to deal with stars, let's deal with the map
The StarmapThe Starmap class is simpler than the Star class. It contains the width and the height of the map (in tiles), and a pointer to the stars in the map.
CODE
class StarMap
{
private:
int width, height; // The size of the starmap in tiles
Star * stars; // Pointer the stars in the map
public:
StarMap(int, int); // Constructor - passed width and height
~StarMap(void); // Destructor
void Dump(void); // Dump the Starmap to an HTML file
};
Pretty self explanatory. The Dump() method will dump a copy of the starmap to an HTML file so we can look at it.
So let's take a look at the methods. We'll start with the Constructor, which actually creates a starmap and populates it with stars.
CODE
StarMap::StarMap(int w, int h)
{
width=w;
height=h;
stars=NULL; // There are no stars yet
int numstars=int(width*height*PERCENT_STARS); // The number of stars we're going to create
int x,y; // x,y coordinates of a created star, generated randomly
int found; // a boolean to determine if we found a good place for a new star
for(int i=0; i<numstars; ++i)
{
found=0; // set found to false
while(!found) // while we haven't found a good place
{
x=rand() % width; // Determine x
y=rand() % height; // and y randomly
Star *TempStar=new Star(x,y); // create a temporary star
if(!stars) // If we have no stars yet, then we don't have to check to see if the location is okay.
{
stars=TempStar; // So we simply point stars to it's first star
found=1; // And we set found to true so we can get out of the loop
}
else if(!stars->here(x,y)) // If there are stars in the list, we have to make sure the current random
//location is okay
{
stars->Add(TempStar); // If it is, add the newly created star
found=1; // And set found to true
}
else // This location is not okay because a star already exists there
{
delete TempStar; // Get rid of this so we don't have memory leaks.
}
}
}
}
This creates a random starmap for us pretty easily. And because we're using linked lists, we can create a list of any size that memory can hold.
The destructor is as follows:
CODE
StarMap::~StarMap(void)
{
delete stars;
}
This just makes sure we clean up all the pointers.
Finally, we have the Dump(), which writes this all out to an HTML file so we can look at it. Right now, this isn't too terribly useful, but when we create planetary systems in a future tutorial, it might be nice to be able to look at the data about them, to make sure it's all working correctly.
The colors come from a site called "What Colors Are the Stars" which is found
here Note that the Dump() method doesn't create well formed HTML. It loads up in Firefox. No guarantees, though. It's just a quick and dirty hack job for testing the classes.
CODE
void StarMap::Dump(void)
{
Star *DumpMe; // Just to get the color and size
char * StarColors[7]; // The colors for all 7 classifications
int classification, size;
StarColors[STAR_O]="#9bb0ff";
StarColors[STAR_B]="#aabfff";
StarColors[STAR_A]="#cad7ff";
StarColors[STAR_F]="#f8f7ff";
StarColors[STAR_G]="#fff4ea";
StarColors[STAR_K]="#ffd2a1";
StarColors[STAR_M]="#ffcc6f";
ofstream outfile("stars.html"); //create ofstream object
// First, let's write out the HTML header
outfile<<"<html><head><title>Starmap</title></head>"<<endl<<"<body bgcolor=#000000>";
for(int j=0; j<height; ++j)
{
for(int i=0; i<width; ++i)
{
DumpMe=stars->GetStar(i,j); // Is there a star at i,j. If so, get it
if(DumpMe) // So is this a valid star or a NULL
{ // If it's valid
classification=DumpMe->GetClassification(); //Get its classification
size=DumpMe->GetSize(); // And its size
if(size==1)
outfile<<"<font color="<<StarColors[classification]<<">.</font>"; // Period for size 1
else if(size==2)
outfile<<"<font color="<<StarColors[classification]<<">,</font>"; // Comma for size 2
else if(size==3)
outfile<<"<font color="<<StarColors[classification]<<">+</font>"; // Plus Sign for size 3
else if(size==5) // Red Giant
outfile<<"<font color=#FF0000>*</font>"; // Asterisk for supergiants
}
else
outfile<<" "<<endl; // Otherwise just put a space
}
outfile<<"<BR>"<<endl; // Put a break at the end of each line
}
outfile<<"</body></html>"<<endl; // close out the body and html tags
}
Note that I didn't seed the randomizer, which means that it will always create the same map. You can seed the randomizer with the time by including time.h and stdlib.h and using the following:
CODE
srand(time(NULL));
And that's it. The source code for the whole thing is attached as a zip file. In the next tutorial, we're going to look at generating random star names using Markov chains and a list of Latin words.
Comments welcome and appreciated.
Generating Random Starmaps in C++
14 Jul, 2007 - 12:41 PM
|