获取网格中可见体素的列表。

Question

我正在开发一个类似Minecraft的游戏，需要一种减少渲染世界数量的方法。目前，我使用的是朴素的“渲染所有”方法，这显然存在着扩展问题。我需要一种方法，能够获取一组方块，并以某种方式查找哪些方块接触了空气、水或其他半透明方块。

我可以尝试使用NumPy或SciPy等外部模块，但它们的文档有些超出我的理解范围。另外，也可以通过迭代每个方块并获取邻居列表来实现，但在Python中进行这些计算而不是C的性能成本会相当高。

顺便说一下，我已经尝试过NetworkX，但它似乎更适用于科学分析或路径查找，而不是可见性检查。

- James

Answer 1

如果您只需要执行一次，性能不应成为问题。如果您还会在世界更改时递增更新块的.isBoundary属性，那么您将永远不必再次执行该操作。

但是，如果您的世界过大或充满洞穴和透明交错非透明，则仍然会遇到问题。如果您需要动态确定可见性，则可以保留八叉树(http://en.wikipedia.org/wiki/Octree)，其中可以将巨大的空气/水等区域作为单个节点(巨大块)，标记为“透明”。然后使用“油漆桶”算法(修改为执行Dijkstra算法，以便通过检查当前块和原点之间是否存在块来检测是否“绕过角落”)快速确定哪些块可见。如果玩家移动缓慢，则远处物体的更新可以被显著延迟。

- ninjagecko

---

听起来是一个相当可靠的技术，即使它比我所期望的要多一些。有没有一些库可以为我完成这个？我不能写自己的C语言以获得更好的性能，并且我希望在整个开发过程中尽可能保留原有的内容。 - James

@James：通常情况下，除非你正在编写一个大型程序，已经确定了一个关键部分，并且回报巨大（例如新用户、大量现金奖励等），否则不应考虑降低到更低级别的语言以提高性能。当然，对此的看法可能有所不同。我建议看看MMORPG和其他3D游戏如何解决这些规模问题；它可能是一个已经解决的问题，也可能不是（由于你的游戏的块状特性）。如果没有其他解决方案，你的解决方案足够简单，只需几行代码即可测试，以确定你是否真的需要更强大的工具。 - ninjagecko

Answer 2

你可以使用Z-Buffer解决方案。关于速度，我建议尽可能多地使用Python，并使用pypy。我相信EVE Online（一个成功的3D MMO）是用Stackless Python编写的。

- ubershmekel