Sign in to follow this  
dmoree

2d map generation

Recommended Posts

I've been googling all night as well as reading through the forums and haven't found much help. I read once in a thread that a good method of generating 2d maps was to first seed the map with land seeds, then grow those out to create land masses. Well, I tried that, but my system seemed to always generate maps that grew the same direction. So the top of the map was water and the bottom was mostly land with little spits along the way. I'm looking to get a good idea or even an addition to my code to grow my seeds better or a way to generate a 2d map better. Below is my current Map class that controls the tiles and map generation.
// CMap.cpp
/*
 * Generate a 2d map file
 */
void CMap::GenerateMap(){
	srand((unsigned)time(0)); // Seed random number generator

	// Change the map to blue
	for(int iY = 0; iY < MAPHEIGHT; iY++){
		for(int iX = 0; iX < MAPWIDTH; iX++){
			pMap[iX][iY].iTileID = 0;
		}
	}

	// Seed and grow the map
	for(int iY = 0; iY < MAPHEIGHT; iY++){
		for(int iX = 0; iX < MAPWIDTH; iX++){
			if((rand() % 100) + 1 >= 100 && pMap[iX][iY].iTileID == 0){
				pMap[iX][iY].iTileID = 1;
			}
		}
	}
}

//cMap.h
#include <SDL/SDL.h>
#include <SDL/SDL_image.h>

#include <ctime>

#include "defines.h"

using namespace std;

#ifndef CMAP_H_
#define CMAP_H_

class CTile {
	public:
		int iTileID;
		int iFlags;
		int iX;
		int iY;
		int iHeight;
		int iOverlayID;
		SDL_Surface* pSurface;
};

class CMap {
	public:
		void GenerateMap();

		CTile pMap[MAPWIDTH][MAPHEIGHT];

	private:
};

#endif /* CMAP_H_ */

Share this post


Link to post
Share on other sites
Quote:
Original post by dmoree
srand((unsigned)time(0)); // Seed random number generator

Every time you generate a map, you're reseeding the random generator with the same seed. This will always lead to the same sequence, hence the same map being generated.

Seed once, with an 'unpredictable' value such as the current time, and everything should be fine.

Share this post


Link to post
Share on other sites
Well, I'm getting fairly random seeds. They are appearing in random spots on the map, the problem I'm having is growing them. I've tried a growing them by getting a random number between 0 and 3 and using that to grow the seed a particular direction. But if I do that, all my seeds seem to grow downward more than any direction.

Share this post


Link to post
Share on other sites
A couple things.

I really didnt see your "growth" model in there, maybe I wasn't looking close enough. It seems like you were looping through and simply creating the seeds, but nothing after that.

This doesent impact your problem, but something you really should consider. You are looping through the entire map, and in that 1 in 100 chance you are producing a landmass. You could speed things up, and allow more control of map generation by choosing a number of seeds and randomly plotting them.

PSUDO:

mapw = 100;
maph = 100;
num_seeds = 10;
for(i=0;i<num_seeds;i++){
map_data[rand()%mapw][rand()%maph].tileid = 1;
}

now , we can take this a step further and actualy store the seeds locations in a new array during the generation step, that way you dont have to loop through and find them (this appears more organic to me at any rate)

mapw = 100;
maph = 100;
num_seeds = 10;
for(i=0;i<num_seeds;i++){
seed_x = rand()%mapw;
seed_y = rand()%maph;
seed_vector.add(point(seed_x,seed_y));
}

then we could iterate through the seeds and grow them, and you can then
control the number of iterations (roughly the size of landmasses)

iterations = 30;
for(i=0;i<iterations;i++){
start_count = seed_vector.count;
foreach(seed_vector as seed){
// the 4 points of growth, notice we grow outword instead of picking a path.
// you might want to use some bounds checking in here, but you could always
// do this in the next step if you want the map to appear as a piece rather
// then islandish
if(rand()%2==1) seed_vector.add(point(seed_x + 1,seed_y));
if(rand()%2==1) seed_vector.add(point(seed_x, seed_y+1));
if(rand()%2==1) seed_vector.add(point(seed_x -1, seed_y));
if(rand()%2==1) seed_vector.add(point(seed_x, seed_y-1));
}
}

now you can loop through the seeds and produce your map

foreach(seed_vector as seed){
if(seed.x < mapw && seed.y < maph && seed.x > 0 && seed.y > 0)
map_data[seed.x][seed.y].id = 1;
}

this is a bit more work, but roughly should produce much more organic and configurable maps (please note, this is a quick whip up of psudo code, you would have to translate, stl would be your friend in this case)

-cesar

Share this post


Link to post
Share on other sites
oh, and more interestingly, if using the formulae I sudgested, it would not be difficult to INCREMENT the index when the seed is encountered multiple times in order to produce a height map, or store the data in a seperate hightmap that translates to tiles in another step. this would realisticaly allow you to create hills and mountains that favored the insides of the islands. you could also force it to repeat (ie, once the height is 3, it gets reset to 0 when encountered again) which will serve to produce valleys and lakes.

Share this post


Link to post
Share on other sites
Cesar!

I did put my code for growing in the snippets I provided. I recently rebuilt the generation and tile storage to provide better control. I had my tiles stored as a simple 2d array with just the tile id. Now its moved to a class so I can store the tile height, id, flags, and overlay. This allowed for greater control, as you already know. The first draft was just to set all tile ids to 0(for water) then plot seeds. I really like your idea of plotting a set amount of seeds. I should have thought of that. That definitely would have made generation faster. I'll have to put that in there. Last night, before my initial post, I actually thought of the idea to start all heights at 0, then increment the height by 1 as the seed grows. If the seed grows over another tile that is at 1, I get a height of 2. So we are on the same page. You've helped a lot. I'm thinking once I get the plotting in, I might grow the seed out from the center, incrementing through all coordinates next to it and giving each one a chance to sprout. I think this should make for a decently random map. Hopefully it will come out looking nice. Once I'm done with the growth code, I'll generate a map and post an image on here. See what you guys think.

-Captain P
I saw what you were talking about passing srand a time of 0. Changed that to NULL so I should be seeding with a fairly random seed. Thanks for the catch.

Share this post


Link to post
Share on other sites
No, your seeding call was fine, I just overlooked the time() call. Silly me. -_- Still, there's a problem if you generate many maps after each other, because they'll then be using the same seed, which is why you usually should only seed once.


I did some searching for terrain generation and a common approach seems to be to use fractals. You may want to investigate that some more. This article may also be of interest.

Share this post


Link to post
Share on other sites
Captain,

The map generation wouldn't be fast. A map is only generated at the beginning of the game. I'm working on a game that at the beginning you can choose from different size maps, land area, and local biology amounts to create a unique map. Basically, every time you play the game, you'll get a different map to play on. In turn, creating different game play experience every time you play. Something similar to Sid Meyers Alpha Centauri. It generated random maps at the start of a new game based on a few simple choices. This made for each game to be new.

Forgot to mention. I've read that article on gameprogrammer.com before. Wasn't sure how to make it work for me. But, maybe I'll give it another crack.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this