15 replies to this topic

[tom_mai78101]

I have a dot in a blank screen. I have calculated the dot's coordinates (relative location from source component) and the mouse coordinates (after the user clicks on the screen). The constant speed of the dot is fixed at 1 pixels per tick, 60 ticks per second.

Now, there are two points in the screen. You can imagine a invisible line connecting the two points, and the dot traverses on this imaginary line from its source coordinates to the target coordinates.

What math should I use to move the dot along the line in a more linear way?

I have here a crude path movement for the dot, now basked in your glorifying eyes:

public void tick(MouseInputHandler input)
{
  target = input.mousePosition;
  if (target == null)
   return;
  int direction = 0;
  if (position.x > target.x)
   direction = -1;
  else
   direction = 1;
  if (position.x == target.x)
   direction = 0;

  position.x += direction;

  if (position.y > target.y)
   direction = -1;
  else
   direction = 1;
  if (position.y == target.y)
   direction = 0;
  position.y += direction;
}

If possible, where can I improve? And where can I learn more about path movement algorithms? Thanks in advance.

[KazenoZ]

You can use trigonometry to calculate the exact direction you need to move at.
Consider this code:

double angle = atan2(target.y-position.y, target.x-position.x);
double xVel = speed*cos(angle);
dboule yVel = speed*sin(angle);

And then you simply add the velocity values from the last code to the position of your point.

position.x += xVel;
position.y += yVel;

Hope this is what you meant and that it answers your question =)

[RulerOfNothing]

Actually, if you use vector math, you can avoid using trigonometry entirely. You can do this:

double xVel=target.x-position.x;
double yVel=target.y-position.y;
double mag=sqrt(xVel*xVel+yVel*yVel);
xVel=xVel*speed/mag;
yVel=yVel*speed/mag;

and then add the xVel and yVel to your position like in KazenoZ's example.

[tom_mai78101]

To KazenoZ:

The dot keeps jumping around. When the dot moves, it jerks its way in straight lines, instead of going diagonally. I don't know why, but when I do logging, it shows that the values for xVel and yVel jumps without staying put in one direction.

--------------------


To RulerOfNothing:

This is what I've got:



In the console, it reveals that xVel and yVel keeps jumping around, positive to negative and back. When it's running, the dot you see in the black screen jumps around quite a lot, and the distance increases when the speed increases. It's pretty blurry.

[BeerNutts]

If you use RulerOfNothing's code, you cannot continually re-calculate the velocity every tick. Calculate the velocity once, and then use the velocity until the dot reach the target. Or, only recalculate when the target dot moves.

In Fact RulerOfNothing's code is a bit misleading. It should be:


double xDist=target.x-position.x;
double yDist=target.y-position.y;
double mag=sqrt(xDist*xDist+yDist*yDist);
double xVel=xDist*speed/mag;
double yVel=yDist*speed/mag;



Although, I personally prefer the trig method.

[medv4380]

It's jumping around due to the loss of procession. You need to put something in so that it gets to exactly the pixel you want it to or gets close to it. If you use Doubles all the way through you'll get it to move in prefect diagonals but due to the speed never getting it perfectly correct it over shoots on the last frame of the calculation. This results in it having to turn around and go the other direction which it over shoots again and again. Your original code had this correct because it was using raw integers but could result in it going faster then 1 pixel per frame since going 1 up and 1 accost would be a speed of sqrt(2) 1.4 pixels when it moved diagonal but 1 pixel when it moved in only one direction. Even with Integers if you use the donated formulas it will jump around due to over shooting.


Something like this should work

				    if (PointX < PointDestX && (PointX + xVel) > PointDestX) {
					    PointX = PointDestX;
				    } else if (PointX != PointDestX) {
					    PointX += xVel;
				    }
				    if (PointY < PointDestY && (PointY + yVel) > PointDestY) {
					    PointY = PointDestY;
				    } else if (PointY != PointDestY) {
					    PointY += yVel;
				    }

Personally I don't like the way you're passing in the MouseInputHandeler every time. I'm not sure how the rest of your code looks ether but I have my susspisions based on you passing in the Mouse Handeler.

Something like this may help you.

import java.awt.Canvas;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.WindowEvent;
import java.awt.event.WindowListener;
import javax.swing.JFrame;
public class Test extends JFrame implements WindowListener, MouseListener {
    public static void main(String args[]) {
	    Test t = new Test();
    }
    Canvas canvas;
    double speed = 1;
    double PointX = 100;
    double PointY = 100;
    double PointDestX = 200;
    double PointDestY = 200;
    volatile boolean isRunning = true;
    Thread animationThread;
    public Test() {
	    super("Test");
	    animationThread = new Thread(new animation());
	    setSize(320, 240);
	    canvas = new myCanvas();
	    add(canvas);
	    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	    addWindowListener(this);
	    canvas.addMouseListener(this);
	    setVisible(true);
    }
    @Override
    public void windowOpened(WindowEvent e) {
	    animationThread.start();
    }
    @Override
    public void windowClosing(WindowEvent e) {
	    isRunning = false;
    }
    @Override
    public void mouseClicked(MouseEvent e) {
	    PointDestX = e.getX();
	    PointDestY = e.getY();
    }
    class animation implements Runnable {
	    @Override
	    public void run() {
		    while (isRunning) {
			    canvas.repaint();
			    try {
				    /*
				    int direction = 0;
				    if (PointX > PointDestX) {
				    direction = -1;
				    } else {
				    direction = 1;
				    }
				    if (PointX == PointDestX) {
				    direction = 0;
				    }
				   
				    PointX += direction;
				   
				    if (PointY > PointDestY) {
				    direction = -1;
				    } else {
				    direction = 1;
				    }
				    if (PointY == PointDestY) {
				    direction = 0;
				    }
				    PointY += direction;
					 */
				   
				    double xVel = PointDestX - PointX;
				    double yVel = PointDestY - PointY;
				    double mag = Math.sqrt(xVel * xVel + yVel * yVel);
				    xVel = xVel * speed / mag;
				    yVel = yVel * speed / mag;
				    //double xDist = PointDestX - PointX;
				    //double yDist = PointDestY - PointY;
				    //double mag = Math.sqrt(xDist * xDist + yDist * yDist);
				    //double xVel = (int) (xDist * 2 / mag);
				    //double yVel = (int) (yDist * 2 / mag);
				    if (PointX < PointDestX && (PointX + xVel) > PointDestX) {
					    PointX = PointDestX;
				    } else if (PointX != PointDestX) {
					    PointX += xVel;
				    }
				    if (PointY < PointDestY && (PointY + yVel) > PointDestY) {
					    PointY = PointDestY;
				    } else if (PointY != PointDestY) {
					    PointY += yVel;
				    }
				    Thread.sleep(10);
			    } catch (InterruptedException ex) {
			    }
		    }
	    }
    }
    class myCanvas extends Canvas {
	    Image offscreen = null;
	    Graphics offgc;
	    @Override
	    public void paint(Graphics g) {
		    if (offscreen == null) {
			    offscreen = createImage(getWidth(), getHeight());
			    offgc = offscreen.getGraphics();
		    } else if (offscreen.getHeight(canvas) != getHeight() | offscreen.getWidth(canvas) != getWidth()) {
			    offscreen = createImage(getWidth(), getHeight());
			    offgc = offscreen.getGraphics();
		    }
		    offgc.setColor(Color.black);
		    offgc.fillRect(0, 0, this.getWidth(), this.getHeight());
		    offgc.setColor(Color.white);
		    offgc.fillRect((int) PointX, (int) PointY, 1, 1);
		    g.drawImage(offscreen, 0, 0, this);
	    }
	    @Override
	    public void update(Graphics g) {
		    paint(g);
	    }
    }
/*unused handlers go here*/
}

I even have problems with this code since I should be doubling up on the points when they are being changed vs when they are being drawn so that it can work on two processors properly but that would take more time then I'm willing to do. However this allows the logic to be run without having the mouse object passed to it every single time. I'm also using Thread.sleep to control the frames and there are better ways of doing that when you're using something like the lwjgl instead of a canvas. Then again I like having more control over my threads since tossing them into a thread pool or scheduler causes too much blocking which will slow it down on code this small.

[Álvaro]

EDIT: I am too sick of the behavior of the code tags to repeat what I just typed. Sorry.

[tom_mai78101]

I'm passing my MouseInputHandler because I need the mouse click positions.

New information:

I found out that my dot moves vertically and horizontally, but never diagonally when using any of the methods mentioned. I shall try to refine this. All in all, my dot moves in an unnatural way, I'm not satisfied with it, but if I need to make it move more smoothly, it would require implementing the A* algorithm or something, which I'm not ready to tackle it yet.

One last thing, how do you check and stop updating the X and Y if the dot starts to jump back and forth? The only (bad) way is to add a lot of if...else conditions.

===================================================

@alvaro, is this your code?

double xDist = target.x - position.x;
  double yDist = target.y - position.y;
  double mag = sqrt(xDist * xDist + yDist * yDist);
  if(mag >= speed)
  {
   double xVel = xDist * speed / mag;
   double yVel = yDist * speed / mag;
   position.x += xVel;
   position.y += yVel;
  }
  else
  {
   position.x = target.x;
   position.y = target.y;
  }
//-----------------------------------------------------------------------------------
  Vector2D dist = target - position;
  double mag = length(dist);
  if(mag >= speed)
   position += dist * (speed / mag);
  else
   position = target;

[Álvaro]

@alvaro, is this your code?

Yes, it is! How did you get it? When I posted it I saw some garbled mess and I couldn't see how to recover it...

[Álvaro]

I found out that my dot moves vertically and horizontally, but never diagonally when using any of the methods mentioned. I shall try to refine this.

That is a bug. Perhaps you are using `int' in some place where you should be using `double'?

All in all, my dot moves in an unnatural way, I'm not satisfied with it, but if I need to make it move more smoothly, it would require implementing the A* algorithm or something, which I'm not ready to tackle it yet.

No, A* has nothing to do with smooth movement. Figure out exactly what your code is doing wrong and fix it.

[tom_mai78101]

That is a bug. Perhaps you are using `int' in some place where you should be using `double'?

Nope. On second thought, I shouldn't have used "double" in the first place. Pixel manipulation don't need to use double, right? I'm using "int" variables to calculate the simple pathing in a one-dimensional array, so it wouldn't be wise to use a double as an array iterator.

I'll try to find my logic errors. I'm pretty sure calculating xVel and yVel are done at the same pace, and not calculating the results separately.

Or better yet, I will upload my source code here, archived into ZIP, exported from Eclipse. (Hosted at Mediafire)

[Álvaro]

Do your computations using doubles and then round only when you need to convert to a pixel. In general, things work much better when you keep your computations independent from the way you'll display the results.

[BeerNutts]

That is a bug. Perhaps you are using `int' in some place where you should be using `double'?

Nope. On second thought, I shouldn't have used "double" in the first place. Pixel manipulation don't need to use double, right? I'm using "int" variables to calculate the simple pathing in a one-dimensional array, so it wouldn't be wise to use a double as an array iterator.

I'll try to find my logic errors. I'm pretty sure calculating xVel and yVel are done at the same pace, and not calculating the results separately.

Or better yet, I will upload my source code here, archived into ZIP, exported from Eclipse. (Hosted at Mediafire)

Tom, you'll screw yourself if you only use int. Just use doubles or else your calculations will never be very precise, and you'll miss badly. Often time, your pixel location during one step will be different from the previous step. For example, a velocity of 1.5, moving from 0,0 to 10,0:
Frame 1: x = 1.5 (draw at 1)
Frame 2: x = 3.0 (draw at 3)
Frame 3: x = 4.5 (draw at 4)
Frame 4: x = 6.0 (draw at 6)
Frame 5: x = 7.5 (draw at 7)
Frame 6: x = 9.0 (draw at 9)
Frame 7: x = 10.0 (draw at 10)

If you use int, then your velocity will be rounded down to 1, and it will take 10 frames when it should take 7.

Again, I prefer the trig method when doing this, but you can use which ever you want.

One other thing. There's obviously a bug in your code if you can't move diagonally. Each frame you should be able to change x and y location.

[tom_mai78101]

Unfortunately, the diagonal velocity is less than 1 (velocity vector = 1/sqrt(starting point and finishing point)), which when converted to "int" for the pixel coordinates, it is misplaced as 0. Same goes for all of the calculations done per frame.

When using the trigonometric method and the vector method, all of the xVel and yVel ranges from 0.4 to 0.9. If I increase my speed, I would get a more accurate range of 1.0 to 1.5, but it causes the dot pixel to jump around. Other than the jumping, the direct path movement for speed more than 5 is correct.

Due to the way I set my speed to 1 pixel per tick, 60 ticks per second, I have to click multiple times in order for the program is obtain a number larger than 1.0, which by that point, the dot then moves.

I even tried adding a new thread to do the calculations in case the reaction time is less than par, but then it complicates things; I have discarded it.

Here's my next theory:

What if I add this:

   xa -= (xm * Math.cos(rot) + ym * Math.sin(rot)) * speed;
   ya -= (ym * Math.cos(rot) - xm * Math.sin(rot)) * speed;

Where rot is the angle from Point 2 to Point 1 in radians, xm and ym are the directional vectors for Point 1 and Point 2, xm for X axis, ym for Y axis, and the xa and ya are the acceleration for the dot.

[RulerOfNothing]

This is why you should use floating point for your positions, and only convert to ints when you want to render something.

[tom_mai78101]

I credit C++ Programming Forum members, dwks and _Mike, for giving me the information I lack in my linear algebra class, or I should blame my school for teaching the lessons up to subspaces before we even reached vectors for this semester's linear algebra course and gave us a winter vacation. The source for the information is linked here.

I credit RulerOfNothing in his very last post for giving me the inspiration to rewrite my program from scratch, and from there I finally took notice of a bug when comparing the new project with my old in Subversion.

This time, from dwks, I calculate the two points by using normal vectors and distances, along with doing the arithmetic entirely in double. I revised my Dot class by not using the java.awt.Point class, and added a few more functions to separate the logic in a more versatile way.

Here is my results:

public class Dot implements Tickable {
public double xPosition = 0;
public double yPosition = 0;
public double xTarget = 0;
public double yTarget = 0;
public double xDist = 0;
public double yDist = 0;
public void tick() {
  // Setting up a vector.
  xDist = xTarget - xPosition;
  yDist = yTarget - yPosition;
  // Normalize the vector.
  double length = Math.sqrt(xDist * xDist + yDist * yDist);
  xDist /= length;
  yDist /= length;
}
public void update() {
  if (Math.abs(xTarget - xPosition) < 1)
   xDist = 0;
  if (Math.abs(yTarget - yPosition) < 1)
   yDist = 0;
  xPosition += xDist;
  yPosition += yDist;
  System.out.println(xPosition + " " + yPosition + "	 " + xDist + " " + yDist + "	" + xTarget + " " + yTarget);
}
public void render(int[] pixels, int offset, int width, int height) {
  if (xPosition < 0 || xPosition >= width)
   return;
  if (yPosition < 0 || yPosition >= height)
   return;
  pixels[(((int) xPosition) + offset) + ((int) yPosition) * width] = -1;
}
public void getInput(MouseInputHandler i) {
  if (xTarget == -1 || yTarget == -1)
   return;
  xTarget = i.X / Game.SCALE;
  yTarget = i.Y / Game.SCALE;

}
}

There is no trigonometric calculations involved, due to Math.atan2() function containing many special cases, and there's one of the special cases turning into the source of my logic error, resulting in a bug, as mentioned by most people in this thread. I didn't use plain vectors, due to me lacking information in this subject. In fact, I don't even know what it's called until I read the thread mentioned at the top of this post.

There is room for improvements in this class, but I'm pretty sure I have laid a nice looking foundation that works pretty nicely. All there's left to do, is to thank the people who helped in this thread.

In short, I have my problem solved, thanks to the people mentioned at the top.