I ran into a similar problem and decided to create my own structure to handle the data. It's based loosely on a quadtree, but has infinite (at least as big as an Int) expandability in all directions. It was designed to handle grid-based data which expanded from a central point, much like Minecraft does now. It is space efficient in memory, and very fast.

You can specify a minimum magnitude for each node (a magnitude of 7 would be 128x128) and once any node has a specified percentage of its subnodes populated, it automatically flattens itself into a two-dimensional array. This means that a very densely populated portion (e.g., a completely explored continent) will have the performance of an array (very fast) but a sparsely populated portion (e.g., a shoreline someone wandered up and down but didn't explore inland) will have good performance and a low memory usage.

My code can be found here. The code is complete, tested (unit- and load-tests), and quite optimized. The inner workings aren't too well documented yet, however, but all the public methods are so it should be usable. If anyone decides to try it out, feel free to contact me with questions or comments.

I've not yet used it to store data to a file, but it's an interesting problem and I may tackle that next.

I ran into a similar problem and decided to create my own structure to handle the data. It's based loosely on a quadtree, but has infinite (at least as big as an Int) expandability in all directions. It was designed to handle grid-based data which expanded from a central point, much like Minecraft does now. It is space efficient in memory, and very fast.

You can specify a minimum magnitude for each node (a magnitude of 7 would be 128x128) and once any node has a specified percentage of its subnodes populated, it automatically flattens itself into a two-dimensional array. This means that a very densely populated portion (e.g., a completely explored continent) will have the performance of an array (very fast) but a sparsely populated portion (e.g., a shoreline someone wandered up and down but didn't explore inland) will have good performance and a low memory usage.

My code can be found here. The code is complete, tested (unit- and load-tests), and quite optimized. The inner workings aren't too well documented yet, however, but all the public methods are so it should be usable. If anyone decides to try it out, feel free to contact me with questions or comments.

I've not yet used it to store data to a file, but it's an interesting problem and I may tackle that next.