代码之家  ›  专栏  ›  技术社区  ›  carlos cerda diaz

如何避免重复?

  •  -2
  • carlos cerda diaz  · 技术社区  · 7 年前

    很好的一天,

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

    但是,我的问题是,我不希望它们发生碰撞,这样就没有圆在另一个圆内,甚至一点也没有。

    代码中详细解释了逻辑,我想知道为什么会失败,为什么会出现无限循环。

    重要功能包括:

    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>
    1 回复  |  直到 7 年前
        1
  •  1
  •   M Oehm    7 年前

    在您的代码中,您通过已经使用的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 顺便说一句,在循环控制中发生的一切都很可怕。)