Best way to handle large map data?

[Ralph]

Hi there. So currently I have a single player open world game which I am in the process of developing multiplayer for. The current system of map gen is local, and done through a bunch of arrays lol. I chose this route LONG ago, and I know it wasn't the best option, but it was easier for me to throw this together than to learn how to used tiled and object layers etc. Using arrays seemed easier to me because I understood how I can respawn/kill dead objects from the array instead of having to learn tiled's object layer stuff.

Anyway, my current system is as follows: At the top of my game basically I have something like this run PS: (The map is 2k x 2k TILES long, each tile is 32x32 so map is 64k x 64k pixels)

var mapSize = 2000;
var grid = new Array(mapSize).fill(0);
for(var i = 0; i<mapSize+1; i++){
    grid[i] = new Array(mapSize).fill(0);
};

for(var i = 0; i<18000; i++){
    var tempX = Math.round(Math.random()*(mapSize-1));
    var tempY = Math.round(Math.random()*(mapSize-1));
    if(grid[tempX][tempY] == 0){
        grid[tempX][tempY] = 2;
    }
}
    
for(var i = 0; i<12000; i++){
    var tempX = Math.round(Math.random()*(mapSize-1));
    var tempY = Math.round(Math.random()*(mapSize-1));
    if(grid[tempX][tempY] == 0){
        grid[tempX][tempY] = 3;
    }
}

This is an example of how i am generating the map. Basically it creates a 2 dimensional array with values 0, 2, or 3 in this example. My rendering system is shown bellow, basically spawn any non 0 entry within 3k pixels of the person (or 91 tiles) by reading the map array from points based on the players current position: 

function mapGen(x1, y1, x2, y2){
    
    if(x1<0){
        x1 = 0;
    } else if(x2>(mapSize-1)){
        x2 = mapSize-1;
    }
    
    if(y1<0){
        y1 = 0;
    } else if(y2>(mapSize-1)){
        y2 = mapSize-1;
    }
    
    for(var row = x1; row<x2; row++){ 
        for(var col = y1; col<y2; col++){
            if(grid[row][col]!=0){ 
                temp = position(row, col);
                if(grid[row][col]==2){
                    createSprite = itemGroup.create(temp[0], temp[1], 'tree');
                    createSprite.scale.set(1.1, 1.1);
                } else if(grid[row][col]==3){
                    createSprite = itemGroup.create(temp[0], temp[1], 'boulder');
                }
                createSprite.body.immovable = true;
            }
        };
    };
    
}

 

This is the render system that is called whenever a player ventures 3k pixels away from a position (The function variables are the corners of the 3k x 3k box around the player in tiles), when called, the position it's using as reference is changed to the current position of the player, so basically it just renders 3k pixels around the player until a player moves to far from that squares center and renders a new one, I do this bc the game cant handle more than a couple thousand sprites on the screen, and doing this lets me have like 200 rendered and have flawless performance. This system works fine for what I need, if there is a 0, leave it blank and the tilesprite background will show, if there is something there then spawn a tree or a rock or whatever said item is (This is just dummy code). For destroying sprites once a player destroys a sprite I get the pixel location of the now dead sprite and change it into tile position and set that tile position to 0. Which is why i chose this system over tiled, it seemed easier to me.

Now finally, here is my problem: I have created a lot of the multiplayer aspect, and all the connections and player positions etc. However, the map is still different on every players screen due to the random gen that happens every time game loads. I can create the giant array on the server, however there is no way I can transfer it to the players. Creating the giant array only takes 300ms which is kinda a lot in terms of performance for my game, but if i render it once on the server and send it to every client my server crashes, i assume its because its wayyy too much data or takes too long. I tried writing it out to a file to read then from my clients but that's 11mb lol and I dont know where to smoothly read something like that. So basically, what are my options here. I would be open to switching to tiled, however i dont know how to randomly generate terrain there, and cant do it manually, as well as i like the system I have now bc how easily i can manipulate it.

Another solution I have yet to try but I might, is instead of sending the entire map file, just write a file or a variable i could send through sockets with where all the non 0 items are around the array to cut down on space and increase performance. 

 

This was kinda poorly written, however I appreciate anyone who took the time to read this, I always chose bad times to write forum posts and right now Im in a rush so I didnt get a chance to re-read this and make myself not sound like I have the English skills of an 8 year old. So if anything needs clarifying let me know! Thanks again for the help.

[Arcanorum]

For the issue of generating a random map, but still wanting multiple players to have the same result map, the map on the client could be generated from a key that is made on the server, that is then sent to all the clients that need to see the same map. Sending just a key will be far smaller than the raw map data, but the map data can still be constructed the same for all players using that key.

I'm more questioning your reasoning for having so many tiles. Also Tiled is well worth getting better with. It will save you time in the long-run.

[Ralph]

1 hour ago, Arcanorum said:

For the issue of generating a random map, but still wanting multiple players to have the same result map, the map on the client could be generated from a key that is made on the server, that is then sent to all the clients that need to see the same map. Sending just a key will be far smaller than the raw map data, but the map data can still be constructed the same for all players using that key.

I'm more questioning your reasoning for having so many tiles. Also Tiled is well worth getting better with. It will save you time in the long-run.

Oooooo a key, like minecrafts seed system seems like a really good idea, however I also need a system to make edits to the mapdata and send it between players as well lol. The reason its a large map is because its a large open world near survival game, (you walk on the array essentially, its not a side scroller). If tiled had some way I could generate large amounts of map at a time, I would def switch to it and figure out how to work object layers as I go but as far as i know i cant. Ill keep thinking about the key generation but dont know where to start in terms of editing the map, bc over time the edits to map would end up giving me the same problem as sending the entire map every time. 

[mattstyles]

You first need an algorithm that deterministically generates a map, the first step is ditching Math.random and using a better RNG, one that you can seed. There are many around (none of them are particularly random, neither is Math.random, but they'll be random enough).

And you'll find that in practise there are far far far fewer mutations to the map than there are changes in the map, as you aren't storing a history you only need to record a change from the original seeded value to the latest value, absolute worse case where someone replaces every tile in your world with another is the same (not worse) than your current system of sending everything. In practise you'd send the seed, which is fed into a deterministic process so that everyone gets the same map, then the changes, apply those, and the world is consistent.

[Ralph]

1 hour ago, mattstyles said:

You first need an algorithm that deterministically generates a map, the first step is ditching Math.random and using a better RNG, one that you can seed. There are many around (none of them are particularly random, neither is Math.random, but they'll be random enough).

And you'll find that in practise there are far far far fewer mutations to the map than there are changes in the map, as you aren't storing a history you only need to record a change from the original seeded value to the latest value, absolute worse case where someone replaces every tile in your world with another is the same (not worse) than your current system of sending everything. In practise you'd send the seed, which is fed into a deterministic process so that everyone gets the same map, then the changes, apply those, and the world is consistent.

Ya this sounds great but im stuck at creating or finding an algorithm that generates the map for me based on a key. 

[prvi_treti]

I have a similar issue ( that user needs to get map data from server ) , in case you can live with seed number , that's best option. But if you can't like me, I think your best option is sending map data as PNG file.

You can either generate a PNG file as the size of map ( 2k x 2k in that case , PNG-8 if 8 bit is enough ) or use PNG file as binary data container. (not tested but in theory it can be like first 2x11 bytes are (2^11 = 2048) for grid location and remaining 10 bytes to store extra data (in case of RGBA))

Or maybe can use best of both worlds you generate whole map but one PNG pixel (RGBA) holds data for 4 grids or so.

And PNG files can be used with TypedArrays (and may need a fallback/polyfill for browser not supporting)

[mattstyles]

2 hours ago, Ralph said:

Ya this sounds great but im stuck at creating or finding an algorithm that generates the map for me based on a key. 

I've had a play with some techniques, but there are many many techniques for map generation, not sure these would help at all:

https://github.com/mattstyles/heightmap

https://github.com/mattstyles/poc-mapgen

They're only proof-of-concepts, so they are very messy, no optimisation or anything. There probably aren't good readme's either, if you know how npm works then check the package, there are some scripts in there that can build and run the projects. Otherwise poke through the code to see what is happening.

There is one based on perlin noise in the poc-mapgen repo that generates a world and I think it creates some mountains, sea, land etc, very very basic but its a large array it creates that you can move around in using arrow keys in the demo.

I used a module called seedrandom which is a seeded RNG, the theory of course is that it is deterministic, so, given the same seed you will always get the same progression of pseudo-random numbers (the type of random numbers computers can generate, some of the theory around how computers generate entropy is awesome). I then use a couple of different noise generation modules to create different varieties of noise, you can always roll your own if your maths is tip-top.

The algorithm then runs a number of processes to fill up or mutate an array (or whatever representation you use). It is the interplay of these factors, backed by a deterministic RNG that generates the land. Stuff like perlin and simplex noise is designed to be non-periodical, i.e. it does not repeat (or tries not to) and it can be used to generate terrain at any location, meaning your world can be almost limitless and you can generate any part of it at will. Minecraft uses extensive use of perlin terrain generation, using very simple techniques stitched together. They added some other special generation features later on but its basically just noise and smoothing.

Search for procedurally generated terrain, and prepare yourself, its a deep and interesting world with many many applications. Notch wrote an article on MC generation, thats a good high-level resource if you can find it. There are also a few procedural generation sites with gaming slants, for everything from Roguelike dungeons to large open worlds.

Other techniques include using different noise generators, voronoi is a good one, walking algorithms, combined algorithms, its a really interesting field to explore as a programmer. Emergent systems are awesome—you create a few simple rules, run the simulation, and watch what emerges. Proper cool.

I created a tunnelling algorithm once that randomly placed circles of varying sizes on to a grid and got them to bunch together. By tweaking it to create mainly small circles it would bunch them into tunnels, or corridors, or rivers, but very natural looking, ended up looking like a diagram of neurons in the brain. Fun to play with. Be creative, map generation is all about creating using and creating algorithms and tying them together.

[mattstyles]

In case you struggle to get those examples to run, here are a few screenshots of the output, the code to generate each is alarmingly simple.

The first one is basic perlin heightmap (might be simplex, I forget) showing sea and land, but in the middle of landmasses there are mountains.

2nd one shows the same sort of technique but a coarser granularity, it shows a smoothing technique between 'chunks'. I can generate any number of those chunks that are based on the same underlying noise map but add their own chunk noise on top, the underlying grid ensures they are close at the edges (they seam) so there is only a little bit of smoothing required and this can be done for each newly generated chunk so your old chunk does not start mutating as you generate more world (if you do this far enough away from active players then it doesn't actually matter as no-one will ever reach the edge of an infinite world anyway).

The 3rd one adds some techniques for biome resolution using height, moisture, temperature etc (no wind or geothermal activity). It's based on what minecraft used for biome generation, which is pretty unrealistic but ensures biomes are placed fairly logically next to each other even if it does not produce anywhere near realistic landmasses. It actually uses voronoi under the hood to create regions so its pretty heavy on the processing. Took a while to make it seam. This image isn't great generation, some of the parameters need tweaking so the edges don't bleed so much into each other, again, this is simply reducing the noise factor for one of the passes.

 

The last one is the tunnelling algorithm. I can not wait to use something like this is a dungeon game. A few tweaks to variables and smoothing and you can end up with some larger chambers naturally forming, but you could seed your world with those before or at specific points during the simulation. Solving the 'floating room' problem would be complex, a good challenge.

[Ralph]

8 hours ago, mattstyles said:

In case you struggle to get those examples to run, here are a few screenshots of the output, the code to generate each is alarmingly simple.

The first one is basic perlin heightmap (might be simplex, I forget) showing sea and land, but in the middle of landmasses there are mountains.

2nd one shows the same sort of technique but a coarser granularity, it shows a smoothing technique between 'chunks'. I can generate any number of those chunks that are based on the same underlying noise map but add their own chunk noise on top, the underlying grid ensures they are close at the edges (they seam) so there is only a little bit of smoothing required and this can be done for each newly generated chunk so your old chunk does not start mutating as you generate more world (if you do this far enough away from active players then it doesn't actually matter as no-one will ever reach the edge of an infinite world anyway).

The 3rd one adds some techniques for biome resolution using height, moisture, temperature etc (no wind or geothermal activity). It's based on what minecraft used for biome generation, which is pretty unrealistic but ensures biomes are placed fairly logically next to each other even if it does not produce anywhere near realistic landmasses. It actually uses voronoi under the hood to create regions so its pretty heavy on the processing. Took a while to make it seam. This image isn't great generation, some of the parameters need tweaking so the edges don't bleed so much into each other, again, this is simply reducing the noise factor for one of the passes.

 

The last one is the tunnelling algorithm. I can not wait to use something like this is a dungeon game. A few tweaks to variables and smoothing and you can end up with some larger chambers naturally forming, but you could seed your world with those before or at specific points during the simulation. Solving the 'floating room' problem would be complex, a good challenge.

Wow! great post this has suddenly become much more interesting for me! Thank you so much!

[Ralph]

Also lol just realized what I need is a seeded random number generator, that is what im looking for, I dont need anything more (I thought I did lol). Right now is completely random generation, but ultimately biomes like the first and 3rd example @mattstyles showed, I will def be looking into his examples and others!

 

[mattstyles]

The biome one was great fun to do. I think its basically just terrain generation done over different aspects, although some stuff like temperature depends on elevation and then has an effect on rainfall etc etc etc I forget the details, but maybe I should revisit that...