voxels.cs

using NG.Coroutines;
using NG.Math;
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace NG.VoxelMap {
    public static class Const {
        public const int CHUNK_SIZE_I = 32;
        public static readonly Vec3i CHUNK_SIZE = new Vec3i(CHUNK_SIZE_I);
        public static readonly Vec3i STORAGE_CHUNK_SIZE = new Vec3i(8, 8, 16);
        public static readonly Vec3i SEGMENT_SIZE = new Vec3i(4, 4, 16);
    }

    public static class Location {
        public static Vec2i StorageChunkToChunkColumn(Vec2i loc) {
            return loc * Const.STORAGE_CHUNK_SIZE.XY;
        }
        public static Vec2i ChunkColumnToStorageChunk(Vec2i loc) {
            return Vec2i.FloorDiv(loc, Const.STORAGE_CHUNK_SIZE.XY);
        }
        public static Vec3i SegmentToChunk(Vec2i loc) {
            var v = loc * Const.SEGMENT_SIZE.XY;
            return new Vec3i(v.X, v.Y, 0);
        }
        public static Vec2i ChunkToSegment(Vec3i loc) {
            return Vec2i.FloorDiv(loc.XY, Const.SEGMENT_SIZE.XY);
        }
    }

    public struct ChunkColumnInfo {
        public int Readers;
        public bool HasWriter => Readers == -1;
        public bool HasReaders => Readers > 0;
    }

    public enum RequestType {
        Read,
        Write
    }

    public enum Operation {
        Grab,
        Release,
    }

    public class Request {
        public RequestType Type;
        public Vec2i Location;
        public Vec2i Size;
        public C.MapChunkColumn[,] Data;
    }

    public class DeferredRequest {
        public Request Request;
        public Coroutine Coroutine;
    }

    public class StorageChunk : IDisposable {
        string filename;
        Vec2i location;
        C.MapStorageChunk storageChunk = C.MapStorageChunk.New();
        internal ChunkColumnInfo[,] columnInfos =
            MathUtils.New2D<ChunkColumnInfo>(Const.STORAGE_CHUNK_SIZE.XY);

        internal StorageChunk(Vec2i loc) {
            location = loc;
            filename = $"{loc.X:X8}_{loc.Y:X8}.ngc";
        }

        internal IEnumerator<Co> Save(string dir) {
            storageChunk.Serialize();
            yield return Co.WaitFor(
                () => { storageChunk.SaveData(Path.Combine(dir, filename)); },
                Co.NormalIO);
        }

        internal IEnumerator<Co> Load(string dir, Action<bool> result) {
            bool loaded = false;
            yield return Co.WaitFor(
                () => { loaded = storageChunk.LoadData(Path.Combine(dir, filename)); },
                Co.NormalIO);
            if (loaded)
                storageChunk.Deserialize();
            result(loaded);
        }

        internal IEnumerator<Co> generateCol(Vec2i baseLoc, Vec2i loc) {
            C.MapGenerator.GenerateColumn(storageChunk.Column(loc), baseLoc + loc);
            yield break;
        }

        internal IEnumerator<Co> Generate() {
            var baseLoc = Location.StorageChunkToChunkColumn(location);
            yield return Co.WaitFor(
                MathUtils.Range2D(Const.STORAGE_CHUNK_SIZE.XY).
                Select(p => generateCol(baseLoc, p))
            );
        }

        internal C.MapChunkColumn Column(Vec2i p) => storageChunk.Column(p);

        public void Dispose() {
            storageChunk.Dispose();
        }
    }

    public class Storage {
        string dir;
        Dictionary<Vec2i, StorageChunk> storageChunks = new Dictionary<Vec2i, StorageChunk>();
        List<DeferredRequest> deferredRequests = new List<DeferredRequest>();
        Mutex mutex = new Mutex();

        void AddSelfToDeferredRequests(Request r) {
            deferredRequests.Add(new DeferredRequest{
                Request = r,
                Coroutine = Scheduler.CurrentCoroutine,
            });
        }

        void ApplyOperation(Request r, Operation op) {
            Func<ChunkColumnInfo, ChunkColumnInfo> mutator = null;
            if (op == Operation.Grab) {
                if (r.Type == RequestType.Read)
                    mutator = info => new ChunkColumnInfo{ Readers = info.Readers+1 };
                else
                    mutator = info => new ChunkColumnInfo{ Readers = -1 };
            } else {
                if (r.Type == RequestType.Read)
                    mutator = info => new ChunkColumnInfo{ Readers = info.Readers-1 };
                else
                    mutator = info => new ChunkColumnInfo{ Readers = 0 };
            }

            foreach (var p in MathUtils.RangeBase2D(r.Location, r.Size)) {
                // storage chunk location for given chunk column
                var scloc = Location.ChunkColumnToStorageChunk(p);
                // location of the chunk column inside the given storage chunk
                var scp = p - Location.StorageChunkToChunkColumn(scloc);
                var sc = storageChunks[scloc];
                sc.columnInfos[scp.Y, scp.X] = mutator(sc.columnInfos[scp.Y, scp.X]);
            }
        }

        bool TrySatisfyRequest(Request r) {
            bool result = true;
            foreach (var p in MathUtils.RangeBase2D(r.Location, r.Size)) {
                // storage chunk location for given chunk column
                var scloc = Location.ChunkColumnToStorageChunk(p);
                // location of the chunk column inside the given storage chunk
                var scp = p - Location.StorageChunkToChunkColumn(scloc);
                // chunk column location relative to request data array
                var rp = p - r.Location;

                StorageChunk sc;
                if (storageChunks.TryGetValue(scloc, out sc)) {
                    if (sc != null) {
                        var info = sc.columnInfos[scp.Y, scp.X];
                        switch (r.Type) {
                        case RequestType.Read:
                            if (info.HasWriter) {
                                result = false;
                            }
                            break;
                        case RequestType.Write:
                            if (info.HasReaders) {
                                result = false;
                            }
                            break;
                        }
                        r.Data[rp.Y, rp.X] = sc.Column(scp);
                    } else {
                        // still loading
                        result = false;
                    }
                } else {
                    // not here, let's load it
                    result = false;
                    storageChunks[scloc] = null;
                    Co.Go(LoadOrGenerateStorageChunk(scloc));
                }
            }
            if (result) {
                ApplyOperation(r, Operation.Grab);
            }
            return result;
        }

        bool TrySatisfyDeferredRequest(DeferredRequest dr) {
            if (TrySatisfyRequest(dr.Request)) {
                Co.Go(dr.Coroutine);
                return true;
            } else {
                return false;
            }
        }

        void TrySatisfyDeferredRequests() {
            deferredRequests.RemoveAll(dr => TrySatisfyDeferredRequest(dr));
        }

        IEnumerator<Co> LoadOrGenerateStorageChunk(Vec2i loc) {
            var sc = new StorageChunk(loc);
            bool loaded = false;
            yield return Co.Do(sc.Load(dir, r => loaded = r));
            if (!loaded) {
                yield return Co.Do(sc.Generate());
            }

            yield return Co.Lock(mutex);
            storageChunks[loc] = sc;
            TrySatisfyDeferredRequests();
        }

        public IEnumerator<Co> AcquireChunkColumns(RequestType rt, Vec2i loc, Vec2i size, Action<Request> result) {
            yield return Co.Lock(mutex);
            var req = new Request{
                Type = rt,
                Location = loc,
                Size = size,
                Data = MathUtils.New2D<C.MapChunkColumn>(size),
            };
            if (!TrySatisfyRequest(req)) {
                // If request cannot be satisfied immediately, we queue
                // ourselves and sleep. Eventually somebody will wake us up.
                AddSelfToDeferredRequests(req);
                yield return Co.Sleep();
            }
            result(req);
        }

        public IEnumerator<Co> ReleaseChunkColumns(Request r) {
            yield return Co.Lock(mutex);
            ApplyOperation(r, Operation.Release);
            TrySatisfyDeferredRequests();
        }

        public Storage(string d) {
            dir = d;
        }
    }

    public class ChunkMesh : IDisposable {
        int refCount = 1;
        C.MapChunkMesh chunkMesh = C.MapChunkMesh.New();

        internal int RefCount => refCount;
        internal C.MapChunkMesh CChunkMesh => chunkMesh;
        internal int VerticesCount => chunkMesh.VerticesCount();
        internal int VerticesOffset = 0;

        public void Dispose() {
            if (--refCount == 0)
                chunkMesh.Dispose();
        }

        internal void Mesh(C.MapChunkColumn[,] columns, int z) {
            using (var a = C.MapChunkColumnArray.New(4)) {
                a.SetNth(0, columns[0, 0]);
                a.SetNth(1, columns[0, 1]);
                a.SetNth(2, columns[1, 0]);
                a.SetNth(3, columns[1, 1]);
                chunkMesh.Mesh(a, z);
            }
        }

        internal ChunkMesh Grab() {
            refCount++;
            return this;
        }
    }

    public class Segment : IDisposable {
        Storage storage;
        Vec2i location;
        C.MapSegment segment;
        ChunkMesh[,,] current;
        ChunkMesh[,,] next;

        public C.MapSegment CSegment => segment;
        public Vec2i Location => location;

        public Segment(C.MapSegment s, Vec2i loc, Storage st) {
            segment = s;
            location = loc;
            storage = st;
            next = MathUtils.New3D<ChunkMesh>(Const.SEGMENT_SIZE);
            current = MathUtils.New3D<ChunkMesh>(Const.SEGMENT_SIZE);
        }

        void Swap() {
            var tmp = current;
            current = next;
            next = tmp;

            foreach (var cm in next) cm?.Dispose();
            MathUtils.Fill3D(next, null);
        }

        IEnumerator<Co> ChunkMeshUpload(ChunkMesh cm) {
            var msg = C.Messages.MapChunkMeshAppend.New();
            msg.Segment = segment;
            msg.ChunkMesh = cm.CChunkMesh;
            yield return Co.WaitFor(msg);
            cm.VerticesOffset = msg.OutVerticesOffset;
            msg.Dispose();
        }

        IEnumerator<Co> ChunkMeshBuildAndUpload(ChunkMesh cm, Vec3i ap) {
            Request req = null;
            yield return Co.WaitFor(storage.AcquireChunkColumns(
                RequestType.Read, ap.XY - new Vec2i(1), new Vec2i(2), r => req = r));
            cm.Mesh(req.Data, ap.Z);
            yield return Co.WaitFor(storage.ReleaseChunkColumns(req));
            if (cm.VerticesCount != 0) {
                var msg = C.Messages.MapChunkMeshAppend.New();
                msg.Segment = segment;
                msg.ChunkMesh = cm.CChunkMesh;
                yield return Co.WaitFor(msg);
                cm.VerticesOffset = msg.OutVerticesOffset;
                msg.Dispose();
            } else {
                cm.VerticesOffset = 0;
            }
        }

        internal IEnumerator<Co> RebuildSegment(Vec3i min, Vec3i max) {
            var baseLoc = VoxelMap.Location.SegmentToChunk(location);
            var buildAndUpload = MathUtils.Range3D(Const.SEGMENT_SIZE).
                Where(p => { p += baseLoc; return min <= p && p <= max; }).
                Select(p => {
                    var ap = baseLoc + p;
                    var cm = current.At(p);
                    if (cm != null) {
                        next.SetAt(p, cm.Grab());
                        return null;
                    } else {
                        cm = new ChunkMesh();
                        next.SetAt(p, cm);
                        return ChunkMeshBuildAndUpload(cm, ap);
                    }
                }).Where(it => it != null);

            var upload = MathUtils.Range3D(Const.SEGMENT_SIZE).
                Where(p => { var cm = next.At(p); return cm != null && cm.RefCount == 2; }).
                Select(p => ChunkMeshUpload(next.At(p)));

            yield return Co.WaitFor(upload);
            yield return Co.WaitFor(buildAndUpload);

            foreach (var p in MathUtils.Range3D(Const.SEGMENT_SIZE)) {
                var cm = next.At(p);
                if (cm != null && cm.VerticesCount != 0) {
                    segment.AppendInfo(p, cm.VerticesOffset, cm.VerticesCount);
                }
            }

            var msg = C.Messages.MapSegmentSwap.New();
            msg.Segment = segment;
            yield return Co.WaitFor(msg);
            msg.Dispose();

            Swap();
        }

        public void Dispose() {
            segment.Dispose();
        }
    }

    public class Map {
        const int viewDistance = 400;
        C.Map map = C.Map.New();
        Dictionary<Vec2i, Segment> segments = new Dictionary<Vec2i, Segment>();
        Storage storage;

        public C.Map CMap => map;

        public Map(Storage s) {
            storage = s;
        }

        IEnumerator<Co> CreateSegment(Vec2i loc, Action<Segment> result) {
            var msg = C.Messages.MapSegmentNew.New();
            msg.Location = loc;
            yield return Co.WaitFor(msg);
            var s = new Segment(msg.OutSegment, loc, storage);
            result(s);
        }

        public IEnumerator<Co> Rebuild(Vec3i ploc) {
            var sw = new Stopwatch();
            sw.Start();

            var viewChunks = viewDistance / Const.CHUNK_SIZE_I;
            var visRange = new Vec3i(viewChunks * 2, viewChunks * 2, Const.STORAGE_CHUNK_SIZE.Z);
            var halfVisRange = visRange / new Vec3i(2);
            var min = (ploc - halfVisRange) * new Vec3i(1, 1, 0);
            var max = min + visRange - new Vec3i(1);
            var sbase = Location.ChunkToSegment(min);
            var ssize = Location.ChunkToSegment(max - min + new Vec3i(1));
            var newSegments = new Segment[ssize.Area()];
            yield return Co.WaitFor(MathUtils.RangeBase2D(sbase, ssize).
                Select((p, i) => {
                    Segment seg;
                    return segments.TryGetValue(p, out seg) ? null :
                        CreateSegment(p, r => newSegments[i] = r);
                }).Where(it => it != null));

            foreach (var seg in newSegments) {
                segments.Add(seg.Location, seg);
            }

            yield return Co.WaitFor(MathUtils.RangeBase2D(sbase, ssize).
                Select(p => segments[p].RebuildSegment(min, max)));

            var v = map.Segments();
            foreach (var s in segments.Values)
                v.Add(s.CSegment);

            var msg = C.Messages.MapSwap.New();
            msg.Map = map;
            yield return Co.WaitFor(msg);
            msg.Dispose();

            sw.Stop();
            Console.WriteLine($"rebuild done in {sw.Elapsed}");
        }
    }
}