Storing Large Amounts of Data

I have a tactics game map (think advanced wars or fire emblem), except it is a large open world. To save on memory there are set tiles (like plains, mountains, buildings, ect.) that each cell in the world will reference. And then on top of that I figured I would divide the world into chunks that are 50x50 cells (though I am not sure if that is necessary?). Ideally the world should be endless (or as close to it as I can get). So I have two questions:

1) How should I go about storing this amount of data? I found that after a 2D array size was above a few thousand it had troubles. I know there are Lists, Arrays, Dictionaries, and so on. Not sure what the best way to store them is though. There must be a few tricks you need to use to hold a large amount of data like this. I like the 2 dimensional array because it allowed me to easily save positions cells.

2) On top of the set tiles, there are also some variables that can change on certain tiles (building health for example) but is not present in all tiles. What method would be good to store this data on only certain cells?

Thanks in advance you wonderful people

 

It sounds like you need to rely more on procedural generation. If you control the random seed, you can have essentially infinite amounts of stuff, and not have to store a single byte of it - it's all generated on demand based on algorithms you write. If you look at a simulation like SpaceEngine, that's exactly what it does - it has literally the entire universe that you can go to on a whim, but it only generates small bits of it at a time as you move through them. On a smaller but more relevant scale, Kerbal Space Program does this for the terrain to great effect (they have some talks on how they do this).

Once you have the algorithm that can generate the world you want - or more to the point that can generate little bits of your world independent of each other - you basically only need to store which parts of the game the player has changed; after you procedurally generate the world, you then apply those changes.

 

This would certainly be ideal However I don't even know how to begin to do that.

EDIT: And if it helps at all, this is a year long student project. So would that be viable in this time frame?

 

It's certainly not for the faint of heart. But, having your map be tile based makes it easier.

You'll have to start with your framework. This is probably going to be little more than a function where you feed it X and Y coordinates of your tile, it spawns a new tile, places it in the right spot, and then returns that object. Don't worry about randomness yet - that'll come later. Just write something that generates endless tiles of flat ground.

This function will be called by some manager class. Once it recieves the object that's returned, you'll want to mark that area off so that your generator knows not to spawn it again. I'd recommend nested Dictionaries - Dictionary<int, Dictionary<int, SomeTileType>> - and then you'd be able to access any SomeTileType that exists through these dictionaries without breaking the bank on memory. If you need to, find tutorials on the .NET's Dictionary class, as you'll need to be very comfortable to do this. (You may want to use long's instead of int's as your coordinates - no real reason to be stingy there!)
...so, once you have that, the manager class will check against its existing array to make sure that a given tile doesn't exist before it tries to generate a new one.

Once you have that function, you need to start being clever about when you call it. If your game is mostly top down, this is pretty easy - you just start at the camera's X position - someNumber, round it to the nearest int, then loop up to X + someNumber, generating tiles as you go. Make sure that this goes through the manager above so you're not generating duplicate tiles.

Next, I recommend that you work out when to intelligently delete unused tiles. This one will be heavily dependent on your game logic and the user patterns in your game, but since it's less mission-critical than the others, I'll leave it as an exercise to the reader.

To review: up to this point you should have a system that just generates endless repeating tiles of flat ground. You have your camera or player object calling Manager.GenerateTilesForRange(minimumX, maximumX, minimumZ, maximumZ). The manager loops through those ranges and figure out which tiles are not yet generated, and if they need to be, calls a function GenerateTileFor(long X, long Z), and ads that tile to its manifest of tiles.

Now, and only now, do you start worrying about randomizing your terrain. I recommend you start by just playing with Perlin Noise for a little while and get used to it. Then you can start adding some randomness with the Random class - and, in particular, you want to control Random.seed before you begin. (You can combine these all you like, for example you might use the Perlin noise value to set Random.seed.)

 

A yearlong student project is a rather arbitrary amount of time. Do you have other student obligations? How many hours a week are you devoting to this project, on average? It could be anywhere from 4 a week to 50 a week, depending on a number of factors.

Creating a procedural grid system that you described is certainly feasible in a year, though by the sounds of it (no idea where to begin), you should spend some time studying up and taking things one step at a time. Try generating a simple, preset 10x10 map.

http://forum.unity3d.com/threads/best-unity-procedural-generation-tutorials.294890/

This a link to some discussion on Unity Procedural Generation, for when you want to really expand things.

Lastly, its common to overscope your first large project. An open world tactical game like this could easily surpass a year for a beginner, depending on your content and features. Start small, focus on your framework, and get the basics fleshed out, ideally within the first couple months.

 

Roughly 10 hours a week over two semesters. And we are keeping the scope of the project down by making most of the game simulated. Rather than performing actions yourself you command people to perform actions and they move along the grid and do them when they get to the destination. It is a short survival game where the emphasis is on management rather than combat. Thanks for the tips

I have become very familiar with Dictionaries recently actually So are you suggesting the first int would be the X and second be the Y (or Z in this case)? And luckily for me thanks to having an isometric view I can just detect when the camera's focal point leaves a Tile and load the tiles in that direction.

 

Yep, exactly.

A great optimization on my algorithm! I suspect you won't have much trouble implementing this.

 

So question, in stead of using a nested Dictionary, why not just use Dictionary<Vector2, Tile>?

 

Three reasons. For one, anything based on specific values should not rely on anything float-based, which Vector2 is. floats are a bit imprecise, and if your algorithm relies on the difference between 2f and 2.00000001f, float is probably not the right choice.
Two, longs in particular have a MUCH bigger range (the floating point range can be bigger, but is inversely dependent on its precision, and we need no less than 1 unit, at which long is bigger. Floats effectively have 23 bits of precision/range compared to int's 31 bits (one is for the sign) and long's 63 bits.
Three, math (including comparisons and lookup, like the Dictionary) is faster with a long than a float.

HOWEVER, if you want to whip up a quick "Long2" class to use as your dictionary key that would undoubtedly simplify your code. I'm not certain what's involved in writing a class to be used as a key, but I think you may want to override GetHashCode for it. Here is a little discussion about doing that.

 

Ok, let's see how I am doing so far! I have a few different components here...

I have the GameManager, which is currently just holding the seed and tile types.

The MapGenerator, which is able to get a tile type when you feed it the location, seed, and tile type database.

The CameraController, which does exactly what you think.

And the MapRenderer, which creates a 50x50 grid of sprites and rotates them so they are flat. It contains a function that sets the entire grid's position to a rounded number and then uses the MapGenerator to generate every tile and set the sprites of the grid as needed.

So I took a slightly different approach. Whenever I need to check up on a tile it is generated on the spot by MapGenerator. Since it is a grid all I really need visually are sprites, so I won't need to actually create or destroy any sort of functional object, this 50x50 grid of sprites just follows the camera and has their values set.

 

Sounds good to me.

I just want to point out one other thing. Asking "what data structure should I use to store this data" is generally focusing on the wrong question. The right first question to ask, always, is "how can I hide what data structure I'm using from the rest of the code?"

To do that, you make some object whose job it is to provide access to this contents. Sounds like maybe this is MapGenerator. The rest of the code only knows about MapGenerator; it knows nothing of how MapGenerator is doing its magic. Under the hood, it could be using a 2D array, or nested Dictionaries, or looking things up in a database, or accessing some server over the network, or just flipping a coin. Only the MapGenerator code knows for sure.

To enforce that, be sure the actual data structures inside MapGenerator are private, not public. Provide methods with whatever convenient (probably row/column or X/Y) methods you want to get and set the data.

Doing this hiding of implementation details is much, much more important than the implementation details themselves. Why? Because you will probably change your mind about the implementation, perhaps several times. And if you've hidden those details, you can easily change them with impunity. If you haven't hidden them, but instead have references to Dictionary<int, Dictionary<int>>s all over the place, then attempting to change the implementation will lead to wailing and gnashing of teeth.

 

The nested dictionaries approach could get messy. I'd strongly suggest writing a custom indexer and hiding the implementation.

Beaten to the punch by @JoeStrout.

 

I have actually bypassed the need for a Dictionary all together. MapGenerator has a function called "GetTile(Vector3)" which generates a tile at that position. However, it doesn't do so at that exact position, but rather only in whole numbers (as my tile size is 1x1). Afterwords it is discarded. Of course if I need to keep that data for a bit I could always store it in a variable.