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

Question

我正在开发一个“我的世界”风格的游戏，我需要一种方法来减少渲染的世界的数量。目前，我使用的是一种朴素的、渲染一切的方法，这种方法存在明显的伸缩性问题。我需要一种方法来获取一组块，并以某种方式找出哪些块正在接触空气、水或任何其他半透明块。

我对使用NumPy或SciPy等外部模块持开放态度，尽管它们的一些文档有点让我摸不着头脑。或者，也可以遍历每个块并获得邻居列表，尽管使用Python而不是C进行这些计算的性能成本会非常高。

根据记录，我已经尝试过查看NetworkX，但它似乎更多的是用于科学分析或寻路，而不是可见性检查。

Answer 1

如果您只需要这样做一次，那么性能应该不是问题。如果还在更改世界时以增量方式更新块的.isBoundary特性，则不必再次执行此操作。

然而，如果你的世界太大了，或者充满了洞穴和洞穴，透明-交错-不透明，你仍然会遇到问题。如果你需要动态确定什么是可见的，你可以保留一个八叉树( http://en.wikipedia.org/wiki/Octree )，在那里你可以拥有巨大的空气/水等扩展，作为一个单独的节点(巨型块)，标记为“透明”。然后使用"paintbucket“算法(修改为执行Dijkstra算法，因此很容易通过检查当前块和原点之间是否存在块来检测您是否”绕过了角落“)，以快速找出哪些块在视线中。如果玩家移动速度很慢，那么距离较远的东西的更新可能会显着延迟。

Answer 2

您可以使用Z-Buffer解决方案。关于速度，我会尽可能多地用python编写，并使用pypy。EVE Online (一个成功的3DMMO)是用无栈python编写的，我相信。