Algorithm: Modern Fisher-Yates algorithm for shuffling an array

If you have some information or images stored in an array and every time you wish to show those things in random order, then you may need to shuffle the array. Fisher-Yates algorithm is one of the efficient algorithms that can be implemented to achieve this task.

Suppose we have an array a[] containing n elements. The modern Fisher-Yates algorithm follows the given steps-

  1. Iterate through the array from i=n to 1 (assuming the array starts from 0 and we will skip the first element). So, the loop runs n-1 times.
  2. At each iteration,choose a random number j between 0 and i and select the random element a[j].
  3. Swap a[i] and a[j].

To generate the random number we will use the JavaScript’s built-in math function Math.random() which returns any floating number between 0 and 1. Since, we need an integer we will round it up using Math.floor() function.

Advertisements

Algorithm: Collision or Intersection of circles and rectangles

Knowing how to handle collision between different objects of varying shapes will come in handy if you are into game development or just enjoy solving algorithmic problems. In this post I discussed the conditions to determine the collision between circles, non-rotated rectangles and collision between rectangle and circle.

Circle-Circle collision

Two circles collide if the distance between them is less than the sum of their radii. i.e

collision or intersection of circles
Overlapping/Intersection of circles
intersection or collison of circles
Non-overlapping circles

The distance is calculated using Pythagoras formula by taking the sum of the square of the differences of x-coordinates and y-coordinates of two circles and square rooting them.

d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

Now,¬†let’s write the code-

var c1={
    x:30,
    y:25,
    r:10;
}
var c2={
    x:20,
    y:25,
    r:10;
}
var dx=c1.x-c2.x,
    dy= c1.y-c2.y,
    dist=Math.sqrt(dx*dx+dy*dy),
    rdist=c1.r+c2.r;
if(dist<=rdist){
   console.log("Collision detected!");
}

Rectangle-Rectangle Collision

Rectangles collide if there is no gap between them and here the rectangles considered must be non-rotating.

collision/intersection/overlapping of rectangles
Overlapping/Intersection of Rectangles
var r1={
    x:30,
    y:25,
    w:50,
    h:50;
}
var r2={
    x:20,
    y:25,
    w:50.
    h:30;
}
if(r1.x<r2.x+r2.w && r1.x+r1.w>r2.x &&
   r1.y<r2.y+r2.h && r1.y+r1.h>r2.y){
   console.log("Rectangles collided");
}

Rectangle-Circle Collision

We find the closest point of the rectangle from the circle’s center. If the distance of this point from the center is less than the radius, then the two shapes collide. The nearest point is found by clamping circle’s center to rectangle’s coordinates.

rect2
Overlapping/intersection of circle and rectangle
var circle={
    x:40,
    y:60,
    r:20;
}
var rect={
   x:35,
   y:50,
   w:100,
   h:50;
}
var nX=circle.x-Math.max(rect.x,Math.min(circle.x,rect.x+rect.w),
    nY=circle.y-Math.max(rect.y,Math.min(circle.y,rect.y+rect.h);
if(nX*nX+nY*nY<=circle.r*circle.r){
   console.log("Collision!");
}

Note that the rectangle here must not also be rotated.