0
\$\begingroup\$

I am trying to use Separating Axis Theorem to check for collision between two shapes, but it's not working correctly. It's giving all incorrect results. The problem is in the collision-checking function. Is there something wrong in calculating the projection-overlap ?

This is my collision-checking function :-

function collisionCheck() {
    /* getting all the axes from both shapes */
    var axes = [];
    for(var i=0; i<shape1.vertices.length; i++) {
        var v1 = shape1.vertices[i];
        var v2 = [];
        if(i < shape1.vertices.length-1) {
            v2 = shape1.vertices[i+1];
        }
        else {
            v2 = shape1.vertices[0];
        }
        var edge = [v2[0]-v1[0], v2[1]-v1[1]];
        var normal = [-edge[1], edge[0]];
        var mag = Math.sqrt(normal[0]*normal[0] + normal[1]*normal[1]);
        var unit = [normal[0]/mag, normal[1]/mag];
        axes.push(unit);
    }
    for(var i=0; i<shape2.vertices.length; i++) {
        var v1 = shape2.vertices[i];
        var v2 = [];
        if(i < shape2.vertices.length-1) {
            v2 = shape2.vertices[i+1];
        }
        else {
            v2 = shape2.vertices[0];
        }
        var edge = [v2[0]-v1[0], v2[1]-v1[1]];
        var normal = [-edge[1], edge[0]];
        var mag = Math.sqrt(normal[0]*normal[0] + normal[1]*normal[1]);
        var unit = [normal[0]/mag, normal[1]/mag];
        axes.push(unit);
    }
    /* projecting both shapes onto each axes */
    for(var i=0; i<axes.length; i++) {
        var axis = axes[i];
        // projecting shape 1
        var min = Infinity;
        var max = -Infinity;
        for(var j=0; j<shape1.vertices.length; j++) {
            var vertex = shape1.vertices[j];
            var proj = axis[0]*vertex[0] + axis[1]*vertex[1];
            if(proj < min) {
                min = proj;
            }
            else if(proj > max) {
                max = proj;
            }
        }
        var projection1 = [min, max];
        // projecting shape 2
        var min = Infinity;
        var max = -Infinity;
        for(var j=0; j<shape2.vertices.length; j++) {
            var vertex = shape2.vertices[j];
            var proj = axis[0]*vertex[0] + axis[1]*vertex[1];
            if(proj < min) {
                min = proj;
            }
            else if(proj > max) {
                max = proj;
            }
        }
        var projection2 = [min, max];
        if(projection1[1] > projection2[0] && projection1[0] < projection2[0]) {

        }
        else if(projection2[1] > projection1[0] && projection2[0] < projection1[0]) {

        }
        else { 
            return false; // return false if projections not overlapping on any one axis
        }
    }
    return true; // return true if projections is overlapping on all the axes
};

Here is what's happening :-

<html>
	<head>
		<title>Separating Axis Theorem</title>
		<script>
			var canvas = null;
			var canvas2d = null;
			var lastTime = null;
			var leftKey = null;
			var rightKey = null;
			var upKey = null;
			var downKey = null;
			var aKey = null;
			var dKey = null;
			var wKey = null;
			var sKey = null;
			var text = "";

			var shape1 = {
				vertices: [],
				draw: function(canvas2d) {
					canvas2d.beginPath();
					var v1 = this.vertices[0];
					canvas2d.moveTo(v1[0], v1[1]);
					for(var i=1; i<this.vertices.length; i++) {
						var v = this.vertices[i];
						canvas2d.lineTo(v[0], v[1]);
					}
					canvas2d.closePath();
					canvas2d.strokeStyle = "red";
					canvas2d.stroke();
				},
				update: function(delta, leftKey, rightKey, upKey, downKey) {
					var dx = 0;
					var dy = 0;
					var dxValue = 0.3;
					var dyValue = 0.3;
					if(leftKey) {
						dx = -dxValue;
					}
					if(rightKey) {
						dx = dxValue;
					}
					if(!leftKey && !rightKey) {
						dx = 0;
					}
					if(upKey) {
						dy = -dyValue;
					}
					if(downKey) {
						dy = dyValue;
					}
					if(!upKey && !downKey) {
						dy = 0;
					}
					for(var i=0; i<this.vertices.length; i++) {
						var v = this.vertices[i];
						v = [v[0]+(dx*delta), v[1]+(dy*delta)];
						this.vertices[i] = v;
					}
				},
				initialize: function() {
					this.vertices.push([100, 100], [250, 150], [220, 250], [120, 230]);
				}
			};

			var shape2 = {
				vertices: [],
				draw: function(canvas2d) {
					canvas2d.beginPath();
					var v1 = this.vertices[0];
					canvas2d.moveTo(v1[0], v1[1]);
					for(var i=1; i<this.vertices.length; i++) {
						var v = this.vertices[i];
						canvas2d.lineTo(v[0], v[1]);
					}
					canvas2d.closePath();
					canvas2d.strokeStyle = "green";
					canvas2d.stroke();
				},
				update: function(delta, aKey, dKey, wKey, sKey) {
					var dx = 0;
					var dy = 0;
					var dxValue = 0.3;
					var dyValue = 0.3;
					if(aKey) {
						dx = -dxValue;
					}
					if(dKey) {
						dx = dxValue;
					}
					if(!aKey && !dKey) {
						dx = 0;
					}
					if(wKey) {
						dy = -dyValue;
					}
					if(sKey) {
						dy = dyValue;
					}
					if(!wKey && !sKey) {
						dy = 0;
					}
					for(var i=0; i<this.vertices.length; i++) {
						var v = this.vertices[i];
						v = [v[0]+(dx*delta), v[1]+(dy*delta)];
						this.vertices[i] = v;
					}
				},
				initialize: function() {
					this.vertices.push([400, 200], [500, 200], [480, 300], [400, 280]);
				}
			};

			function initialize() {
				lastTime = new Date().getTime();
				leftKey = false;
				rightKey = false;
				upKey = false;
				downKey = false;
				canvas = document.getElementById("canvas");
				canvas2d = canvas.getContext("2d");
				window.addEventListener("keyup", keyUpListener, false);
				window.addEventListener("keydown", keyDownListener, false);
				shape1.initialize();
				shape2.initialize();
				gameLoop();
			};

			function gameLoop() {
				window.clearTimeout();
				var currentTime = new Date().getTime();
				var delta = currentTime - lastTime;
				lastTime = currentTime;
				draw();
				update(delta);
				var difference = new Date().getTime() - currentTime;
				window.setTimeout(gameLoop, 1000/60-difference);
			};

			function draw() {
				canvas2d.fillStyle = "black";
				canvas2d.fillRect(0, 0, canvas.width, canvas.height);
				shape1.draw(canvas2d);
				shape2.draw(canvas2d);
				canvas2d.font = "25px Arial";
				canvas2d.fillStyle = "yellow";
				canvas2d.fillText("use W, A, S, D keys to move green box", 30, 430);
				canvas2d.fillText("use A, S, D, F keys to move red box", 30, 460);
				canvas2d.fillStyle = "rgba(100, 255, 100, 1)";
				canvas2d.fillText(text, 30, 30);
			};

			function update(deltaVal) {
				var delta = deltaVal;
				if(delta > 50) {
					delta = 50;
				}
				shape1.update(delta, leftKey, rightKey, upKey, downKey);
				shape2.update(delta, aKey, dKey, wKey, sKey);
				if(collisionCheck()) {
					text = "Intersecting";
				}
				else {
					text = "Not intersecting";
				}
			};

			function keyUpListener(e) {
				if(e.which === 37) {
					leftKey = false;
				}
				else if(e.which === 39) {
					rightKey = false;
				}
				else if(e.which === 38) {
					upKey = false;
				}
				else if(e.which === 40) {
					downKey = false;
				}
				if(e.which === 65) {
					aKey = false;
				}
				else if(e.which === 68) {
					dKey = false;
				}
				else if(e.which === 87) {
					wKey = false;
				}
				else if(e.which === 83) {
					sKey = false;
				}
			};

			function keyDownListener(e) {
				if(e.which === 37) {
					leftKey = true;
				}
				else if(e.which === 39) {
					rightKey = true;
				}
				else if(e.which === 38) {
					upKey = true;
				}
				else if(e.which === 40) {
					downKey = true;
				}
				if(e.which === 65) {
					aKey = true;
				}
				else if(e.which === 68) {
					dKey = true;
				}
				else if(e.which === 87) {
					wKey = true;
				}
				else if(e.which === 83) {
					sKey = true;
				}
			};

			function collisionCheck() {
				/* getting all the axes from both shapes */
				var axes = [];
				for(var i=0; i<shape1.vertices.length; i++) {
					var v1 = shape1.vertices[i];
					var v2 = [];
					if(i < shape1.vertices.length-1) {
						v2 = shape1.vertices[i+1];
					}
					else {
						v2 = shape1.vertices[0];
					}
					var edge = [v2[0]-v1[0], v2[1]-v1[1]];
					var normal = [-edge[1], edge[0]];
					var mag = Math.sqrt(normal[0]*normal[0] + normal[1]*normal[1]);
					var unit = [normal[0]/mag, normal[1]/mag];
					axes.push(unit);
				}
				for(var i=0; i<shape2.vertices.length; i++) {
					var v1 = shape2.vertices[i];
					var v2 = [];
					if(i < shape2.vertices.length-1) {
						v2 = shape2.vertices[i+1];
					}
					else {
						v2 = shape2.vertices[0];
					}
					var edge = [v2[0]-v1[0], v2[1]-v1[1]];
					var normal = [-edge[1], edge[0]];
					var mag = Math.sqrt(normal[0]*normal[0] + normal[1]*normal[1]);
					var unit = [normal[0]/mag, normal[1]/mag];
					axes.push(unit);
				}
				/* projecting both shapes onto each axes */
				for(var i=0; i<axes.length; i++) {
					var axis = axes[i];
					// projecting shape 1
					var min = Infinity;
					var max = -Infinity;
					for(var j=0; j<shape1.vertices.length; j++) {
						var vertex = shape1.vertices[j];
						var proj = axis[0]*vertex[0] + axis[1]*vertex[1];
						if(proj < min) {
							min = proj;
						}
						else if(proj > max) {
							max = proj;
						}
					}
					var projection1 = [min, max];
					// projecting shape 2
					var min = Infinity;
					var max = -Infinity;
					for(var j=0; j<shape2.vertices.length; j++) {
						var vertex = shape2.vertices[j];
						var proj = axis[0]*vertex[0] + axis[1]*vertex[1];
						if(proj < min) {
							min = proj;
						}
						else if(proj > max) {
							max = proj;
						}
					}
					var projection2 = [min, max];
					if(projection1[1] > projection2[0] && projection1[0] < projection2[0]) {
						
					}
					else if(projection2[1] > projection1[0] && projection2[0] < projection1[0]) {
						
					}
					else { 
						return false; // return false if projections not overlapping on any one axis
					}
				}
				return true; // return true if projections is overlapping on all the axes
			};

			window.addEventListener("load", initialize, false);
		</script>
	</head>
	<body>
		<canvas id = "canvas" width = "640" height = "480"></canvas>
	</body>
</html>

\$\endgroup\$
  • \$\begingroup\$ Hi Raj. By not getting the right answer what do you mean? Is there a particular angle or situation where the collision isn't valid, or is it just not registering them at all? If there's a specific scenario then it might help us spot the discrepancy. \$\endgroup\$ – Huxellberger Aug 27 '16 at 10:06
  • \$\begingroup\$ @Huxellberget oh okey, I will edit the question. \$\endgroup\$ – arandomguy Aug 27 '16 at 10:14
  • \$\begingroup\$ Question edited. Added html snippet. Run the app. You'll see the results are incorrect. \$\endgroup\$ – arandomguy Aug 27 '16 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.