From 0b89973e8e1b2251545def7796c246d68ad8e061 Mon Sep 17 00:00:00 2001 From: Fbenas Date: Wed, 23 Sep 2020 19:21:31 +0100 Subject: Add simple ray-traced collision detection --- public/js/app.js | 149 ++++++++++++++++++++++++++++++++++++---------- resources/js/app.js | 2 +- resources/js/component.js | 114 ++++++++++++++++++++++++++++------- resources/js/scene.js | 33 +++++++--- 4 files changed, 238 insertions(+), 60 deletions(-) diff --git a/public/js/app.js b/public/js/app.js index 746c558..c9e5c27 100644 --- a/public/js/app.js +++ b/public/js/app.js @@ -1,33 +1,37 @@ class Component { - constructor(radius, color, x, y, direction) { + constructor(context, radius, color, x, y, direction, id) { this.rayLength = 40; - this.turnStepAmount = 4; - this.stepAmount = 3; + this.turnStepAmount = 5; + this.stepAmount = 4; this.radius = radius; this.x = x; this.y = y; this.direction = direction; this.color = color; this.fieldOfView = 180; + this.id = id; + this.boidBuffer = 20; + + this.update(context); } - move(context) { + move(context, boids) { // this.direction += Math.random() * (2 * this.turnStepAmount) - this.turnStepAmount - this.direction = this.findNextRay(context); + this.direction = this.findNextRay(context, boids); var vector = this.detectionPoint(this.x, this.y, this.stepAmount, this.direction); - this.x = vector.x; this.y = vector.y; + this.update(context); } buildRays() { let rays = new Array(); - let rayInteval = 10; + let rayInteval = 2; let noOfSteps = this.fieldOfView / rayInteval; for (let i = 0; i < noOfSteps / 2; i++) { if (i != 0) { @@ -39,35 +43,105 @@ class Component { return rays; } - findNextRay(context) { + findNextRay(context, boids) { let rays = this.buildRays(); for (let i = 0; i < rays.length; i++) { - let tweakAngle = 0; - if (i == 0 && Math.random() > 0.95) { - tweakAngle = this.turnStepAmount * Math.random() * 5; - } else { - tweakAngle = rays[i] * Math.random() * 3; - } + // if (Math.random() > 0.95) { + // tweakAngle = this.turnStepAmount * Math.random() * 5; + // } let rayAngle = tweakAngle + this.direction + rays[i]; + if (i == 0 && this.detectBoid(context, rayAngle, boids)) { + continue; + } + if (this.detectBox(context, context.canvas.width, context.canvas.height, rayAngle)) { continue; } return rayAngle; } + console.log(this.x, this.y); + console.log('cannot find suitable ray'); + } + + detectBoid(context, direction, boids) { + for (let i = 0; i < boids.length; i++) { + // rule out ourselves + if (this.id == boids[i].id) { + continue; + } + + let thisFututrePosition = this.detectionPoint(this.x, this.y, this.boidBuffer, direction); + let thisPath = { + x1: this.x, + y1: this.y, + x2: thisFututrePosition.x, + y2: thisFututrePosition.y + }; + + let boidFuturePosition = this.detectionPoint(boids[i].x, boids[i].y, boids[i].boidBuffer, boids[i].direction); + let boidPath = { + x1: boids[i].x, + y1: boids[i].y, + x2: boidFuturePosition.x, + y2: boidFuturePosition.y + }; + + let thisIntersectsBoid = this.pathsIntersect( + thisPath.x1, thisPath.y1, thisPath.x2, thisPath.y2, boidPath.x1, boidPath.y1, boidPath.x2, boidPath.y2 + ); + + if (thisIntersectsBoid) { + return true; + } + } - throw new Exception(); + return false; + } + + pathsIntersect(x1, y1, x2, y2, x3, y3, x4, y4) { + // Check if none of the lines are of length 0 + if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) { + return false + } + + let denominator = ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1)) + + // // Lines are parallel + // if (denominator === 0) { + // return false + // } + + let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator + let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator + + // is the intersection along the segments + if (ua < 0 || ua > 1 || ub < 0 || ub > 1) { + return false + } + + // Return a object with the x and y coordinates of the intersection + let x = x1 + ua * (x2 - x1) + let y = y1 + ua * (y2 - y1) + + return { + x, + y + } } detectBox(context, width, height, direction) { let perceptionVector = this.detectionPoint(this.x, this.y, this.rayLength, direction); - if (perceptionVector.x < 0 || perceptionVector.y < 0 || perceptionVector.x > width || perceptionVector.y > height) { - this.drawRay(context, perceptionVector.x, perceptionVector.y, this.perceptionDistance, direction) + if (perceptionVector.x - this.radius < 0 || + perceptionVector.y - this.radius < 0 || + perceptionVector.x + this.radius > width - 0 || + perceptionVector.y + this.radius > height - 0 + ) { return true; } @@ -75,11 +149,11 @@ class Component { } update(context) { - this.updateBoid(context); + this.drawBoid(context); this.drawRay(context, this.x, this.y, this.rayLength, this.direction); } - updateBoid(context) { + drawBoid(context) { context.beginPath(); context.fillStyle = "blue"; context.arc(this.x, this.y, this.radius, 0, 2 * Math.PI); @@ -91,7 +165,7 @@ class Component { context.lineWidth = 1; context.beginPath(); - // this.lineToAngle(context, x, y, perceptionDistance, direction); + this.lineToAngle(context, x, y, perceptionDistance, direction); context.stroke(); context.restore(); @@ -153,7 +227,7 @@ class Scene { constructor(component_size, no_of_components) { this.component_size = component_size; this.no_of_components = no_of_components; - this.components = new Array; + this.components = []; this.gameArea = {}; this.initGameArea(); this.initComponents(); @@ -161,17 +235,32 @@ class Scene { } initComponents() { + let components = []; for (let i = 0; i < this.no_of_components; i++) { - let new_component = new Component( + let x, y, z; + if (i == 0) { + x = 100; + y = 100; + z = 0; + } else { + x = 105; + y = 100; + z = 180; + } + + components.push(new Component( + this.gameArea.context, this.component_size, "black", - Math.random() * this.gameArea.canvas.width, - Math.random() * this.gameArea.canvas.height, - Math.random() * 360 - // 18, 100, 180 - ); - this.components.push(new_component); + // x, y, z, + Math.random() * (this.gameArea.canvas.width - 100) + 50, + Math.random() * (this.gameArea.canvas.height - 100) + 50, + Math.random() * 360, + i + )); } + + this.components = components; } initGameArea() { @@ -195,7 +284,7 @@ class Scene { update() { this.gameArea.clear(); for (let i = 0; i < this.no_of_components; i++) { - this.components[i].move(this.gameArea.context); + this.components[i].move(this.gameArea.context, this.components); } } @@ -221,7 +310,7 @@ class Scene { } -let scene = new Scene(5, 100); +let scene = new Scene(5, 20); function stop() { scene.stop(); diff --git a/resources/js/app.js b/resources/js/app.js index b107a71..47cabd6 100644 --- a/resources/js/app.js +++ b/resources/js/app.js @@ -1,4 +1,4 @@ -let scene = new Scene(5, 100); +let scene = new Scene(5, 20); function stop() { scene.stop(); diff --git a/resources/js/component.js b/resources/js/component.js index a6098e0..373b66a 100644 --- a/resources/js/component.js +++ b/resources/js/component.js @@ -1,33 +1,37 @@ class Component { - constructor(radius, color, x, y, direction) { + constructor(context, radius, color, x, y, direction, id) { this.rayLength = 40; - this.turnStepAmount = 4; - this.stepAmount = 3; + this.turnStepAmount = 5; + this.stepAmount = 4; this.radius = radius; this.x = x; this.y = y; this.direction = direction; this.color = color; this.fieldOfView = 180; + this.id = id; + this.boidBuffer = 20; + + this.update(context); } - move(context) { + move(context, boids) { // this.direction += Math.random() * (2 * this.turnStepAmount) - this.turnStepAmount - this.direction = this.findNextRay(context); + this.direction = this.findNextRay(context, boids); var vector = this.detectionPoint(this.x, this.y, this.stepAmount, this.direction); - this.x = vector.x; this.y = vector.y; + this.update(context); } buildRays() { let rays = new Array(); - let rayInteval = 10; + let rayInteval = 2; let noOfSteps = this.fieldOfView / rayInteval; for (let i = 0; i < noOfSteps / 2; i++) { if (i != 0) { @@ -39,35 +43,105 @@ class Component { return rays; } - findNextRay(context) { + findNextRay(context, boids) { let rays = this.buildRays(); for (let i = 0; i < rays.length; i++) { - let tweakAngle = 0; - if (i == 0 && Math.random() > 0.95) { - tweakAngle = this.turnStepAmount * Math.random() * 5; - } else { - tweakAngle = rays[i] * Math.random() * 3; - } + // if (Math.random() > 0.95) { + // tweakAngle = this.turnStepAmount * Math.random() * 5; + // } let rayAngle = tweakAngle + this.direction + rays[i]; + if (i == 0 && this.detectBoid(context, rayAngle, boids)) { + continue; + } + if (this.detectBox(context, context.canvas.width, context.canvas.height, rayAngle)) { continue; } return rayAngle; } + console.log(this.x, this.y); + console.log('cannot find suitable ray'); + } - throw new Exception(); + detectBoid(context, direction, boids) { + for (let i = 0; i < boids.length; i++) { + // rule out ourselves + if (this.id == boids[i].id) { + continue; + } + + let thisFututrePosition = this.detectionPoint(this.x, this.y, this.boidBuffer, direction); + let thisPath = { + x1: this.x, + y1: this.y, + x2: thisFututrePosition.x, + y2: thisFututrePosition.y + }; + + let boidFuturePosition = this.detectionPoint(boids[i].x, boids[i].y, boids[i].boidBuffer, boids[i].direction); + let boidPath = { + x1: boids[i].x, + y1: boids[i].y, + x2: boidFuturePosition.x, + y2: boidFuturePosition.y + }; + + let thisIntersectsBoid = this.pathsIntersect( + thisPath.x1, thisPath.y1, thisPath.x2, thisPath.y2, boidPath.x1, boidPath.y1, boidPath.x2, boidPath.y2 + ); + + if (thisIntersectsBoid) { + return true; + } + } + + return false; + } + + pathsIntersect(x1, y1, x2, y2, x3, y3, x4, y4) { + // Check if none of the lines are of length 0 + if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) { + return false + } + + let denominator = ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1)) + + // // Lines are parallel + // if (denominator === 0) { + // return false + // } + + let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator + let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator + + // is the intersection along the segments + if (ua < 0 || ua > 1 || ub < 0 || ub > 1) { + return false + } + + // Return a object with the x and y coordinates of the intersection + let x = x1 + ua * (x2 - x1) + let y = y1 + ua * (y2 - y1) + + return { + x, + y + } } detectBox(context, width, height, direction) { let perceptionVector = this.detectionPoint(this.x, this.y, this.rayLength, direction); - if (perceptionVector.x < 0 || perceptionVector.y < 0 || perceptionVector.x > width || perceptionVector.y > height) { - this.drawRay(context, perceptionVector.x, perceptionVector.y, this.perceptionDistance, direction) + if (perceptionVector.x - this.radius < 0 || + perceptionVector.y - this.radius < 0 || + perceptionVector.x + this.radius > width - 0 || + perceptionVector.y + this.radius > height - 0 + ) { return true; } @@ -75,11 +149,11 @@ class Component { } update(context) { - this.updateBoid(context); + this.drawBoid(context); this.drawRay(context, this.x, this.y, this.rayLength, this.direction); } - updateBoid(context) { + drawBoid(context) { context.beginPath(); context.fillStyle = "blue"; context.arc(this.x, this.y, this.radius, 0, 2 * Math.PI); @@ -91,7 +165,7 @@ class Component { context.lineWidth = 1; context.beginPath(); - // this.lineToAngle(context, x, y, perceptionDistance, direction); + this.lineToAngle(context, x, y, perceptionDistance, direction); context.stroke(); context.restore(); diff --git a/resources/js/scene.js b/resources/js/scene.js index 684cd11..7e7e895 100644 --- a/resources/js/scene.js +++ b/resources/js/scene.js @@ -3,7 +3,7 @@ class Scene { constructor(component_size, no_of_components) { this.component_size = component_size; this.no_of_components = no_of_components; - this.components = new Array; + this.components = []; this.gameArea = {}; this.initGameArea(); this.initComponents(); @@ -11,17 +11,32 @@ class Scene { } initComponents() { + let components = []; for (let i = 0; i < this.no_of_components; i++) { - let new_component = new Component( + let x, y, z; + if (i == 0) { + x = 100; + y = 100; + z = 0; + } else { + x = 105; + y = 100; + z = 180; + } + + components.push(new Component( + this.gameArea.context, this.component_size, "black", - Math.random() * this.gameArea.canvas.width, - Math.random() * this.gameArea.canvas.height, - Math.random() * 360 - // 18, 100, 180 - ); - this.components.push(new_component); + // x, y, z, + Math.random() * (this.gameArea.canvas.width - 100) + 50, + Math.random() * (this.gameArea.canvas.height - 100) + 50, + Math.random() * 360, + i + )); } + + this.components = components; } initGameArea() { @@ -45,7 +60,7 @@ class Scene { update() { this.gameArea.clear(); for (let i = 0; i < this.no_of_components; i++) { - this.components[i].move(this.gameArea.context); + this.components[i].move(this.gameArea.context, this.components); } } -- cgit v1.2.3