WOrldBuilder.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using Unity.Mathematics;
using System.Runtime.CompilerServices;
using UnityEngine.Profiling;
using UnityEngine.Assertions;
using System.Threading;

namespace WFC
{
    [System.Serializable]
    public struct WorldBuilderConfig
    {
        public PuzzlePack puzzlePack;

        [Header("World Size")]
        public int worldSizeX;
        public int worldSizeY;
        public int worldSizeZ;
    }

    public class WorldBuilder : MonoBehaviour
    {
        public WorldBuilderConfig config;

        [System.NonSerialized] public WorldNode[] nodes = null;
        HashSet<WorldNode> updateList = new HashSet<WorldNode>();
        HashSet<WorldNode> validWorldNodes =  new HashSet<WorldNode>();

        [Header("Output")]
        public GameObject targetMeshOutput;

        [Header("Debug")]
        public bool FixRandomSeed = false;
        public int RandomSeed = 1;

        // output
        List<BakedNode> outputBakedNodes = new List<BakedNode>();

        // thread
        Coroutine _coroutineBuildingWFC = null;
        public bool IsBuildingWFC { get { return _coroutineBuildingWFC != null;  } }
        Thread _threadWFCBuild = null;
        EventWaitHandle _waitWFCBuild = new EventWaitHandle(true, EventResetMode.ManualReset);

        static readonly PieceDir[] neighborDir = new PieceDir[]
        {
            PieceDir.X_NEG,
            PieceDir.X_POS,
            PieceDir.Y_NEG,
            PieceDir.Y_POS,
            PieceDir.Z_NEG,
            PieceDir.Z_POS
        };

        static readonly int3[] neighborGridPosDelta = new int3[]
        {
            new int3(-1, 0, 0),
            new int3(1, 0, 0),
            new int3(0, -1, 0),
            new int3(0, 1, 0),
            new int3(0, 0, -1),
            new int3(0, 0, 1)
        };

        private void Start()
        {
            //BuildRoom();
        }

        private void Update()
        {
#if UNITY_EDITOR
            if (Input.GetKeyDown(KeyCode.F5))
            {
                config = SL.Services.roomService.CurrentSet.GetConfig();

                BuildRoom();
            }
#endif
        }

        [ContextMenu("Rebuild Room")]
        public void BuildRoom()
        {
            if (true) // THREADED (coroutine)
            {
                if (_coroutineBuildingWFC == null)
                    _coroutineBuildingWFC = StartCoroutine(DoRunWFC());
                else
                    Debug.LogError("Already running DoRunWFC()");
            }
            else if (false) // THREADED (halts)
            {
                /*
                WaitHandle[] waitHandles = new WaitHandle[]
                {
                    _waitWFCBuild
                };

                _waitWFCBuild.Reset();

                _threadWFCBuild = new Thread(RunWFC);
                _threadWFCBuild.Start();
                WaitHandle.WaitAll(waitHandles);

                float startTime = Time.realtimeSinceStartup;
                OnCompletedWFC();
                Debug.LogFormat("OnCompletedWFC ran in {0} secs", Time.realtimeSinceStartup - startTime);
            */
            }
            else
            {
                float startTime = Time.realtimeSinceStartup;
                RunWFC();
                Debug.LogFormat("Finished loading {0} pieces in {1} sec", config.worldSizeX * config.worldSizeY * config.worldSizeZ, Time.realtimeSinceStartup-startTime);

                startTime = Time.realtimeSinceStartup;
                OnCompletedWFC();
                Debug.LogFormat("OnCompletedWFC ran in {0} secs", Time.realtimeSinceStartup - startTime);
            }
        }

        IEnumerator DoRunWFC()
        {
            Debug.Log("DoRunWFC() Coroutine");

            _threadWFCBuild = new Thread(RunWFC);
            _threadWFCBuild.Start();

            while(_threadWFCBuild.IsAlive)
            {
                yield return null;
            }

            float startTime = Time.realtimeSinceStartup;
            OnCompletedWFC();
            Debug.LogFormat("OnCompletedWFC ran in {0} secs", Time.realtimeSinceStartup - startTime);

            _coroutineBuildingWFC = null;
        }

        void PlaceSeededTiles()
        {
            // for castle
            //ApplyBorder();

            // for house
            int pieceIndexEmpty = 0;
            int pieceIndexCornerFloor = 1;
            int pieceIndexCornerCeiling = 2;
            //int pieceIndexGrass = 5;

            // fill in center with EMPTY
            ApplyFloodCenter(pieceIndexEmpty, math.int3(2, 1, 2));

            // add edge corners (top)
            ApplyPieceAtPosition(pieceIndexCornerCeiling, math.int3(0, config.worldSizeY - 1, 0), PieceDir.Z_POS);
            ApplyPieceAtPosition(pieceIndexCornerCeiling, math.int3(config.worldSizeX - 1, config.worldSizeY - 1, 0), PieceDir.X_NEG);
            ApplyPieceAtPosition(pieceIndexCornerCeiling, math.int3(config.worldSizeX - 1, config.worldSizeY - 1, config.worldSizeZ - 1), PieceDir.Z_NEG);
            ApplyPieceAtPosition(pieceIndexCornerCeiling, math.int3(0, config.worldSizeY - 1, config.worldSizeZ - 1), PieceDir.X_POS);
            
            // add edge corners (bot)
            ApplyPieceAtPosition(pieceIndexCornerFloor, math.int3(0, 0, 0), PieceDir.Z_POS);
            ApplyPieceAtPosition(pieceIndexCornerFloor, math.int3(config.worldSizeX-1, 0, 0), PieceDir.X_NEG);
            ApplyPieceAtPosition(pieceIndexCornerFloor, math.int3(config.worldSizeX - 1, 0, config.worldSizeZ-1), PieceDir.Z_NEG);
            ApplyPieceAtPosition(pieceIndexCornerFloor, math.int3(0, 0, config.worldSizeZ - 1), PieceDir.X_POS);

            //ApplyLayer(pieceIndexCornerBottom, 0);

            /*
            //ApplyLayer(pieceIndexGrass, 0);

            ApplyEdgeBorder(pieceIndexGrass, 0);
            //ApplyLayer(pieceIndexGrass, 0);

            if (worldSizeY > 1)
            {
                ApplyLayer(pieceIndexEmpty, worldSizeY - 1);
                for (int i = 1; i < worldSizeY; ++i)
                    ApplyEdgeBorder(pieceIndexEmpty, i);
            }*/
        }

        private void RunWFC()
        {
            Profiler.BeginSample("WorldBuilder:RunWFC");
            Debug.LogFormat("RunWFC on world {0}x{1}x{2}", config.worldSizeX, config.worldSizeY, config.worldSizeZ);

            if (FixRandomSeed)
               SL.StaticRandom.seed = RandomSeed;

            outputBakedNodes.Clear();
            outputBakedNodes.Capacity = config.worldSizeX * config.worldSizeY * config.worldSizeZ;

            updateList.Clear();
            InitializeWorldNodes();
            PlaceSeededTiles();
            ProcessUpdateList();

            // while there are valid WorldNodes to ascertain
            // once each space has only one piece left, you're done!
            while (validWorldNodes.Count > 0)
            {
                // grab a worldnode at random (that is not already locked)
                // choose one random piece and throw away the rest
                var ienum = validWorldNodes.GetEnumerator(); // TODO: RANDOMIZE ACCESS (not in order)
                ienum.MoveNext();
                WorldNode currWorldNode = ienum.Current;
                currWorldNode.SelectSingleRandomPiece();
                BakeWorldNode(currWorldNode);

                // add its neighbors to the update list
                AddNeighborsToUpdateList(currWorldNode);
                ProcessUpdateList();
                //Debug.LogFormat("{0}/{1} Num pieces left", validWorldNodes.Count, worldSizeX* worldSizeY* worldSizeZ);
            }

            Profiler.EndSample();
            _waitWFCBuild.Set();
        }


        Transform _tfmBakedNodesParent = null;

        void OnCompletedWFC()
        {
            Debug.LogFormat("WFC Completed! Instantiating {0} WFC tiles", outputBakedNodes.Count);

            // destroy objects
            TypedObjectTracking<WFC.WFC_GameObject>.DestroyAll();

            _tfmBakedNodesParent = (new GameObject()).transform;

            float startTime = Time.realtimeSinceStartup;

            // instantiate all baked nodes
            for (int i = 0; i < outputBakedNodes.Count; ++i)
            {
                var outputBakedNode = outputBakedNodes[i];

                var go = GameObject.Instantiate(outputBakedNode.prefabPiece.gameObject, outputBakedNode.localPos, outputBakedNode.localRot);
                if (go != null)
                    go.transform.SetParent(_tfmBakedNodesParent, true);
            }

            // now it is baked, can clear list
            Debug.LogFormat("Instantiated {0} pieces in {1} sec", outputBakedNodes.Count, Time.realtimeSinceStartup - startTime);
            outputBakedNodes.Clear();

            // pull out all gameobjects before baking mesh
            var wfcGameObject = TypedObjectTracking<WFC.WFC_GameObject>.Instances;
            for (int i = 0; i < wfcGameObject.Count; ++i)
            {
                wfcGameObject[i].transform.SetParent(null, true);
            }

            startTime = Time.realtimeSinceStartup;
            CombineAllMeshes();
            Debug.LogFormat("CombineAllMeshes() in {0} sec", Time.realtimeSinceStartup - startTime);

            // destroy baked nodes gameobjects
            GameObject.Destroy(_tfmBakedNodesParent.gameObject);

            // wfc objects
            for (int i = 0; i < wfcGameObject.Count; ++i)
            {
                var tfmWfcGameObj = wfcGameObject[i].transform;
                tfmWfcGameObj.transform.position = targetMeshOutput.transform.TransformVector(tfmWfcGameObj.localPosition);
                tfmWfcGameObj.transform.localScale = targetMeshOutput.transform.TransformVector(tfmWfcGameObj.localScale);
            }
        }

        void CombineAllMeshes()
        {
            const int subMeshIndex = 0;

            var meshFilters = _tfmBakedNodesParent.gameObject.GetComponentsInChildren<MeshFilter>(false);

            List<CombineInstance> combinedInstanced = new List<CombineInstance>();
            combinedInstanced.Capacity = meshFilters.Length;

            List<Vector3> vertices = new List<Vector3>();
            List<Vector3> normals = new List<Vector3>();
            List<int> indices = new List<int>();

            int vertWriteIndex = 0;

            for (int i = 0; i < meshFilters.Length; ++i)
            {
                var meshFilter = meshFilters[i];

                if (meshFilter.gameObject.activeInHierarchy)
                {
                    Mesh mesh = meshFilter.sharedMesh;
                    Matrix4x4 localToWorldMatrix = meshFilter.transform.localToWorldMatrix;

                    /*CombineInstance combine = new CombineInstance();
                    combine.mesh = mesh;
                    combine.transform = localToWorldMatrix;
                    combine.subMeshIndex = subMeshIndex;
                    combinedInstanced.Add(combine);*/

                    // positions
                    var meshVertices = mesh.vertices;
                    for(int iVert = 0; iVert < meshVertices.Length; ++iVert)
                    {
                        Vector3 vertPos = localToWorldMatrix.MultiplyPoint3x4(meshVertices[iVert]);
                        vertices.Add(vertPos);
                    }
                    
                    // normals
                    var meshNormals = mesh.normals;
                    for (int iVert = 0; iVert < meshNormals.Length; ++iVert)
                    {
                        normals.Add(localToWorldMatrix.MultiplyVector(meshNormals[iVert]));
                    }

                    // indices
                    var meshIndices = mesh.triangles;
                    for (int iVert = 0; iVert < meshIndices.Length; ++iVert)
                    {
                        Debug.Assert(meshIndices[iVert] >= 0 && meshIndices[iVert] < mesh.GetIndexCount(subMeshIndex));
                        int index = vertWriteIndex + meshIndices[iVert];
                        indices.Add(index);
                    }

                    vertWriteIndex += meshVertices.Length;
                }
                else
                {
                    meshFilters[i] = null;
                }
            }

            /*
            float startTime = Time.realtimeSinceStartup;
            var resultMesh = new Mesh();
            resultMesh.Clear();
            resultMesh.CombineMeshes(combinedInstanced.ToArray(), mergeSubMeshes:true, useMatrices:true);
            resultMesh.UploadMeshData(markNoLongerReadable: false);
            Debug.LogFormat("Mesh.CombineMeshes() in {0} sec", Time.realtimeSinceStartup - startTime);
            Assert.IsTrue(resultMesh.isReadable);*/

            var resultMesh = new Mesh();
            resultMesh.vertices = vertices.ToArray();
            resultMesh.normals = normals.ToArray();
            resultMesh.triangles = indices.ToArray();
            //resultMesh.SetIndices(indices.ToArray(), MeshTopology.Triangles, subMeshIndex);
            resultMesh.UploadMeshData(markNoLongerReadable: false);

            Debug.Log("YOOOO NUM VERTICES: " + vertices.Count);

            targetMeshOutput.GetComponent<MeshFilter>().sharedMesh = resultMesh;
            targetMeshOutput.GetComponent<MeshCollider>().sharedMesh = resultMesh;
        }

        void ProcessUpdateList()
        {
            Profiler.BeginSample("WorldBuilder:ProcessUpdateList()");

            // for each space in list, remove pieces that no longer match their neighbors
            // if any of its neighbors gets updated, add THOSE neighbors to the update list
            while (updateList.Count > 0)
            {
                var targetWorldNode = PopFromUpdateList();
                UpdateWorldNode(targetWorldNode);
            }

            Profiler.EndSample();
        }

        void ApplyFloodCenter(int pieceIndex, int3 padding)
        {
            for (int x = padding.x; x < config.worldSizeX - padding.x; ++x)
            {
                for (int y = padding.y; y < config.worldSizeY - padding.y; ++y)
                {
                    for (int z = padding.z; z < config.worldSizeZ - padding.z; ++z)
                    {
                        ApplyPieceAtPosition(pieceIndex, math.int3(x, y, z));
                    }
                }
            }
        }

        void ApplyPieceAtPosition(int pieceIndex, int3 gridPos, PieceDir forceDir = PieceDir.NULL)
        {
            var node = GetWorldNodeAtGridPos(gridPos);

            if (validWorldNodes.Contains(node))
            {
                node.SelectSinglePiece(pieceIndex);
                BakeWorldNode(node, forceDir);

                // add its neighbors to the update list
                AddNeighborsToUpdateList(node);
            }
        }

        void ApplyEdgeBorder(int pieceIndex = 0, int gridPosY = 0)
        {
            for (int x = 0; x < config.worldSizeX; x += config.worldSizeX - 1)
            {
                for (int z = 0; z < config.worldSizeZ; ++z)
                {
                    ApplyPieceAtPosition(pieceIndex, math.int3(x, gridPosY, z));
                }
            }

            for (int x = 1; x < config.worldSizeX - 1; x += 1)
            {
                for (int z = 0; z < config.worldSizeZ; z += config.worldSizeZ - 1)
                {
                    ApplyPieceAtPosition(pieceIndex, math.int3(x, gridPosY, z));
                }
            }
        }

        void ApplyLayer(int pieceIndex, int gridPosY)
        {
            for (int x = 0; x < config.worldSizeX; ++x)
            {
                for (int z = 0; z < config.worldSizeZ; ++z)
                {
                    ApplyPieceAtPosition(pieceIndex, math.int3(x, gridPosY, z));
                }
            }
        }

        void AddNeighborsToUpdateList(WorldNode srcNode)
        {
            for (int i = 0; i < neighborGridPosDelta.Length; ++i)
            {
                var neighborWorldNode = GetWorldNodeAtGridPos(srcNode.gridPos + neighborGridPosDelta[i]);

                // if neighbor is valid, add it in
                if (neighborWorldNode != null && validWorldNodes.Contains(neighborWorldNode))
                {
                    PushToUpdateList(neighborWorldNode);
                }
            }
        }

        WorldNode PopFromUpdateList()
        {
            var ienum = updateList.GetEnumerator(); // TODO: RANDOMIZE ACCESS (not in order)
            ienum.MoveNext();
            WorldNode node = ienum.Current;

            updateList.Remove(node);

            return node;
        }

        void PushToUpdateList(WorldNode node)
        {
            updateList.Add(node);
        }

        void UpdateWorldNode(WorldNode srcNode)
        {
            Profiler.BeginSample("WorldBuilder:UpdateWorldNode()");

            bool didSrcNodePiecesChange = false;

            // can this current  piece connect to neighbor's pieces set
            for (int iNeighbor = 0; iNeighbor < neighborGridPosDelta.Length; ++iNeighbor)
            {
                var neighborGridPieceDir = neighborDir[iNeighbor];
                var neighborGridPos = srcNode.gridPos + neighborGridPosDelta[iNeighbor];
                var neighborWorldNode = GetWorldNodeAtGridPos(neighborGridPos);

                if (neighborWorldNode != null)
                {
                    // compare `node` against `neighborWorldNode` and clean `node's pieces list to comply with neighbor
                    for (int iNodePiece = 0; iNodePiece < srcNode.pieces.Count; ++iNodePiece)
                    {
                        bool srcNodePieceChanged = false;
                        srcNode.ValidateWithNeighbor(iNodePiece, neighborGridPieceDir, neighborWorldNode, out srcNodePieceChanged);

                        // if piece can't connect to neighbor, que for deletion
                        if (!srcNode.IsPieceValid(iNodePiece))
                        {
                            srcNode.RemovePiece(iNodePiece);

                            // because swapped with last one, need to revisit same index to see if still valid
                            --iNodePiece;

                            srcNodePieceChanged = true;
                        }

                        if (srcNodePieceChanged)
                            didSrcNodePiecesChange = true;
                    }
                }
            }

            // if `node` gets changed, add `node`s neighbors to the update list
            if (didSrcNodePiecesChange)
            {
                if (srcNode.IsOnePieceRemaining())
                    BakeWorldNode(srcNode);

                AddNeighborsToUpdateList(srcNode);
            }

            Profiler.EndSample();
        }

        void BakeWorldNode(WorldNode node, PieceDir forceDir = PieceDir.NULL)
        {
            Debug.Assert(node.IsOnePieceRemaining());

            var bakedNode = node.Bake(forceDir);
            if (bakedNode.HasValue)
            {
                outputBakedNodes.Add(bakedNode.Value);
            }

            validWorldNodes.Remove(node);
            updateList.Remove(node);
        }

        void InitializeWorldNodes()
        {
            validWorldNodes.Clear();
            nodes = new WorldNode[config.worldSizeX * config.worldSizeY * config.worldSizeZ];

            for (int i = 0; i < nodes.Length; ++i)
            {
                int3 gridPos = ConvertIndexToGridPos(i);

                WorldNode node = new WorldNode();
                node.localPosition = ConvertGridPosToWorldPos(gridPos) - math.float3(config.worldSizeX * 0.5f, 0f, config.worldSizeZ * 0.5f);
                node.gridPos = gridPos;
                node.InitPieces(config.puzzlePack.puzzlePieces);

                nodes[i] = node;
                validWorldNodes.Add(node);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        WorldNode GetWorldNodeAtGridPos(int3 gridPos)
        {
            if (gridPos.x < 0 || gridPos.x >= config.worldSizeX || gridPos.y < 0 || gridPos.y >= config.worldSizeY || gridPos.z < 0 || gridPos.z >= config.worldSizeZ)
                return null;

            int index = ConvertGridPosToIndex(gridPos);

            // out of bounds
            Debug.Assert(index >= 0 && index < nodes.Length);

            return nodes[index];
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        int3 ConvertIndexToGridPos(int index)
        {
            int3 result = int3.zero;

            result.y = index / (config.worldSizeX * config.worldSizeZ);
            result.z = (index - result.y * config.worldSizeX * config.worldSizeZ) / config.worldSizeX;
            result.x = index % config.worldSizeX;

            return result;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        float3 ConvertGridPosToWorldPos(int3 gridPos)
        {
            float3 result = float3.zero;
            result.x = gridPos.x;
            result.y = gridPos.y;
            result.z = gridPos.z;

            return result;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        int ConvertGridPosToIndex(int3 gridPos)
        {
            return gridPos.x + gridPos.z * config.worldSizeX + gridPos.y * config.worldSizeX * config.worldSizeZ;
        }
    }
}