WPF：沿着路径查找元素

Question

我还没有标记这个问题为已回答。
当前被接受的答案是因为赏金限时自动接受的。

---

关于我正在开发的编程游戏this programming game。

从上面的链接可以看出，我正在开发一个游戏，在这个游戏中，用户可以编写程序，使机器人在竞技场中自主作战。

---

现在，我需要一种方法来检测机器人是否以特定的角度（取决于炮塔面向的方向）检测到另一个机器人：

如上图所示，我绘制了坦克的视角，现在我需要在我的游戏中模拟它，以检查其中的每个点，看看是否有其他机器人在视野范围内。

这些机器人只是不断在战斗竞技场（另一个画布）上移动的画布。

我知道炮塔的朝向（它当前面向的方向），并且需要找出是否有任何机器人在其路径上（路径应以“视点”方式定义，在上图中以红色“三角形”的形式呈现）。我希望该图像可以更清楚地说明我试图传达的内容。

我希望有人能指导我如何解决这个问题涉及的数学问题。

---

[更新]

我已经尝试了你告诉我的计算方法，但是它并没有正常工作，因为如你所见，Bot1 不应该能看到 Bot2。以下是一个例子:

alt text http://img12.imageshack.us/img12/7416/examplebattle2.png

在上述情况下，Bot1 正在检查他是否能看到 Bot2。根据Waylon Flinn的答案，以下是细节：

angleOfSight = 0.69813170079773179 //in radians (40 degrees)
orientation = 3.3 //Bot1's current heading (191 degrees)

x1 = 518 //Bot1's Center X
y1 = 277 //Bot1's Center Y

x2 = 276 //Bot2's Center X
y2 = 308 //Bot2's Center Y

cx = x2 - x1 = 276 - 518 = -242
cy = y2 - y1 = 308 - 277 =  31

azimuth = Math.Atan2(cy, cx) = 3.0141873380511295

canHit = (azimuth < orientation + angleOfSight/2) && (azimuth > orientation - angleOfSight/2)
       = (3.0141873380511295 < 3.3 + 0.349065850398865895) && (3.0141873380511295 > 3.3 - 0.349065850398865895)
       = true

根据上述计算，Bot1能看到Bot2，但从图像中可以看出这是不可能的，因为它们面对着不同的方向。在上述计算中我做错了什么？

- Dreas Grech

---

这是一个纯粹的二维问题还是你的绘图是三维问题的二维表示？ - DJClayworth

希望能听到一些赏金系统的成功故事，因为到目前为止我只看到了失败的例子。 - Jon Ericson

啊，老好玩的Robocode。我一直想创建一个WallsHunter机器人，可以预测该死的墙壁机器人会在哪里。但从未有机会。 - OscarRyz

@Cœur 我开了这个问题已经八年了。现在修复它们有点困难。 - Andreas Grech

我知道这是旧的，但我认为你应该删除到imageshack的死链接。 - Cœur

Answer 1

机器人之间的夹角是arctan(x-距离, y-距离)（大多数平台提供这种两个参数的arctan函数，可以为您进行角度调整。然后只需检查此角度是否比当前朝向小于某个数字即可。

---

2020编辑：这里是基于问题中更新的示例代码和一个已删除的 imageshack 图像的更完整的分析。

1. Atan2：找到两点之间的角度所需的关键函数是 atan2。它接受矢量的 Y 坐标和 X 坐标，并返回该矢量与正 X 轴之间的角度。该值将始终被包装在 -Pi 和 Pi 之间。
2. 航向 vs 方位：atan2，以及一般所有的数学函数，都工作在"数学标准坐标系"中，这意味着一个"0"角度对应于直接东方，而角度逆时针增加。因此，如 atan2(1, 0) 所给出的"数学角度"为 Pi / 2 表示的是"相对于正东逆时针旋转90度"的方向，与点 (x=0, y=1) 对应。"航向"是一种导航概念，它表达的是相对于正北的顺时针角度。
• 分析：在现已删除的 imageshack 图像中，您的"heading"（航向）为191度，对应着一个南南西方向。这实际上是一个-101度或-1.76的三角形"方位"。因此，更新后的代码中第一个问题是混淆了"heading"和"orientation"。你可以通过 orientation_degrees = 90 - heading_degrees 或 orientation_radians = Math.PI / 2 - heading_radians 来从前者获取后者，或者你可以在数学坐标系中指定输入方位而不是海上导航坐标系。
3. 检查某个角度是否介于另外两个角度之间：检查一个矢量是否介于其他两个矢量之间并不像检查数字角度值是否在两个角度之间那么简单，因为角度在 Pi/-Pi 处包装。
• 分析：在你的例子中，方位是3.3，视野的右边缘是方位为2.95，左边缘是3.65。计算出来的方位角是3.0141873380511295，它恰好是正确的（它确实介于两者之间）。但是，对于像-3这样的方位角值，这种方法将失败，而它应该被计算为"命中"。有关解决方案，请参见 Calculating if an angle is between two angles。

- Jimmy

---

你仍然需要计算出从航向向量到角度的角度，才能确定它是否仍在视野范围内。在这一步骤完成之前，这个答案只是不完整的。 - Boon

这个回答因为赏金限时自动被接受了。 - Andreas Grech

Answer 2

在您的机器人类中可以这样写（C# 代码）：

/// <summary>
/// Check to see if another bot is visible from this bot's point of view.
/// </summary>
/// <param name="other">The other bot to look for.</param>
/// <returns>True iff <paramref name="other"/> is visible for this bot with the current turret angle.</returns>
private bool Sees(Bot other)
{
    // Get the actual angle of the tangent between the bots.
    var actualAngle = Math.Atan2(this.X - other.X, this.Y - other.Y) * 180/Math.PI + 360;

    // Compare that angle to a the turret angle +/- the field of vision.
    var minVisibleAngle = (actualAngle - (FOV_ANGLE / 2) + 360);
    var maxVisibleAngle = (actualAngle + (FOV_ANGLE / 2) + 360); 
    if (this.TurretAngle >= minVisibleAngle && this.TurretAngle <= maxVisibleAngle)
    {
        return true;
    }
    return false;
}

注意：

• +360的作用是将任何负角度强制转换为相应的正值，并将角度0的边界情况移动到更容易进行范围测试的位置。
• 这可能可以使用弧度角来完成，但我认为它们很难读懂 :/
• 有关更多详细信息，请参见Math.Atan2文档。
• 我强烈建议您了解XNA Framework，因为它是专为游戏设计而创建的。但是，它不使用WPF。

这假定：

• 没有障碍物阻挡视线
• Bot类具有X和Y属性
• X和Y属性位于机器人的中心。
• Bot类具有TurretAngle属性，表示炮塔相对于x轴逆时针方向的正角度。
• Bot类具有静态常量角度FOV_ANGLE，表示炮塔的视野。

免责声明：此代码未经测试甚至检查是否可编译，请根据需要进行适当的调整。

- Ben S

---

minVisibleAngle（和max）的计算结果始终大约为600以上，但TurretAngle >= 0且< 360，因此TurretAngle大于minVisibleAngle的条件永远不可能成立。我做错了什么？ - Andreas Grech

顺便提一下，关于FOV_ANGLE，我目前正在硬编码40。这是太多了，太少了，还是刚刚好？ - Andreas Grech

典型第一人称射击游戏中的视野范围为45-90度。人类视野范围约为200度，以便您有一个参考框架。 - Ben S

一台35毫米相机的视角为39.6度（http://en.wikipedia.org/wiki/Angle_of_view），所以我认为40度非常完美。 - Ben S

将360添加到炮塔的角度（在Sees函数中，而不是整体）以比较右侧范围内的所有内容。我添加了360以避免测试接近0度的角度边界情况。 - Ben S

Answer 3

这将告诉您canvas1是否可以击中canvas2的中心。如果您想考虑canvas2的宽度，那么情况会变得更加复杂。简而言之，您需要进行两个检查，分别针对canvas2的相关角落，而不是在中心进行一次检查。

/// assumming canvas1 is firing on canvas2

// positions of canvas1 and canvas2, respectively
// (you're probably tracking these in your Tank objects)
int x1, y1, x2, y2;

// orientation of canvas1 (angle)
// (you're probably tracking this in your Tank objects, too)
double orientation;
// angle available for firing
// (ditto, Tank object)
double angleOfSight;

// vector from canvas1 to canvas2
int cx, cy;
// angle of vector between canvas1 and canvas2
double azimuth;
// can canvas1 hit the center of canvas2?
bool canHit;

// find the vector from canvas1 to canvas2
cx = x2 - x1;
cy = y2 - y1;

// calculate the angle of the vector
azimuth = Math.Atan2(cy, cx);
// correct for Atan range (-pi, pi)
if(azimuth < 0) azimuth += 2*Math.PI;

// determine if canvas1 can hit canvas2
// can eliminate the and (&&) with Math.Abs but this seems more instructive
canHit = (azimuth < orientation + angleOfSight) &&
    (azimuth > orientation - angleOfSight);

- Waylon Flinn

---

我在我的帖子中发布了一些计算（[更新]）。你能否请检查一下？谢谢。 - Andreas Grech

Answer 4

计算每个机器人相对于当前机器人的相对角度和距离。如果角度在当前方向的某个阈值内且在最大视野范围内，则可以看到它。

唯一棘手的问题是处理角度从2pi弧度到0的边界情况。

- geofftnz

Answer 5

在实现类似功能后，有几个建议（很久以前！）：

以下假设您正在遍历战场上的所有机器人（这不是一个特别好的做法，但可以快速轻松地让某些东西工作！）

1）检查机器人是否在范围内比检查它是否在FOV中可见要容易得多。

int range = Math.sqrt( Math.abs(my.Location.X - bots.Location.X)^2 + 
            Math.abs(my.Location.Y - bots.Location.Y)^2 );

if (range < maxRange)
{
    // check for FOV
}

这确保了它可能会缩短很多FOV检查并加速运行模拟的过程。但需要注意的是，你可以在此处加入一些随机性，使其更有趣，例如，在某个距离之后，看到的机会与机器人的范围成线性比例关系。

2) 这篇文章似乎有FOV计算相关的内容。

3) 作为一名人工智能专业的毕业生，你是否尝试过神经网络？你可以训练它们来识别机器人是否在范围内并且是一个有效的目标。这将消除任何可怕的复杂和纠缠不清的数学问题！你可以使用多层感知器[1]，[2]输入机器人坐标和目标坐标，并在最后得到一个好的开火/不开火决策。警告：我觉得有必要告诉你，这种方法并不容易实现，当出现问题时可能会非常令人沮丧。由于这种算法形式的（简单）非确定性特性，调试可能会很麻烦。此外，你需要某种形式的学习，无论是反向传播（带有训练案例）还是遗传算法（另一个完美的复杂过程）！如果可以选择，我会选择第三种方法，但并不适合每个人！

- TK

Answer 6

使用向量数学中称为点积的概念可以很容易地实现。

http://en.wikipedia.org/wiki/Dot_product

看起来有点吓人，但其实并不难。这是处理FOV问题最正确的方法，而且美妙之处在于无论你处理2D还是3D，都可以使用相同的数学方法（这就是你知道解决方案正确的时候）。

（注意：如果有什么不清楚的地方，请在评论区提问，我会填补缺失的链接。）

步骤：

1）你需要两个向量，一个是主坦克的头部向量。另一个向量是从所讨论的坦克位置和主坦克派生出来的。

为了讨论方便，假设主坦克的头部向量是（ax，ay），主坦克位置和目标坦克之间的向量是（bx，by）。例如，如果主坦克位于位置（20,30），目标坦克位于（45,62），那么向量b =（45-20，62-30）=（25,32）。

同样，为了讨论方便，假设主坦克的头部向量是（3,4）。

这里的主要目标是找到这两个向量之间的角度，点积可以帮助你得到它。

2）点积的定义如下：

a * b = |a||b| cos(angle)

这里的 a 和 b 不是数字，而是向量，因此读作 a（点乘）b。

3) 或者可以通过一些代数运算来表示如下：

angle = acos((a * b) / |a||b|)

其中 angle 是向量 a 和 b 之间的角度信息，仅凭这个信息就可以判断一辆坦克是否能够看到另一辆坦克。

|a| 表示向量 a 的大小，根据勾股定理，可以得到 |a| = sqrt(ax * ax + ay * ay)，同样的，|b| 也是如此。

现在问题来了，如何计算 a * b（a 点乘 b），以便求出它们之间的夹角。

4) 现在解救来了。原来点乘也可以表示为以下形式：

a * b = ax * bx + ay * by

因此可得 angle = acos((ax * bx + ay * by) / |a||b|)

如果这个角度小于你的视野范围的一半，那么目标坦克就在视野范围中，否则不在。

所以，以上面的数字为例：

根据我们的例子：

a = (3, 4) b = (25, 32)

|a| = sqrt(3 * 3 + 4 * 4)

|b| = sqrt(25 * 25 + 32 * 32)

angle = acos((20 * 25 + 30 * 32) /|a||b|

(在将结果与视野范围进行比较之前，请确保将得出的角度转换为适当的度数或弧度)

- Boon

---

如果你聪明的话，可以改进这种方法（消除余弦反函数），这可能是我在实践中采用的方法，如果代码将在紧密循环中运行。否则，我认为数学复杂度会使其难以维护，从而变得代价高昂。 - Waylon Flinn

它并不像看起来那么昂贵。一旦你把所有东西都用代码写下来，它不到十行代码。是解释让它看起来复杂和令人生畏。反余弦可以通过其他技巧进行优化，但几乎从不必要。 - Boon

我同意，这段代码可能更快。问题在于对于数学新手来说很难理解。我的想法是，通过在循环外部一次性地对FOV/2的余弦值进行计算，可以消除反余弦函数。你还可以确保'a'是一个单位向量并节省乘法运算。 - Waylon Flinn

不错的想法，FOV/2 上做余弦运算一次，避免每次都要做反余弦运算。 - Boon

Answer 7

看了你们两个的问题，我认为你们可以使用提供的数学方法来解决这个问题，然后你还需要解决许多其他与碰撞检测、发射子弹等相关的问题。这些问题不容易解决，特别是如果你的机器人不是正方形的话。我建议你们看看物理引擎 - farseer 在 codeplex 上是一个很好的 WPF 示例，但这会使项目变得比高中开发任务更大。

我得到的最好建议是，做一些简单的事情，做得非常好，不要部分交付出色的东西。

- MrTelly

---

这是很好的建议。使用圆形进行碰撞检测对于初步的处理来说既容易又足够准确。 - geofftnz

Answer 8

你的炮塔真的有那么宽的射击范围吗？子弹飞行的路径应该是一条直线，不会随着距离增加而变大。你应该有一个简单的向量表示炮塔杀伤区域的方向。每个坦克都应该有一个表示其易受攻击区域的边界圆。然后你可以像射线追踪一样进行处理。一个简单的射线/圆相交即可。请参考文档第3节Intersection of Linear and Circular Components in 2D。

- John Ellinwood

---

你在图像中看到的宽三角形是坦克的视野。也就是说，如果该视野内有机器人，则应通知正在查看的机器人。但我不知道如何检查是否有机器人在该特定范围内。 - Andreas Grech

它被称为视景体。这是一种用于确定在3D场景中绘制哪些元素的标准图形算法。您想知道一个对象从特定的视角是否在视景体内。我会寻找参考资料。 - John Ellinwood

Answer 9

您更新的问题似乎来自于不同的“零”方向，即方向和方位角：0度的方向似乎表示“垂直向上”，但0度的方位角则表示“水平向右”。

- Svante