jbochi · February 25, 2013 01:35
diff --git a/collisions.html b/collisions.html
 <!DOCTYPE html>
 <html>
 <head>
  <meta http-equiv="content-type" content="text/html; charset=UTF-8">
  <title> - jsFiddle demo</title>
  
  <script type='text/javascript' src='/js/lib/dummy.js'></script>
  <link rel="stylesheet" type="text/css" href="/css/normalize.css">
  
  <link rel="stylesheet" type="text/css" href="/css/result-light.css">
  
  <style type='text/css'>
    #canvas {
    border:1px solid black;
    width: 500px;
    height: 250px;
 }
  </style>
  


 <script type='text/javascript'>//<![CDATA[ 
 window.onload=function(){
 //http://introcs.cs.princeton.edu/java/assignments/collisions.html
 //http://eloquentjavascript.net/appendix2.html

 function BinaryHeap(scoreFunction) {
    this.content = [];
    this.scoreFunction = scoreFunction;
 }

 BinaryHeap.prototype = {
    push: function (element) {
        // Add the new element to the end of the array.
        this.content.push(element);
        // Allow it to bubble up.
        this.bubbleUp(this.content.length - 1);
    },

    pop: function () {
        // Store the first element so we can return it later.
        var result = this.content[0];
        // Get the element at the end of the array.
        var end = this.content.pop();
        // If there are any elements left, put the end element at the
        // start, and let it sink down.
        if (this.content.length > 0) {
            this.content[0] = end;
            this.sinkDown(0);
        }
        return result;
    },

    remove: function (node) {
        var length = this.content.length;
        // To remove a value, we must search through the array to find
        // it.
        for (var i = 0; i < length; i++) {
            if (this.content[i] != node) continue;
            // When it is found, the process seen in 'pop' is repeated
            // to fill up the hole.
            var end = this.content.pop();
            // If the element we popped was the one we needed to remove,
            // we're done.
            if (i == length - 1) break;
            // Otherwise, we replace the removed element with the popped
            // one, and allow it to float up or sink down as appropriate.
            this.bubbleUp(i);
            this.sinkDown(i);
            break;
        }
    },

    size: function () {
        return this.content.length;
    },

    bubbleUp: function (n) {
        // Fetch the element that has to be moved.
        var element = this.content[n],
            score = this.scoreFunction(element);
        // When at 0, an element can not go up any further.
        while (n > 0) {
            // Compute the parent element's index, and fetch it.
            var parentN = Math.floor((n + 1) / 2) - 1,
                parent = this.content[parentN];
            // If the parent has a lesser score, things are in order and we
            // are done.
            if (score >= this.scoreFunction(parent)) break;

            // Otherwise, swap the parent with the current element and
            // continue.
            this.content[parentN] = element;
            this.content[n] = parent;
            n = parentN;
        }
    },

    sinkDown: function (n) {
        // Look up the target element and its score.
        var length = this.content.length,
            element = this.content[n],
            elemScore = this.scoreFunction(element);

        while (true) {
            // Compute the indices of the child elements.
            var child2N = (n + 1) * 2,
                child1N = child2N - 1;
            // This is used to store the new position of the element,
            // if any.
            var swap = null;
            // If the first child exists (is inside the array)...
            if (child1N < length) {
                // Look it up and compute its score.
                var child1 = this.content[child1N],
                    child1Score = this.scoreFunction(child1);
                // If the score is less than our element's, we need to swap.
                if (child1Score < elemScore) swap = child1N;
            }
            // Do the same checks for the other child.
            if (child2N < length) {
                var child2 = this.content[child2N],
                    child2Score = this.scoreFunction(child2);
                if (child2Score < (swap == null ? elemScore : child1Score)) swap = child2N;
            }

            // No need to swap further, we are done.
            if (swap == null) break;

            // Otherwise, swap and continue.
            this.content[n] = this.content[swap];
            this.content[swap] = element;
            n = swap;
        }
    }
 };

 ////////////


 function Sim(particles) {
    this.canvas = document.getElementById("canvas");
    this.ctx = this.canvas.getContext("2d");
    this.height = this.canvas.height;
    this.width = this.canvas.width;
    this.particles = particles;

    var self = this;
    this.canvas.onclick = function () {
        self.pause.call(self);
    };
 }

 Sim.prototype = {
    run: function () {
        this.time = (new Date()).valueOf();
        this.events = new BinaryHeap(function (event) {
            return event.time;
        });
        for (var i = 0; i < this.particles.length; i++) {
            this.forecastEvents(this.particles[i]);
            for (var j = 0; j < i; j++) {
                this.forecastParticleCollisions(this.particles[i], this.particles[j]);
            }
        }
        this.nextEvent = this.events.pop();
        this.updateLoop();
    },
    updateLoop: function () {
        var self = this;
        this.request = window.webkitRequestAnimationFrame(function (time) {
            self.update.call(self, time);
        });
    },
    update: function (time) {
        var nEvents = 0;
        while (this.nextEvent.time < time && nEvents < 10) {
            this.handleEvent(this.nextEvent);
            this.nextEvent = this.events.pop();
            nEvents++;
            if (nEvents > 20) {
                console.log('fuuuuuu');
                this.pause();
                return;
            }
        }
        this.clearCanvas();
        this.moveParticles(time);
        this.drawParticles();
        this.updateLoop();
    },
    handleEvent: function (event) {
        for (var i = 0; i < event.particles.length; i++) {
            if (event.particles[i].n_collisions != event.n_collisions[i]) {
                return;
            }
        }
        this.moveParticles(event.time);
        event.callback.call(this);
        for (var i = 0; i < event.particles.length; i++) {
            event.particles[i].n_collisions = (event.particles[i].n_collisions || 0) + 1;
        }
        for (var i = 0; i < event.particles.length; i++) {
            this.forecastEvents(event.particles[i]);
            for (var j = 0; j < this.particles.length; j++) {
                if (event.particles[i] != this.particles[j]) {
                    this.forecastParticleCollisions(event.particles[i], this.particles[j]);
                }
            }
        }
    },
    forecastEvents: function (particle) {
        this.forecastVerticalCollision(particle);
        this.forecastHorizontalCollision(particle);
    },
    forecastVerticalCollision: function (particle) {
        var d;
        if (particle.velocity.y > 0) {
            d = this.height - particle.radius - particle.position.y;
        } else if (particle.velocity.y < 0) {
            d = particle.radius - particle.position.y;
        }
        if (d) {
            var dt = d / particle.velocity.y;
            this.addEvent(dt, [particle], function () {
                particle.velocity.y = -particle.velocity.y;
            });
        }
    },
    forecastHorizontalCollision: function (particle) {
        var d;
        if (particle.velocity.x > 0) {
            d = this.width - particle.radius - particle.position.x;
        } else if (particle.velocity.x < 0) {
            d = particle.radius - particle.position.x;
        }
        if (d) {
            var dt = d / particle.velocity.x;
            this.addEvent(dt, [particle], function () {
                particle.velocity.x = -particle.velocity.x;
            });
        }
    }, //http://introcs.cs.princeton.edu/java/assignments/collisions.html
    forecastParticleCollisions: function (a, b) {
        var ds = a.radius + b.radius;
        var ds2 = Math.pow(ds, 2);
        var drx = a.position.x - b.position.x;
        var dry = a.position.y - b.position.y;
        var dvx = a.velocity.x - b.velocity.x;
        var dvy = a.velocity.y - b.velocity.y;
        var dr2 = Math.pow(drx, 2) + Math.pow(dry, 2);
        var dv2 = Math.pow(dvx, 2) + Math.pow(dvy, 2);
        var dvr = dvx * drx + dvy * dry;
        var d = Math.pow(dvr, 2) - dv2 * (dr2 - ds2);
        if (dvr >= 0 || d < 0) return;
        var dt = -(dvr + Math.sqrt(d)) / dv2;
        console.log(dt);
        this.addEvent(dt, [a, b], function () {

            var ds = a.radius + b.radius;
            var ds2 = Math.pow(ds, 2);
            var drx = a.position.x - b.position.x;
            var dry = a.position.y - b.position.y;
            var dvx = a.velocity.x - b.velocity.x;
            var dvy = a.velocity.y - b.velocity.y;
            var dr2 = Math.pow(drx, 2) + Math.pow(dry, 2);
            var dv2 = Math.pow(dvx, 2) + Math.pow(dvy, 2);
            var dvr = dvx * drx + dvy * dry;
            var d = Math.pow(dvr, 2) - dv2 * (dr2 - ds2);

            var j = 2 * a.mass * b.mass * dvr / ds / (a.mass + b.mass);
            var jx = j * drx / ds;
            var jy = j * dry / ds;
            a.velocity.x -= jx / a.mass;
            a.velocity.y -= jy / a.mass;
            b.velocity.x += jx / b.mass;
            b.velocity.y += jy / b.mass;
        });
    },
    addEvent: function (dt, particles, callback) {
        var event = {
            time: this.time + dt,
            particles: particles,
            n_collisions: [],
            callback: callback
        }
        for (var i = 0; i < particles.length; i++) {
            event.n_collisions.push(particles[i].n_collisions);
        }
        this.events.push(event);
    },
    moveParticles: function (time) {
        var dt = time - this.time;
        for (var i = 0; i < this.particles.length; i++) {
            this.moveParticle(this.particles[i], dt);
        }
        this.time = time;
    },
    moveParticle: function (particle, dt) {
        particle.position.x += particle.velocity.x * dt;
        particle.position.y += particle.velocity.y * dt;
    },
    drawParticles: function () {
        for (var i = 0; i < this.particles.length; i++) {
            this.drawParticle(this.particles[i]);
        }
    },
    drawParticle: function (particle) {
        this.ctx.beginPath();
        this.ctx.arc(particle.position.x,
        particle.position.y,
        particle.radius,
        0, 2 * Math.PI);
        this.ctx.lineWidth = 2;
        this.ctx.fillStyle = particle.color;
        this.ctx.fill();
        this.ctx.stroke();
    },
    clearCanvas: function () {
        this.ctx.save();
        this.ctx.setTransform(1, 0, 0, 1, 0, 0);
        this.ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
        this.ctx.restore();
    },
    pause: function () {
        if (this.request) {
            window.cancelAnimationFrame(this.request);
        }
    }
 }

 var red = {
    position: {
        x: 100,
        y: 100
    },
    velocity: {
        x: 0.05,
        y: 0
    },
    radius: 5,
    mass: 25,
    color: "#FF0000"
 };

 var yellow = {
    position: {
        x: 250,
        y: 100
    },
    velocity: {
        x: -0.05,
        y: 0
    },
    radius: 20,
    mass: 400,
    color: "#FFFF00"
 };

 var blue = {
    position: {
        x: 150,
        y: 150
    },
    velocity: {
        x: -0.2,
        y: 0.2
    },
    radius: 10,
    mass: 100,
    color: "#0000ff"
 };

 var green = {
    position: {
        x: 180,
        y: 20
    },
    velocity: {
        x: 0.2,
        y: 0.2
    },
    radius: 7,
    mass: 49,
    color: "#00ff00"
 };

 var green2 = {
    position: {
        x: 180,
        y: 180
    },
    velocity: {
        x: 0.2,
        y: 0.2
    },
    radius: 7,
    mass: 49,
    color: "#00ff00"
 };

 var green3 = {
    position: {
        x: 20,
        y: 20
    },
    velocity: {
        x: -0.2,
        y: 0.2
    },
    radius: 7,
    mass: 49,
    color: "#00ff00"
 };

 var red2 = {
    position: {
        x: 200,
        y: 100
    },
    velocity: {
        x: 0.05,
        y: 0
    },
    radius: 5,
    mass: 25,
    color: "#FF0000"
 };

 var red3 = {
    position: {
        x: 50,
        y: 100
    },
    velocity: {
        x: 0.05,
        y: 0
    },
    radius: 5,
    mass: 25,
    color: "#FF0000"
 };

 var s = new Sim([red, yellow, blue, green, green2, green3, red2, red3]);
 s.run();
 }//]]>  

 </script>


 </head>
 <body>
  <canvas id="canvas" />
  
 </body>


 </html>
	<!DOCTYPE html>
	<html>
	<head>
	<meta http-equiv="content-type" content="text/html; charset=UTF-8">
	<title> - jsFiddle demo</title>

	<script type='text/javascript' src='/js/lib/dummy.js'></script>
	<link rel="stylesheet" type="text/css" href="/css/normalize.css">

	<link rel="stylesheet" type="text/css" href="/css/result-light.css">

	<style type='text/css'>
	#canvas {
	border:1px solid black;
	width: 500px;
	height: 250px;
	}
	</style>



	<script type='text/javascript'>//<![CDATA[
	window.onload=function(){
	//http://introcs.cs.princeton.edu/java/assignments/collisions.html
	//http://eloquentjavascript.net/appendix2.html

	function BinaryHeap(scoreFunction) {
	this.content = [];
	this.scoreFunction = scoreFunction;
	}

	BinaryHeap.prototype = {
	push: function (element) {
	// Add the new element to the end of the array.
	this.content.push(element);
	// Allow it to bubble up.
	this.bubbleUp(this.content.length - 1);
	},

	pop: function () {
	// Store the first element so we can return it later.
	var result = this.content[0];
	// Get the element at the end of the array.
	var end = this.content.pop();
	// If there are any elements left, put the end element at the
	// start, and let it sink down.
	if (this.content.length > 0) {
	this.content[0] = end;
	this.sinkDown(0);
	}
	return result;
	},

	remove: function (node) {
	var length = this.content.length;
	// To remove a value, we must search through the array to find
	// it.
	for (var i = 0; i < length; i++) {
	if (this.content[i] != node) continue;
	// When it is found, the process seen in 'pop' is repeated
	// to fill up the hole.
	var end = this.content.pop();
	// If the element we popped was the one we needed to remove,
	// we're done.
	if (i == length - 1) break;
	// Otherwise, we replace the removed element with the popped
	// one, and allow it to float up or sink down as appropriate.
	this.bubbleUp(i);
	this.sinkDown(i);
	break;
	}
	},

	size: function () {
	return this.content.length;
	},

	bubbleUp: function (n) {
	// Fetch the element that has to be moved.
	var element = this.content[n],
	score = this.scoreFunction(element);
	// When at 0, an element can not go up any further.
	while (n > 0) {
	// Compute the parent element's index, and fetch it.
	var parentN = Math.floor((n + 1) / 2) - 1,
	parent = this.content[parentN];
	// If the parent has a lesser score, things are in order and we
	// are done.
	if (score >= this.scoreFunction(parent)) break;

	// Otherwise, swap the parent with the current element and
	// continue.
	this.content[parentN] = element;
	this.content[n] = parent;
	n = parentN;
	}
	},

	sinkDown: function (n) {
	// Look up the target element and its score.
	var length = this.content.length,
	element = this.content[n],
	elemScore = this.scoreFunction(element);

	while (true) {
	// Compute the indices of the child elements.
	var child2N = (n + 1) * 2,
	child1N = child2N - 1;
	// This is used to store the new position of the element,
	// if any.
	var swap = null;
	// If the first child exists (is inside the array)...
	if (child1N < length) {
	// Look it up and compute its score.
	var child1 = this.content[child1N],
	child1Score = this.scoreFunction(child1);
	// If the score is less than our element's, we need to swap.
	if (child1Score < elemScore) swap = child1N;
	}
	// Do the same checks for the other child.
	if (child2N < length) {
	var child2 = this.content[child2N],
	child2Score = this.scoreFunction(child2);
	if (child2Score < (swap == null ? elemScore : child1Score)) swap = child2N;
	}

	// No need to swap further, we are done.
	if (swap == null) break;

	// Otherwise, swap and continue.
	this.content[n] = this.content[swap];
	this.content[swap] = element;
	n = swap;
	}
	}
	};

	////////////


	function Sim(particles) {
	this.canvas = document.getElementById("canvas");
	this.ctx = this.canvas.getContext("2d");
	this.height = this.canvas.height;
	this.width = this.canvas.width;
	this.particles = particles;

	var self = this;
	this.canvas.onclick = function () {
	self.pause.call(self);
	};
	}

	Sim.prototype = {
	run: function () {
	this.time = (new Date()).valueOf();
	this.events = new BinaryHeap(function (event) {
	return event.time;
	});
	for (var i = 0; i < this.particles.length; i++) {
	this.forecastEvents(this.particles[i]);
	for (var j = 0; j < i; j++) {
	this.forecastParticleCollisions(this.particles[i], this.particles[j]);
	}
	}
	this.nextEvent = this.events.pop();
	this.updateLoop();
	},
	updateLoop: function () {
	var self = this;
	this.request = window.webkitRequestAnimationFrame(function (time) {
	self.update.call(self, time);
	});
	},
	update: function (time) {
	var nEvents = 0;
	while (this.nextEvent.time < time && nEvents < 10) {
	this.handleEvent(this.nextEvent);
	this.nextEvent = this.events.pop();
	nEvents++;
	if (nEvents > 20) {
	console.log('fuuuuuu');
	this.pause();
	return;
	}
	}
	this.clearCanvas();
	this.moveParticles(time);
	this.drawParticles();
	this.updateLoop();
	},
	handleEvent: function (event) {
	for (var i = 0; i < event.particles.length; i++) {
	if (event.particles[i].n_collisions != event.n_collisions[i]) {
	return;
	}
	}
	this.moveParticles(event.time);
	event.callback.call(this);
	for (var i = 0; i < event.particles.length; i++) {
	event.particles[i].n_collisions = (event.particles[i].n_collisions \|\| 0) + 1;
	}
	for (var i = 0; i < event.particles.length; i++) {
	this.forecastEvents(event.particles[i]);
	for (var j = 0; j < this.particles.length; j++) {
	if (event.particles[i] != this.particles[j]) {
	this.forecastParticleCollisions(event.particles[i], this.particles[j]);
	}
	}
	}
	},
	forecastEvents: function (particle) {
	this.forecastVerticalCollision(particle);
	this.forecastHorizontalCollision(particle);
	},
	forecastVerticalCollision: function (particle) {
	var d;
	if (particle.velocity.y > 0) {
	d = this.height - particle.radius - particle.position.y;
	} else if (particle.velocity.y < 0) {
	d = particle.radius - particle.position.y;
	}
	if (d) {
	var dt = d / particle.velocity.y;
	this.addEvent(dt, [particle], function () {
	particle.velocity.y = -particle.velocity.y;
	});
	}
	},
	forecastHorizontalCollision: function (particle) {
	var d;
	if (particle.velocity.x > 0) {
	d = this.width - particle.radius - particle.position.x;
	} else if (particle.velocity.x < 0) {
	d = particle.radius - particle.position.x;
	}
	if (d) {
	var dt = d / particle.velocity.x;
	this.addEvent(dt, [particle], function () {
	particle.velocity.x = -particle.velocity.x;
	});
	}
	}, //http://introcs.cs.princeton.edu/java/assignments/collisions.html
	forecastParticleCollisions: function (a, b) {
	var ds = a.radius + b.radius;
	var ds2 = Math.pow(ds, 2);
	var drx = a.position.x - b.position.x;
	var dry = a.position.y - b.position.y;
	var dvx = a.velocity.x - b.velocity.x;
	var dvy = a.velocity.y - b.velocity.y;
	var dr2 = Math.pow(drx, 2) + Math.pow(dry, 2);
	var dv2 = Math.pow(dvx, 2) + Math.pow(dvy, 2);
	var dvr = dvx * drx + dvy * dry;
	var d = Math.pow(dvr, 2) - dv2 * (dr2 - ds2);
	if (dvr >= 0 \|\| d < 0) return;
	var dt = -(dvr + Math.sqrt(d)) / dv2;
	console.log(dt);
	this.addEvent(dt, [a, b], function () {

	var ds = a.radius + b.radius;
	var ds2 = Math.pow(ds, 2);
	var drx = a.position.x - b.position.x;
	var dry = a.position.y - b.position.y;
	var dvx = a.velocity.x - b.velocity.x;
	var dvy = a.velocity.y - b.velocity.y;
	var dr2 = Math.pow(drx, 2) + Math.pow(dry, 2);
	var dv2 = Math.pow(dvx, 2) + Math.pow(dvy, 2);
	var dvr = dvx * drx + dvy * dry;
	var d = Math.pow(dvr, 2) - dv2 * (dr2 - ds2);

	var j = 2 * a.mass * b.mass * dvr / ds / (a.mass + b.mass);
	var jx = j * drx / ds;
	var jy = j * dry / ds;
	a.velocity.x -= jx / a.mass;
	a.velocity.y -= jy / a.mass;
	b.velocity.x += jx / b.mass;
	b.velocity.y += jy / b.mass;
	});
	},
	addEvent: function (dt, particles, callback) {
	var event = {
	time: this.time + dt,
	particles: particles,
	n_collisions: [],
	callback: callback
	}
	for (var i = 0; i < particles.length; i++) {
	event.n_collisions.push(particles[i].n_collisions);
	}
	this.events.push(event);
	},
	moveParticles: function (time) {
	var dt = time - this.time;
	for (var i = 0; i < this.particles.length; i++) {
	this.moveParticle(this.particles[i], dt);
	}
	this.time = time;
	},
	moveParticle: function (particle, dt) {
	particle.position.x += particle.velocity.x * dt;
	particle.position.y += particle.velocity.y * dt;
	},
	drawParticles: function () {
	for (var i = 0; i < this.particles.length; i++) {
	this.drawParticle(this.particles[i]);
	}
	},
	drawParticle: function (particle) {
	this.ctx.beginPath();
	this.ctx.arc(particle.position.x,
	particle.position.y,
	particle.radius,
	0, 2 * Math.PI);
	this.ctx.lineWidth = 2;
	this.ctx.fillStyle = particle.color;
	this.ctx.fill();
	this.ctx.stroke();
	},
	clearCanvas: function () {
	this.ctx.save();
	this.ctx.setTransform(1, 0, 0, 1, 0, 0);
	this.ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
	this.ctx.restore();
	},
	pause: function () {
	if (this.request) {
	window.cancelAnimationFrame(this.request);
	}
	}
	}

	var red = {
	position: {
	x: 100,
	y: 100
	},
	velocity: {
	x: 0.05,
	y: 0
	},
	radius: 5,
	mass: 25,
	color: "#FF0000"
	};

	var yellow = {
	position: {
	x: 250,
	y: 100
	},
	velocity: {
	x: -0.05,
	y: 0
	},
	radius: 20,
	mass: 400,
	color: "#FFFF00"
	};

	var blue = {
	position: {
	x: 150,
	y: 150
	},
	velocity: {
	x: -0.2,
	y: 0.2
	},
	radius: 10,
	mass: 100,
	color: "#0000ff"
	};

	var green = {
	position: {
	x: 180,
	y: 20
	},
	velocity: {
	x: 0.2,
	y: 0.2
	},
	radius: 7,
	mass: 49,
	color: "#00ff00"
	};

	var green2 = {
	position: {
	x: 180,
	y: 180
	},
	velocity: {
	x: 0.2,
	y: 0.2
	},
	radius: 7,
	mass: 49,
	color: "#00ff00"
	};

	var green3 = {
	position: {
	x: 20,
	y: 20
	},
	velocity: {
	x: -0.2,
	y: 0.2
	},
	radius: 7,
	mass: 49,
	color: "#00ff00"
	};

	var red2 = {
	position: {
	x: 200,
	y: 100
	},
	velocity: {
	x: 0.05,
	y: 0
	},
	radius: 5,
	mass: 25,
	color: "#FF0000"
	};

	var red3 = {
	position: {
	x: 50,
	y: 100
	},
	velocity: {
	x: 0.05,
	y: 0
	},
	radius: 5,
	mass: 25,
	color: "#FF0000"
	};

	var s = new Sim([red, yellow, blue, green, green2, green3, red2, red3]);
	s.run();
	}//]]>

	</script>


	</head>
	<body>
	<canvas id="canvas" />

	</body>


	</html>