How should I store a large number of rooms with objects in them?

Right now I'm using C# in XNA/MonoGame. I'm brainstorming an isometric game that consists of rectangular rooms. The allowed dimensions of each room range from 3x3x3 to 12x12x6.

The max volume of each level is 432x432x216. That volume can hold a max of 1,492,992 rooms! That's practically 1.5 million! So it's important to consider how rooms are stored. My default idea is to use 2D arrays to hold a list of objects on the floor, wall, and ceiling (yes, I want to use magic spells for wall walk and even ceiling walk to get secrets on the walls/ceilings).

So, again, a 3x3x3 room would have 6 2D arrays that are each 3x3 arrays. Each array element is a list holding items. So each room would hold 54 lists. So now 1.5 million rooms would hold 81 million lists!!! I don't know what the max or average number of elements in each list will be, but I'm guessing up to a max of 6.

If we assume each Object in the list will be only 1 kilobyte in size (that's a low estimate), we're talking 81 gigabytes of memory. This does not even count the overhead of 2D arrays and lists.

Obviously, this cannot be stored in memory. So I need some other scheme. Is there some officially recommended scheme for this sort of thing?

One more caveat. The player character will not be the only guy walking around. There will be monsters too. They need to run around in other rooms.

Here is my explanation for the 1KB object data size.

1KB is my estimate based on past experience. Off the top of my head, here's what each object needs:

• enum byte for the type (block, food, key, etc.)
• byte for subtype (like different colored keys or different colored tiles)
• 2 bools for pushable, pullable
• byte for points (treasure might give 50 or 100 points, food might fill 10 or 20 health points)
• byte for height (some objects are flat, others have height 1, 2, 3, up to 6)
• 8 bools for 4 enterable dirs and 4 exit dirs (for force-field blocks)
• a List of target objects for switches (this is a 32-byte or 64-byte pointer depending on architecture, and each entry will also be 32 or 64 bytes).
• a pointer back to the room object (32 or 64 bytes again)

I count 14 bytes + the list and final pointer. This is probably only the beginning. I can compact some things, if I want, like compacting the 8 force field bools into a single bool (which is normally 8 bits, but I could use a byte and do integer comparisons for which bit I'm looking at).

The real question is what will be the average size of each object, which I think is impossible to estimate right now. I'm sticking with my 1KB estimate; I think at the very least, it's a reasonable cap on the worst case scenario.

EDIT

Max volume is now reduced to 144x144x144. Assuming all rooms are 3x3x3, the max rooms is about 110,000, which would take over 30 hours just to traverse all rooms assuming 1 second is spent in each room. So 144x144x144 is plenty of volume. I will proly store levels as giant string or byte arrays since the data has to come from disk anyway (when loading a new level). A few rooms can be culled with more elaborate 2D and 3D arrays holding actually objects, which will drawing and interactions much easier.

• I don't understand why you're jumping immediately to a solution that involved 2D arrays. That seems overly complicated? – user1430 Sep 14 '16 at 5:05
• @JoshPetrie I don't see anything over complicated about 2D arrays. They are random access and you use the col/row coordinate of where its located to access it. When drawing isometric scenes, you have to start at the back and work your way to the front anyway. Iterating over a 2D array is the logical way to do it. – DrZ214 Sep 14 '16 at 5:10
• Sure, but you already have a 2D array in the form of the room's tiles themselves. Why also give a room six 2D arrays of 3x3 tile information? Why not just store the list of items associated with a tile with that tile itself? Assuming square tiles, that should work out to six arrays (four walls, floor, ceiling) per isometric tile. I don't see where your extra "2D arrays" of "3x3" are coming from? – user1430 Sep 14 '16 at 5:14
• @JoshPetrie six arrays (four walls, floor, ceiling) per isometric tile 6 arrays per tile in a 3x3 room would result in 9 arrays just for the floor. Idk where you got the array per tile idea. I said a list per square/tile and its already confusing enough without worrying if you mean array as in list or array as in the 2D arrays I was talking about. The floor has a surface area of 9 (3x3). The walls and ceiling have the same surface area. My idea is to use 2D arrays for each of them, so 6 arrays, and each element stores an object. The tile data would be in a block object, for example. – DrZ214 Sep 14 '16 at 5:36
• That makes a bit more sense put that way. The next thing that is concerning is your 1KB object size; is all of that 1KB really per-instance item data? What's in there? Is there any of that that you can pull out into shared, immutable "item type" data? – user1430 Sep 14 '16 at 5:48

If you store the items in a single array per room, where each item in the array looks like

struct ItemPlacement {
byte X, Y, Z;
byte Side;// Floor? Ceiling? Wall?
ItemInstance Item;
};


you'll drastically cut down the number of arrays you have to deal with (down to 1.5 million). You can probably actually pack the location and side information into fewer total bits, given that each room has a small fixed upper-bound in terms of volume. If you pack everything tightly you can fit it into two bytes for both the 'side' information and the XYZ position.

This makes it a little slower to find out what items are on a specific tile in the room. You should still be able to easily draw or enumerate all the items in a room, but finding out "what can I pick up on the tile I'm on now" is slightly slower. Given an expected item stack size of six, however, and some sorting of the item list, this algorithmically slower search shouldn't be too much slower in actual practice.

With 1.5 million rooms, though, you're almost certainly going to run into a situation where you just can't keep the whole level in memory. There's got to be more than just item data you're storing in your game, so no matter how much you squeeze it, the scope of your game might simply be large enough that you have to resort to a streaming solution.

This means you have to be able to tell which rooms the player is in, and which rooms they can get to soon. You can build a graph of the room connectivity based on doorways, decide on a reasonable distance beyond which you start streaming rooms out, and then serialize the entire state of the room to disk once the player moves more than, say, four rooms away from any given room. Once the player gets close by again, you bring the state of the room back online. That way you can cut your working set of rooms down from the millions to something like the hundreds, and that's much more reasonable from a memory footprint perspective.

If it's important to your game that certain things continue to happen while the player isn't in a room (for example, monsters need to keep moving or whatnot), you can serialize only the static state of the room. Hopefully monsters cannot pick up or move items around in rooms when the player is far away from them in your game, so that the static state of the room includes these 1.5 million lists of item placements.

While it's not directly related to the storage of data for rooms or items in rooms, I think you can save some memory by splitting your items into type and instance data. I still think your estimate of 1KB per item is extremely high; your breakdown doesn't come anywhere near that, and given the type of information in your breakdown if you do get near 1KB per item instance you're probably being wasteful with memory somewhere.

What I mean by splitting the item up is to do this:

class ItemType {
byte Type;    //(block, food, key, etc.)
byte SubType; //(like different colored keys or different colored tiles)
bool IsPushable;
bool IsPullable;
byte Points;
...et cetera...
};


These item type structures contain everything about an item that will not change for the lifetime of the item. If you have an item that is a "pile of bricks," and you have ten of these, there's no reason to duplicate that push/pull information and many of the other properties for all ten instances. Instead, make an item instance look like:

class Item {
ItemType Type; // Simply reference the item type.

...per instance data here, like a pointer to the room the item is in...
};


Then you store List<Item> (no need for List<object>) in your rooms. You can further compress this data by not storing references to the ItemType, but instead store an index into an array of all item types. Chances are this array will be small enough that a 16-bit index will be sufficient, saving a few more bytes. You can also bitpack various flags in both the item type and item instance structures. You don't need two bools for push/pull. You can store that information in a single byte, using the 0th bit for push and the 1st bit for pull. The remaining six bits in the byte can be allocated to other boolean flags or similar values requiring few bits of storage.

These are all really small footprint reductions but when you multiply them out across the sheer volume of item instances you seem to expect to have they can start saving you megabytes of memory.

• The byte X, Y, Z; byte Side;// Floor? Ceiling? Wall? idea can work except for drawing order. Isometric drawing has to start at the back and word to the front. It is logical to use coordinates mapped directly to the 2 indexes of the 2D array. (P.S., i prefer char side; // FNSEWC where F is floor, NSEW is a north/south/east/west wall, and C is ceiling.) Let me make another comment on the rest of your post, tho, cuz I agree with the rest. – DrZ214 Sep 14 '16 at 6:21
• the scope of your game might simply be large enough that you have to resort to a streaming solution. Yes, I'm interested in reading more about a streaming solution. However, the goal right now is to figure out a way to store an entire level in a reasonable space. 81 million lists was just the illustration that I can't do it straightforwardly. I don't wanna store 81 GB on the disk either because that would have absurd overhead. Whether in RAM or streaming from disk, the immediate goal is to find a scheme to reduce the data size of the entire level. – DrZ214 Sep 14 '16 at 6:24
• This means you have to be able to tell which rooms the player is in, and which rooms they can get to soon. No problem. Doors have pointers pointing to the Room Object it connects to. Same thing with stairs, elevators, holes in the floor, warps, and any other way to move vertically between rooms. Hopefully monsters cannot pick up or move items around in rooms I wasn't planning on it, but I do want Boss Monsters that will be much smarter than normal monsters. Maybe bosses will be able to set up traps. Even so, I think they'll only be manipulating things if they're in the same room as you. – DrZ214 Sep 14 '16 at 6:28
• @DrZ214 Note that char in C# is larger than a byte (it's two bytes), which is wasteful since you only need three bits to store which side an item is on. – user1430 Sep 14 '16 at 15:23
• I'm using UTF-8 encoding for chars and strings. I could've sworn I read that its normally 1 byte per char until going above the normal ASCII range. UTF-8 is variable width chars.but done transparently. I like your idea of an ItemType though. Never thought to make type its own class instead of an enum. – DrZ214 Sep 14 '16 at 23:22

Have you considered external files, like xml or json? You could read and write to them, keeping them from taking up memory.

It's not realistic to keep so many rooms in memory at once en toto or to have the monsters traverse every single room and pathfind through every single object within 1.5 million rooms. It's just not reality.

You could probably store the rooms as a node structure for pathfinding purposes and have monsters just wander room to room between points a reasonable distance away over time and then only when they are very close to the user load up the actual room itself and keep track of the absolute position of the monster. 1.5 million NODES is not that hard to deal with and then the internal layout of your rooms does not really matter much from a memory conservation standpoint because you will only ever have a reasonable amount of rooms loaded into memory.