Move To Point

Does anyone know of a good algorithm which moves a point towards another in 2d space? I only have a basic knowledge of geometry and the only thing i could think of was finding the intersection of two circles (the radius of the first is the distance change and the center is the point that changes and the radius of the other is the new distance and the center is the point to move towards) but I'm worried that because of precision there might not always be an intersection so I'm trying to find something a little better.

I don't know if this is the best way, but here's how I would do it:

Say we have 2 points, A and B. And we want A to move towards B with a distance of d (whatever unit the points' position is stored as. Pixels/inches/mm/etc)

Calculate a normalized 2d vector v from A towards B and then
A.x += v.x * d
A.y += v.y * d

Alright thanks for the reply. Now I just have to read up on whatever that means...

If you want to find the distance along a straight line between two points, you can use Pythagoras' Theorem. Just figure out how far away the two points are on the X axis, how far apart they are on the Y axis, and solve for "c", like so:

Code:

---

x_diff = A.x - B.x;
y_diff = A.y - B.y;
distance = sqrt(x_diff*x_diff + y_diff*y_diff);

---

You can imagine what that is doing: you are forming a right-angle triangle with sides of length x_diff and y_diff, and then using Pythagoras' Theorem to find the length of the hypotenuse, the longest side of the triangle.

If you want to figure out the angle between one point and another, you can use a lot of complicated trigonometry (actually using the function atan2() really helps with this), but I really wouldn't recommend it. For one thing it's complicated, and for another you have the issue of representing straight up, which can be division by zero unless you're careful.

A far more reasonable way to represent the relationship between two points is to draw a vector between them. If you haven't heard of them before, a vector is an entity with a direction and a magnitude (a length). You can form a vector from A to B by using

Code:

---

v..x = B.x - A.x;
v.y = B.y - A.y;

---

You can think of this representing a direction, because it says that you'd need to travel v.x units along the X and v.y units along the Y in order to get to the destination; so it's a bit of a roundabout way of representing a direction, but a very useful one as it turns out.

If you really wanted to calculate the angle of the vector, you could do it at this point, but usually you don't need to. This is because the ratio between v.x and v.y tells you all you need to know about the direction. It says that if you move v.x units in the X direction, you have to move v.y units in the Y direction and vise versa. By keeping to this constraint you will eventually end up at the target point that you formed the vector towards (i.e. you always move in the direction of the vector, or the opposite direction if you move in the -X and -Y).

The thing is, it's a bit awkward to talk about "moving Y units when you move X units", because what if you don't want to move X units? The method of forming the vector that I described above will give you exactly the X offset you need to get to your destination point (and likewise for the Y); if you just moved that many units X and that many units Y you'd end up right on top of your destination, which is probably too fast. So what if you moved 1/2 X and 1/2 Y? Well, that would work, but you'd still move too fast, and the speed of the movement would depend on how far apart the objects were originally. Sometimes that's what you want, but not always.

That's why we like to use normalized vectors. I'll explain what they are in a moment, but first I have to say what the length of a vector is. We use the same idea as Pythagora's Theorem to calculate the length of a vector: the X component of the vector defines one side of a right-angle triangle, the Y component defines the other, and the hypotenuse is the length of the vector. Essentially the Pythagora's Theorem method which calculates the distance between two points is first forming a vector and then taking the length of it, though perhaps you didn't notice that at the time. :)

A normalized vector is just a vector with length one. You can calculate this pretty easily by

Code:

---

int length(vector v) {
    return sqrt(v.x*v.x + v.y*v.y);
}

// create a vector
v.x = 5.2;
v.y = -2.0;

// normalize the vector
len = length(v);
v.x /= len;
v.y /= len;

---

Essentially you calculate the length of the vector, and then divide each of its components by that length. The really nice thing about normalized vectors is that they're a lot more consistent. If you created a vector between two nearby points, their vector might be very short, and another vector between distant points might have much longer length. Trying to move v.x units along the X axis would give decidedly different results in these cases. But if you normalize the vector first, then v.x units along the X axis is exactly the same speed, no matter how far apart the original points were.

[Note that this works even if the points are extremely close together, so that the vector has length, say, 0.01. Then you'd divide each component by 0.01, which makes them larger and yields a vector with length 1.]

Anyway, if you're interested in learning more about this you could always get a beginning book on computer graphics or linear algebra. I really wish I had done so when I was first doing this sort of thing on my own. :)

Have fun, and do ask more questions and post your code when you feel it is ready to have other people look at it -- you'll probably get some comments and suggestions which might be useful . . . .

I'm not sure on how to explain vectors without things ending up more confusing than they already are, I'm not a very good tutor :)
If you want to know more you can google for vector math tutorials or something, but I can give some basic explanations on how to do this special case.

Think of a vector as an imaginary line going from any point A to any point B.
In a 2d system you could have a vector from x=2,y=2 to x=3,y=3. This is known as a free vector.
Then there are also bound vectors, where point A is always 0,0 (or 0,0,0 for 3d, etc). To define a bound vector you only need to know the end point because you know it will always start at 0,0
(note: I'm not exactly sure they are called free and bound vectors in English but I think they are. For the sake of this post just pretend that they are :))

To get the length of a bound 2d vector you take the square root of (x*x + y*y)
A vector with a length of 1 is called a normalized vector, or a unit vector.
To create a unit vector from any given bound vector all you need to do is divide x and y by the length of the vector. Example

Code:

---

struct Vector2 // I named the vector struct Vector2 to indicate it's a 2d vector
{
  float x, y;
};
struct Vector2 v, unit_vector;
float v_length = sqrtf(v.x*v.x + v.y*v.y);
unit_vector.x = v.x / v_length;
unit_vector.y = v.y / v_length;

---

If v was a vector from 0,0 to 2,2 then unit_vector would be a vector from 0,0 to roughly 0.7, 0.7
It still points in the same direction but now has a length of 1

Now if we have 2 points like you asked about in the OP (let's call them A and B), and we want to get a vector between them to know the direction from A to B we can do this

Code:

---

struct Vector2 direction;
/* if we just take the positions directly we would
 * end up with a free vector from A.x, A.y to B.x, B.y
 * To make it a bound vector (starting at 0,0) we have
 * to subtract A from both the starting and end point.
 * (A-A=0,0) */
direction.x = B.x - A.x;
direction.y = B.y - A.y;

---

Now we know the direction from A to B, and we also know how to calculate the distance (length) between them.

If we now want to move A towards B with a distance of 10 pixels per step, we would to these calculations:

Code:

---

/* refer to the previous sample on how to normalize a vector */
Vector2 unit_vector = NormalizeVector(direction);
/* assume the unit vector turns out to be 0.44, 0.89
 * Now we add the vector * distance (10) to point A's position */
A.x += unit_vector.x * distance;
A.y += unit_vector.y * distance;

---

Now we would end up moving point A 4.4 pixels along the x axis (10*0.44) and 8.9 pixels along the y axis (10*0.89) towards point B

I hope this was understandable. Like I said, I'm not very good at explaining things. Especially not in English :)

Here is a small example of a console app where 3 "points" are chasing each other.
The code is C++ and uses windows-specific APIs but hopefully the logic will be understandable even if you can't run it.
C++ pastebin - collaborative debugging tool

Edit:
Bah! Dwks types faster than me :)

I might type faster but you managed to cover more ground. :)

I just thought I'd mention one other thing. You can use vectors for a number of different things. In physics the position of an object is actually a vector from the origin to some point in space; so when you say that an object is at (5,3), what you really mean is that starting from (0,0) and traveling 5 units in the X and 3 units in the Y will get you to the place you want to be.

It becomes more interesting as you use vectors to represent velocity (as I believe _Mike has done with that example). Again, a speed of 4 units in the X and -2 units in the Y can really just be thought of as another type of vector. Every frame, or second, or whatever the position vector changes by this amount. And you can even go another level beyond this and use vectors to represent acceleration. Every time period the *velocity* vector changes by some given amount.

Just food for thought . . . .

Quote:

---

Originally Posted by dwks

It becomes more interesting as you use vectors to represent velocity (as I believe _Mike has done with that example)

---

Aye I guess you can call it velocity if you think of it as distance per an unspecified amount of time.
In my first draft I had written "a speed of 10 pixels per second" instead of "distance per step" but then I realized it would add unneeded complication to the example by having to calculate time deltas to compensate for the code not being called exactly once every second :)

Thanks so much for the help guys I totally get it. You guys would make really good math teachers.

Vectors are an integral part of any graphics programming. You would do yourself good to study them and learn the various vector operations like the back of your hand.