2d maps: two or one dimensional array?
Author
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
I would use a recursive vector. It''s faster than the 2d array but uses the same syntax. Init it like this
vector > map;
Then you just access the element individually like this:
map[x][y];
-----------------------------
Final Frontier Trader
vector > map;
Then you just access the element individually like this:
map[x][y];
-----------------------------
Final Frontier Trader
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
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.
But if you need to dynamically allocate the map then
obviously the 1D array would be better.
Author
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
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
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..
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]
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/2PosInStringOfTypes = (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]
Author
hi,
Shouldn''t wbit be the second square of the width instead of half the width?
bye
chris
Shouldn''t wbit be the second square of the width instead of half the width?
bye
chris
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
