A Question of Draw performance

[Pash]

I think larger table iterations are killing my performance. We are talking 100,000's of table items to look through.

I suppose you have a table with to indeces, with all the tiles in it. If this is the case, you can shorten the iteration by using the two-index structure. So lets say you have a table with two indices, containing information on what tiles have to be drawn: tile[x][y]. For a whole loop you would do two nested for loops for x and y each from 1 to the respective maximum. You can shorten these loopes, if you know the camera position. From the camera position, first determine the (tile)-coordinates of the first tile in the upper left corner and of the last tile in the lower right corner. These tile coordinates can now be used as the start and the end of the for loops. That way, the number of table entries to consider will never be larger than the number of tiles visible on screen.

Hi Micha,

So you mean something like this:-

for i,v in ipairs(tablename) do
logic for x match up to camera x pos
for i,v in ipairs(tablename) do
logic for y match up to camera y pos
end
end

Im guessing this is what you mean?

Cheers,

Pash

Cancel That. I get what you mean.

[micha]

No, that's not what I mean. My explanation was a bit short maybe. Let me explain better.

I suggest, instead of having one long table worldBlocks with i going from 1 to 1.000.000 you should have a 2dimensional array worldBlocks[j] with i and j each ranging from 1 to 1.000. That alone will not make anything easier. But it will become easier, if you align this 2-d array structure with the 2-d structure of the tiles in the game. By that I mean that
worldBlocks[1][1] refers to the block in the upper left corner of the whole domain
worldBlocks[1][2] is the block right next to it. And so on. So the indices themselves contain the information about the position of the tiles in your domain.

Next, if you have a position, that does not contain a tile, you simply assign nil to it. This will save memory.

You now, no longer need to store the x and y coordinates of the tiles as they are stored in the indices already. Now you only need to store the actual tile graphic you want to display and additional information for your game mechanics (collision and stuff).

Now for the actual shortening of the loop:
The naive approach is:

Code: Select all

for i=1,1000 do
  for j=1,1000 do
    whatever you want with worldBlocks[i][j]
  end
end

This will loop through all 1.000.000 blocks. To avoid this, you first calculate the (i,j) coordinates of the tile in the upper left corner, lets call them imin, jmin. Also calculate the (i,j) coordinates of the lower right corner, imax, jmax. Now you only need this loop:

Code: Select all

for i=imin,imax do
  for j=jmin,jmax do
    whatever you want with worldBlocks[i][j]
  end
end

If your window is only 20 by 30 tiles wide, then this will only iterate through 600 tiles, instead of 1.000.000.

In short, this technique allows you to know the coordinates of a tile, before even accessing the corresponding variable.

[Pash]

No, that's not what I mean. My explanation was a bit short maybe. Let me explain better.

I suggest, instead of having one long table worldBlocks with i going from 1 to 1.000.000 you should have a 2dimensional array worldBlocks[j] with i and j each ranging from 1 to 1.000. That alone will not make anything easier. But it will become easier, if you align this 2-d array structure with the 2-d structure of the tiles in the game. By that I mean that
worldBlocks[1][1] refers to the block in the upper left corner of the whole domain
worldBlocks[1][2] is the block right next to it. And so on. So the indices themselves contain the information about the position of the tiles in your domain.

Next, if you have a position, that does not contain a tile, you simply assign nil to it. This will save memory.

You now, no longer need to store the x and y coordinates of the tiles as they are stored in the indices already. Now you only need to store the actual tile graphic you want to display and additional information for your game mechanics (collision and stuff).

Now for the actual shortening of the loop:
The naive approach is:

Code: Select all

for i=1,1000 do
  for j=1,1000 do
    whatever you want with worldBlocks[i][j]
  end
end

This will loop through all 1.000.000 blocks. To avoid this, you first calculate the (i,j) coordinates of the tile in the upper left corner, lets call them imin, jmin. Also calculate the (i,j) coordinates of the lower right corner, imax, jmax. Now you only need this loop:

Code: Select all

for i=imin,imax do
  for j=jmin,jmax do
    whatever you want with worldBlocks[i][j]
  end
end

If your window is only 20 by 30 tiles wide, then this will only iterate through 600 tiles, instead of 1.000.000.

In short, this technique allows you to know the coordinates of a tile, before even accessing the corresponding variable.

Brilliant example and well explained. Thanks micha.

[Robin]

Also, to save even more memory, you can have worldBlocks be nil for every specific i if for that i and for every j, worldBlocks[j] would be nil anyway. You need a few extra checks if you do that, though, but if there are a lot of gaps it can definitely be worth it.

[Pash]

Also, to save even more memory, you can have worldBlocks be nil for every specific i if for that i and for every j, worldBlocks[j] would be nil anyway. You need a few extra checks if you do that, though, but if there are a lot of gaps it can definitely be worth it.

More great advice!! Thanks Robin.

So am I correct in saying i need to design my table structure as so:-
eg.
WorldBlocks = {{ x = 16,y = 16, img = cBlock },{ x = 32,y = 32, img = cBlock },{ x = 48,y = 48, img = cBlock }}

To make that loop micha gave me work? So each block position is accessible as a grid before I even do anything fancy.

Sorry, im new to multi di arrays in lua. Trying to get my head around using them in this example.

Cheers,

Pash

[Robin]

For this, you will want to do something like this:

Code: Select all

WorldBlocks = {
   [1] = {[1] = {img = cBlock} },
   [2] = {[2] = {img = cBlock} },
   [3] = {[3] = {img = cBlock} }
}

If you don't have any other information you'd like to store in the tiles, you might want to replace {img = cBlock} by cBlock.

Note that I used indexes instead of offsets: this is easier with for-loops and counting things and makes it easier to change tile size later on (or if you suddenly decide you want the ability to zoom in or out).

[Pash]

Ok I think I got it. So my table structure would look something like this infact (purely as an example):-

WorldBlocks = {

[1] = {
[1] = {img = dirt, type = 1}
[2] = {img = dirt, type = 1}
}
[2] = {
[1] = {img = dirt, type = 1}
[2] = {img = gold, type = 1}
}
}

So id create the above table structure by doing something like this:-

for i=1,blockYCount do
for j=1,blockXCount do
table.insert(WorldBlocks, i, { [j] = {img = cBlock, type = typ}})
end
end

As Robin mentioned, I don't need to really store the x and y's as that can be worked out by the indices values and multiplying by block size (for purposes of adding items to spritebatch).

I really do like this as an idea, aslong as my understanding is correct (which I "think" it is)

[micha]

You understand correctly.

To generate such a table instead of

Code: Select all

for i=1,blockYCount do
for j=1,blockXCount do
table.insert(WorldBlocks, i, { [j] = {img = cBlock, type = typ}})
end
end

Do this:

Code: Select all

worldBlocks = {}
for i=1,blockYCount do
  worldBlocks[i] = {}
  for j=1,blockXCount do
    worldBlocks[i][j].img = cBlock
    worldBlocks[i][j].type = typ
  end
end

Next I suggest you implement some form of input-file-reader. So you can just write a block of numbers into a txt-file and then read it on run time, instead of hardcoding the levels. I believe there is a tutorial around explaining how to do this.

[Pash]

You understand correctly.

To generate such a table instead of

Code: Select all

for i=1,blockYCount do
for j=1,blockXCount do
table.insert(WorldBlocks, i, { [j] = {img = cBlock, type = typ}})
end
end

Do this:

Code: Select all

worldBlocks = {}
for i=1,blockYCount do
  worldBlocks[i] = {}
  for j=1,blockXCount do
    worldBlocks[i][j].img = cBlock
    worldBlocks[i][j].type = typ
  end
end

Next I suggest you implement some form of input-file-reader. So you can just write a block of numbers into a txt-file and then read it on run time, instead of hardcoding the levels. I believe there is a tutorial around explaining how to do this.

Thanks micha! Yeh ive seen that tutorial, thanks. I was also of thinking of some kind of procedural generation of caves, elevations, resource locations etc for larger maps and implement these systems after the standard blocks are in place.

[Robin]

Micha, you mean:

Code: Select all

worldBlocks = {}
for i=1,blockYCount do
  worldBlocks[i] = {}
  for j=1,blockXCount do
    worldBlocks[i][j] = {}
    worldBlocks[i][j].img = cBlock
    worldBlocks[i][j].type = typ
  end
end

or

Code: Select all

worldBlocks = {}
for i=1,blockYCount do
  worldBlocks[i] = {}
  for j=1,blockXCount do
    worldBlocks[i][j] = {img = cBlock, type = typ}
  end
end