3

我在为我的游戏运行算法时遇到了一些问题，希望这里有人可以帮助我。谷歌似乎不是一个很好的帮助，因为大多数解决方案只适用于完整的瓷砖。

在游戏中，单位可以在一个棋子内占据不同的位置，即它们可以在左上角，中心，右下角，... 棋子的位置（2/3），即（2.2/3.1），（2.5/3.5） ), (2.8/3.9)。

如果他们从位置 (2.2/3.1) 移动到 (5.7/4.1)，我需要检查路径中是否有障碍物。

我目前的算法是：

  1. 从（2.2/3.1）开始
  2. 计算运动的角度（即70度）
  3. 朝那个方向移动 0.1 步
  4. 检查我在哪个瓷砖上（地板（pX）/地板（pY））
  5. 从 2 开始重复

该算法有效，但对我来说它看起来不是很有效，因为障碍物只能是完整的瓷砖，而不是瓷砖的一部分（单位不会碰撞）。如果我增加步长，我开始错过仅略微交叉的瓷砖（即您只穿过左下角）。即使步长为 0.1，仍然有可能错过障碍。

我试图找到一个解决方案来获取子地图（所有带有角落的瓷砖（地板（start.X）/地板（start.Y））和（ceil（start.X）/ceil（start.Y）），移动穿过每块瓷砖并在数学上检查它是否越过。遗憾的是，我似乎缺乏这项检查所需的数学知识。

我的最后一个想法是将图块的所有 4 个边界作为一条线并进行线相交，但这似乎比我原来的方法慢。

有什么提示吗？

谢谢。

4

1 回答 1

5

而不是通过沿着线步进来跟踪路径 - 您想直接跳到下一个可能的图块（边界）。这可以相当简单地计算出来。我将使用您上面的示例编号。

  1. 计算线 eqn (y= .286x + 2.471)
  2. 您从 2,3 瓷砖开始，向 5,4 瓷砖移动。因此，当 x 变为 3 时计算 y 值（紧靠右侧的图块的边界）。它是 3.329。
  3. 然后计算 y 变为 4 时的 x 值（紧邻上方瓷砖的边界）。它是 5.346。
  4. 从 2,3 开始向右移动到 3,3.329。向上移动到 5.346,4。您在右侧相交（在 x 上移动 2 -> 3 不会在 y 上移动瓷砖）。在 x 中的第 5 块瓷砖上之前，您不会在上面相交。
  5. 在 4 中计算的图块成为您的新比较 (3,3)。从第 2 步开始重复。

此过程仅对移动的每个图块进行一次计算（无论您的精度或图块有多大）并且是精确的。请注意，计算出的值可以存储和重复使用，而不是一遍又一遍地盲目地计算两个交叉点。在上面我们知道（第 4 步）我们直到 x=5 才向上移动一个图块。因此可以推断出整个路径而无需其他计算（2,3 -> 3,3 -> 4,3 -> 5,3 -> 5,4）。

也可以预先计算所有转换而不是逐步进行，尽管这只有在您总是需要整个路径时才有用（您不需要，因为一旦发现障碍物就想停止处理）。

两个警告。注意标志和线路的走向——许多错误都是由于没有密切注意负斜率而发生的。此外，使用实数几乎永远不会穿过对角线（一次有两个边界），但您应该注意它（在代码中处理它）以防万一。

这种方法有一个名称，但我不记得它了。我相信它可能来自 Game Programming Gems 系列，但也许其他人可以提供更好的参考。

于 2010-05-06T13:39:27.223 回答