Algorithm for searching a grid radially from a point

Question

I have an object that sits at point 0,0. This object cannot share space with any other object of its type that may appear on top of it, next to it, above it, etc.. There may be more than a few of these objects present overlapping each other and i have no knowledge of where the other ones are placed until i try the collision detection method.

My thinking is that i'll use a collision detection along side a grid search. Along the lines of the photo below.

The object will first try its default best case location. If that doesn't work then it tries to the left, left-above, left-below, etc, until it has searched all the #1 positions. Then it moves onto the #2 positions and so on until it finds a place to drop the element where it won't be overlapping another.

this is the code i'm playing around with right now but it is choosing some very, very random locations for things. I'm pretty sure it isn't following the algorithm i described above.

  for (let i = 0; i < 5 && this._hasCollisions(this._tagWrapper); i++) {
    /**
     * This algorithm explores positions inside nested boxes.
     * The move algorithm behaves the following way. It goes,
     * down, up, left, down, up, right * 2, repeat.
     *
     * For example this is how it works given the height of 5 and a width of 7
     * numbers are expressed in the offset generated
     * 1: 5,0       4: 5,-7     7: 5,7      10: 10,-14
     * 2: -5,0      5: -5,-7    8: -5,7     11: -10,-14
     * 3: 0,-7      6: 0,7     9: 0,-14
     */

    // Calculate which box the collision detector is working in
    // This happens every 9 iterations
    let multiplier = (i / 9) + 1;

    /**
     * Get the x offset
     */
    if (i % 3 === 0) {
      // Clear the height offset on multiples of 3
      xOffset = 0;
    } else {
      // Set the height to the multiplier
      xOffset = this._tagWrapper.offsetWidth * multiplier;
    }
    if (i % 3 === 2) {
      // Get the sequence 2, 5, 8, 11, 14, etc..
      xOffset *= -1;
    }

    /**
     * Get the y offset
     */
    if (i > 2) {
      // Set the width to a multiple of the multiplier and assign the existing negativeness
      yOffset = this._tagWrapper.offsetHeight * multiplier * (yOffset > 0 ? 1 : -1);
    }
    if (i % 3 === 0) {
      // Flip the sign every 3 numbers
      yOffset *= -1;
    }
    console.log('iteration', i);

    this._tagWrapper.style.top = (basePosition.y + yOffset) + 'px';
    this._tagWrapper.style.left = (basePosition.x + xOffset) + 'px';
  }

What is the best way to go about performing this search? I already hav

Answer 1

I would suggest using distance solution

point1 has x1 and y1

point2 has x2 and y2

var d = Math.sqrt( (x2-=x1)*x2 + (y2-=y1)*y2 );

link here: Get distance between two points in canvas

Answer 2

Something like this work? (most of the code is just for the visualization)

// just draw a table to visualize
var SIZE = 15;
for (var i = 0; i < SIZE; i++) {
  $("#a").append("<tr>");
  for (var j = 0; j < SIZE; j++) {
    $("#a > tr").last().append("<td>.</td>");
  }
}


// where to start searching from
var startX = 8;
var startY = 8;


function loop() {
  // tell the world which grid we are on
  $("#a > tr:nth-child(" + y + ") > td:nth-child(" + x + ")").css("backgroundColor", "red");

  // check if done here!!! - x and y are our positions in the grid
  // also do bounds checking here

  if (isX) {
    x = x + xDirection;
    i--;
    if (!i) {
      // switch dimension
      isX = !isX;
      i = moveFor;
      // switch direction
      xDirection *= -1;
    }
  } else {
    y = y + yDirection;
    i--;
    if (!i) {
      // switch dimension
      isX = !isX;
      // increase the width / height we are spanning
      moveFor += 1;
      i = moveFor;
      // switch direction
      yDirection *= -1;
    }
  }

  // jsut so that we have a nice animation
  if (x > 0 && y > 0 && x <= SIZE && y <= SIZE) {
    setTimeout(loop, 10)
  }
}

var x = startX;
var y = startY;
var moveFor = 1;
// our step (down) counter
var i = moveFor;
var xDirection = -1;
var yDirection = -1;
// are we moving along x or y
var isX = true;

loop();

body {
  font-family: monospace;
}

td {
  height: 20px;
  width: 20px;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table>
  <tbody id="a"></tbody>
</table>

Answer 3

Here is an implementation of scanning points in a ring around a center point. You define the center point and the distance you want to sample and it returns the list of points in clock-wise order. It is in Python not JavaScript but it is simple enough that you can translate if needed.