怎么避免重复？

Question

美好的一天，

我正在生成一些颜色，大小和位置的圆圈。所有这些都是随机的。

但是，我的问题是我不希望它们发生碰撞，因此没有圆圈在另一个内部，甚至没有一点。

逻辑内部详细解释了代码，我想知道为什么失败以及为什么无限循环。

重要的功能是：

checkSeparation和setPositions

window.addEventListener("load", draw);
 
 function draw() {
  var canvas = document.getElementById("balls"), // Get canvas
      ctx = canvas.getContext("2d"); // Context
      
  canvas.width = document.body.clientWidth; // Set canvas width
  canvas.height = document.documentElement.scrollHeight; // Height
      var cW = canvas.width, cH = canvas.height; // Save in vars
      ctx.fillStyle = "#fff022"; // Paint background
      ctx.fillRect(0, 0, cW, cH); // Coordinates to paint
      var arrayOfBalls = createBalls(); // create all balls
      setPositions(arrayOfBalls, cW, cH);
      arrayOfBalls.forEach(ball => { // iterate balls to draw
      ctx.beginPath(); // start the paint
      ctx.fillStyle = ball.color;
      ctx.arc(ball.x, ball.y, ball.radius, 0, (Math.PI/180) * 360, false); // draw the circle
      ctx.fill(); // fill
      ctx.closePath(); // end the paint
      });
 }

 function Ball() {
  this.x = 0; // x position of Ball
  this.y = 0; // y position of Ball
  this.radius = Math.floor(Math.random() * ( 30 - 10 + 1) + 10);
  this.color = "";
 }
 
 Ball.prototype.setColor = function(){
 for(var j = 0, hex = "0123456789ABCDEF", max = hex.length,
    random, str = ""; j <= 6; j++, random = Math.floor(Math.random() * max), str += hex[random])
    this.color = "#" + str;
 };
  
 function random(val, min) {
  return Math.floor(Math.random() * val + min); // Random number
 }
 
 function checkSeparation(value, radius, toCompare) {
   var min = value - radius, // Min border of circle
       max = value + radius; // Max border of circle
       // Why ? e.g => x position of circle + this radius it will   be its right edge 
       for(; min <= max; min++) {
       if(toCompare.includes(min)) return false;
       /*
       Since all the positions previously obtained, I add them to          the array, in order to have a reference when verifying the          other positions and that they do NOT collide.
       Here I check if they collide.

       In the range of:

       [pos x - its radius, pos x + its radius]
       */
       }
   return true;   // If they never collided, it returns true
 }
 
 function createBalls() { 
  var maxBalls = 50, // number of balls
      balls = []; // array of balls
       
     for(var j = 0; j < maxBalls; j++) { // create 50 balls
     var newBall = new Ball(); // create ball 
         newBall.setColor(); // set the ball color
         balls.push(newBall); //push the ball to the array of balls
     }
     return balls; // return all balls to draw later
 }
 
 
 function setPositions(balls, canvasW, canvasH) {
  var savedPosX = [], // to save x pos of balls
      savedPosY = []; // to save y pos of balls
  for(var start = 0, max = balls.length; start < max; start++) {
   var current = balls[start], // current ball
       randomX = random(canvasW, current.radius), // get random value for x pos
       randomY = random(canvasH, current.radius); // get random value for y pos

       if(checkSeparation(randomX, current.radius, savedPosX)) {
         current.x = randomX; // If it position, along with your radio does not touch another circle, I add the position
       } else { 
         // start--; continue;
         console.log("X: The above code causes an infinite loop");
       }
       if(checkSeparation(randomY, current.radius, savedPosY)) {
         current.y = randomY;
       } else {
         // start--; continue;
         console.log("Y: The above code causes an infinite loop");
       }
  }
 }

body,html {
 margin: 0; border: 0; padding: 0; overflow: hidden;
}

<canvas id="balls"></canvas>

Answer 1

在您的代码中，您可以通过已使用的x和y位置的数组来测试可能的碰撞，但是您永远不会向这些数组添加新位置。您还可以分别检查x和y坐标，这意味着您实际上正在测试边界框的碰撞。

当它们的中心之间的距离小于它们的半径之和时，两个圆碰撞，因此您可以使用：

function collides(balls, n, x, y, r) {
    for (let i = 0; i < n; i++) {
        let ball = balls[i];
        let dx = ball.x - x;
        let dy = ball.y - y;
        let dd = dx*dx + dy*dy;
        let rr = r + ball.radius;

        if (dd < rr * rr) return true;
    }

    return false;
}

function setPositions(balls, canvasW, canvasH) { 
    for (let i = 0, max = balls.length; i < max; i++) {

        let ball = balls[i],
            r = ball.radius,
            maxTries = 20;

        ball.x = -canvasW;
        ball.y = -canvasH;

        for (let tries = 0; tries = maxTries; tries++) {
            let x = random(canvasW - 2*r, r),
                y = random(canvasH - 2*r, r);

            if (!collides(balls, i, x, y, r)) {
                ball.x = x;
                ball.y = y;
                break;
            }
        }
    }
}

对于50个球来说这相当快，但如果你有更多的球，它会很慢。在这种情况下，一些空间数据结构可以加速碰撞搜索。

你还必须防止没有找到好地方的情况。上面的代码在20次尝试后放弃并将球移到可见画布之外。您可以通过半径排序球并首先对大球进行平整来提高放置球的几率。

最后，您将一个十六进制数字添加到随机颜色太多。 （那个for循环，循环控制中发生的一切都很糟糕，顺便说一句。）