在类似3D十六进制的平铺贴图上进行光线跟踪(LoS)

Question

问候,

我正在开发一个使用六角形瓷砖地图的3D变体的游戏项目.瓷砖实际上是立方体,而不是六角形,但是像六边形一样布局(因为正方形可以转换为立方体从2D到3D外推,但没有十六进制的3D版本).这里有一个4x4x4地图的例子,而不是冗长的描述:

(我已经突出显示了一个任意的瓷砖(绿色)及其相邻的瓷砖(黄色),以帮助描述整个事物应该如何工作;但邻接功能不是问题,已经解决了.)

我有一个结构类型来表示图块,而地图则表示为一个3D图块的图块(包含在一个Map类中以添加一些实用工具方法,但这并不是很相关).每个瓷砖应该代表一个完美的立方体空间,它们的大小完全相同.而且,相邻"行"之间的偏移恰好是图块大小的一半.

这是足够的背景; 我的问题是:
考虑到两个点的坐标A和B,我怎么能生成砖(或者说,它们的坐标),其之间的直线的名单A和B会生气吗？

这将在以后用于各种目的,例如确定视线,充电路径合法性等.

顺便说一下,这可能很有用:我的地图使用(0,0,0)作为参考位置.地图的"锯齿状"可以定义为将每个瓷砖((y+z) mod 2) * tileSize/2.0从它在"理智"笛卡尔系统上的位置向右偏移.对于非锯齿状的行,产生0; 对于行为(y+z) mod 21,它产生0.5个tile.

我正在研究面向.Net Framework 4.0的C#4; 但我真的不需要特定的代码,只需要算法来解决奇怪的几何/数学问题.我一直在努力解决这个问题几天无济于事; 并试图在纸上绘制整个东西以"可视化"它也没有帮助:(.

提前感谢您的回答

Answer 1

在一位聪明的 SOers 出现之前，这是我的愚蠢解决方案。我会用 2D 来解释它，因为这样更容易解释，但它很容易推广到 3D。我认为任何尝试完全在单元格索引空间中进行此操作的尝试都注定会失败（尽管我承认这正是我的想法，并且我期待被证明是错误的）。

因此，您需要定义一个函数来从笛卡尔坐标映射到单元格索引。这很简单，但有点棘手。首先，确定是point(0,0)左下角cell(0,0)还是中心，或者其他点。因为它使解释更容易，所以我将选择左下角。观察到任何point(x,floor(y)==0)映射到cell(floor(x),0). 事实上，任何point(x,even(floor(y)))映射到cell(floor(x),floor(y)).

在这里，我发明了一个布尔函数even，如果其参数是偶数，则该函数返回 True。接下来我将使用odd：任何点point(x,odd(floor(y))映射到cell(floor(x-0.5),floor(y)).

现在您已经了解了确定视线的方法的基础知识。

您还需要一个函数来从cell(m,n)回映射到笛卡尔空间中的点。一旦你确定了起源在哪里，这应该很简单。

现在，除非我放错了一些括号，否则我想你已经上路了。您需要：

• 决定cell(0,0)你的位置point(0,0)；并相应调整功能；
• 决定沿着单元边界的点落在哪里；和
• 将其概括为 3 个维度。

根据比赛场地的大小，您可以将单元格边界的笛卡尔坐标存储在查找表（或其他数据结构）中，这可能会加快速度。