Efficiently storing sparsely populated 2D grid

Question

I have a huge map, and tiles on it. It's a dungeon, so there clearly is a lot of empty space, where I'd store nulls.

Obviously, having a huge 2D array is an option, but I think it's not the most elegant one. Also when I want to save it to file, it's not very neat to store tons of null marks.

Something like this, but A LOT bigger:

+--------------+
|   X     X    |
| XXX    XX    |
|   XXXXXXX    |
|    X   XX    |
|   XXX   XXX  |
|     X   X    |
+--------------+ 

What other alternatives to width×height array do I have?

Only something like Map<IntCoord, Tile>? Or is there some widely-used solution for similar scenario?

Answer 1

There are three things you could use:

1. 2D Array.
2. List.
3. Map.

2D Arrays are the best, unless your map is huge, in which case you could use Lists.

---

2D Array:

Pros: It has the fastest lookup times.

Cons: It (most likely) takes the most memory.

The lookup times probably heavily outweigh the memory costs. Unless your dungeon is hundreds of thousands of tiles large, this is probably the way to go.

---

List (probably ArrayList):

Pros: Only storing items you need.

Cons: Lookup times will be horrible.

While Lists will use less memory, it will take a lot longer to find a tile or item, as you'll have to iterate over the List to find something matching a location.

---

Map (probably HashMap):

Pros: Each location will be linked to an object per map, so lookup times will be ok.

Cons: Lookup times will not be optimal, will use moderate amounts of memory.

Maps are in between Lists and Arrays. The will use up more memory than arrays, but have better lookup times than Lists.

---

2D Arrays are the best because of the lookup time. On most modern computers, memory is not a concern. If it is, you can always cache areas not currently being used to files and dynamically load them as needed.

Answer 2

I won't comment much on how to store the data in memory at run-time, since Anubian's answer seems to have covered that well enough. I also agree with him that unless you have some severe memory restrictions and/or your dungeons are truly massive (like 10,000 x 10,000), then there's no real reason not to just store it as a 2D array. The coding effort you save and the run-time performance you gain, will almost certainly outweigh whatever space-efficiency advantage you might gain by using lists, maps, etc. And if you really do have insufficient RAM to store your dungeons, you could always segment them into blocks and load only the blocks you need at any given time (typically, whatever block the player is currently on, plus maybe a few adjacent blocks so that there's no noticeable load-time lag when the player moves from one block to the next). That's a bit more work than just one big array, but still probably easier than storing the data in some sparse data structure and then having to compute the contents of each cell every single time it gets accessed.

As for storing it to file, however, you might want to consider Run Length Encoding (RLE).

It's trivial to write the encode and decode functions for RLE, and you can arbitrarily decide on your own syntax and character set, etc.

The problem you're trying to solve (efficient encoding of a 2D grid) is actually very similar to the problem of storing states in Conway's Game of Life simulation programs, and one of the most common file formats they use is RLE: http://conwaylife.com/wiki/Run_Length_Encoded.

Your example dungeon is similar enough to a Game of Life object/state/whatever that you could even just use the same exact RLE encoding that they use, in which case you'd get something like this for your example dungeon:

# Optional comment lines
#   (perhaps a dungeon name and/or description?)
x = 14, y = 6
3bo5bo$b3o4b2o$3b7o$4bo3b2o$3b3o3b3o$5bo3bo!