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

Question

我正在开发一个类似于Minecraft的游戏，需要找到一种方法来减少渲染的世界范围。目前，我的做法是简单粗暴地渲染所有东西，这样做显然会遇到扩展性的问题。我需要一种方法，能够从一个方块数组中找出哪些方块是接触到空气、水或者其他透明方块的。

我愿意使用一些外部模块，比如NumPy或SciPy，尽管它们的文档有些难懂。另外，也可以通过遍历每个方块，获取邻近方块的列表，虽然在Python中进行这些计算的性能开销会比在C语言中大得多。

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

Answer 1

你可以使用 Z-缓冲区 这种方法。关于速度，我建议尽量多用 Python 来写代码，并且可以使用 pypy 这个工具。听说《EVE Online》（一款成功的3D大型多人在线游戏）就是用无栈的 Python 写的。

Answer 2

如果你只需要做一次这个操作，性能问题就不是大问题。如果你在每次世界变化的时候，逐步更新 .isBoundary 属性，那么你就不需要再做这个操作了。

不过，如果你的世界太大，或者里面有很多洞、峡谷，或者透明和不透明的部分交错在一起，你还是会遇到一些问题。如果你需要动态判断哪些东西是可见的，可以使用一个八叉树（http://en.wikipedia.org/wiki/Octree）。在这个八叉树里，你可以把大块的空气、水等当作一个节点（一个大块），标记为“透明”。然后使用“油漆桶”算法（经过修改以执行Dijkstra算法，这样可以很容易地检测到你是否“转了个弯”，通过检查当前块和起点之间是否有块存在）来快速找出哪些块是可见的。如果玩家移动得比较慢，远处的更新可以大大延迟。