c++ - 从源开始，在 C++ 中找到最接近网格上目标的下一个点

Question

我有一个包含 2 个点的 NxN 网格，即源点和目标点。我需要一步一步地从源头移动到目的地(它也在移动)。我如何确定下一个要移动到的点？

一种方法是评估所有 8 个点，并使用欧几里德距离查看哪个点产生的距离最短。但是，我希望有一个很酷的(数学)技巧可以产生更优雅的结果。

Answer 1

你的问题陈述允许沿对角线移动，这更快(因为它在一个步骤中同时水平移动和垂直):这个解决方案将始终这样做，除非它具有与以下相同的 x 或 y 坐标目标。

using Position = pair<int,int>;

Position move(Position const &current, Position const &target) {
    // horizontal and vertical distances
    const int dx = target.first - current.first;
    const int dy = target.second - current.second;
    // horizontal and vertical steps [-1,+1]
    const int sx = dx ? dx/abs(dx) : 0;
    const int sy = dy ? dy/abs(dy) : 0;
    return { current.first + sx, current.second + sy };
}

虽然我不确定这是否算作一个很酷的数学技巧，但它只取决于知道:

• dx = target.x-current.x 如果您应该朝正 x 方向移动则为正，如果您应该朝负方向移动则为负，如果您应该直线向上则为零/向下
• dx/abs(dx) 保留符号并删除大小，因此它始终是 -1,0,+1 之一(但要避免被零除)