Public Group

Archived

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

2d maps: two or one dimensional array?

This topic is 5642 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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 on other sites
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];

-----------------------------
sorry, I didn''t say that I''m using C++!

Share on other sites
I think 2D array is better.Since it make sorce code easier to read.And simple access.

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?

-----------------------------
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 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 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/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]

Share on other sites
hi,
Shouldn''t wbit be the second square of the width instead of half the width?

bye
chris

1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5

• 13
• 26
• 10
• 11
• 9
• Forum Statistics

• Total Topics
633724
• Total Posts
3013556
×