How to optimize my custom mapformat (Java)

Question

I'm creating a 3D game where I have a large open world (200×200 kilometers), that uses a heightmap. I divide the heightmap in 200×200 = 40,000 regions of 1000×1000 meter, and those are again divided in 20×20 = 400 chunks of 50×50 meter. The heightmap is generated from a PNG file.

I am thinking about ways of storing the terrain. I have tried something, but it generates files of about 16MB per region, which is 640GB for the whole world (40,000 regions).

An example of a region-file can be found here: http://updo.nl/file/e10ce974.umap

My question: how can I compactly store so much information in region files and read them later?

Answer 1

Heightmaps are an efficient method of storing information if the values are typically different at each coordinate and the way the way are different is not predictable. In other words, heightmaps are efficient when you are working with random data. If there is a pattern to your data, there is usually a better solution.

Consider the line described by y = x. You can describe this slope with a heightmap of resolution 1, which would be something like [(1, 1), (2, 2), (3, 3), ...]. If you heightmap has high resolution, that list will be very large. Alternatively, you could describe that slope as the line that goes through the points (1, 1) and (2, 2). Defining a line/volume via particular points/vertices is much more efficient, in this case.

For terrain-like data, since it typically non-random, I would recommend the second approach via polygonal meshes. You might find a library like JMesh of use.

For further reading, here is a great answer (way better than mine, frankly) on the Game Development Stack Exchange related to this topic.

Answer 2

How about some 2D FFT?

http://fourier.eng.hmc.edu/e101/lectures/image_processing/node6.html

http://paulbourke.net/miscellaneous/dft/