c++ - 检查线是否穿过 2D 地图上的墙壁

Question

我有 2d 地图，我想检查线条是否与任何元素发生碰撞。我需要一个函数来告诉我这条线是否在途中与任何对象相交。

看一看：

红线不正确（函数应该返回假），绿线是（返回真）。我的碰撞图是布尔图，1 表示墙壁，0 表示空白空间。

这个怎么办？我读过我需要检查线是否与任何墙壁相交，但我完全不知道如何在 2d 地图上执行此操作。

感谢任何回复。

Answer 1

这取决于你的墙是如何表示的。

如果它们是矩形，则在您的线和代表矩形的 4 个线段之间寻找线/线段交叉点。

如果是像素点，可以使用bresenham线算法来查看线上的像素点是否在这些块上。

Answer 2

如果您的墙壁表示为线段，您可以测试线段的交叉点，如 Paul Bourke 所述：http ://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/

如果您的墙壁表示为多边形，您可以将测试线剪裁到墙壁多边形上，并查看剪裁结果是否如 Paul Bourke 所描述的那样非空：http ://local.wasp.uwa.edu.au/~pbourke/geometry /cliplinetopoly/

Answer 3

所以，我想象你的单元格是正方形......假设它们是单位正方形。所以，如果我有任何坐标，对于像浮点数或双精度这样的点，它们在 cell 中。

1. 您需要知道哪些单元格是线的端点
2. 从一个端点直接走到另一个端点，对于每个单元格，测试它是否是一堵墙
3. 找到墙时返回 false，否则返回 true。

要从一个端点走到另一个端点，您需要计算每个轴的增量（调用 delta_x 和 delta_y，这些值是“int”，因为我们在这里讨论的是单元格），即它在垂直方向上的单元格数量和在水平面上。你取两者中最大的一个。您将为循环使用该最大值。假设这个值是 D = max(delta_x, delta_y) 并且 XX 和 YY 是一个端点的单元格的坐标。

float step = 1.0f / D;
float current_location = 0.0;
for (int i = 0; i <= D; ++i, current_location += step)
{
  int cur_x = XX + current_location * delta_x;
  int cur_y = YY + current_location * delta_y;
  if (intersect_wall(cur_x, cur_y))
    return false;
}
return true;

就是这样......根据您的功能调整它。