🔒 Locked

Efficient 2D array resizing

Started by BNY Feb 27, 2008 at 11:40 PM 15 replies 1.7k views

Original Post

Feb 27, 2008 at 11:40 PM

I have a 2D array that is dynamically allocated and used to display a tile map in a map editor program... it's really just linear memory of size [rows * columns] that can be accessed like map[r][c] the way the pointers are set. It works well and gets the job done, but I have some concerns when it comes to resizing the map. By default, the map is 32 by 32 tiles, and the user is allowed to add rows and columns as well as delete them and resize to any dimension. At maximum, I expect it to be about 256 by 256 tiles. The problem I see is that the simple way of resizing by creating the new map array and then copying in the old one can take up a bit of memory. With the current worst case scenario, it'll take about 8MB for a resize operation, which isn't horrible, but I think I could do better. Using the memory pool I have, I don't see any possible way of appending or deleting a row or column, so I was hoping there were some ideas out there. One idea was to have the 2D array set up so that the memory is not linear, but so that each row number of the array points to an allocated area of memory that makes up each row. When resizing, allocate a new list of row pointers and then copy the old pointer values in with the correct locations, then just allocate or free the row being deleted. For columns, I would have to step through every row and copy the information in, then delete the old one for every row there is. It sounds like it's a lot of work, but only a single row of tiles is being allocated at a time, so it's just an additional 1.6KB for a resize in the worst case. Should this be something I could work on, or am I over reacting about memory conservaition? Suppose I up the map max size to 512 * 512... the total resize operation would take 32MB worst case. If there are any ideas or articles about similar operations, I'd be glad to listen.

Zakwayda

Feb 28, 2008 at 12:15 AM

What platform are you developing for? What language are you using?

BNY

Feb 28, 2008 at 5:48 PM

Windows, using Visual C++. I'm more interested in the theory rather than specific code.

DrEvil

Feb 28, 2008 at 6:06 PM

This is one of those operations that seem to me like it shouldn't matter performance or memory wise. Resizing shouldn't normally happen in the game, and its speed and efficiency matters even less if this is in a tool. If it's a tool I would just allocate a 'largest map size I could want' buffer, and treat it as a small map buffer by hiding those details in your map class. For example your map class could be allocated with a memory block to support a 256x256 map, but you could be actually working with and loading a 128x128. With that, a resize would simply be expanding the soft bounds of the map.

swiftcoder

Feb 28, 2008 at 6:11 PM

Quote:
Original post by BNY
the user is allowed to add rows and columns as well as delete them

What is the frequency of addition and deletion other than at the edge of the map? In general, I would expect this to be a very rare operation, and thus not worthy of considerable effort on your part.

TheTroll

Feb 28, 2008 at 6:37 PM

People always make things more complicated then it has to be.

We have X_MAX and Y_MAX, you said that will be 256, so we define them as that.

Next we make X_Current_Max and Y_Current_Max. Those are your current maximums.

Always declare size[X_MAX, Y_MAX]. It is just a array of pointers so the memory consideration is not that significant. You them allow the user to see and use map[X_Current_Max][Y_Current_Max]. This will allow you to give them more or less without actually having to redo the memory. So the dynamic part is really just changing the values of X_Current_Max and Y_Current_Max, not memory allocation.

As for the 512 X 512, just make your X_MAX and Y_MAX 512, you could just have a setting in some config file with the maximums, if they need to bump up the maximum just have the the application restart.

TaDa dynamic memory. :)

theTroll

Iftah

Feb 29, 2008 at 6:35 AM

just do the simplest solution, but make sure it is abstracted from the rest of the application.

ie.

class Level {  Layer *currentLayer=0;  void changeLayerSize(const Size &newSize);};void Level::changeLayerSize(const Size &newSize){   if (currentLayer)     currentLayer->setSize(newSize);  // <--- abstracted }

you can later change the layer to be a linked list of rows, or a quad tree or whatever, just make sure its all private.

BNY

Feb 29, 2008 at 5:53 PM

swiftcoder:
It's really up to the user. Maybe they have a set size of a map in mind that they'd like to work around so that it would be a very minimal operation, and if not, they'd have a map planned out and then decide to add something in the middle, which then becomes a very often used operation.

DrEvil and TheTroll:
I had that idea as well, but I thought it would be taking up more memory than nedded by the program. However, when the map is to be compiled, only the visible areas would be written to file, which is a plus. Maybe if I treat the map similar to how a vector is resized... have min and maximum dimension variables, so when the user wants more than the current max, it will allocate more memory to the next availalable max. For instance, the current max is 32 rows and the user wants to have 48, so then a max of 64 rows would be allocated, but only 48 show. Resizing by memory allocation would be much less frequent then.

Iftah:
Absolutely. I have a TileMap class right now which the main program can use. Some methods available are addRow(), deleteRow(), and resize().

I'll have to look into all possible options. Thanks for your replies!

iMalc

Feb 29, 2008 at 5:55 PM

As you put it, I believe you are "over reacting about memory conservaition"
Vectors do the same, allocating the new array, copying over and deleting the old array. For that matter, you should simply be using a vector anyway.

Ravyne

Feb 29, 2008 at 6:36 PM

If it were me, I'd go for a std::vector of std::vectors (of std::vectors, if multiple layers are supported.)

Also, either your tile structs are ridiculously large, or your math is off in regards to your memory use. 256x256 cells results in 65536 units, now double that for a grown buffer -- that's 131072 units... Are your tile structs *really* 64 bytes each? That seems more than a little large... If that's strictly tile properties you would do well to reference an array of tile structs via pointer or index, you could easily get your worst-case memory usage down to 256KB (assuming 16bit indices) during a grow operation

TheTroll

Feb 29, 2008 at 9:54 PM

Even a 512 x 512 map would only have just over 1 MB for the pointer memory. So in reality the memory issue is not that big.

It comes down to speed vs. memory. Vector is slower then a static array but will not use the extra memory.

You just need to make sure to clean up the memory after you shrink the map.

theTroll

BNY

Mar 1, 2008 at 5:30 PM

Quote:
Original post by ravyne2001Are your tile structs *really* 64 bytes each? That seems more than a little large... If that's strictly tile properties you would do well to reference an array of tile structs via pointer or index, you could easily get your worst-case memory usage down to 256KB (assuming 16bit indices) during a grow operation

Yes, each tile struct is 64 bits.
16 for base layer ID
16 for detail layer ID
16 for overhead layer ID
16 padding / undecided

Initially I used a 32 integer for tile IDs and just bitmasked them so it was a max of 1024 unique tile IDs per layer, but that could get used up pretty quick with large detailed maps. The actual tile objects contain information about collision type, animation, particle effects, color, and destructability.

Darragh

Mar 1, 2008 at 7:19 PM

Quote:
Original post by BNY
I have a 2D array that is dynamically allocated and used to display a tile map in a map editor program... it's really just linear memory of size [rows * columns] that can be accessed like map[r][c] the way the pointers are set. It works well and gets the job done, but I have some concerns when it comes to resizing the map.

By default, the map is 32 by 32 tiles, and the user is allowed to add rows and columns as well as delete them and resize to any dimension. At maximum, I expect it to be about 256 by 256 tiles. The problem I see is that the simple way of resizing by creating the new map array and then copying in the old one can take up a bit of memory. With the current worst case scenario, it'll take about 8MB for a resize operation, which isn't horrible, but I think I could do better.

Using the memory pool I have, I don't see any possible way of appending or deleting a row or column, so I was hoping there were some ideas out there. One idea was to have the 2D array set up so that the memory is not linear, but so that each row number of the array points to an allocated area of memory that makes up each row. When resizing, allocate a new list of row pointers and then copy the old pointer values in with the correct locations, then just allocate or free the row being deleted. For columns, I would have to step through every row and copy the information in, then delete the old one for every row there is.

It sounds like it's a lot of work, but only a single row of tiles is being allocated at a time, so it's just an additional 1.6KB for a resize in the worst case. Should this be something I could work on, or am I over reacting about memory conservaition? Suppose I up the map max size to 512 * 512... the total resize operation would take 32MB worst case. If there are any ideas or articles about similar operations, I'd be glad to listen.

As far as I can see you have 3 potential options here, and which one you pick depends on where you consider performance to be the most important. I'm trying to think of a more exotic data structure that might provide a reasonable solution to this problem but these are the ones that immediately spring to mind:

Option 1:

Keep the original resize code, and just delete / recreate the array. This would make for fast access (access doesn't get much quicker than arrays!) and redrawing, increasing the responsiveness of your editor. However, as you rightly pointed out, changing the size of the map would be pig slow. You could use some hand coded inline assembly to try and speed up this operation however; SIMD instructions in conjunction with cache control instructions would help, but it's only making a slow algorithmn slightly faster..

Option 2:

Store each row or column in the map as a separate array and keep a list of all the rows or columns. Access speed would be reduced in this case but would make for faster insertion / deletion of either rows or columns, depending on whether you opted to store each row or column in a separate array. This is kind of a half way compromise..

Option 3:

Maintain a completely dynamic structure where each tile has pointers to north / south / east / west tiles. This would make for the fastest insertion or deletion but access times would suffer considerably because of all the pointers you would have to follow, just to get to where you want.

Personally, I would keep your current code (Option 1). Resizing the map would not be a routine operation so I would favor performance for displaying and editing tiles rather than resizing the map. Keeping the editor responsive for routine editing would be more important than speeding up a seldom used command I think.

[Edited by - Darragh on March 1, 2008 7:19:24 PM]

Zahlman

Mar 1, 2008 at 7:56 PM

Noone else is going to mention boost::multi_array? :(

Ravyne

Mar 1, 2008 at 9:13 PM

Quote:
Original post by BNY
Quote:
Original post by ravyne2001Are your tile structs *really* 64 bytes each? That seems more than a little large... If that's strictly tile properties you would do well to reference an array of tile structs via pointer or index, you could easily get your worst-case memory usage down to 256KB (assuming 16bit indices) during a grow operation

Yes, each tile struct is 64 bits.
16 for base layer ID
16 for detail layer ID
16 for overhead layer ID
16 padding / undecided

Initially I used a 32 integer for tile IDs and just bitmasked them so it was a max of 1024 unique tile IDs per layer, but that could get used up pretty quick with large detailed maps. The actual tile objects contain information about collision type, animation, particle effects, color, and destructability.

Hold on a sec. I'm talking bytes while you're talking bits. This might be the cause of your miscalculation. If your tile struct has 4 16bit integers, then that's only 8 bytes per array element, and you're only using 1/8th of what you think you are.

That said, Zahlman's suggestion of boost::multi_array is an excellent choice. All the work is done for you already, and the stuff in boost is basically a second-tier to the standard library (except of course, the stuff from boost that is now included in the tr1 extension to the standard library [grin]). I should really get more into the habit of recommending it...

Scythen

Mar 1, 2008 at 9:43 PM

Quote:
Original post by DrEvil
and its speed and efficiency matters even less if this is in a tool

Anyone who would say this has not written many tools. When you have huge amounts of game assets to processes tools have to be just as fast and efficient as the game its self. Build times have to kept to a minimum and some tools have to respond in real time to user input.

BNY:
Given that you’re only working with a 256x256 map it sounds like you should just allocate the maximum size and use the portion you need. One array of this size is of no consequence as long as your not constantly allocating and freeing it. I’d suggest abstracting the tile system so no code actually interacts with the array. Then later if memory does become an issue you can choose a better system like a sparse array of something to store tiles.

BNY

Mar 1, 2008 at 9:58 PM

Quote:
Original post by ravyne2001Hold on a sec. I'm talking bytes while you're talking bits. This might be the cause of your miscalculation. If your tile struct has 4 16bit integers, then that's only 8 bytes per array element, and you're only using 1/8th of what you think you are.

AHH! How did I not catch this? That sounds much more reasonable now that you pointed out that mistake. I've been designing this thing for a while around the thought I was working with bytes the whole time. It's pretty embarassing actually. Thank you for pointing that out. :)

As for boost::multi_array, I'll check it out. It sounds like just the tool I'd need. I appreciate everyone's comments!

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.