Algorithm for particles targeting

Question

I'm building a particles systems, one of the features I'd like to add is a "target" feature. What I want to be able to do is set an X,Y target for each particle and make it go there, not in a straight line though (duh), but considering all other motion effects being applied on the particle.

The relevant parameters my particles have:

• posx, posy : inits with arbitrary values. On each tick speedx and speedy are added to posx and posy respectively
• speedx, speedy : inits with arbitrary values. On each tick accelx and accely are added to speedx speedy respectively if any)
• accelx, accely : inits with arbitrary values. With current implementation stays constant through the lifespan of the particle.
• life : starts with an arbitrary value, and 1 is reduced with each tick of the system.

What I want to achieve is the particle reaching the target X,Y on it's last life tick, while starting with it's original values (speeds and accelerations) so the motion towards the target will look "smooth". I was thinking of accelerating it in the direction of the target, while recalculating the needed acceleration force on each tick. That doesn't feel right though, would love to hear some suggestions.

Answer 1

For a "smooth" motion, you either keep the speed constant, or the acceleration constant, or the jerk constant. That depends on what you call "smooth" and what you call "boring". Let's keep the acceleration constant.

From a physics point of view, you have this constraint

targetx - posx = speedx*life + 1/2accelx * life * life
targety - posy = speedy*life + 1/2accely * life * life

Because distance traveled is v*t+1/2at^2. Solving for the unknown acceleration gives

accelx = (targetx - posx - speedx*life) / (1/2 * life * life)
accely = (targety - posy - speedy*life) / (1/2 * life * life)

(For this to work speedy must be in the same unit as time, for example "pixels per tick" and life is a number of "ticks". )

Since you use euler integration, this will not bring the particle exactly on the target. But I doubt it'll be a real issue.

Works like a charm:

Another picture, this time with constant jerk

jerkx = 6.0f*(targetx-x - speedx*life - 0.5f*accelx*life*life)/(life*life*life) 

Looks like there is another bend in the curve...

Java code

import java.awt.Color;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;

@SuppressWarnings("serial")
public class TargetTest extends JPanel {

  List<Particle> particles = new ArrayList<Particle>();
  float tx, ty; // target position

  public TargetTest() {

    tx = 400;
    ty = 400;
    for (int i = 0; i < 50; i++)
      particles.add(new Particle(tx / 2 + (float) (tx * Math.random()), ty / 2
          + (float) (ty * Math.random())));

    this.setPreferredSize(new Dimension((int) tx * 2, (int) ty * 2));
  }

  @Override
  protected void paintComponent(Graphics g1) {
    Graphics2D g = (Graphics2D) g1;
    g.setColor(Color.black);
    // comment next line to draw curves
    g.fillRect(0, 0, getSize().width, getSize().height);

    for (Particle p : particles) {
      p.update();
      p.draw(g);
    }
  }

  public static void main(String[] args) {
    EventQueue.invokeLater(new Runnable() {
      public void run() {
        JFrame f = new JFrame("Particle tracking");
        final TargetTest world = new TargetTest();
        f.add(world);

        // 1 tick every 50 msec
        new Timer(50, new ActionListener() {
          @Override
          public void actionPerformed(ActionEvent arg0) {
            world.repaint();
          }
        }).start();

        f.pack();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.setVisible(true);
      }
    });
  }

  class Particle {
    float x, y;// position
    float vx, vy;// speed
    float ax, ay;// acceleration
    float jx, jy;// jerk

    int life; // life

    float lastx, lasty;// previous position, needed to draw lines
    int maxlife; // maxlife, needed for color

    public Particle(float x, float y) {
      this.x = x;
      this.y = y;
      // pick a random direction to go to
      double angle = 2 * Math.PI * Math.random();
      setVelocity(angle, 2);// 2 pixels per tick = 2 pixels per 50 msec = 40
                            // pixels per second

      // the acceleration direction 'should' be close to being perpendicular to
      // the speed,
      // makes it look interesting, try commenting it if you don't believe me ;)
      if (Math.random() < 0.5)
        angle -= Math.PI / 2;
      else
        angle += Math.PI / 2;
      // add some randomness
      angle += (Math.random() - 0.5) * Math.PI / 10;
      setAcceleration(angle, 0.1);

      life = (int) (100 + Math.random() * 100);
      maxlife = life;
      lastx = x;
      lasty = y;
    }

    public void setVelocity(double angle, double speed) {
      vx = (float) (Math.cos(angle) * speed);
      vy = (float) (Math.sin(angle) * speed);
    }

    public void setAcceleration(double angle, double speed) {
      ax = (float) (Math.cos(angle) * speed);
      ay = (float) (Math.sin(angle) * speed);
    }

    @SuppressWarnings("unused")
    private void calcAcceleration(float tx, float ty) {
      ax = 2 * (tx - x - vx * life) / (life * life);
      ay = 2 * (ty - y - vy * life) / (life * life);
    }

    private void calcJerk(float tx, float ty) {
      jx = 6.0f * (tx - x - vx * life - 0.5f * ax * life * life)
          / (life * life * life);
      jy = 6.0f * (ty - y - vy * life - 0.5f * ay * life * life)
          / (life * life * life);
    }

    public void update() {
      lastx = x;
      lasty = y;
      if (--life <= 0)
        return;

      // calculate jerk
      calcJerk(tx, ty);
      // or uncomment and calculate the acceleration instead
      // calcAcceleration(tx,ty);

      ax += jx;
      ay += jy;// increase acceleration

      vx += ax;
      vy += ay;// increase speed

      x += vx;
      y += vy;// increase position
    }

    public void draw(Graphics2D g) {
      if (life < 0)
        return;
      g.setColor(new Color(255 - 255 * life / maxlife, 
            255 * life / maxlife,0));
      g.drawLine((int) x, (int) y, (int) lastx, (int) lasty);
    }
  }
}

Answer 2

You could consider that your particule is initially "applied" a force (Fv) which corresponds to the inertia it has from its initial velocity. Then you apply an attraction force (Fa) that is proportionnal to the distance to the target. You can then sum those forces, and given a particle weight, you can deduce acceleration to consider at time t.

Fa(t) = (Constant / distanceToTarget(t))* [direction to target]
Fv(t) = [initialForce] * dampening(t)
a(t) = (Fa(t) + Fv(t)) / mass

Then you can compute v(t) from v(t-1) and a(t) as usual

Edit: I forgot the life of the particle can directly be computed from the distance to the target (for instance: life = distance / initialDistance will go from 1 at start and approch 0 near the target)

Edit: You could think of this as a kind of magnet. See wikipedia for the force formula.

Answer 3

one kind of movement you can use is the uniform acceleration http://en.wikipedia.org/wiki/Acceleration#Uniform_acceleration

Your particles will make a smoth move towards the target and hit it with rather high velocity

For meeting your stated criteria, do the following:

• calculate the distance from the target, the particle will have at the end of it's life time, assuming the speed doesn't change from now on.

• this distance put in this equation: http://upload.wikimedia.org/math/6/2/9/6295e1819e6bfe1101506caa4b4ec706.png and solve it for a

• use this as your acceleration

• Do this seperately for x and y