CODEWITHSUNDEEP
c++math
Nick
Nick

Reputation: 2980

Starting from a source, find the next point closest to an objective on a grid in C++

I have an NxN grid with 2 points, the source and destination. I need to move step by step from the source to the destination (which is also moving). How do I determine what the next point is to move to?

One way is to assess all 8 points and see which yields the lowest distance using an Euclidian distance. However, I was hoping there is a cool (mathematical) trick which will yield more elegant results.

Upvotes: 1

Views: 252

Answers (3)

Useless
Useless

Reputation: 67733

Your question statement allows moving diagonally, which is faster (since it's moving both horizontally and vertically in a single step): this solution will always do that unless it has the same x or y coordinate as the target.

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 };
}

I'm not sure if this counts as a cool mathematical trick though, it just depends on knowing that:

  • dx = target.x-current.x is positive if you should move in the positive x-direction, negative if you should go in the negative direction, and zero if you should go straight up/down
  • dx/abs(dx) keeps the sign and removes the magnitude, so it's always one of -1,0,+1 (avoiding however division by zero)

Upvotes: 2

wich
wich

Reputation: 17127

I would simply use some vector math, take dest minus source as a vector, and then calculate the angle between that vector and some reference vector, e.g. <1, 0>, with standard methods.

Then you can simply divide the circle in 8 (or 4 if your prefer) sections and determine in which section your vector lies from the angle you obtained.

See euclidean space for how to calculate the angle between two vectors.

Upvotes: -1

Alex Aparin
Alex Aparin

Reputation: 4512

I suppose that answer to your question is Bresenham's line algorithm. It allows to build sequence of integer points between start and end points in your grid. Anyway you can adapt ideas from it to your problem

For more information see https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html

Upvotes: 1

Related Questions