Checking if values in object array fit into a range?

user_683068 0
Viewed 110

I have an array of objects. Every object represents a square that's being drawn on the screen - x/y for placement and s for size, c for color).

const elements = [
  { x: 0, y: 0, s: 20, c: 'red' },
  { x: 110, y: 55, s: 7, c: 'blue' },
  { x: 250, y: 250, s: 50, c: 'green' },
  { x: 400, y: 400, s: 30, c: 'pink' }
]

That's how those would look on a canvas or just the page (doesn't have to be canvas really):

enter image description here

Now Imagine I have a 25x25px black square that is rendered instead of my cursor. When I move cursor over one of the colourful squares - so the square is fully covered - my pointer "eats" them up, so they disappear from the array and the canvas. Just like eating food in good old snake!

const pointer = { x: event.pageX, y: event.pageY, s: 25, c: 'black' }

So doing this:

enter image description here

Would remove elements[1] aka { x: 110, y: 55, s: 7, c: 'blue' }. As my cursor covers the whole blue square. I can't obviously eat up the green square as it's bigger than my cursor.

My question is - what's the best algorithm to find what items in my elements array are fully covered by the cursor considering I could have a lot of colourful squares (let's say over 1000)?

I've been trying to filter the covered item like so:

let squareCovered = elements.filter(square => square.x == pointer.x && square.y == pointer.y);

But this is not good enough as does not take both squares and cursors sizes, so I always have to put the cursor exactly at the very center of the square. When I'm trying to introduce sizes in this filtering method my project gets really laggy very fast.

Any hints? Is there a performant algorithm for this?

Feel free to edit the question title, no idea what I'm actually asking for.

game-development canvas arrays javascript
1 Answers

Touching the DOM is the expensive part; you'll be able to brute-force this up to a surprisingly large number of squares if you work as much as possible against the source data instead of the rendered page.

The only DOM manipulation below, other than initializing the layout, is repositioning the black square on mouse move and removing the "eaten" elements; looping through the elements array is much faster than looping through them as DOM nodes.

Here's a demo with 10,000 squares; it starts to get laggy at about 25,000 squares:

const colors = ['red', 'blue', 'green', 'violet', 'indigo', 'pink', 'orange', 'bisque', 'chocolate', 'gold', 'fuschia', 'firebrick', 'peru'];

// make a lot of squares.
const elements = []
for (let i = 0; i < 10000; i++) {
  elements.push({
    x: Math.floor(Math.random() * window.innerWidth),
    y: Math.floor(Math.random() * window.innerHeight),
    s: Math.floor(Math.random() * 10), // keeping them small or the screen gets too crowded with uneatable squares
    c: colors[Math.floor(Math.random() * colors.length)]
  });
}

// quick and dirty way to draw the squares:
let squaresHTML = "";
for (let i = 0; i < elements.length; i++) {
  let el = elements[i];
  squaresHTML += `<div id="square${i}" style="position:absolute; left:${el.x}px; top: ${el.y}px; width: ${el.s}px; height: ${el.s}px; background-color: ${el.c}"></div>`;
}

// This is *much* faster than a lot of createElement() appendChild() stuff
document.getElementById('container').innerHTML = squaresHTML;

// handle mousemove:
const cursor = document.getElementById('cursor');
const apothem = cursor.clientWidth / 2;
document.body.addEventListener('mousemove', e => {

  // position the black square:
  [cursor.style.left, cursor.style.top] = [`${e.clientX - apothem}px`, `${e.clientY - apothem}px`];


  // brute force search for overlaps:
  for (let i = 0; i < elements.length; i++) {
    let el = elements[i];
    if (
      (el.x >= e.clientX - apothem) &&
      (el.y >= e.clientY - apothem) &&
      (el.x + el.s <= e.clientX + apothem) &&
      (el.y + el.s <= e.clientY + apothem)
    ) {
      // found a sqare that is completely covered; "eat" it (if we haven't already):
      if (document.getElementById(`square${i}`)) {
        document.getElementById(`square${i}`).remove()
        // Do not modify the elements array here! The indexes are hardcoded!
      }
    }
  }
})
body {
  overflow: hidden
}

#container {
  width: 100vw;
  height: 100vh
}

#cursor {
  width: 25px;
  height: 25px;
  position: absolute;
  background-color: black
}
<div id="container"></div>

<div id="cursor"></div>

If I had to further optimize this, I'd probably break the page up into "zones" and precalculate which squares are in which "zone"; that way when the mouse moves you can quickly identify which subset of elements you need to iterate over. (Squares that overlap zone boundaries would add some complexity but you could work around that by either duplicating the squares’ entries for each relevant zone, or basing both their zone and the “which zone am I searching” on anything consistent, say, the squares’ top left pixel.)

user_34123220
Related