How to efficiently render many tiles (rect())

Caramazula

Hello,

I have been making a tile based game. Every tile in the game is represented by a 5 * 5 rect and has to be redrawn in every frame. This however leads to a very low framerate. In this example I render 19200 rects every frame and I reach a framerate of about 62fps.

void setup() {
  size(800, 600);
  noStroke();
  frameRate(1000);
}

void draw() {
  for(int y = 0; y < height / 5; y++) {
    for(int x = 0; x < width / 5; x++) {
      fill(0);
      //fill(noise(x * 0.05, y * 0.05) * 255);
      rect(x * 5, y * 5, 5, 5);
    }
  }
  fill(255, 0, 0);
  text(round(frameRate), width / 2, 20);
}

So the question is, is there any way to render the tiles smarter?

tlecoz

Hello !

62 FPS is an excellent frameRate actually. What is your FPS when you have nothing on the screen ? - it's very close to 62 FPS for me -

EDIT : But you could create a PShape and draw your grid inside it a single time using vertex. All your vertex will be then drawn in the same time when you'll try a draw the PShape and every vertex will share the same texture (and then it will be lighter for the CPU).

You can "paint" your vertex-quad (the cells of your grid) with different images even if you share the same texture for every vertex. You just need to draw each image on the same PImage and then target what you want to draw using the UV values of "vertex" method.

Good luck !

EDIT2 : I'm not sure at all about that, but I would not be so surprise if the frameRate was blocked to floor(1000/16) (=>> 62) if you try to draw something on the screen. It was what happened in AS3 when it used GPU operations

• the "16" in the operation "1000/16" was found like that "floor(1000/60)" -

GoToLoop

As an extra, here's an online tile prototype: =:)
http://studio.processingtogether.com/sp/pad/export/ro.9Ql2E8JBC54LJ/latest

Caramazula

Sure you are right, 62 is an excellent framerate, but we are not talking about a complete game here, we are just talking about the basic background and a max framerate of 1000. And in this case I would like to see at least 300fps.

I followed your advice and something similiar to PShape; PGraphics to create a chunk of tiles and now the code is running at 400+fps.

PGraphics chunk;

void setup() {
  size(800, 600);
  frameRate(1000);
  chunk = createGraphics(width, height);

  chunk.beginDraw();
  chunk.noStroke();

  for(int y = 0; y < height / 5; y++) {
    for(int x = 0; x < width / 5; x++) {
      chunk.fill(noise(x * 0.05, y * 0.05) * 255);
      chunk.rect(x * 5, y * 5, 5, 5);
    }
  }

  chunk.endDraw();
}

void draw() {  
  image(chunk, 0, 0, width, height);
  fill(255, 0, 0);
  text(round(frameRate), width / 2, 20);
}

However this does not really help me any further because I need to redraw the chunk every frame when I add light and drop back to 40fps:

PGraphics chunk;
float map[][], light[][];

void setup() {
  size(800, 600);
  frameRate(1000);

  map = new float[width / 5][height / 5];
  light = new float[width / 5][height / 5];

  for(int y = 0; y < height / 5; y++) {
    for(int x = 0; x < width / 5; x++) {
      map[x][y] = noise(x * 0.05, y * 0.05);
      light[x][y] = 0;
    }
  }
}

void draw() {  
  background(0);
  updateChunk();
  image(chunk, 0, 0, width, height);
  fill(255, 0, 0);
  text(round(frameRate), width / 2, 20);
}

void updateChunk() {
  updateLight();

  chunk = createGraphics(width, height);

  chunk.beginDraw();
  chunk.noStroke();

  for(int y = 0; y < height / 5; y++) {
    for(int x = 0; x < width / 5; x++) {
      chunk.fill(map[x][y] * 255, light[x][y]);
      chunk.rect(x * 5, y * 5, 5, 5);
    }
  }

  chunk.endDraw();
}

void updateLight() {
  for(int y = 0; y < height / 5; y++) {
    for(int x = 0; x < width / 5; x++) {
      light[x][y] = map(new PVector(mouseX, mouseY).dist(new PVector(x * 5, y * 5)) * 5, 0, 1000, 255, 0);
    }
  }
}

GoToLoop

If a PImage, and any subtype of it like PGraphics, got same dimensions as the canvas, we can use it as background()'s argument: *-:) https://processing.org/reference/background_.html

tlecoz

Hello !

As I though, the frameRate is blocked to 62 when you're using openGL.

Here the code I used to make that affirmation

PShape s;

class Cell {

 float minX;
 float minY;
 float maxX;
 float maxY; 

 Cell(float _minX,float _minY,float _maxX,float _maxY){
    minX = _minX;
    minY = _minY;
    maxX = _maxX;
    maxY = _maxY;
 }

}


void setup(){

  size(1280,1024,P3D);

  int nbX = 200;
  int nbY = 200;
  int i,j,k = 0;
  float cellSize = 5.0;

  Cell[] cells = new Cell[nbX*nbY];

  float x0,x1,y0,y1;

  for(i=0;i<nbX;i++){
     for(j=0;j<nbY;j++){
        x0 = i * cellSize;
        x1 = (i+1) * cellSize;
        y0 = j * cellSize;
        y1 = (j+1) * cellSize;
        cells[k++] = new Cell(x0,y0,x1,y1);
     } 
  }


  s = createShape();
  s.beginShape(QUAD);
  s.noStroke();
  s.fill(255,0,0);
  Cell c;
  for(i=0;i<k;i++){
    c = cells[i];
    s.vertex(c.minX,c.minY);
    s.vertex(c.maxX,c.minY);
    s.vertex(c.maxX,c.maxY);
    s.vertex(c.minX,c.maxY);
  }
  s.endShape();

  frameRate(1000);
}

void draw(){
  background(255);

  shape(s);

  println(frameRate);
}

I got the exact framerate if I set nbX & nbY to 20 instead of 200

Caramazula

Well thats good to know and it adds about 5fps to my example program, but the map of the actual game is far bigger than one screen so I will have to seperate it into multiple chunks.

EDIT: Your code runs at 60fps for me and I don't know why you are talking about openGL, I am using size(x, y) with no openGL render selcted and I can reach up to almost 30k fps with this code:

void setup() {
  frameRate(10000000);
}

void draw() {
  println(frameRate);
}

tlecoz

"I will have to seperate it into multiple chunks."

You really should draw only what is on the screen. This is the true way to do.

EDIT : it's not the same kind of game but GTA5 for example has HUGE maps in it. It's only possible if the game render only the 10 000 triangles (for example) closer to the main character. During the first part of rendering process, you need to know what is relevant to draw, what is not.

What we call "reality" works exactly in the same way actually. The behaviour of a particle becomes much more complex if we had an observer and then we know that "reality" appears when we look at it but acts as "background-process" when we dont.

Caramazula

Thats a good point. I have changed my program so that it only shows the tiles which are illuminated and the result is (depending on the size of the light circle) 50 to 600fps.

float map[][], light[][];

void setup() {
  size(800, 600);
  frameRate(1000);
  noStroke();

  map = new float[width / 5][height / 5];
  light = new float[width / 5][height / 5];

  for(int y = 0; y < height / 5; y++) { // generate random map
    for(int x = 0; x < width / 5; x++) {
      map[x][y] = noise(x * 0.05, y * 0.05);
      light[x][y] = 0;
    }
  }
}

void draw() { 
  int tiles = 0; 
  background(0);
  updateLight();
  for(int y = 0; y < height / 5; y++) {
    for(int x = 0; x < width / 5; x++) {
      if(light[x][y] < 1) // only render illuminated tiles
        continue;
      tiles++;
      fill(map[x][y] * 255, light[x][y]);
      rect(x * 5, y * 5, 5, 5);
    }
  }
  fill(255, 0, 0);
  text("FPS: " + round(frameRate) + " Tiles drawn: " + tiles, width / 2, 20);
}

void updateLight() {
  for(int y = 0; y < height / 5; y++) { // set light level of each tile depending on mouse distance
    for(int x = 0; x < width / 5; x++) {
      light[x][y] = map(new PVector(mouseX, mouseY).dist(new PVector(x * 5, y * 5)) * 3, 0, 1000, 255, 0);
    }
  }
}

You can change the 3 multiplier in updateLight() for a smaller or bigger light circle. However I am still not fine with this. I want the framerate to be higher than 100 at any amount of drawn tiles (0 - 19200 tiles). So that even if the whole screen is illuminated my framerate remains stable.

tlecoz

I don't understand how you can get FPS higher than 62... Maybe it's blocked by my computer... Sounds weird...

[...]

Oh I see ! It works as expected with P2D but it's blocked to 60 with P3D

tlecoz

In my own test (I'm building a library right now that do the same kind of thing) , P3D looks to render faster than P2D (with textures that use alpha at least, didn't try with solid textures).

koogs

I don't know why you are talking about openGL

it's the default in processing 2

Maybe it's blocked by my computer... Sounds weird...

often it is limited to the monitor's refresh rate to prevent tearing. you can probably turn this off in the settings, somewhere.

GoToLoop

It's the default in processing 2.

JAVA2D is the default renderer for Processing 1.x.x, 2.x.x & 3.x.x! :O)

Caramazula

I changed my program to non alpha using and now it runs like this in the different render modes at 19200 tiles drawn per frame:

size(800, 600);
Alpha: 53fps NoAlpha: 58fps
size(800, 600, P2D);
Alpha: 51fps NoAlpha: 51fps
size(800, 600, P3D);
Alpha: 60fps NoAlpha: 60fps (both capped by graphic gard)

Well, as you can see, if I don't set any renderer at all the framerate is somehow different to P2D even though it should be the same. Furthermore my OpenHardwareMonitor shows graphic card usage in P2D and P3D render mode but there is no graphic card load with no render selected. This is really odd.

GoToLoop

... but there is no graphic card load with no render selected. This is really odd.

The "no render" is JAVA2D, the default renderer! We can check OpenGL usage via isGL() though. >-)
A pity this important Processing aspect, and some others, is hidden away by purpose! X(

quark

I took the code you first posted and modified it to measure the time taken to draw the 19200 rectangles and used this to calculate the maximum framerate possible.

Obviously they were measured on my machine so you would have to try this for yourself, but the results were interesting.

The maximum frame rate was ~98 for all 3 renderers. The achieve frame rate was ~64 for Java2D and ~82 for P2D or P3D (i.e. OpenGL)

These result were measured using Processing 2.2.1 on OSX

Here is the test code.

void setup() {
  size(800, 600, P3D);
  noStroke();
  frameRate(120);
}

void draw() {
  long t = System.nanoTime();
  background(255);
  for (int y = 0; y < height; y += 5) {
    for (int x = 0; x < width; x += 5) {
      fill(200);
      //fill(noise(x * 0.05, y * 0.05) * 255);
      rect(x, y, 5, 5);
    }
  }
  t = System.nanoTime() - t;
  float maxFrameRate = 1e9 / t;
  fill(255, 0, 0);
  text(round(frameRate), width / 2, 20);
  text(round(maxFrameRate), width / 2, 40);
}

Caramazula

Well this proves that the rect function needs quite some power which leads back to my initial post. I am searching for an option to render the same amount of detail while using way less power. I mean I know that it is somehow possible, since games like Terraria excist.

tlecoz

Hello As I said before, you should use "vertex" instead of rect, and you should render all of them in a single time using PShape.

Then, what is "slow" in Processing is the fact it's not optimized to one specific scenario, and then there is a lot amount of loop inside the rendering process of PGraphics. There is also a lot of "useless" data passed to the GPU. These data are here to be compatible with others scénarios.

For example, if you just want to render a color rect, Processing will send all the data needed to draw a rect with fill/stroke/texture/light (and more... there is 37 datas by vertex).

If you want your stuff to be the most optimized, you should build your rendering structure from scratch with openGL

[... thinking... ]

Actually there is another way to do it ! :)

You could (& should) create your grid directly inside the Shader. Instead of sending vertex-XYZ to define the triangles used to render stuff inside, you should send only the index of each vertex and then compute the XYZ from that ID.

The interest is that your vertex-attribute (= your array of index) never change and is totally out of the main-rendering pipeline.

This is how I did that (in AS3) http://beginfill.com/

or that (in JS + webGL) http://beginfill.com/WebGL_Video3D/

In each one, I move 512x512 triangle.

It make me thinking about another great way to multiply by two (no less ) the speed of your current demo :)

As I said before, you should use "vertex" instead of "rect". But when I said that, I though about using 4 vertexs defining 2 triangles defining 1 rect. But it's not at all the best way to do :)

You should create a texture that embed a square inside a triangle, and then you should draw rotated-triangle with your square in it. If you do that, you will divide the amount of triangles used to render your stuff by two ! (and with 25% less "vertex")

But it's much more complex to do... (I'm doing that work right now, I know the subject... :) )

Caramazula

Well, I am coming back to this.

At first, @tlecoz, I am not quite sure how you mean this

I though about using 4 vertexs defining 2 triangles defining 1 rect. But it's not at all the best way to do

Furtermore I made some a test useing the different render options while drawing 10,000 400 x 300 rectangles to the screen with different methodes, but I am not sure about the outcome. I probably did something wrong. Results: http://pastebin.com/FtssGURx (in seconds) Code: http://pastebin.com/hCRUMRab

However I came up with the idea of drawing the background in one image without any updates and the shadow/light on top of that. I will try this right now and report my results.

amnon

Don't overcomplicate things. The answer was already given, use a PShape.

See: https://processing.org/tutorials/pshape/

tlecoz

"At first, @tlecoz, I am not quite sure how you mean this

I though about using 4 vertexs defining 2 triangles defining 1 rect. But it's not at all the best way to do"

Well, when Processing draw a rect with a texture in it, it actually draw 2 triangles-rectangle based on 4 vertex and fit a texture in it. It's a logical and elegant way to process (and almost every rendering engine works like that). But in the case where you have a huge amount of object, it's not the most optimized way to draw rectangles.

The most optimized way to draw rect is actually to draw one big triangle that contain the rect. Then, instead of drawing a rectangle (and 2 triangles) you only draw a single triangle with you rect texture in it.

If you do that, you will able to draw 2x the amount of objects you 're using without loss of performance because you will draw the same amount of triangles.

EDIT : to see the difference, do the tests you did but instead of using "rect" , do 3 call of "vertex" inside a "beginShape(TRIANGLES);' (and draw every triangles inside the same "beginShape/endShape instruction )

something like that

float px=0.0f,float py=0.0f,float triangleSize = 5.0f;
PImage img = loadImage("rectInsideTriangleTexture.png");
int imgW = img.width;
int imgH = img.height;

beginShape(TRIANGLES);
texture(img);

int i,nb = 10000;
for(i=0;i<nb;i++){
   vertex(px,py,0,0);
   vertex(px + triangleSize,py,imgW,0);
   vertex(px,py+triangleSize,0,imgH);
}

endShape();

Caramazula

@amnon I made the same program useing PShape and it runs with 6fps. http://pastebin.com/Up4nLiL7 see yourself, maybe I did something wrong.

@tlecoz My problem is that if you tell me to draw a triangle that contains the rect, then I think about this:

And if you tell me to draw two triangles to get one rectangle, then I think about this:

How excatly do you mean it?

tlecoz

"My problem is that if you tell me to draw a triangle that contains the rect, then I think about this:"

This is it ! This is the idea ! As you see, the quad inside the triangle take the half of the space of the triangle. Your texture will be bigger but you will be able to draw more elements.

"And if you tell me to draw two triangles to get one rectangle, then I think about this"

This way is how Processing do when you use "rect"

amnon

The idea behind a PShape is to minimize interaction between CPU and GPU, thus increasing the frameRate. So what you want is to create a GROUP PShape containing all the tiles that you create/send to the GPU ONCE, then display it continuously at 60 fps. Then you can have millions of triangles at interactive frameRates. Below is the example with the same number of tiles running at 60 fps. (By the way, 60 fps as discussed above, is the capped frameRate for OpenGL on many computers.)

The lighting or changing of colors etc. should be done in a GLSL shader, not by directly changing the PShape. Otherwise these are exactly the CPU-GPU interactions that kill your frameRate.

In fact the same visual outcome could be achieved using a single fragment shader, but I don't know if this was just a code example to display the problem or the actual visual outcome you are after.

Code Example

PShape tiles;
int scale = 5;

void setup() {
  size(800, 600, P2D);
  tiles = createShape(GROUP);
  for (int y=0; y<height/scale; y++) {
    for (int x=0; x<width/scale; x++) {
      PShape tile = createShape(RECT, x * scale, y * scale, scale, scale);
      float noiseValue = noise(x * 0.05, y * 0.05);
      tile.setFill(color(noiseValue * 255));
      tile.setStroke(false);
      tiles.addChild(tile);
    }
  }
}

void draw() {
  shape(tiles);
  fill(255, 0, 0);
  text("FPS: " + round(frameRate), width/2, 20);
}

tlecoz

PShape is good is you don't need to update the position of your tiles. You can move it using PShape.translate but it's not very easy to use (depends on what kind of motion you need)

Caramazula

@tlecoz I reach about 11ms frametime with this solution. Thats actually better then rect(). Progress :D But the shaders thingy sounds nice too.

  beginShape(TRIANGLES);
  texture(a); // a.w = 400 // a.h = 300
  for (int y = 0; y < height / 5; y++) {
    for (int x = 0; x < width / 5; x++) {
      vertex(x * 5, y * 5, 0, 0);
      vertex(x * 5, y * 5 + 10, 800, 0);
      vertex(x * 5 + 10, y * 5, 0, 600);
    }
  }
  endShape();

@amnon The program I postet is what I want it to look like. I could try to get that result by useing shaders. There is a whole lot stuff about 3D shaders, but I couldn't find any 2D shaders. Is there any tutorial on writing 2D shaders? I couldn't find any.

amnon

You can use the filter() method with only a fragment shader or you could use the shader() method with a rectangle that will be renderer using the PShader.

See: Examples > Topics > Shaders

Here is a basic example with a grid and some mouse-centered light...

Processing sketch

PShader tiles;
float scale = 10;

void setup() {
  size(800, 600, P2D);
  tiles = loadShader("tiles.glsl");
  tiles.set("resolution", float(width), float(height));
  tiles.set("scale", scale);
}

void draw() {
  tiles.set("mouse", float(mouseX), float(height-mouseY));
  shader(tiles);
  rect(0, 0, width, height);
}

Fragment Shader

#ifdef GL_ES
precision mediump float;
#endif

#define COLOR_W vec4(1.0,1.0,1.0,1.0)
#define COLOR_R vec4(1.0,0.0,0.0,1.0)
#define COLOR_B vec4(0.0,0.0,0.0,1.0)

uniform float scale;
uniform vec2 mouse;
uniform vec2 resolution;

void main( void ) {
 vec2 pos = mod(gl_FragCoord.xy, resolution) - mouse;
 float dist_squared = dot(pos, pos);
 vec4 color;

 int x = int(gl_FragCoord.x) / scale;
 int y = int(gl_FragCoord.y) / scale;

 float sum = float(x+y);

 if (mod(sum, 2.) == 0.) {
  color = COLOR_W;
 } else {
  color = COLOR_R;
 }

 gl_FragColor = mix(color, COLOR_B, smoothstep(floor(0.0),floor(20000.00),dist_squared));
}

tlecoz

a Shader has no dimension,it do what we want and that's all. If you want to do 3D computation, it will do 3D. If you want to do 2D computation, it's the same... A shader only do the computation you want.

For a light shader, you should look for "fragment shader" , it's what you're looking for.

A shader is always composed by two parts : the "vertex shader" that represent a single triangle triangle of your mesh , and the "fragment shader" that will "paint" the pixel inside your specific triangle.

When a shader is executed, openGL do a loop on every vertex you have in your buffers and process one triangle at a time, triangle by triangle.

Caramazula

Well, I feel quite comfortable with the triangle solution, but there is some serious overlapping going on:

Do I really need to draw all of the triangle? Or should I read into shaders?

tlecoz

I don't understand your last draw. Every triangle should be oriented in the same direction, but the position of the triangle should depend on the size of a rect instead of the size of the triangle. Every triangles should overlap but not the rect inside triangle.

"Do I really need to draw all of the triangle? Or should I read into shaders?"

The best is to do the two thing :)

Shader are very powerfull, you may should focus on it :)

Caramazula

Well, there is just one last thing I would like to know. What do I do if I want the triangles to have different textures? I can only set one texture per shape.

tlecoz

Hello !

You have to use a big texture, draw every single texture in it and then target each subTexture with the UV data (the 2 last parameters of the function "vertex")

As I said before, it's much more complex to proceed like that, but this is the most efficient way to do

Caramazula

Nice! I got all my textures working, so lets proceed with my next concern.

Lets say this is my texturesheet:

Then my triangle looks like this:

But I only want it to be the red 1/4 of my texturesheet and the rest of the triangle should be invisible, is that possible?

tlecoz

you have to leave some space (the triangle at right and at the bottom of your rect must be transparent - then your main texture will be much bigger than if you use quad-texture , but this is the only one solution I know - and that's how I do - )

EDIT : If your game is supposed to run on mobile device, you should "divide the work" into différent "texture" because most of device doesn't support big texture (but it's not a big problem because you can define a particular texture inside a shader if needed)

EDIT2 : Everything is important. Shader are very important and you really should look into it, even if you don't need it directly. Because you can do so much of things with Shaders... As Amnon said before, if you want to build a light effect, it would be ridiculous to do it in java instead of GLSL because GLSL can do much more than Java and faster. Shader can be used to do a lot of thing, you can even work with sound-data with a shader :) If you are enough "expert" to build your game with single-triangle-texture, you really should look at it, it's not an option :)