Optimizing a huge nested for loop

[Zulach]

Hey guys, I wrote code that procedurally generates maps with water, land and mountains.
The results look like this:

 

As you can see, there are many many points\pixels\however you want to call it in every map.

To render the map I've used a particle container where every point on the map is a sprite from the same three textures, and the rendering times are very fast.

 

However, the bottleneck in my code is the two nested for loops for initializing the map.

Chromes profiler shows that they take about 70% of the running time, whereas pixi's rendering takes about 5% (Running time is usually 3 seconds where the whole screen is frozen ).

The problematic lines currently look like this: 

function drawMap() {    mapContainer.removeChildren();    for (var i = 0; i < stageWidth / tileWidth; i++) {        for (var j = 0; j < stageHeight / tileHeight; j++) {            var tile = new PIXI.Sprite(                noiseMotion(i, j) > landMinimum ? (noiseMotion(i,j) > mountainMinimum ? mountainTexture : landTexture) : seaTexture            );            tile.x = i * tileWidth;            tile.y = j * tileHeight;            mapContainer.addChild(tile);        }    }    renderer.render(stage);}

*noiseMotion is my Fractional Brownian Motion implementation 

 

Can you think about a way not to run through all the ~40k iterations of these loops? (40k on this resolution, I can't even fantasize about doing bigger maps right now)

Can I do it with a couple of web workers?

I also tried googling rendering chunks in pixi to no avail, as I have no idea on how to even approach it.

 

Any help will be very welcome.

[xerver]

You could probably find a way to combine large chunks of the same kind of terrain into a single sprite. You can generate the terrain data on a webworker and use ownership transfer to move the byte array of data to the main thread, then intelligently create sprites. Reducing the num of sprites and iterations on the main thread.

[Vrashq]

You can generate it by chunks.

 

For example, imagine your map is divided in squares of 50x50 pixels.  You can make a function that you can invoke with a requestAnimationFrame. Inside, you have just to load your chunk and send a new raq. It will load 100 pixels per frame. Your program won't freeze and your map is going to appear chunk by chunk.

 

For the cutting of your map, you're free to use which method you want. You can set a rectangle(x,y,w,h) and make a double loop inside : 

var rectangle = new PIXI.Rectangle(0,0,10,10);function loadChunk() {	for(var x = rectangle.x; x < rectangle.x + rectangle.width; x++)	{		for(var y = rectangle.y; y < rectangle.y + rectangle.height; y++)		{			// load your pixels		}	}	rectangle.x += rectangle.width;	rectangle.y += rectangle.height;	requestAnimationFrame(loadChunk);}loadChunk();

You can set the rectangle size according to your needs.

 

 

It's just a quick idea, but if someone find better way (webworkers or other), I would be glad to know ^^

[coolblue]

I don't have the knowledge yet but, wouldn't this be a prime candidate for implementing as a fragment shader?

[xerver]

I don't have the knowledge yet but, wouldn't this be a prime candidate for implementing as a fragment shader?

 

This would ideally be the best thing to do. Generate the data on a webworker, transfer ownership, pass it as a buffer into a shader, draw. Only issue is that will be WebGL only, if that is acceptable this is the best way.

[coolblue]

This would ideally be the best thing to do. Generate the data on a webworker, transfer ownership, pass it as a buffer into a shader, draw. Only issue is that will be WebGL only, if that is acceptable this is the best way.

Ok, thanks for explaining that. I was just curious.

I was thinking that the terrain is generated based on a function of x and y position - like a Mandelbrot set - in which case you could just do the calculation in the fragment shader with no need for buffers but, only if noiseMotion(i, j) is deterministic and yeh, maybe it's not.

[xerver]

Ok, thanks for explaining that. I was just curious.

I was thinking that the terrain is generated based on a function of x and y position - like a Mandelbrot set - in which case you could just do the calculation in the fragment shader with no need for buffers but, only if noiseMotion(i, j) is deterministic and yeh, maybe it's not.

 

Very true.

[Zulach]

Ok, thanks for explaining that. I was just curious.

I was thinking that the terrain is generated based on a function of x and y position - like a Mandelbrot set - in which case you could just do the calculation in the fragment shader with no need for buffers but, only if noiseMotion(i, j) is deterministic and yeh, maybe it's not.

 

It is deterministic, so it can work with a fragment shader