体素世界优化

Question

这与我的克隆人没有关系.

我目前正在写一个基于转弯的战略游戏，像最后的幻想战术。游戏是在浮体素风格的岛屿上进行的，这些岛屿是由高度图图像生成的(很快将使用system.drawing动态生成)。我已经编写了world生成器(15分钟模拟)和体素世界优化器。

我唯一的问题是，体素世界优化需要大约900 My才能完成(我在Stack Overflow推荐的Parallel.ForEach上收到了这样的建议，并将其降低到260-300 My)。我想给你们看一些代码，看看是否有人能帮我把选择时间降到100到200 me左右。

下面是我当前的Heightmap (此时的系统非常粗糙)：

下面是对上述Heightmap的简要描述：

我已经写过的“世界优化者”考虑了当脸看不见的时候，如果可以肯定的话，就会隐藏这些面孔(尽管存在体素，但土地是空心的)。同样，我只需要有人帮助我优化优化器，以便它能够更快地工作。

这里是我的世界优化器；如果需要，我将提供任何其他源代码。

可以下载完整的项目源这里。(包括OpenTK必需的预编译演示)

using GameProject.Game.Framework.Geometry;
using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.Generators {
    public enum OptimizationType {
        FullOptimization
    }
    public static class WorldOptimizer {
        public static void OptimizeVoxelWorld( List<Voxel> world , OptimizationType optimizationType ) {
            switch( optimizationType ) {
                case OptimizationType.FullOptimization:
                    DoFullOptimization( world );
                    break;
            }
        }

        private static void DoFullOptimization( List<Voxel> world ) {
            /**
             * Loop Through The Voxel Collection and collect
             * potential neighbors.
             */
            foreach( Voxel currentVoxel in world ) {
                Vector3 backNeighbor = currentVoxel.Location;
                backNeighbor.X += 2.0f;
                Vector3 frontNeighbor = currentVoxel.Location;
                frontNeighbor.X -= 2.0f;
                Vector3 leftNeighbor = currentVoxel.Location;
                leftNeighbor.Z -= 2.0f;
                Vector3 rightNeighbor = currentVoxel.Location;
                rightNeighbor.Z += 2.0f;
                Vector3 topNeighbor = currentVoxel.Location;
                topNeighbor.Y += 2.0f;
                Vector3 bottomNeighbor = currentVoxel.Location;
                bottomNeighbor.Y -= 2.0f;

                /**
                 * This is the part that needs to be fixed.
                 * Basically we loop back through the collection
                 * AGAIN for every voxel. This means that we
                 * check every voxel at least twice, if not up
                 * to six times...I think.
                 */
                foreach( Voxel voxel in world ) {
                    if( voxel != currentVoxel ) {
                        if( voxel.Location == backNeighbor ) {
                            currentVoxel.ShowBackFace = false;
                        } else if( voxel.Location == frontNeighbor ) {
                            currentVoxel.ShowFrontFace = false;
                        } else if( voxel.Location == leftNeighbor ) {
                            currentVoxel.ShowLeftFace = false;
                        } else if( voxel.Location == rightNeighbor ) {
                            currentVoxel.ShowRightFace = false;
                        } else if( voxel.Location == topNeighbor ) {
                            currentVoxel.ShowTopFace = false;
                        } else if( voxel.Location == bottomNeighbor ) {
                            currentVoxel.ShowBottomFace = false;
                        }
                    }
                }
            }
        }

        /**
         * Add this feature later with bitwise flags and other sorts of glorious sugar.
         */
        private static void DoFullControlOptimization(List<Voxel> world) {

        }
    }
}

建议1；使用Parallel.ForEach循环(将时间从900 to降至260-300 to)

using System.Threading.Tasks;
using GameProject.Game.Framework.Geometry;
using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.Generators {
    public enum OptimizationType {
        FullOptimization
    }
    public static class WorldOptimizer {
        public static void OptimizeVoxelWorld( List<Voxel> world , OptimizationType optimizationType ) {
            switch( optimizationType ) {
                case OptimizationType.FullOptimization:
                    DoFullOptimization( world );
                    break;
            }
        }

        private static void DoFullOptimization( List<Voxel> world ) {
            /**
             * Loop Through The Voxel Collection and collect
             * potential neighbors.
             */

            // Parallel.ForEach drops Opt-Time down to 260-300ms!
            // Was 900ms with regular for-each loop.
            Parallel.ForEach( world , currentVoxel => {
                Vector3 backNeighbor = currentVoxel.Location;
                backNeighbor.X += 2.0f;
                Vector3 frontNeighbor = currentVoxel.Location;
                frontNeighbor.X -= 2.0f;
                Vector3 leftNeighbor = currentVoxel.Location;
                leftNeighbor.Z -= 2.0f;
                Vector3 rightNeighbor = currentVoxel.Location;
                rightNeighbor.Z += 2.0f;
                Vector3 topNeighbor = currentVoxel.Location;
                topNeighbor.Y += 2.0f;
                Vector3 bottomNeighbor = currentVoxel.Location;
                bottomNeighbor.Y -= 2.0f;

                /**
                 * This is the part that needs to be fixed.
                 * Basically we loop back through the collection
                 * AGAIN for every voxel. This means that we
                 * check every voxel at least twice, if not up
                 * to six times...I think.
                 */
                foreach( Voxel voxel in world ) {
                    if( voxel != currentVoxel ) {
                        if( voxel.Location == backNeighbor ) {
                            currentVoxel.ShowBackFace = false;
                        } else if( voxel.Location == frontNeighbor ) {
                            currentVoxel.ShowFrontFace = false;
                        } else if( voxel.Location == leftNeighbor ) {
                            currentVoxel.ShowLeftFace = false;
                        } else if( voxel.Location == rightNeighbor ) {
                            currentVoxel.ShowRightFace = false;
                        } else if( voxel.Location == topNeighbor ) {
                            currentVoxel.ShowTopFace = false;
                        } else if( voxel.Location == bottomNeighbor ) {
                            currentVoxel.ShowBottomFace = false;
                        }
                    }
                }
            } );
        }

        /**
         * Add this feature later with bitwise flags and other sorts of glorious sugar.
         */
        private static void DoFullControlOptimization(List<Voxel> world) {

        }
    }
}

Answer 1

为了解决这个问题，我让每个Voxel都知道它的邻居，这是在世界生成/高度图加载阶段实现的。

然后，我能够将优化算法更改为以下内容(在Program.cs中找到)：

private static void DoFullOptimization(IEnumerable<Voxel> world)
{
    foreach (var currentVoxel in world)
    {
        var visibleFaces = Faces.None;
        if (currentVoxel.BackNeighbor == null)
        {
            visibleFaces |= Faces.Back;
        }
        if (currentVoxel.FrontNeighbor == null)
        {
            visibleFaces |= Faces.Front;
        }
        if (currentVoxel.BottomNeighbor == null)
        {
            visibleFaces |= Faces.Bottom;
        }
        if (currentVoxel.TopNeighbor == null)
        {
            visibleFaces |= Faces.Top;
        }
        if (currentVoxel.LeftNeighbor == null)
        {
            visibleFaces |= Faces.Left;
        }
        if (currentVoxel.RightNeighbor == null)
        {
            visibleFaces |= Faces.Right;
        }

        currentVoxel.VisibleFaces = visibleFaces;
    }
}

这确实意味着我将性能提升到了加载世界，但是加载样本高度-地图图像并生成体素只需要21 1ms，优化只需要0.96ms (是的，小于1ms)。

我的整个解决方案都可以在BitBucket 这里上找到。

加载阶段的关键是跟踪加载的邻居，我在WorldLoader中通过拥有一个Dictionary<Vector3d, Voxel>来实现这一点。我只需要搜索左/后/下邻居，因为我的体素实现已经处理了设置邻居之间关系的另一端(如果x.LeftNeighbor =y，那么y.RightNeighbor == x)。

Note

我不是GameDev，所以我的X，Y和Z可能都是错误的，或者指的是错误的东西！

Answer 2

在Visual上花了几个小时之后，我终于能够产生一个解决方案(基于@Lukazoid的帖子)。此解决方案使用一个泛型字典，它将Vector3作为键，Voxel作为值。你所要做的就是问是否存在体素。

这是我的VoxelWorld课程：

using GameProject.Game.Framework.Generators;
using GameProject.Game.Framework.Geometry;
using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.DataStructure {
    public class VoxelWorld {
        public List<Voxel> Voxels;
        public Dictionary<Vector3 , Voxel> SpatialStore;
        public VoxelWorld() {
            Voxels = new List<Voxel>();
            SpatialStore = new Dictionary<Vector3 , Voxel>( new Vector3EqualityComparator() );
        }

        public void AddVoxel( Voxel voxel ) {
            Voxels.Add( voxel );
            SpatialStore.Add( voxel.Location , voxel );
        }

        public Voxel GetVoxelAt( Vector3 location ) {
            return SpatialStore.ContainsKey( location ) ? SpatialStore[ location ] : null;
        }

        public void Rebuild() {
            WorldOptimizer.OptimizeVoxelWorld( this , OptimizationType.FullOptimization );
        }
    }
}

我的优化器，现在可以在9-10毫秒内处理空间存储。我相信我还可以做一些其他的事情来使它更快；如果我发现了任何东西，我会很高兴地把它们扔到这里，让大家看看。

using System.Threading.Tasks;
using GameProject.Game.Framework.DataStructure;
using GameProject.Game.Framework.Geometry;
using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.Generators {
    public enum OptimizationType {
        FullOptimization
    }
    public static class WorldOptimizer {
        public static void OptimizeVoxelWorld( VoxelWorld world , OptimizationType optimizationType ) {
            switch( optimizationType ) {
                case OptimizationType.FullOptimization:
                    DoFullOptimization( world );
                    break;
            }
        }

        private static void DoFullOptimization( VoxelWorld world ) {
            Parallel.ForEach( world.Voxels , currentVoxel => {
                Vector3 backNeighbor = currentVoxel.Location;
                backNeighbor.X += 2.0f;
                Vector3 frontNeighbor = currentVoxel.Location;
                frontNeighbor.X -= 2.0f;
                Vector3 leftNeighbor = currentVoxel.Location;
                leftNeighbor.Z -= 2.0f;
                Vector3 rightNeighbor = currentVoxel.Location;
                rightNeighbor.Z += 2.0f;
                Vector3 topNeighbor = currentVoxel.Location;
                topNeighbor.Y += 2.0f;
                Vector3 bottomNeighbor = currentVoxel.Location;
                bottomNeighbor.Y -= 2.0f;

                if( world.SpatialStore.ContainsKey( frontNeighbor ) ) {
                    currentVoxel.ShowFrontFace = false;
                }
                if( world.SpatialStore.ContainsKey( backNeighbor ) ) {
                    currentVoxel.ShowBackFace = false;
                }
                if( world.SpatialStore.ContainsKey( leftNeighbor ) ) {
                    currentVoxel.ShowLeftFace = false;
                }
                if( world.SpatialStore.ContainsKey( rightNeighbor ) ) {
                    currentVoxel.ShowRightFace = false;
                }
                if( world.SpatialStore.ContainsKey( topNeighbor ) ) {
                    currentVoxel.ShowTopFace = false;
                }
                if( world.SpatialStore.ContainsKey( bottomNeighbor ) ) {
                    currentVoxel.ShowBottomFace = false;
                }
            } );
        }

        /**
         * Add this feature later with bitwise flags and other sorts of glorious sugar.
         */
        private static void DoFullControlOptimization( List<Voxel> world ) {

        }
    }
}

您也需要这一点，这是一个Vector3比较器扩展。(新编辑使优化时间减少到9-10 to )

using System.Collections.Generic;
using OpenTK;

namespace GameProject.Game.Framework.DataStructure.ComparatorExtensions {
    public class Vector3Comparator : IEqualityComparer<Vector3> {

        public bool Equals( Vector3 left , Vector3 right ) {
            return (left.X == right.X) && (left.Y == right.Y) && (left.Z == right.Z);
        }

        public int GetHashCode( Vector3 obj ) {
            return obj.GetHashCode();
        }
    }
}