How can I avoid int-floor bias while mouse-targeting at small speeds?

Question

I have a simple algorithm for an object to follow the mouse pointer at a given max speed in Java. The crux of the algorithm is this:

// Set up displacement trackers for later.
// (These are used in another part of the algorithm, which rotates
//  the object to face along its path tangent with a moving average.)
double dx = 0, dy = 0;

// ... more code

// Find the angle of travel.
double angle = Math.atan2(m.y - target.getY(), m.x - target.getX());

// Set displacements with polar coordinate transforms.
dx = maxSpeed * Math.cos(angle);
dy = maxSpeed * Math.sin(angle);

// Now go there.
target.setX((int) Math.round(target.getX() + dx));
target.setY((int) Math.round(target.getY() + dy));

This is being run at 30 frames per second. Performance is not an issue.

The code runs fine at medium-to-large values of maxSpeed (5 and above are fine), but at really low values, the code causes the object to move only at certain angles. For example, at maxSpeed = 1, the target can only move at 45° angles.

---

Here's how I understand the problem:

Let maxSpeed equal 1. Therefore, because Math.sin and Math.cos always return values in the range [-1, 1], dy and dx will also be in the range [-1, 1]. When converting to an integer by rounding (because the target x and y positions are defined as int variables), the displacements are each rounded to either -1, 0, or 1, effectively limiting the possible movement to the same eight angles.

So, for example, if the object starts at (0, 0) and I position my mouse at (300, 100), the object will move first perfectly horizontally, then at an angle of -45°. I would like the object to move at an (approximately) constant angle, in an (approximately) straight line from the point of origin to the destination.

What would be the best way to do this, short of converting the underlying x and y coordinates to double values?

Answer 1

I feel like your last sentence is a major clue here. The more "correct" your solution gets, the more it will begin to approximate simply keeping track of the fractional parts of the position of the slow-moving object. Why not simply do that?

However, if that's absolutely impossible, there are always hacks.

Let's simplify the issue by reducing to one direction in one dimension, eliminating the integer part of the speed and the sign. You have an object moving at speed dx pixels per frame, dx is between 0.0 and 1.0.

You're doing a frame update. How many integral pixels do you move the object by? Zero or one?

We want to update not only with the correct probability, but also more or less smoothly (equally spaced). Moreover, since our aim is predictable visual behaviour we don't want to use randomness.

What we need if we can't use that is to keep track of the frame number, to know where we are in a sequence of equally spaced updates.

I think a good way to get "correct" results in a fairly easy way is something like this:

int last_frame = (int) (((double)(current_frame_number-1)) * dx);
int this_frame = (int) (((double)current_frame_number) * dx);
if( this_frame != last_frame ) {
   ++x; // advance one pixel
}

For any given (constant!) dx this should give the correct result. In practice, I expect it'd give a decent result with a dx that occasionally changes.

I've ignored the effects of frame number overflow, but they should be minimal (beware if you use subtraction instead of incrementing by one, though).

You'd have to add back in the integral parts, signs and the fact that there are two dimensions. If you move at speed (2.7,-0.4) per frame, then you always move (2,0) every frame, and you use the method above with dx=0.7 to determine whether you additionally move (1,0), and with dx=0.4 to determine whether you additionally move (0,-1).

However, although this was an interesting problem to consider theoretically, for practical implementation I'd really advise that you just use doubles for the underlying values. Besides the fact that the above is much harder to understand, it's also not guaranteed to be correct faced with a non-constant speed -- so it's both more complex and worse than the obvious solution.

Answer 2

I'm a tad rusty at Java, but maybe you could use vector math as opposed to trig?

double xPos, yPos; // should be initialized with the starting position and updated with each change in position - rounding on each update will accumulate errors and produce odd behavior as you described
// start of update
Vector2d direction = (new Vector2d(m.x - target.getX(), m.y - target.getY())).normalize(); // create unit vector in the direction of the target
Vector2d velocity = direction.scale(maxSpeed); // set the scalar speed in the direction of the target
xPos += velocity.x;
yPos += velocity.y; 
target.setX((int) xPos); // move (maxSpeed)*cos(angle) units in the x direction
target.setY((int) yPos); // move (maxSpeed)*sin(angle) units in the y direction
// end of update

...should work - faster than the trig approach :).