Sign in to follow this  
Yarb

C# Best way to extend array

Recommended Posts

I have made great progress in my C# education the Roguelike way (Thanks in large part to tips from gamedev.net). I am redoing everything in XNA and adding graphic tiles but have come up against a situation with a lot of options. I currently have my map in a 2 dimensional array of int. each cell contains an int indicating the terrain type. I have a Terrain class that keeps info by type (Terrain type, whether it is walkable, whether it blocks LOS, what Character is used for it etc...). Now I need to extend the info for each cell on the map, I need to track whether the location has been seen before and will probably need to add more later. What is the best way to do this, I could make a class and make the map array a 2 dimensional array of objects. Is it reasonable to instantiate a class 65,536 times? I could also use multiple arrays (This is the way I would have done it in the 80’s). I think I could use a list (Something I have read about but am not yet clear on). What is the accepted way of doing this? Yarb PS I know this is a bit newbish but then again I am a newb, I am relearning programming during evenings and weekends after 20+ years away.

Share this post


Link to post
Share on other sites
Hi,

Having 64k objects should not be a problem. The overhead of an object in .NET is 8 bytes on a 32 bit machine (iirc 16 bytes on 64 bit machines). Let's say each tile object stores 40 bytes of extra data you would end up using 48 bytes x 65536 = 3 MB (on 32 bit machines), which is nothing on todays hardware. The garbage collector should not have problems with the objects either.

If you want, you can use structs instead of classes, especially if you store very little information per tile (say < 32 bytes). Structs don't have any per-instance overhead, an array of structs can be allocated as a whole block in memory and will put less pressure on the GC. On the other hand you might end up copying more data between variables and method calls because struct instances are passed by value.

If the dimension of your map is fixed during the game (which I assume) an array is ok as data container. You could of course wrap things up a bit and implement a class (say Map) that internally stores the tiles as an array (preferably a 2D-array) and allows access to individual tiles trough an indexer (this[int x, int y]). Again, keep in mind that struct instances will be returned by value from the indexer.

To sum it up, 64k objects should not be problematic, neither memory wise nor speed wise. An array is most likely a good container for the tiles if the size is static.

Regards,
Andre

Share this post


Link to post
Share on other sites
Well there are a few things you could do. First, if you made them structs instead of classes, you wouldn't run into the garbage collector penaltie that may occur with having that many objects around. In all likelihood, however, even that many classes probably won't cause any noticeable performance issues (on a PC. XBox360 is another story.)

What I would do is to have a simple List<> of one of each possible graphics tile, with all the settings for each tile. Then, in the array, simply reference the list (since classes are just reference types) of stored tile data.

EDIT: VizOne beat me to it. :)

Share this post


Link to post
Share on other sites
Well there are a lot of ways to do this. One way would be to create a 2d list of elements of a custom type, but as you asid creating 65K of objects isn't really a good option.

You could instead go with virtualization since most tiles would the same and you most likely only have a limited set of states you can reuse these. You would still need your list of ints, but now you simply map a int to the specific map data.

Instead of using a array of fixed size you could simply use a list of int and just keep the difference in the list. This would also limit the mem footprint, it might even be worth keeing a second list for the visibility this way you wouldn't need to keep two instance data (visited/not visited).

Just a few comments.

Share this post


Link to post
Share on other sites
Thanks for the quick response. I have been making some refinements to my engine specs and I think I am going to try a linked list (If for no ther reason, because I have never used one). I am thinking that I can then not only keep track of whether or not the player has seen that x,y location before but also I can keep the base tile, transiton tile, object tile and data tile references in the list.

Yarb

Share this post


Link to post
Share on other sites
Quote:
Original post by Yarb
I think I am going to try a linked list

A linked list is one of the worst choices for your specific needs. You will likely want to have random access to the game map, which a linked list cannot provide. Plus a linked list consumes a lot more memory than a vector or an array.

Share this post


Link to post
Share on other sites
Quote:
[A linked list is one of the worst choices for your specific needs. You will likely want to have random access to the game map, which a linked list cannot provide. Plus a linked list consumes a lot more memory than a vector or an array.

Hmmm I R Nubsauce... I was thinking that I could make an array of linked lists, each element of the array would contain a linked list for one x,y location on the map containing pointers to the graphic tiles that are needed to draw the map along with other information such as whether or not the player has ever seen this location.

Honestly though this discussion has moved beyond my admittedly low level of knowledge so I will need to do some reading (Especially on lists) before I can make educated conversation.

Thanks again for the rapid response; you guys make a huge difference when it comes to knowing where I need to look for my answers. I find on this type of project (In this case learning C#) I need to obtain a certain "Critical Mass" of knowledge before everything gels and makes sense, until that point it can be a bit frustrating trying to "Figure out what I need to figure out".

Yarb

Share this post


Link to post
Share on other sites
If you're concerned about memory usage, you might find quadtrees to be useful solutions to storing some of the values, particularly the boolean ones.


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this