Page 1 of 1
How to make an efficient map structure?
Posted: Wed Apr 06, 2016 2:04 pm
by 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
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?
Re: How to make an efficient map structure?
Posted: Wed Apr 06, 2016 2:11 pm
by 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
Awesome! But still would like comments of the efficiency or otherwise of this method!
Re: How to make an efficient map structure?
Posted: Wed Apr 06, 2016 2:44 pm
by 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
Re: How to make an efficient map structure?
Posted: Wed Apr 06, 2016 3:18 pm
by mr_happy
Thanks for the feedback/info
s-ol wrote: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
Re: How to make an efficient map structure?
Posted: Wed Apr 06, 2016 3:43 pm
by 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
Re: How to make an efficient map structure?
Posted: Wed Apr 06, 2016 3:52 pm
by 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!
Re: How to make an efficient map structure?
Posted: Wed Apr 06, 2016 4:22 pm
by mr_happy
Inny wrote: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.
Re: How to make an efficient map structure?
Posted: Wed Apr 06, 2016 10:16 pm
by 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.
Re: How to make an efficient map structure?
Posted: Sun Apr 10, 2016 12:04 pm
by bobbyjones
Use ffi structs and arrays \o/