How to build a level file format

[Robin]

That will only make a difference if the objects are all different. If they are the same, they all point to the same memory, so it won't be a problem.

[Kadoba]

I like to use nil because I don't think it's particularly hard to work with and it does save a little memory, especially in multilayered maps where the upper layers have mostly empty tiles.

Even if you use a single "empty" object then the map still has to store memory pointers to that object and the indexes to the memory pointers. That's still very small but if you have a large multilayered map then it can add up.

[kikito]

I don't think the memory gain would be very significant - even if the cells were references to tables.

If I had issues with memory, I'd try to compress the tables more - say like this:

Code: Select all

map = {
  { 2, " ", 50, '#', 3, '^', 5, " " },
  { 3, "*", 50, '#', 2, '^', '#', 5, "*" }
}

A cell can be either a character, or a number followed by a character. Each number would mean "the following character repeated n times".

The code to manage those would be more cumbersome, of course. But it would use up less memory.

Another option would be using a pallete-based PNG file (which is already quite compressed), codify the cells as colors and read the map info with ImageData:getPixel. Holding a, say, 2000x2000 image in memory shouldn't be terribly expensive - but I might be wrong, this depends on how ImageData is implemented.

But I would only go there if I had detected a memory issue in the maps to begin with. Otherwise, I'd use the simplest, easiest structure possible.

Has anyone made any memory consumption tests?

[Robin]

Or maybe use quadtrees. (I thought you would have suggested them, kikito )

The thing is, it is not likely to matter. Especially with less experience, try to do the simplest thing that could possibly work first.

[Kadoba]

I ran this code in lua:

Code: Select all

local size = 1000

print("Measuring memory size of a " .. size .. "x" .. size .. " array.")
print("Start memory: " .. collectgarbage("count") .. "KB")

local map = {}
local empty = {}
for i=1,size do
  map[i] = {}
end

print("Nil memory: " .. collectgarbage("count") .. "KB")

for i=1,size do
  map[i] = {}
  for j=1,size do
    map[i][j] = empty
  end
end

print("Object memory: " .. collectgarbage("count") .. "KB")

and got this output:

Measuring memory size of a 1000x1000 array.
Start memory: 43.3359375KB
Nil memory: 111.025390625KB
Object memory: 16162.928710938KB

So a 1000x1000 array filled with pointers to the same object is roughly about 16MB. Of course a tilemap would never get near this size but there you go.

Edit: By the way I do think this is splitting hairs. Looking back it seems like I was trying to make an argument for using nil but honestly the memory gain wouldn't be very significant.

[vrld]

Well, you are comparing an array that has 1000 elements to one that has 1000000 elements. What did you expect?
A better benchmark:

Code: Select all

local size       = 1000
local prob_empty = .2      -- 20% empty
local mem        = {0,0,0}
mem[1] = collectgarbage("count")

local map = {}
local empty = {}
for i=1,size do
	map[i] = {}
	for j=1,size do
		if math.random() < prob_empty then
			map[i][j] = empty
		else
			map[i][j] = math.random()
		end
	end
end
mem[2] = collectgarbage("count")

map = nil
empty = nil
collectgarbage()

local map = {}
for i=1,size do
	map[i] = {}
	for j=1,size do
		if math.random() < prob_empty then
			map[i][j] = nil
		else
			map[i][j] = math.random()
		end
	end
end
mem[3] = collectgarbage("count")

print( ([[Memory consumption of a %dx%d map:
  Start:         %d KB
  Using symbols: %d KB (delta = %d)
  Using nil:     %d KB (delta = %d)
  symbols/nil:   %f]]):format(size,size, mem[1], mem[2], mem[2]-mem[1], mem[3], mem[3]-mem[1], mem[2]/mem[3]))

Output:

Code: Select all

Memory consumption of a 1000x1000 map:
  Start:         263 KB
  Using symbols: 16296 KB (delta = 16032)
  Using nil:     16296 KB (delta = 16032)
  symbols/nil:   1.000006

In other words: no difference at all.

Edit: Interestingly the nil-approach actually consumes more memory with certain probabilities:

Code: Select all

Memory consumption of a 1000x1000 map and 50% empty tiles.
  Start:         263 KB
  Using symbols: 16296 KB (delta = 16032)
  Using nil:     19570 KB (delta = 19306)
  symbols/nil:   0.832710

[Robin]

Edit: Interestingly the nil-approach actually consumes more memory with certain probabilities:

I think I might know why that happens:

Lua tables contain both an array-part and a hashmap-part. It makes sure that the size of the array part is the smallest PO2 such that at least half of the array-part is filled. With a high probability of nil, it becomes more likely that a huge chunk of the table has to be stored in the hashmap, which naturally consumes more memory (because keys need to be stored explicitly, rather than implicitly as the index in the array).

[Kadoba]

Well, you are comparing an array that has 1000 elements to one that has 1000000 elements. What did you expect?

I guess I expected nil = nothing so you have a 2d structure filled with nothing and that's how much memory it would use. Of course your benchmark is closer to how a tilemap would be structured in practice. I completely overlooked that lua is going to allocate the same memory for arrays of specific dimensions no matter what you put in them.

I've really been making a fool of myself a lot lately so I'm just going to slink out of this thread.

[kikito]

I've really been making a fool of myself a lot lately so I'm just going to slink out of this thread.

Don't feel bad about it. A surprisingly large amount of time, "obvious" optimizations don't work as intuition would suggest. I got my particular dose of humility via John Resig's* post about tries.

He was trying to solve a particular problem whose solution I had (as many others) studied in the University - it seemed like an "obvious" and "intuitive" solution, using a structure called "Trie" so a lot of people (me included) suggested using it. John didn't know it before, so he decided to try it.

And, he made a bunch of tests.

The results were quite illuminating; for his particular needs, Tries didn't perform as well as other solutions.

The lesson I got from that post was - when optimizing, don't make blind guesses - just make performance tests to try stuff. Otherwise you might be making things worse. "Don't optimize prematurely" derives from that. With all the high-level languages and complex libraries we use these days, there's so much stuff going underneath that intuition alone just doesn't work.

This is all to say that you didn't make yourself look like a fool at all - it happens to a lot of people!

*For those who don't know, John Resig is the author of jquery, one of the most important Javascript libraries ever IMHO.

[LoveHurts]

You can also study the sources of BoxBreaker:
http://love2d.org/forums/viewtopic.php? ... 7&start=20

I am trying to run this game but it crashes in love 0.8.0
It has to do with the physics name changes so I updated the code...
and now applyLinearImpulse doesn't cause the ball to move up I put a print where I think the error is in main.lua

BoxBreaker.love

(584.11 KiB) Downloaded 142 times