Archived

This topic is now archived and is closed to further replies.

Zoomby

2d maps: two or one dimensional array?

Recommended Posts

hi, what technique is better/faster (in your opinion) to store a 2d map? A 2d array where you can access a position directly (i.e. map[x][y]), or a 1d array where you calculate the position (i.e. map[y*width+x]) ? Is there any difference in speed? I would use method two, cause the allocation of the array is easier (when allocating dynamicly) and it''s layed out nicer in memory (only one block). bye chris

Share this post


Link to post
Share on other sites
Oh alright, sorry then.

Well first of all, concider the speed factor.

The normal access into an array by block notation ([]) is a multiplication, so using [][] is a double multiplication. Now, using a single array is one array multiplication ([]) and one inside the (y*width+x) statement.

Although, if I were you, I''d use a pointer, init it with malloc (or new, if you feel like cheating a little) and then use pointer math to access the elements. That way you need only one multiplication:

pObject = y*width+x;

That optimises it quite good I''d think.

Not sure if the code works though, heh, might need some corrections. Anyone sees errors?

-----------------------------
Final Frontier Trader
I would use the 2 dimensional array. As someone said before, it''s easier to access and to read.

But if you need to dynamically allocate the map then
obviously the 1D array would be better.

Share this post


Link to post
Share on other sites
hi,

It doesn''t matter how easy the access at the lowest level is, cause you can/will always have a Map class with a getPos(x,y) method. It''s more a philosophical question and I''m intersted in the speed difference (even if it''s minimal of course).

bye
chris

Share this post


Link to post
Share on other sites
I've always used that (y*width)+x notation.. it is probably slower (a little) than double-dimensioned arrays, but I started out in the daze when memory was precious and strings were faster, but it works just as fine for me and it's something I can do second-nature

If width is a multiple of 2, you could use shifts.. see source below, which would be speedier than straight multiplying. wbit is like the multiple or something, to get to width from 2..



wbit = width/2
PosInStringOfTypes = (y << wbit) + x


I fseek, therefore I fam.

[edited by - drarem on July 5, 2003 10:01:08 AM]

[edited by - drarem on July 5, 2003 10:02:22 AM]

Share this post


Link to post
Share on other sites