0
\$\begingroup\$

I'm making a game similar to Dwarf Fortress and I've run into a large problem from the start. How can you store such a large amount of land on disk. With every voxel holding an integer with the 28 MSB representing its type and the 8 LSB having flags like transparency or if it can be walked through a world similar to dwarf fortress would take up almost 18 000 GB. chunks(16 X 16 X 256 voxels) regions(64 X 64 chunks) and world(128 X 128 regions).

I know about Run Length Encoding which could save a lot of memory but its unpredictable because I don't know how many different block types there will be. However it will definitely use less memory so I will use it. I also thought that if I use Perlin Noise for everything I could regenerate everything from scratch if the player came close and only store the areas the player changed (and maybe towns because regenerating them could be time consuming) so I could definitely save a lot of memory there.

I read that Dwarf Fortress doesn't use Perlin Noise or anything like that, and it seems that it generates the whole map at once and saves it with data like erosion from rivers. Can anyone suggest another method that I could use to store a map as much expansive as the one in dwarf fortress?

Ok so it thought of a way to store rivers erosion, as a heightmap of subtractions to the terrain height and only store the heightmap of chunks that have rivers and also use run length encoding, then generate everything else that the player didn't change each time.

\$\endgroup\$
  • \$\begingroup\$ You need to save only the changes that occur. For instance one of dwarf has created channels in ground. Or you have built a fortress above ground (here you have changed air block to walls) \$\endgroup\$ – user3042253 Dec 22 '16 at 3:28
  • \$\begingroup\$ So you already know of two methods: RLE and delta encoding. What's wrong with those? \$\endgroup\$ – congusbongus Dec 22 '16 at 3:33
  • \$\begingroup\$ These methods seem fine except dwarf fortress calculates erosion from simulating the flow of rivers and I don't see how that could be done except by loading up that large portion of the map again and simulating the erosion each time the player comes close \$\endgroup\$ – Ben Beazley Dec 22 '16 at 12:03
  • \$\begingroup\$ You've pretty much covered the bases, apart from sparse voxel octrees. It's mostly going to be a matter of trying your options and seeing what gets you the best compression ratios for your game content (mixed with what makes good use of your development effort - it's probably not worth doubling your code complexity for an extra 1% data compression for example, given how cheap disc space is these days) \$\endgroup\$ – DMGregory Jan 2 '17 at 17:42
  • \$\begingroup\$ Dwarf Fortress does it by not actually generating the entire world. Sure, it remembers there's a lake here and a river here and a city here. But it doesn't store the actual tiles except for where you've built a fortress. In all other cases it generates it on the fly. \$\endgroup\$ – user253751 Jan 5 '17 at 8:53
0
\$\begingroup\$

I store the voxel values(-1 to 1 range) in a volume texture 512 x 512 x 48 and just convert the 16bit floats to a byte like this value*255 and then write that out to disk and then when I come to reading it back in to be polygonised I just do value/255.

While it may not be the exact value that I had to start with its very close and because I want random terrain it works well plus it only gets rounded up by a little bit. I use Marching cubes to polygonise the volume texture.

That comes in at 25-50mb depending on how full the volume texture is.

Maybe you could store a few volume textures at different resolutions for you regions and world.

I don't really start with an array because I generate my noise on the GPU(Volume Texture). Once I have my volume texture I convert that into one big flat array like this:

    Public Sub ProcessVolumeData(_device As DirectXDevice, ByRef _Context As DrawContext)
    Dim textureCopy As Texture3D
    Dim texDesc As Texture3DDescription
    texDesc.Width = mWidth
    texDesc.Height = mHeight
    texDesc.Depth = mDepth
    texDesc.MipLevels = 0
    texDesc.Format = DXGI.Format.R16_Float
    texDesc.Usage = ResourceUsage.Staging
    texDesc.BindFlags = BindFlags.None
    texDesc.CpuAccessFlags = CpuAccessFlags.Read
    texDesc.OptionFlags = ResourceOptionFlags.None
    textureCopy = New Texture3D(_device, texDesc)

    _Context.CopyResource(NoiseVolume, textureCopy)


    Dim dataBox As DataBox = _Context.MapSubresource(textureCopy, 0, MapMode.Read, Direct3D11.MapFlags.None)

        If mScalars IsNot Nothing Then
            mScalars = Nothing
        End If
        mScalars = New Single(mWidth * mHeight * mDepth - 1) {}
        Utilities.Read(Of Single)(dataBox.DataPointer, mScalars, 0, mScalars.Count)
        HaveVolumeData = True
        dataBox = Nothing
        textureCopy.Dispose()
        textureCopy = Nothing

End Sub 

I don't ever write to the volume texture from the CPU so I cant help you with away to convert your array into a volume texture but it should just be a matter of writing the values in a flat array to a volume texture with the correct stride(just guessing).

I store my noise values in the -1 to 1 range as a float16 on the GPU and then when I want to write it to disk I do this:

        Dim fs As New FileStream(DirectXDevice.ContentPath & "\VolumeData.vdf", FileMode.Create)
        Dim swriter As New BinaryWriter(fs)

        Dim i As Integer = 0
        While i < mScalars.Length
            Dim sc As SByte = CType(mScalars(i) * (255), SByte)
            swriter.Write(sc)
            System.Math.Max(System.Threading.Interlocked.Increment(i), i - 1)
        End While

Now for marching cubes you should really start a new question because its a complex yet fun topic in it self... but ill give you a little bit just to get you started.

I use a very modified version of Paul Bourke's marching cube algorithm well its kind based off of it but I think its a good place to start.

Basically with marching cubes you use array of scalar values as a density field and convert it into a polygon mesh

I run marching cubes and build a 3 dimensional array(512x512x48) of voxels like this using pos.x(512), pos.z(512), pos.y(48) where +Y is up.

  Parallel.[For](0, CInt(size.X), po, Sub(xxx)
                                            Dim y As Integer = 0
                                            While y < size.Y
                                                Dim z As Integer = 0
                                                While z < size.Z
                                                    Dim position As New Vector3(xxx, y, z)
                                                    _grids(xxx, y, z) = New Voxel
                                                    _grids(xxx, y, z).Position = position

                                                    Dim weight As Single
                                                    weight = CSng(WorldVolume.sampleVolume(_grids(xxx, y, z).Position.X, _grids(xxx, y, z).Position.Y, _grids(xxx, y, z).Position.Z))
                                                    _grids(xxx, y, z).Weight = Clamp(weight, -1, 1)

                                                    z += 1
                                                End While
                                                y += 1
                                            End While
                                        End Sub)


 Private Function fSample1(X As Single, Y As Single, Z As Single) As Single
    Return CSng(mScalars(X + (Z * mWidth) + (Y * mWidth * mHeight)))
End Function

Public Function sampleVolume(x As Integer, y As Integer, z As Integer) As Half

    Dim w As Integer = mWidth - 1
    Dim h As Integer = mDepth - 1
    Dim d As Integer = mHeight - 1

    x = If(x < 0, x Mod w + w, x Mod w)
    y = If(y < 0, y Mod h + h, y Mod h)
    z = If(z < 0, z Mod d + d, z Mod d)

    Dim ix As Integer = CType(x, Integer)
    Dim iy As Integer = CType(y, Integer)
    Dim iz As Integer = CType(z, Integer)

    Dim dx As Double = x - ix
    Dim dy As Double = y - iy
    Dim dz As Double = z - iz

    Dim ixi As Integer = ix + 1
    Dim iyi As Integer = iy + 1
    Dim izi As Integer = iz + 1

    ixi = If(ixi = mWidth, 0, ixi)
    iyi = If(iyi = mDepth, 0, iyi)
    izi = If(izi = mHeight, 0, izi)

    Dim c1 As Double = fSample1(ix, iy, iz)
    Dim c2 As Double = fSample1(ix, iy, izi)
    Dim c3 As Double = fSample1(ixi, iy, izi)
    Dim c4 As Double = fSample1(ixi, iy, iz)
    Dim c5 As Double = fSample1(ix, iyi, iz)
    Dim c6 As Double = fSample1(ix, iyi, izi)
    Dim c7 As Double = fSample1(ixi, iyi, izi)
    Dim c8 As Double = fSample1(ixi, iyi, iz)

    Dim c14 As Double = c4 * dx + c1 * (1 - dx)
    Dim c23 As Double = c3 * dx + c2 * (1 - dx)
    Dim c58 As Double = c8 * dx + c5 * (1 - dx)
    Dim c67 As Double = c7 * dx + c6 * (1 - dx)

    Dim c1423 As Double = c23 * dz + c14 * (1 - dz)
    Dim c5867 As Double = c67 * dz + c58 * (1 - dz)

    Dim result As Double = c5867 * dy + c1423 * (1 - dy)

    Return result  
End Function

Only showing a very very small part of the marching cubes stuff.

Ps. marching cubes is not the best but I'm sure you will find that out after doing some reading.... still works well for me but there is better.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ How large of a world takes up the 25-50mb, is that one area of 512X512X48? \$\endgroup\$ – Ben Beazley Dec 22 '16 at 12:01
  • \$\begingroup\$ I like the sound of this idea, how would I take a 3 dimensional array of ints and put them in this format. also what is marching cubes? \$\endgroup\$ – Ben Beazley Dec 22 '16 at 13:05
  • \$\begingroup\$ well the world size really depends on how you scale every thing. For my needs its big enough and if I really want then I could just add more nodes to my Octree. I only have one very large region that I split into cells for rendering and culling. Ill update my answer with info about the array stuff. \$\endgroup\$ – Justin William Stanley Bryant Dec 22 '16 at 14:30
  • \$\begingroup\$ @Ben marching cubes makes smooth meshes out of voxels, it's irrelevant for you now \$\endgroup\$ – Bálint Jan 3 '17 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.