4

游戏小行星在圆环表面上进行。

4

5 回答 5

7

好吧，因为你可以环绕屏幕的任何边缘，所以小行星和飞船之间总是有 4 条直线（上和左、上和右、下和左、下和右）。我只会计算每个的长度并取最小的结果。

int dx1 = abs(ship_x - asteroid_x);
int dx2 = screen_width - dx1;

int dy1 = abs(ship_y - asertoid_y);
int dy2 = screen_height - dy1;

// Now calculate the psuedo-distances as Pete suggests:
int psuedo1 = (dx1 * dx1) + (dy1 * dy1);
int psuedo2 = (dx2 * dx2) + (dy1 * dy1);
int psuedo3 = (dx1 * dx1) + (dy2 * dy2);
int psuedo4 = (dx2 * dx2) + (dy2 * dy2);

这显示了如何计算所涉及的各种距离。将每一个映射到适当的方向有点复杂。

于 2013-01-17T22:09:50.510 回答
4

我会推荐A* 搜索算法

于 2013-01-17T22:08:20.920 回答
1

如果你需要到小行星的最小路径，你不需要计算到它的实际最小距离。如果我理解正确，您需要最短路径而不是最短路径的长度。

我认为，这在计算上是最便宜的方法：

让流星的位置为 (Mx, My) 和船的位置 (Sx, Sy)。视口的宽度为 W，高度为 H。现在，

dx = Mx - Sx，dy = 我的 - Sy。

如果 abs(dx) > W/2（在这种情况下为 256）你的船需要向左走，如果 abs(dx) < W/2 你的船需要向右走。重要 - 如果 dx 为负数，则反转您的结果。（感谢@Toad 指出这一点！）

同样，如果 abs(dy) > H/2 ship UP，abs(dy) < H/2 ship DOWN。与 dx 一样，如果 dy 为 -ve，则翻转结果。

这考虑了包装，并且应该适用于每种情况。不涉及平方或毕达哥拉斯定理，我怀疑它可以做得更便宜。此外，如果您必须找到实际的最短距离，您现在只需应用一次（因为您已经知道需要采取四种可能路径中的哪一种）。@Peter 的帖子提供了一种优雅的方式来做到这一点，同时考虑到包装。

于 2013-01-18T09:27:16.170 回答
1

找到参考船的球体。

在我的示例中避免使用小数。让 x & y = [0 ... 511] 的范围，其中 511 == 0 包装时

让中间为原点。

所以从球体和船的位置中减去 vec2(256,256)

sphere.position(-255,255) = sphere.position(1 - 256,511 - 256);

ship.position(255,-255) = ship.position(511 - 256, 1 - 256)

firstDistance(-510,510) = sphere.position(-255,255) - ship.position(255,-255)

WrapPosition(254,-254) = wrapNewPositionToScreenBounds(firstDistance(-510,510)) // 使用原点偏移量 256 下溢流/溢流

secondDistance(1,-1) = ship.position(255,-255) - WrappedPosition(254,-254)

于 2013-01-17T22:15:06.060 回答
1 
#include <iostream>

template<typename Scalar>
struct vector2d {
  Scalar x;
  Scalar y;
};
template<typename Scalar>
struct position2d {
  Scalar x;
  Scalar y;
};

template<typename S>
S absolute( S in ) {
  if (in < S())
    return -in;
  return in;
}

template<typename S>
S ShortestPathScalar( S ship, S rock, S wrap ) {
  S direct = rock-ship;
  S indirect = (wrap-ship) + (rock);
  if (absolute( direct ) > absolute( indirect ) ) {
    return indirect;
  }
  return direct;
}

template<typename S>
vector2d<S> ShortestPath( position2d<S> ship, position2d<S> rock, position2d<S> wrap ) {
  vector2d<S> retval;
  retval.x = ShortestPathScalar( ship.x, rock.x, wrap.x );
  retval.y = ShortestPathScalar( ship.y, rock.y, wrap.y );
  return retval;
}


int main() {
  position2d<int> world = {1000, 1000};
  position2d<int> rock = {10, 10};
  position2d<int> ship = {500, 900};
  vector2d<int> path = ShortestPath( ship, rock, world );
  std::cout << "(" << path.x << "," << path.y << ")\n";
}

No point in doing crap with squaring stuff in a simple universe like that.

Scalar support for any type that supports a < b, and default construction for a zero. Like double or int or long long.

Note that copy/pasting the above code and handing it in as an assignment at the level of course where you are playing with that problem will get you looked at strangely. However, the algorithm should be pretty easy to follow.

于 2013-01-17T22:56:36.873 回答