What are some ways to accomplish a dynamic array?

Question

I'm going to start working on a new game and one of the things I'd like to accomplish is a dynamic array sort of system that would hold map data. The game will be top-down 2d and made with XNA 4.0 and C#. You will begin in a randomized area which will essentially be tile based. As such a 2 dimensional array would be one way to accomplish this by holding numerical values which would correspond to a list of textures and that would be how it would draw this randomly created map. The problem is I would kind of only like to create the area around where you start and they could venture in which ever direction they wanted to. This would mean I'd have to populate the map array with more randomized data in the direction they go. I could make a really large array and use the center of it and the rest would be in anticipation of new content to be made, but that just seems very inefficient.

I suppose when they start a new game I could have a one time map creation process that would go through and create a large randomly generated map array, but holding all of in memory at all times seems also inefficient. Perhaps if there was a way that I'd only hold parts of that map data in memory at one time and somehow not hold the rest in memory. In the end I only need to have a chunk of the map somewhat close to them in memory so perhaps some of you might have suggestions on good ways to approach this kind of randomized map and dynamic array problem. It wouldn't need to be a dynamic array type of thing if I made it so that it pulled in map data nearby that is needed and then once off the screen and not needed it could somehow get rid of that memory that way I wouldn't have a huge array taking up a bunch of memory.

Answer 1

It sounds to me like you're trying to solve a problem before you're sure the problem actually exists.

Have you actually tried doing it the simple way (just loading everything in memory) and seen that it uses too much memory? Quoth Knuth, "Premature optimization is the root of all evil".

The point is, focus first on the unique thing you're trying to accomplish that is the reason you're creating this game - there is sure to be plenty to keep you busy there. Unless you've got some crazy paradigm-shifting new take on top-down 2D scrollers, memory utilization is not likely to be a limiting factor - even on a restricted environment like a smartphone.

If you finish developing the game and you find that memory utilization is actually an issue, then it would be the right time to start to optimize. Don't only focus on the solution you assume in the question (temporal caching and prefetching), but be open to finding other ways that your program is using memory that it doesn't need.

Answer 2

I am just a student, and don't have any game programming experience, but from what I know, you can't just expand an array while you're using it. I imagine you would need to shift resources back and forth between something like nine buffers (each a 2-D array, one for each NSEW and diagonal direction), and each buffer has say, 9 tiles.

For instance:

The player loads into a zone, and is in the middle of your 3x3 array of tiles, such that they have tiles visible in every direction. In the background, you compute the texture IDs for the surrounding buffers and have them ready.

[  CENTER   ]
+---+---+---+
|   |   |   |
+---+---+---+
|   | X |   |
+---+---+---+
|   |   |   |
+---+---+---+

When a player moves out of the center tile, say, East, they will be positioned on the Eastern edge of the Center buffer.

[  CENTER   ]
+---+---+---+
|   |   |   |
+---+---+---+
|   |   | X |
+---+---+---+
|   |   |   |
+---+---+---+

At this moment place the buffer which is prepared for the East direction along the edge of the center buffer so that the tiles overlap by one.

        [    EAST   ]
[  CENTER   ]
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   | X |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

This allows the player to be able to move into the Eastern buffer. Once there, the Eastern buffer becomes the Center buffer, and the old center buffer is re-cycled as the new Western buffer. The old Western buffer (and those vertically adjacent to it) can also be recycled to become the new North-East, East, and South-East buffers.

[  CENTER   ]
+---+---+---+
|   |   |   |
+---+---+---+
|   | X |   |
+---+---+---+
|   |   |   |
+---+---+---+

Of course, you would need to experiment with how many buffers you need, how many tiles per buffer, and when the appropriate recycle/pre-processing times would be for performance, but I imagine this would work.