🔒 Locked

Generating Large Maps Using Libnoise (Limits?)

Started by Jungletoe Sep 3, 2012 at 10:30 PM 10 replies 6.5k views

Original Post

Sep 3, 2012 at 10:30 PM

Hey guys, I'm working on a map generator using libnoise. The generator works for maps that are 2000x2000 or smaller in pixels, but it won't go higher. I need my maps to be around 100000x100000, and it simply will throw the error "out of memory" after about 20 seconds of generating.

Here is my generator class:
[source lang="cpp"]class Generator
{
private:
void generateNoiseImg();
int mapH;
int mapW;

public:
Generator();
void Generate();
};[/source]

[source lang="cpp"]Generator::Generator()
{
// Tested at 2000x2000
mapH = 500;
mapW = 500;
}

void Generator::Generate()
{
generateNoiseImg();
}

void Generator::generateNoiseImg()
{
module::Perlin noise;
noise.SetFrequency(1.0);
noise.SetPersistence(.4);
noise.SetOctaveCount(2);

srand(time(NULL));
int seed = rand();
noise.SetSeed(seed);

utils::NoiseMap heightMap;
utils::NoiseMapBuilderPlane heightMapBuilder;
heightMapBuilder.SetSourceModule (noise);
heightMapBuilder.SetDestNoiseMap (heightMap);
heightMapBuilder.SetDestSize (mapW, mapH); // Must be divisible by 25
heightMapBuilder.SetBounds (6.0, 10.0, 1.0, 5.0);
heightMapBuilder.Build ();

utils::RendererImage renderer;
utils::Image image;
renderer.SetSourceNoiseMap (heightMap);
renderer.SetDestImage (image);
renderer.Render ();

utils::WriterBMP writer;
writer.SetSourceImage (image);
writer.SetDestFilename ("rsc/noise.bmp");
writer.WriteDestFile ();
}[/source]

Is 2000x2000 a limitation of libnoise's .SetDestSize(w, h)? How have you guys overcome this for huge maps? It looks like the example planetary map in the libnoise tutorial makes a map that's gigantic (5000?) and way over 2000.

JTippetts

Sep 4, 2012 at 12:02 AM

You understand that an array of float 100000x100000 in size is roughly 37 gigabytes of memory, right? That's not a limitation of libnoise, that's a limitation of modern PC computing. If you absolutely must have that whole chunk of data available at once, your best bet is to break it up into blocks and save it to disk a block at a time; after asking the player if it is okay to use up 37 Gb of their hard drive space, of course...

BenjaminSergent

Sep 4, 2012 at 12:22 AM

I'm looking at the sample code's file "complexplanet.cpp". Here's some code around line 128
[source lang="cpp"] // Southernmost coordinate of elevation grid.
const double SOUTH_COORD = -90;
// Northernmost coordinate of elevation grid.
const double NORTH_COORD = 90;
// Westernmost coordinate of elevation grid.
const double WEST_COORD = -180;
// Easternmost coordinate of elevation grid.
const double EAST_COORD = 180;
// Width of elevation grid, in points.
const int GRID_WIDTH = 4096;
// Height of elevation grid, in points.
const int GRID_HEIGHT = 2048;[/source]

Then around line 1843

[source lang="cpp"] planet.SetBounds (SOUTH_COORD, NORTH_COORD, WEST_COORD, EAST_COORD);
planet.SetDestSize (GRID_WIDTH, GRID_HEIGHT);[/source]

Here is the 4096 by 2048 height map the site uses for the terrain sample pictures:
http://libnoise.sour...ages/planet.jpg

So it's only about twice as large as what you found as your maximum, the sample just looks like it needs a much larger map because of the way Terragen renders it. Still, it seems you don't have as much memory as they expect people running the sample to have. Your main options are:
1. Find a way to make due with fewer points.
2. Get more memory. Note, this option will make the minumum system requirements for your game higher.
3. Make multiple smaller height maps and save them to disk, probably after compressing. Then, make your program try to anticipate which ones will be needed soon so it can decompress and load them before they need to be show.

Postie

Sep 4, 2012 at 12:56 AM

Another option is to generate smaller maps and then stitch them together in some fashion. If your stitching is decent enough you can effectively generate an infinite world. Games like Minecraft break the world into chunks, which are streamed to and from the disk as required. If your terrain generator is creating these chunks for you at the start it makes their dynamic loading much easier.

Jungletoe

Sep 4, 2012 at 1:57 AM

You understand that an array of float 100000x100000 in size is roughly 37 gigabytes of memory, right? That's not a limitation of libnoise, that's a limitation of modern PC computing. If you absolutely must have that whole chunk of data available at once, your best bet is to break it up into blocks and save it to disk a block at a time; after asking the player if it is okay to use up 37 Gb of their hard drive space, of course...

Hehe, I think I'll just do 20000x20000 maps and allow the user to select different authorized servers (I hate to say this, but "Runescape style") from a drop down menu on the homescreen. I've seen a game do 1million x 1million tiles before, but they had some weird way of handling it. Anyways, the clients receive the map tiles in chunks, so it's all good for them. I'm not too worried about the server either.

1. Find a way to make due with fewer points.

I think I'll make libnoise generate a 5000x5000 map and then have the server stretch it out into a 20000x20000 map. Every pixel of the generated map file will be equal to 4 tiles.

BTW, this may sound stupid, but I store the server's maps in a .PNG file for easy editing. The server generates a map using the given code and saves it in a .BMP file. It then creates a .PNG file with the converted colors for my maps (turns a grey heightmap into lakes and such) and saves it as well. It then deletes the .BMP file. Every time the server is loaded, it transverses all the pixels of the map.PNG and adds it in my 2D vector array of tiles (int x, int y, int tileID). It works surprising well compared to a binary system, but meh. I'm not too concerned about server loading performance, but rather client performance. This limitation is just annoying though.

swiftcoder

Sep 4, 2012 at 9:16 PM

If you are using a noise generation library to build your map, why not generate it on-the-fly in the client? That way you only need to generate chunks that are currently nearby the player, which reduces you to a very manageable amount of memory.

Jungletoe

Sep 4, 2012 at 11:01 PM

If you are using a noise generation library to build your map, why not generate it on-the-fly in the client? That way you only need to generate chunks that are currently nearby the player, which reduces you to a very manageable amount of memory.

I would do that if I was making a Minecraft-esque game, but I don't think that will work with an ORPG... as far as I know. I'll look into it. Would an unlimited Minecraft-esque map generation style work if I have 64 players on at one time per server?

swiftcoder

Sep 4, 2012 at 11:05 PM

Would an unlimited Minecraft-esque map generation style work if I have 64 players on at one time per server?

Sure. The server just has to do a little more legwork.

Basically, each client just generates the area of the world immediately surrounding that player, while the server has to generate the area(s) surrounding each/all players.

Postie

Sep 5, 2012 at 3:18 AM

Basically, each client just generates the area of the world immediately surrounding that player, while the server has to generate the area(s) surrounding each/all players.

...Also ensuring that the map generation process is deterministic.

JTippetts

Sep 5, 2012 at 3:25 AM

Something that might work would be a hybrid algorithm. The world is generated procedurally on-the-fly, but any changes or edits done to the world are stored as diffs, similar to the process of applying a patch to source code. A particular world chunk would be generated using the pre-determined seed, then the diff files would be checked and any relevant changes made before presenting the chunk to the player. That way, you don't have to store the whole world, just enough data to represent the changes made to it. To be even smarter about it, you could track the number of changes made to a given chunk, and once it reaches a certain arbitrary threshold, then the chunk could be stored as-is, rather than as diffs. This could make heavily-modified chunks more compact and quicker to load.

odrega

Sep 5, 2012 at 9:10 PM

I don't know much about libnoise, but if you use the same seed won't it always generate the same map? Because if it did, you could store the seed on the server, send it to the player (who then generates it) and then retrieve x, y, health and inventory. Would that work?

Jungletoe

Sep 7, 2012 at 12:30 AM

Something that might work would be a hybrid algorithm. The world is generated procedurally on-the-fly, but any changes or edits done to the world are stored as diffs, similar to the process of applying a patch to source code. A particular world chunk would be generated using the pre-determined seed, then the diff files would be checked and any relevant changes made before presenting the chunk to the player. That way, you don't have to store the whole world, just enough data to represent the changes made to it. To be even smarter about it, you could track the number of changes made to a given chunk, and once it reaches a certain arbitrary threshold, then the chunk could be stored as-is, rather than as diffs. This could make heavily-modified chunks more compact and quicker to load.

I've actually thought about this. It seems a bit too complicated, but I don't know. If the game starts to lag then I'll consider it.

I once played a game with a 10 million x 10 million map and it was done this way. For some reason it lagged terribly. I think it had to do with the heavy tile modifications in the game. Game objects were sent by the server.

I don't know much about libnoise, but if you use the same seed won't it always generate the same map? Because if it did, you could store the seed on the server, send it to the player (who then generates it) and then retrieve x, y, health and inventory. Would that work?

Nah, sorry. The tiles change so much that it wouldn't be able to simply generate it. It would need to account for all the changes the players make.\\

Basically, each client just generates the area of the world immediately surrounding that player, while the server has to generate the area(s) surrounding each/all players.

Thanks, I'm working on this now (but not infinite generation-- I don't want the maps to get too big!)

I decided to generate 1000x1000 chunks. Each chunk is stored as a 25x25 PNG. The server loads the chunks around the player and sends it to the client. Object positions will still be held in a single XML file and constantly loaded (I just need to dumb it down a bit so that the map doesn't become overpopulated with objects. If it does, I'll switch methods somehow).

This may not be the best way to store all that data, but it works and should be fast. I'll keep you guys updated.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.