001package algs61; // section 6.1 002import stdlib.*; 003import java.awt.Color; 004import algs24.MinPQ; 005/* *********************************************************************** 006 * Compilation: javac CollisionSystem.java 007 * Execution: java CollisionSystem N (N random particles) 008 * java CollisionSystem < input.txt (from a file) 009 * 010 * Creates N random particles and simulates their motion according 011 * to the laws of elastic collisions. 012 * 013 *************************************************************************/ 014 015public class CollisionSystem { 016 private MinPQ<Event> pq; // the priority queue 017 private double t = 0.0; // simulation clock time 018 private final double hz = 0.5; // number of redraw events per clock tick 019 private final Particle[] particles; // the array of particles 020 021 // create a new collision system with the given set of particles 022 public CollisionSystem(Particle[] particles) { 023 this.particles = particles; 024 } 025 026 // updates priority queue with all new events for particle a 027 private void predict(Particle a, double limit) { 028 if (a == null) return; 029 030 // particle-particle collisions 031 for (Particle particle : particles) { 032 double dt = a.timeToHit(particle); 033 if (t + dt <= limit) 034 pq.insert(new Event(t + dt, a, particle)); 035 } 036 037 // particle-wall collisions 038 double dtX = a.timeToHitVerticalWall(); 039 double dtY = a.timeToHitHorizontalWall(); 040 if (t + dtX <= limit) pq.insert(new Event(t + dtX, a, null)); 041 if (t + dtY <= limit) pq.insert(new Event(t + dtY, null, a)); 042 } 043 044 // redraw all particles 045 private void redraw(double limit) { 046 StdDraw.clear(); 047 for (Particle particle : particles) { 048 particle.draw(); 049 } 050 StdDraw.show(20); 051 if (t < limit) { 052 pq.insert(new Event(t + 1.0 / hz, null, null)); 053 } 054 } 055 056 057 /* ****************************************************************************** 058 * Event based simulation for limit seconds 059 ********************************************************************************/ 060 public void simulate(double limit) { 061 062 // initialize PQ with collision events and redraw event 063 pq = new MinPQ<>(100000); 064 for (Particle particle : particles) { 065 predict(particle, limit); 066 } 067 pq.insert(new Event(0, null, null)); // redraw event 068 069 070 // the main event-driven simulation loop 071 while (!pq.isEmpty()) { 072 073 // get impending event, discard if invalidated 074 Event e = pq.delMin(); 075 if (!e.isValid()) continue; 076 Particle a = e.a; 077 Particle b = e.b; 078 079 // physical collision, so update positions, and then simulation clock 080 for (Particle particle : particles) 081 particle.move(e.time - t); 082 t = e.time; 083 084 // process event 085 if (a != null && b != null) a.bounceOff(b); // particle-particle collision 086 else if (a != null && b == null) a.bounceOffVerticalWall(); // particle-wall collision 087 else if (a == null && b != null) b.bounceOffHorizontalWall(); // particle-wall collision 088 else if (a == null && b == null) redraw(limit); // redraw event 089 090 // update the priority queue with new collisions involving a or b 091 predict(a, limit); 092 predict(b, limit); 093 } 094 } 095 096 097 /* *********************************************************************** 098 * An event during a particle collision simulation. Each event contains 099 * the time at which it will occur (assuming no supervening actions) 100 * and the particles a and b involved. 101 * 102 * - a and b both null: redraw event 103 * - a null, b not null: collision with vertical wall 104 * - a not null, b null: collision with horizontal wall 105 * - a and b both not null: binary collision between a and b 106 * 107 *************************************************************************/ 108 private static class Event implements Comparable<Event> { 109 public final double time; // time that event is scheduled to occur 110 public final Particle a, b; // particles involved in event, possibly null 111 public final int countA, countB; // collision counts at event creation 112 113 114 // create a new event to occur at time t involving a and b 115 public Event(double t, Particle a, Particle b) { 116 this.time = t; 117 this.a = a; 118 this.b = b; 119 if (a != null) countA = a.count(); 120 else countA = -1; 121 if (b != null) countB = b.count(); 122 else countB = -1; 123 } 124 125 // compare times when two events will occur 126 public int compareTo(Event that) { 127 if (this.time < that.time) return -1; 128 else if (this.time > that.time) return +1; 129 else return 0; 130 } 131 132 // has any collision occurred between when event was created and now? 133 public boolean isValid() { 134 if (a != null && a.count() != countA) return false; 135 if (b != null && b.count() != countB) return false; 136 return true; 137 } 138 139 } 140 141 142 143 /* ****************************************************************************** 144 * Sample client 145 ********************************************************************************/ 146 public static void main(String[] args) { 147 //args = new String[]{ "20" }; 148 //StdIn.fromFile ("data/brownian.txt"); 149 StdIn.fromFile ("data/diffusion.txt"); 150 151 // remove the border 152 StdDraw.setXscale(1.0/22.0, 21.0/22.0); 153 StdDraw.setYscale(1.0/22.0, 21.0/22.0); 154 155 // turn on animation mode 156 StdDraw.show(0); 157 158 // the array of particles 159 Particle[] particles; 160 161 // create N random particles 162 if (args.length == 1) { 163 int N = Integer.parseInt(args[0]); 164 particles = new Particle[N]; 165 for (int i = 0; i < N; i++) particles[i] = new Particle(); 166 } 167 168 // or read from standard input 169 else { 170 int N = StdIn.readInt(); 171 particles = new Particle[N]; 172 for (int i = 0; i < N; i++) { 173 double rx = StdIn.readDouble(); 174 double ry = StdIn.readDouble(); 175 double vx = StdIn.readDouble(); 176 double vy = StdIn.readDouble(); 177 double radius = StdIn.readDouble(); 178 double mass = StdIn.readDouble(); 179 int r = StdIn.readInt(); 180 int g = StdIn.readInt(); 181 int b = StdIn.readInt(); 182 Color color = new Color(r, g, b); 183 particles[i] = new Particle(rx, ry, vx, vy, radius, mass, color); 184 } 185 } 186 187 // create collision system and simulate 188 CollisionSystem system = new CollisionSystem(particles); 189 system.simulate(10000); 190 } 191 192}