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}