体素世界优化_编程黑洞网

这与Minecraft克隆无关。

我目前正在编写基于回合制的策略游戏，例如《最终幻想战术》。游戏在浮动的体素风格的岛上玩，这些岛是根据高度图图像生成的（不久将使用system.drawing动态生成）。我已经写了世界生成器（模拟了15分钟）和体素世界优化器。

我唯一的问题是体素世界优化大约需要900毫秒才能完成（建议我在Stack Overflow上收到此建议Parallel.ForEach，并将其降至260-300ms）。我想向大家展示一些代码，看看是否有人可以帮助我将选择时间降低到100-200毫秒左右。

这是我当前的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循环（将时间从900ms缩短到260-300ms）

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) {

        }
    }
}

#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;
    }
}

这确实意味着我将性能影响转移到了世界上，但是仅加载样本高度图图像并生成体素21ms，优化花费0.96ms（是的，不到1ms）。

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

加载阶段的关键是保持跟踪已加载的邻居，我在WorldLoader中通过执行Dictionary<Vector3d, Voxel>来实现。我只麻烦搜索左/后/底邻居，因为我的Voxel实现已经处理了设置邻居之间关系的另一端的问题（如果x.LeftNeighbor = y，然后y.RightNeighbor == x）。 />注意

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

\ $ \ begingroup \ $
哇，很好。并且请。
\ $ \ endgroup \ $
– Krythic
2014-09-10 22:44

\ $ \ begingroup \ $
很好，等待预处理部分，真正的魔力在哪里！
\ $ \ endgroup \ $
–user52292
2014年9月11日下午5:34

\ $ \ begingroup \ $
我已经对这里的情况提出了元问题。请在此处查看我的描述和推理，并加入讨论以表达您的意见。
\ $ \ endgroup \ $
–user52292
2014年9月11日7:58

\ $ \ begingroup \ $
@firda我已经用答案解释了我的所作所为，并链接到我的示例项目，我将加入有关meta的讨论。
\ $ \ endgroup \ $
–卢卡索德
2014年9月11日上午9:14

\ $ \ begingroup \ $
我喜欢通用词典方法。实际上，我可以有一个加载屏幕或用于初始构建/缓存的内容。我选择这个作为答案；谢谢！
\ $ \ endgroup \ $
– Krythic
2014年9月11日下午16:15

#2 楼

您知道这两个循环是问题所在（二次复杂度-O（n2）），因此，您想以某种方式降低它。 Parallel.ForEach将使用其他核心来获得一定的速度，但最好是使用不同的结构-2D或3D，以帮助您更快地找到体素。如果3D占用过多内存，则2D仍应提供帮助（上下体素列表）。如果这仍然太多，请尝试使用R树whis非常适合最近邻居搜索。最后，一旦完成工作，您就可以将结构丢弃。

EDIT2：同时使用Parallel.ForEach和heightmap应该可以提供最佳性能。（注意：我们显然与作者产生了类似的想法，以便同时使用Parallel.ForEach，但没有看到他的更新。）

\ $ \ begingroup \ $
谢谢，我很快就会研究R-Tree。如果找到解决方案，请在此处发布。
\ $ \ endgroup \ $
– Krythic
2014-09-10 21:19

\ $ \ begingroup \ $
期待看到它：) R-tree或八叉树可能很好，但可能会过大。
\ $ \ endgroup \ $
–user52292
2014-09-10 21:31

\ $ \ begingroup \ $
宁可移至评论：您可以（Krynn）包含加载阶段的代码，在该阶段使用高度图创建体素？也许可以使用高度图来完成优化，在此您可以知道哪些体素是邻居-您甚至不需要创建它们，以隐藏当前正在创建的体素的面孔，高度图可以立即从周围显示像素。
\ $ \ endgroup \ $
–user52292
2014年9月11日在8:44

\ $ \ begingroup \ $
我不认为八叉树会过大。想到它，八叉树打开了其他优化可能性，例如渲染具有与一个图元相同的高度和材质的整个图块（这会增加吞吐量）并提高空间查询的效率。
\ $ \ endgroup \ $
–没人远离SE
2014年9月11日上午10:37

\ $ \ begingroup \ $
我只是重写了高度图生成器；我不喜欢将其粘贴到任何地方，因为这是使我的游戏难以复制的唯一原因。截至目前，heightmap加载器采用12种不同的颜色阴影，最多支持12层体素（在3D空间中为22层）。它可以在不到30毫秒的时间内加载100 * 100 png。我想保持专有性是一件事……即使有人可以自己编写它。
\ $ \ endgroup \ $
– Krythic
2014年9月12日21:16在

#3 楼

在Visual Studio上工作了几个小时之后，我终于能够产生一个解决方案（基于@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-10ms）

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();
        }
    }
}

\ $ \ begingroup \ $
另一个提示：尝试同时使用Parallel.ForEach和heightmap来禁用一些面孔。那应该给你最好的表现；）
\ $ \ endgroup \ $
–user52292
2014年9月12日下午21:13

\ $ \ begingroup \ $
我知道，但是我喜欢我的方法，因为我现在可以进入“可破坏的世界”心态并轻松地重建整个层次。我希望装载机只装载；优化器仅进行优化。
\ $ \ endgroup \ $
– Krythic
2014年9月12日在21:19

\ $ \ begingroup \ $
当然，我也喜欢字典中的想法。我也在考虑它可能带来的其他可能性。 Lukazoid有了一个绝妙的主意。
\ $ \ endgroup \ $
–user52292
2014年9月12日21:21在

\ $ \ begingroup \ $
当然。尤其是因为我实际上可以传入Vector3并从该位置取出体素。
\ $ \ endgroup \ $
– Krythic
2014年9月12日在21:24

\ $ \ begingroup \ $
实际上，您可能会发现Parallel.ForEach的开销超过了收益，因此请同时进行分析。
\ $ \ endgroup \ $
–卢卡索德
2014年9月13日在1:11