Engo Engo - 1 month ago 22
Javascript Question

Collision detection circles using recursion in JavaScript

I want to generate circles on random locations with a specific distance from the main circle. The circles should not intersect with each other. I've created a method that checks for each circle if it's not intersecting all other circles. The collision detection does its thing, but the recursion part in my code doesn't work:

if (collision > 0) {
console.log("GENERATE NEW RANDOM COORDINATE")
generateRandomCoordinate(d, r)
}


Result

As you can see in the output, my app generates new coordinates
(158,290) when it detects collision (138,272). However, it still draws
circle at (138,272).

Any idea why this happens? Please let me know if you know more efficient way...

generateRandomCoordinate function

function generateRandomCoordinate(d, r) {
var phi = Math.random() * 2 * Math.PI
var x = topicCoordinates[0].x + Math.round(d * Math.cos(phi))
var y = topicCoordinates[0].y + Math.round(d * Math.sin(phi))
var collision = 0
for (var j = 0; j < topicCoordinates.length; j++) {
var dx = x - topicCoordinates[j].x
var dy = y - topicCoordinates[j].y
var distance = Math.sqrt(dx * dx + dy * dy)

if (distance < r + topicCoordinates[j].r) {
collision++
console.log("COLLISION DETECTED BETWEEN POINT(" + "x: " + x + ", y: " + y + ") AND POINT(x1: " + topicCoordinates[j].x + ", y1: " + topicCoordinates[j].y + ")")
}
}
if (collision > 0) {
console.log("GENERATE NEW RANDOM COORDINATE")
generateRandomCoordinate(d, r)
}

var topicCoordinate = {
"x": x,
"y": y,
"r": r
}
return topicCoordinate
}


Calling the generateRandomCoordinate function

var randomCoordinate = generateRandomCoordinate(d, r)
x = randomCoordinate.x
y = randomCoordinate.y
r = randomCoordinate.r
}

console.log("ADDED POINT(x: " + x + ", y: " + y + ", r: " + r + ")")
var topicCoordinate = {
"x": x,
"y": y,
"r": r
}
topicCoordinates.push(topicCoordinate)
drawCircle(x, y, r)


Output

enter image description here

UPDATE
Working code


function generateRandomCoordinate(d, r) {
var collision = true
while (collision) {
collision = false
var phi = Math.random() * 2 * Math.PI
var x = topicCoordinates[0].x + Math.round(d * Math.cos(phi))
var y = topicCoordinates[0].y + Math.round(d * Math.sin(phi))
for (var j = 0; j < topicCoordinates.length; j++) {
var dx = x - topicCoordinates[j].x
var dy = y - topicCoordinates[j].y
var distance = Math.sqrt(dx * dx + dy * dy)

if (distance < r + topicCoordinates[j].r) {
collision = true
console.log("COLLISION DETECTED BETWEEN POINT(" + "x: " + x + ", y: " + y + ") AND POINT(x1: " + topicCoordinates[j].x + ", y1: " + topicCoordinates[j].y + ")")
}
}
}

var topicCoordinate = { "x" : x, "y" : y, "r" : r }
return topicCoordinate
}

MBo MBo
Answer

There is no need in recursive function call. Just organize cycle (pseudocode)

 repeat
     iscollision = false 
     generate x,y
     for other circles check
         if collision occurs
             iscollision = true
             break  //no need to check later circles    
 until iscollision = false

Concerning your recursive confusion - for every recursive call level function instance contains own internal copies of variables, so outer function doesn't know about inner x,y - you don't return them in this code piece:

  if (collision > 0) {
    vvvvvvvvvvvvvvvvvv
    generateRandomCoordinate(d, r)
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}
Comments