How to make an efficient map structure?

[mr_happy]

I'm trying to figure out the best way to store my randomly ("procedurally") generated map. In some other language I'd use a 2D array of structures or objects but the way I'm thinking of doing it in Love/Lua feels clunky and inefficient (I haven't learned how OO works in Lua yet).

Lets say each cell of my 10x10 map needs a tile number, a 'seen' flag and a 'passable' flag - this is how I'm leaning atm but it feels wrong...

Code: Select all

mapStruct = {}

for y = 1, 10 do       
    mapStruct[y] = {}
    for x = 1, 10 do
        mapStruct[y][x] = {love.math.random(100), false, true}
    end
end

Then to see if a cell is passable, I'd use

Code: Select all

if mapStruct[5][5][3] == true

I'd prefer something like

Code: Select all

if mapStruct[5][5].passable == true

but I can't think how to achieve this or whether this whole scheme is just plain bad design.

Any suggestions please?

[mr_happy]

Just realised I can do this

Code: Select all

mapStruct[y][x] = {love.math.random(100)}
mapStruct[y][x]["passable"] = true

then access via

Code: Select all

mapStruct[y][x].passable

Awesome! But still would like comments of the efficiency or otherwise of this method!

[s-ol]

You are probably overoptimizing. I can only think of two simple ways of improving it:

1.) Use one contiguous array-like-table instead of a nested one:
you can get rid of a bunch of tables by indexing map with [x+y*width]. Drawback: need to have a constant and known width (or height).

2.) Use ffi to use an actual array
makes everything better and more complicated.

I would just leave it as-is right now, it shoudn't matter.

Also note that in your code above you don't need to do ["passable"] = true, you can assign with .passable = true too, or do that in the table constructor ({type=love.math.random(100), passable=true}).

And about OOP: that cannot help with the type of optimization you are looking for "at all". it might be a good idea to get familiar with it anyway. Also, if you haven't read about that yet, there is no "way OOP is done in Lua", everyone can have their own. but not to talk about that too much or someone will come in an discuss OOP with me and you, and that's not this thread's point

[mr_happy]

Thanks for the feedback/info

You are probably overoptimizing.

I haven't really thought about optimising as such, I just don't want to go building a program around the wrong data structure.

2.) Use ffi to use an actual array
makes everything better and more complicated.

Lol, I don't know what that is and it sounds like I don't want to!

Also note that in your code above you don't need to do ["passable"] = true, you can assign with .passable = true too, or do that in the table constructor ({type=love.math.random(100), passable=true}).

OK thanks, I must have misunderstood that somewhere.

Also, if you haven't read about that yet, there is no "way OOP is done in Lua", everyone can have their own. but not to talk about that too much or someone will come in an discuss OOP with me and you, and that's not this thread's point

Hehe, I will not mention it again

[Inny]

One thing I can recommend is to abstract away the checks behind function calls so that you're free to change it later when you identify (via performance testing of course) that it's a source of dropped framerates.

e.g.

Code: Select all

function mapStruct:isPassable(x, y) return self[y][x].passable end

[ivan]

Good post by s-ol. Another optimization could be to use "parallel tables" so that you have:

Code: Select all

_map = {1,2,3,4}
_passable = {true,true,false,true}

The idea being, reducing the number of tables.

But yes, generally you shouldn't have to optimize the table access since this is pretty fast anyways.
You may save some memory this way, but if your maps are huge it's better to load them in chunks.
It doesn't make sense loading a 10000x10000 map if you're going to display/update a small part of that map.
Good luck!

[mr_happy]

One thing I can recommend is to abstract away the checks behind function calls so that you're free to change it later when you identify (via performance testing of course) that it's a source of dropped framerates.

Cheers Inny, I think that will depend on what is required - the overhead of a function call to replace a single if statement won't achieve much but yes I'm a fan of utility functions when they make life easy and code clearer

Thanks Ivan, I don't fancy the parallel arrays idea (seems very old school!) but I can see where you're coming from. I'll just press on with what I've got for now and see how it pans out.

[kikito]

If you are doing a tile-based game, a 2d-table of "tiles" (were every tile is a table with properties like tile.solid) is a perfectly valid structure for your data.

[bobbyjones]

Use ffi structs and arrays \o/