algorithm - 3D 六边形瓦片 map 上的光线追踪 (LoS)

Question

问候，

我正在开发一个游戏项目，该项目使用六边形瓷砖 map 的 3D 变体。瓷砖实际上是立方体，而不是六边形，但布局就像六边形(因为可以将正方形变成立方体以从 2D 推断为 3D，但没有 3D 版本的六边形)。这里不是冗长的描述，而是一个 4x4x4 map 的示例:

(我突出显示了任意一个图 block (绿色)及其相邻图 block (黄色)以帮助描述整个事物应该如何工作；但邻接函数不是问题，这已经解决了。)

我有一个结构类型来表示图 block ， map 表示为图 block 的 3D 数组(包装在 Map 类中以添加一些实用方法，但这不是很相关)。 每个图 block 都应该代表一个完美的立方体空间，并且它们的大小都完全相同。此外，相邻“行”之间的偏移量正好是图 block 大小的一半。

上下文足够了；我的问题是:
给定两点坐标A和 B ，如何生成 A 之间的直线的图 block 列表(或者更确切地说，它们的坐标)和 B会穿越吗？

稍后将用于各种目的，例如确定视线、充电路径合法性等。

顺便说一句，这可能很有用:我的 map 使用 (0,0,0) 作为引用位置。 map 的“锯齿”可以定义为偏移每个图 block ((y+z) mod 2) * tileSize/2.0从它在“理智的”笛卡尔系统上的位置向右。对于非锯齿状的行，结果为 0；对于 (y+z) mod 2 的行为 1，它产生 0.5 个图 block 。

我正在研究针对 .Net Framework 4.0 的 C#4；但我真的不需要特定的代码，只需要解决奇怪的几何/数学问题的算法。我已经尝试了几天来解决这个问题，但无济于事；并试图在纸上画出整个东西以“可视化”它也无济于事:(。

提前感谢您的回答

Answer 1

在聪明的 SOer 出现之前，这是我的愚蠢解决方案。我将在 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))。

在这里，我发明了 bool 函数 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 个维度。

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