001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
package algs61; // section 6.1
import stdlib.*;
import java.awt.Color;
import algs24.MinPQ;
/* ***********************************************************************
 *  Compilation:  javac CollisionSystem.java
 *  Execution:    java CollisionSystem N               (N random particles)
 *                java CollisionSystem < input.txt     (from a file)
 *
 *  Creates N random particles and simulates their motion according
 *  to the laws of elastic collisions.
 *
 *************************************************************************/

public class CollisionSystem {
  private MinPQ<Event> pq;        // the priority queue
  private double t  = 0.0;        // simulation clock time
  private final double hz = 0.5;        // number of redraw events per clock tick
  private final Particle[] particles;   // the array of particles

  // create a new collision system with the given set of particles
  public CollisionSystem(Particle[] particles) {
    this.particles = particles;
  }

  // updates priority queue with all new events for particle a
  private void predict(Particle a, double limit) {
    if (a == null) return;

    // particle-particle collisions
    for (Particle particle : particles) {
      double dt = a.timeToHit(particle);
      if (t + dt <= limit)
        pq.insert(new Event(t + dt, a, particle));
    }

    // particle-wall collisions
    double dtX = a.timeToHitVerticalWall();
    double dtY = a.timeToHitHorizontalWall();
    if (t + dtX <= limit) pq.insert(new Event(t + dtX, a, null));
    if (t + dtY <= limit) pq.insert(new Event(t + dtY, null, a));
  }

  // redraw all particles
  private void redraw(double limit) {
    StdDraw.clear();
    for (Particle particle : particles) {
      particle.draw();
    }
    StdDraw.show(20);
    if (t < limit) {
      pq.insert(new Event(t + 1.0 / hz, null, null));
    }
  }


  /* ******************************************************************************
   *  Event based simulation for limit seconds
   ********************************************************************************/
  public void simulate(double limit) {

    // initialize PQ with collision events and redraw event
    pq = new MinPQ<>(100000);
    for (Particle particle : particles) {
      predict(particle, limit);
    }
    pq.insert(new Event(0, null, null));        // redraw event


    // the main event-driven simulation loop
    while (!pq.isEmpty()) {

      // get impending event, discard if invalidated
      Event e = pq.delMin();
      if (!e.isValid()) continue;
      Particle a = e.a;
      Particle b = e.b;

      // physical collision, so update positions, and then simulation clock
      for (Particle particle : particles)
        particle.move(e.time - t);
      t = e.time;

      // process event
      if      (a != null && b != null) a.bounceOff(b);              // particle-particle collision
      else if (a != null && b == null) a.bounceOffVerticalWall();   // particle-wall collision
      else if (a == null && b != null) b.bounceOffHorizontalWall(); // particle-wall collision
      else if (a == null && b == null) redraw(limit);               // redraw event

      // update the priority queue with new collisions involving a or b
      predict(a, limit);
      predict(b, limit);
    }
  }


  /* ***********************************************************************
   *  An event during a particle collision simulation. Each event contains
   *  the time at which it will occur (assuming no supervening actions)
   *  and the particles a and b involved.
   *
   *    -  a and b both null:      redraw event
   *    -  a null, b not null:     collision with vertical wall
   *    -  a not null, b null:     collision with horizontal wall
   *    -  a and b both not null:  binary collision between a and b
   *
   *************************************************************************/
  private static class Event implements Comparable<Event> {
    public final double time;         // time that event is scheduled to occur
    public final Particle a, b;       // particles involved in event, possibly null
    public final int countA, countB;  // collision counts at event creation


    // create a new event to occur at time t involving a and b
    public Event(double t, Particle a, Particle b) {
      this.time = t;
      this.a    = a;
      this.b    = b;
      if (a != null) countA = a.count();
      else           countA = -1;
      if (b != null) countB = b.count();
      else           countB = -1;
    }

    // compare times when two events will occur
    public int compareTo(Event that) {
      if      (this.time < that.time) return -1;
      else if (this.time > that.time) return +1;
      else                            return  0;
    }

    // has any collision occurred between when event was created and now?
    public boolean isValid() {
      if (a != null && a.count() != countA) return false;
      if (b != null && b.count() != countB) return false;
      return true;
    }

  }



  /* ******************************************************************************
   *  Sample client
   ********************************************************************************/
  public static void main(String[] args) {
    args = new String[]{ "20" };
    //StdIn.fromFile ("data/brownian.txt");
    //StdIn.fromFile ("data/diffusion.txt");

    // remove the border
    StdDraw.setXscale(1.0/22.0, 21.0/22.0);
    StdDraw.setYscale(1.0/22.0, 21.0/22.0);

    // turn on animation mode
    StdDraw.show(0);

    // the array of particles
    Particle[] particles;

    // create N random particles
    if (args.length == 1) {
      int N = Integer.parseInt(args[0]);
      particles = new Particle[N];
      for (int i = 0; i < N; i++) particles[i] = new Particle();
    }

    // or read from standard input
    else {
      int N = StdIn.readInt();
      particles = new Particle[N];
      for (int i = 0; i < N; i++) {
        double rx     = StdIn.readDouble();
        double ry     = StdIn.readDouble();
        double vx     = StdIn.readDouble();
        double vy     = StdIn.readDouble();
        double radius = StdIn.readDouble();
        double mass   = StdIn.readDouble();
        int r         = StdIn.readInt();
        int g         = StdIn.readInt();
        int b         = StdIn.readInt();
        Color color   = new Color(r, g, b);
        particles[i] = new Particle(rx, ry, vx, vy, radius, mass, color);
      }
    }

    // create collision system and simulate
    CollisionSystem system = new CollisionSystem(particles);
    system.simulate(10000);
  }

}