Implementing quadtree collision with javascript?

Question

I am working on an io game similar to agar.io and slither.io (using node.js and socket.io) where there are up to 50 players and around 300 foods in 2d space on the map at a time. Players and food are both circular. Every frame, the server needs to check whether a player has collided with food and act accordingly. Players and foods are both arrays of JSON objects with varying coordinates and sizes. The brute-force method would be looping through all the foods, and for each food, looping through all players to see if they are in collision. Of course, that makes 300*50 iterations, 60 times per second (at 60fps), which is of course way too heavy for the server.

I did come across the quadtree method which is a new concept to me. Also my scarce knowledge on javascript is making me wonder how exactly I might implement it. The problems that I cannot solve are the following: 1. Since players can theoretically be of any size (even as big as the map), then how big would the sections that I divide the map in have to be? 2. Even if I do divide the map into sections, then the only way I can see it working is that for every player, I need to get the foods that share the same sections as the player. This is the big question - now matter how much I think of it, I would still need to loop through every food and check if it's in the required sections. How would I do that without looping? Because that still makes 50*300 iterations, 60 times per second, which does not sound in any way faster to me.

tldr: I need to find a way to detect collisions between a set of 50 objects and a set of 300 objects, 60 times per second. How do I do that without looping through 50*300 iterations at 60 fps?

I could not find any information online that answers my questions. I apologize in advance if I have missed something somewhere that could yield the answers I seek.

Answer 1

This is a small example that only checks a single layer, but I think it demonstrates how you can check for collisions without iterating over all objects.

// 2d array of list of things in said square
// NOT A QUADTREE JUST DEMONSTRATING SOMETHING
let quadlayer = [];
for (let i=0;i<4;++i) {
    quadlayer[i] = [];
    for (let j=0;j<4;++j) {
        quadlayer[i][j] = [];
    }
}

function insertObject(ur_object) {
    quadlayer[ur_object.x][ur_object.y].push(ur_object);
}

function checkCollision(ur_object) {
    let other_objects = quadlayer[ur_object.x][ur_object.y];
    console.log('comparing against '+other_objects.length+' instead of '+100);
}

for (let i=0;i<10;++i) {
    for (let j=0;j<10;++j) {
        insertObject({
            x:i%4,
            y:j%4
        })
    }
}


checkCollision({x:1,y:2});

Answer 2

An interesting problem... Here's another take, which essentially uses the sweep line algorithm. (For a good explanation of the sweep line algorithm, see https://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/ ).

The typical performance of a sweep line algorithm is O(n log n) compared to brute force of O(n^2).

In this particular implementation of the sweep line algorithm, all objects (food and people) are kept in a queue, with each object having two entries in the queue. The first entry is x - radius and the second entry is x + radius. That is, the queue tracks the lower/left and upper/right x bounds of all the objects. Furthermore, the queue is sorted by the x bounds using function updatePositionInQueue, which is essentially an insertion sort.

This allows the findCollisions routine to simply walk the queue, maintaining an active set of objects that need to be checked against each other. That is, the objects that overlap in the x dimension will be dynamically added and removed from the active set. Ie, when the queue entry represents a left x bound of an object, the object is added to the active set, and when the queue entry represents an right x bound of an object, the object is removed from the active set. So as the queue of objects is walked, each object that is about to be added to the active set only has to be checked for collisions against the small active set of objects with overlapping x bounds.

Note that as the algorithm stands, it checks for all collisions between people-and-people, people-and-food, and food-and-food...

As a pleasant bonus, the updatePositionInQueue routine permits adjustment of the sorted queue whenever a object moves. That is, if a person moves, the coordinates of their x,y position can be updated on the object, and then updatePositionInQueue( this.qRight ) and updatePositionInQueue( this.qLeft ) can be called, which will look to the previous and next objects in the sorted queue to move the updated object until its x bound is properly sorted. Given that the objects position should not be changing that much between frames, the movement of the left and right x bound entries in the queue should be minimal from frame-to-frame.

The code is as follows, which towards the bottom randomly generates object data, populates the queue, and then runs both the sweep line collision check along with a brute force check to verify the results, in addition to reporting on the performance as measured in object-to-object collision checks.

var queueHead = null;

function QueueEntry(paf, lor, x) {
  this.paf = paf;
  this.leftOrRight = lor;
  this.x = x;
  this.prev = null;
  this.next = null;
}

function updatePositionInQueue( qEntry ) {
  
  function moveEntry() {
    // Remove qEntry from current position in queue.
    if ( qEntry.prev === null ) queueHead = qEntry.next;
    if ( qEntry.prev ) qEntry.prev.next = qEntry.next;
    if ( qEntry.next ) qEntry.next.prev = qEntry.prev;
    
    // Add qEntry to new position in queue.
    if ( newLocation === null ) {
      qEntry.prev = null;
      qEntry.next = queueHead;
      queueHead = qEntry;
    } else {
      qEntry.prev = newLocation;
      qEntry.next = newLocation.next;
      if ( newLocation.next ) newLocation.next.prev = qEntry;
      newLocation.next = qEntry;
    }
  }
  
  // Walk the queue, moving qEntry into the
  // proper spot of the queue based on the x
  // value.  First check against the 'prev' queue
  // entry...
  let newLocation = qEntry.prev;
  while (newLocation && qEntry.x < newLocation.x ) {
    newLocation = newLocation.prev;
  }
  if (newLocation !== qEntry.prev) {
    moveEntry();
  }

  // ...then against the 'next' queue entry.
  newLocation = qEntry;
  while (newLocation.next && newLocation.next.x < qEntry.x ) {
    newLocation = newLocation.next;
  }
  if (newLocation !== qEntry) {
    moveEntry();
  }

}

function findCollisions() {

  console.log( `\nfindCollisions():\n\n` );
  var performanceCount = 0;
  var consoleResult = [];
  
  activeObjects = new Set();
  
  var i = queueHead;
  while ( i ) {
  
    if ( i.leftOrRight === true ) {
      activeObjects.delete( i.paf );
    }
    
    if ( i.leftOrRight === false ) {
    
      let iPaf = i.paf;
    
      for ( let o of activeObjects ) {
        if ( (o.x - iPaf.x) ** 2 + (o.y - iPaf.y) ** 2 <= (o.radius + iPaf.radius) ** 2 ) {
          if ( iPaf.id < o.id ) {
            consoleResult.push( `Collision:  ${iPaf.id} with ${o.id}` );
          } else {
            consoleResult.push( `Collision:  ${o.id} with ${iPaf.id}` );
          }
        }
        performanceCount++;
      }
      
      activeObjects.add( iPaf );
    }
    
    i = i.next;
  }
  
  console.log( consoleResult.sort().join( '\n' ) );
  console.log( `\nfindCollisions collision check count: ${performanceCount}\n` );
}

function bruteForceCollisionCheck() {

  console.log( `\nbruteForceCollisionCheck():\n\n` );
  var performanceCount = 0;
  var consoleResult = [];
  
  for ( i in paf ) {
    for ( j in paf ) {
      if ( i < j ) {
        let o1 = paf[i];
        let o2 = paf[j];
        if ( (o1.x - o2.x) ** 2 + (o1.y - o2.y) ** 2 <= (o1.radius + o2.radius) ** 2 ) {
          if ( o1.id < o2.id ) {
            consoleResult.push( `Collision:  ${o1.id} with ${o2.id}` );
          } else {
            consoleResult.push( `Collision:  ${o2.id} with ${o1.id}` );
          }
        }
        performanceCount++;
      }
    }
  }
  
  console.log( consoleResult.sort().join( '\n' ) );
  console.log( `\nbruteForceCollisionCheck collision check count: ${performanceCount}\n` );
}

function queuePrint() {
  var i = queueHead;
  while (i) {
    console.log(`${i.paf.id}: x(${i.x}) ${i.paf.type} ${i.leftOrRight ? 'right' : 'left'} (x: ${i.paf.x} y: ${i.paf.y} r:${i.paf.radius})\n`);
    i = i.next;
  }
}

function PeopleAndFood( id, type, x, y, radius ) {
  this.id = id;
  this.type = type;
  this.x = x;
  this.y = y;
  this.radius = radius;
  
  this.qLeft = new QueueEntry( this, false, x - radius );
  this.qRight = new QueueEntry( this, true, x + radius );
    
  // Simply add the queue entries to the
  // head of the queue, and then adjust
  // their location in the queue.
  if ( queueHead ) queueHead.prev = this.qRight;
  this.qRight.next = queueHead;
  queueHead = this.qRight;
  updatePositionInQueue( this.qRight );
  
  if ( queueHead ) queueHead.prev = this.qLeft;
  this.qLeft.next = queueHead;
  queueHead = this.qLeft;
  updatePositionInQueue( this.qLeft );
 
}

//
// Test algorithm...
//
var paf = [];

const width = 10000;
const height = 10000;

const foodCount = 300;

const foodSizeMin = 10;
const foodSizeMax = 20;

const peopleCount = 50; 
const peopleSizeMin = 50;
const peopleSizeMax = 100;

for (i = 0; i < foodCount; i++) {
  paf.push( new PeopleAndFood(
    i,
    'food',
    Math.round( width * Math.random() ),
    Math.round( height * Math.random() ),
    foodSizeMin + Math.round(( foodSizeMax - foodSizeMin ) * Math.random())
  ));
}

for (i = 0; i < peopleCount; i++) {
  paf.push( new PeopleAndFood(
    foodCount + i,
    'people',
    Math.round( width * Math.random() ),
    Math.round( height * Math.random() ),
    peopleSizeMin + Math.round(( peopleSizeMax - peopleSizeMin ) * Math.random())
  ));
}

queuePrint();

findCollisions();
bruteForceCollisionCheck();

(Note that the program prints the queue, followed by the results of findCollisions and bruteForceCollisionCheck. Only the tail end of the console appears to show when running the code snippet.)

Am sure that the algorithm can be squeezed a bit more for performance, but for the parameters in the code above, the test runs are showing a brute force check of 61075 collisions vs ~600 for the sweep line algorithm. Obviously the size of the objects will impact this ratio, as the larger the objects, the larger the set of objects with overlapping x bounds that will need to be cross checked...

An enjoyable problem to solve. Hope this helps.