3D 六角形图块地图上的光线追踪 (LoS)
您好，
我正在开发一个使用 3D 六角形瓷砖地图变体的游戏项目。瓷砖实际上是立方体，而不是六角形，但布局就像六角形（因为正方形可以变成立方体以从 2D 推断到 3D，但六角形没有 3D 版本）。这里没有详细的描述，而是 4x4x4 地图的示例：
（我突出显示了任意图块（绿色）及其相邻图块（黄色），以帮助描述整个事情应该如何工作；但是邻接函数不是问题，这就是已经解决了。）
我有一个结构类型来表示图块，并且地图表示为图块的 3D 数组（包装在 Map 类中以添加一些实用方法，但这不是很相关的）。 每个图块都应该代表一个完美的立方空间，并且它们的大小完全相同。此外，相邻“行”之间的偏移恰好是图块大小的一半。
背景已经足够了；我的问题是：
给定两个点 A 和 B 的坐标，我如何生成 A 和 B 之间的直线的图块列表（或者更确切地说，它们的坐标） code>A 和 B 会交叉吗？
这稍后将用于多种目的，例如确定视距、充电路径合法性等。
顺便说一句，这可能很有用：我的地图使用 (0,0,0) 作为参考位置。地图的“锯齿”可以定义为将每个图块 ((y+z) mod 2) *tileSize/2.0 从“正常”笛卡尔坐标系上的位置向右偏移系统。对于非锯齿状行，结果为 0；对于 (y+z) mod 2 为 1 的行，它会产生 0.5 个图块。
我正在研究针对 .Net Framework 4.0 的 C#4；但我真的不需要特定的代码，只需要解决奇怪的几何/数学问题的算法。我已经尝试了好几天来解决这个问题，但没有成功；并试图将整个事情画在纸上以“可视化”它也没有帮助:(。
提前感谢您的任何回答
Greetings,
I'm working on a game project that uses a 3D variant of hexagonal tile maps. Tiles are actually cubes, not hexes, but are laid out just like hexes (because a square can be turned to a cube to extrapolate from 2D to 3D, but there is no 3D version of a hex). Rather than a verbose description, here goes an example of a 4x4x4 map:
(I have highlighted an arbitrary tile (green) and its adjacent tiles (yellow) to help describe how the whole thing is supposed to work; but the adjacency functions are not the issue, that's already solved.)
I have a struct type to represent tiles, and maps are represented as a 3D array of tiles (wrapped in a Map class to add some utility methods, but that's not very relevant).
Each tile is supposed to represent a perfectly cubic space, and they are all exactly the same size. Also, the offset between adjacent "rows" is exactly half the size of a tile.
That's enough context; my question is:
Given the coordinates of two points A and B, how can I generate a list of the tiles (or, rather, their coordinates) that a straight line between A and B would cross?
That would later be used for a variety of purposes, such as determining Line-of-sight, charge path legality, and so on.
BTW, this may be useful: my maps use the (0,0,0) as a reference position. The 'jagging' of the map can be defined as offsetting each tile ((y+z) mod 2) * tileSize/2.0 to the right from the position it'd have on a "sane" cartesian system. For the non-jagged rows, that yields 0; for rows where (y+z) mod 2 is 1, it yields 0.5 tiles.
I'm working on C#4 targeting the .Net Framework 4.0; but I don't really need specific code, just the algorithm to solve the weird geometric/mathematical problem. I have been trying for several days to solve this at no avail; and trying to draw the whole thing on paper to "visualize" it didn't help either :( .
Thanks in advance for any answer
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在一位聪明的 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。接下来我将使用奇数：任何点point(x,odd(floor(y))映射到cell(floor(x-0.5),floor( 。现在您已经掌握了确定视线的基础知识，
您还需要一个从
cell(m,n)映射回点的函数 在笛卡尔空间中，一旦你确定了原点在哪里，那应该很简单。现在，除非我放错了一些括号，否则我认为你需要：
cell(0 中的位置)。 ,0)你定位point(0,0)；并相应地调整函数；根据 的大小 在游戏环境中，您可以将单元格边界的笛卡尔坐标存储在查找表（或其他数据结构）中，这可能会加快速度。
Until one of the clever SOers turns up, here's my dumb solution. I'll explain it in 2D 'cos that makes it easier to explain, but it will generalise to 3D easily enough. I think any attempt to try to work this entirely in cell index space is doomed to failure (though I'll admit it's just what I think and I look forward to being proved wrong).
So you need to define a function to map from cartesian coordinates to cell indices. This is straightforward, if a little tricky. First, decide whether
point(0,0)is the bottom left corner ofcell(0,0)or the centre, or some other point. Since it makes the explanations easier, I'll go with bottom-left corner. Observe that anypoint(x,floor(y)==0)maps tocell(floor(x),0). Indeed, anypoint(x,even(floor(y)))maps tocell(floor(x),floor(y)).Here, I invent the boolean function
evenwhich returns True if its argument is an even integer. I'll useoddnext: any pointpoint(x,odd(floor(y))maps tocell(floor(x-0.5),floor(y)).Now you have the basics of the recipe for determining lines-of-sight.
You will also need a function to map from
cell(m,n)back to a point in cartesian space. That should be straightforward once you have decided where the origin lies.Now, unless I've misplaced some brackets, I think you are on your way. You'll need to:
cell(0,0)you positionpoint(0,0); and adjust the function accordingly;Depending on the size of the playing field you could store the cartesian coordinates of the cell boundaries in a lookup table (or other data structure), which would probably speed things up.
如果您以另一种方式看待您的问题，也许您可以避免所有复杂的数学：
我发现您仅沿第一个轴将块（交替）移动块大小的一半。如果你沿着这个轴分割你的块，上面的例子将变成（带有移位）一个带有规则堆叠块的（9x4x4）简单笛卡尔坐标系。现在，进行光线跟踪变得更加简单并且更不容易出错。
Perhaps you can avoid all the complex math if you look at your problem in another way:
I see that you only shift your blocks (alternating) along the first axis by half the blocksize. If you split up your blocks along this axis the above example will become (with shifts) an (9x4x4) simple cartesian coordinate system with regular stacked blocks. Now doing the raytracing becomes much more simple and less error prone.