This page is a mirror of Tepples' nesdev forum mirror (URL TBD).

# simplest chain physics algorithm

Anybody know how to simplify this algorithm:

(x1,x2) are the coordinates of the object pulling the other object, and (x2,y2) are the coordinates of the object being pulled.

x2 - x1 = x
x / abs(x) = x_sign
x^2 = u
y2 - y1 = y
y / abs(x) = y_sign
y^2 = v
u / (u + v) = u
1 - u = v
sqrt(u) * x_sign + x1 = x2
sqrt(v) * y_sign + y1 = y2
Stepping back a little:
Are you trying to find the point along the line segment from A to B that is no farther than L units from A? If so, I'll share the algorithm I'm using in my own project:

1. Find angle (arctan2, implemented with some reflections, one division, and some comparisons)
2. Find unit vector in the same direction (table lookup)
3. Dot product vector from A to B with unit vector to find length
4. Subtract excess length times unit vector from B to find correction displacement
A simpler way to make a chain might be just to interpolate toward the target position, and not bother with normalized vectors or stuff like that. Something like this:

Code:
int x_diff = x1 - x2
int y_diff = y1 - y2
if (x_diff + y_diff > threshold)
{
x2 = x2 + (x_diff >> 3)
y2 = y2 + (y_diff >> 3)
}

The idea with this code is that every frame, if the (manhattan) distance threshold is exceeded, it will just take up 1/8 of the distance between them. This will repeat each frame until the distance has been reduced enough to be under the threshold specified. It would not be incredibly smooth, but if you need to do it a lot per frame it's a simpler operation. You can tweak this in a lot of ways, e.g. instead of using x_diff, you could just move a fixed number of pixels based on the sign of x_diff.

Also, x / abs(x) is something you'd use in math class, but it's not good in a program. Normally I think I would write this in C:
Code:
sign_x = (x > 0) ? 1 : -1
I thought of an easy way of estimating the distance between two points:

if: abs(x) > abs(y)
then: abs(x) + .5*abs(y) = distance
if: abs(x) < abs(y)
then: .5*abs(x) + abs(y) = distance
That's the Angband metric, with an octagonal boundary. If you want to swing smoothly in a circle, you'll need something more precise than that.
Doesn't seem to fare very bad with low numbers though:

Code:
8 8 8
8 8 7 7 7 8 8
8 8 7 7 6 6 6 7 7 8 8
8 7 7 6 6 5 5 5 6 6 7 7 8
8 7 6 5 5 4 4 4 5 5 6 7 8
8 7 6 5 4 4 3 3 3 4 4 5 6 7 8
8 7 6 5 4 3 2 2 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1 1 1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1 1 1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 2 2 3 4 5 6 7 8
8 7 6 5 4 4 3 3 3 4 4 5 6 7 8
8 7 6 5 5 4 4 4 5 5 6 7 8
8 7 7 6 6 5 5 5 6 6 7 7 8
8 8 7 7 6 6 6 7 7 8 8
8 8 7 7 7 8 8
8 8 8

Source. Removed the 9s to make the shape more obvious.

As for me, I just use a look-up table and adjust the coordinates if they're too large. I lose precision at long distances, but for what I need so far that has been enough.
But when you scale up the Angband metric beyond about 11 units, the sharp points at the eight corners of the boundary become clearer. Try sketching a radius 48 "circle" and see why it wouldn't necessarily work for a pendulum.
I thought of another method, that is as accurate as the "arctan" method, but only needs 1 LUT, as opposed to 2 LUTs.

Assuming that both x and y are positive, and x > y.

d = x * LUT(y/x*256)
LUT(n) = sqrt(1+(n/256)^2)

I also almost forgot, when the distance is less than the radius of the circle of rotation, the coordinates of the sprite can be left alone, letting them go through the other sprite.
tepples wrote:
But when you scale up the Angband metric beyond about 11 units, the sharp points at the eight corners of the boundary become clearer. Try sketching a radius 48 "circle" and see why it wouldn't necessarily work for a pendulum.

For a pendulum you wouldn't be using this kind of calculations anyway, you'd be using a sin/cos table and then just determine the point in the circle where you want the pendulum to be...

psycopathicteen wrote:
d = x * LUT(y/x*256)

That first multiplication and that division look awfully expensive...
Sik wrote:
For a pendulum you wouldn't be using this kind of calculations anyway, you'd be using a sin/cos table and then just determine the point in the circle where you want the pendulum to be...

psycopathicteen wrote:
d = x * LUT(y/x*256)

That first multiplication and that division look awfully expensive...

how about a hakmem - Minsky circle/ellipse

x' = x - (e * y)
y' = y + (e * x')

with e = 2 ^ -n

http://www.inwap.com/pdp10/hbaker/hakme ... ml#item149
I programmed it using the arctan method, and so far it works except for one problem. When the hanging sprite is swinging low, it slows to a stop, but when it is swinging high, it doesn't slow to a stop, nor has any decrease in altitude. I think it may be due to quantizing error. Should I bump up the LUT resolution from 8-bit to 16-bit?
Here is the finished chain physics demo.

I could probably use my code to resurrect this guy http://www.youtube.com/watch?v=9maoY2ZQiqk with controller input and real time physics. I could also use my dynamic animation engine for smoother sprite rotation.