1
\$\begingroup\$

Given a 2d scene and 10,000 players with coordinates in the scene, I want to implement a function, the input is a circle with the center coords and its radius, the output is those players that lie on the circle.
And the function will be called very often
My solution is to divide all players into a quadtree according to their coordinates and limit the tree height. Each tree node will contain some players. Then we can compare the center point P of the circle and players in the tree node containing P to calculate the result. In this way, we can cut down many unnecessary calculations.
So is there a more efficient solution?

\$\endgroup\$
2
  • \$\begingroup\$ Our site works best with actual issues. You have a solution that appears good for the issue at hand so the suggestion is usually to test it and come back to us if it did not fix it. \$\endgroup\$
    – Vaillancourt
    Oct 22 '21 at 10:21
  • \$\begingroup\$ @Vaillancourt Thanks for your suggestion. Actually, this is what an interviewer asks me, but my solution may not be what he wants. Anyway, I'll try and code it. \$\endgroup\$ Oct 22 '21 at 11:06
1
\$\begingroup\$

How about a spatial hash using concentric rings as buckets? Basically the same concept as your quad tree, but much simpler.

Here's a quick example:

#include <stdio.h>
#include <time.h>
#include <cmath>
#include <list>

//total number of buckets, tweak as needed
const int NUM_BUCKETS = 100;

//max radius of the circle
const double WORLD_RADIUS = 100'000.0;

const double BUCKET_SIZE = WORLD_RADIUS / NUM_BUCKETS;

struct Player {
    double x, y;
    int ID; //unique player ID
    int bucket;
};

//our circle
struct {
    double x, y;
    double radius;
} circle;

std::list<Player*> buckets[NUM_BUCKETS];

double calcDistance(double x0, double y0, double x1, double y1){
    float dx = x0 - x1;
    float dy = y0 - y1;
    return sqrt((dx*dx)+(dy*dy));
}

int clampi(int v, int min, int max){
    if(v < min) return min;
    if(v > max) return max;
    return v;
}

//returns the bucket that contains an object at distance `dist`
int hashDistance(double dist){
    int ret = (int) floor(dist / BUCKET_SIZE);
    return clampi(ret, 0, NUM_BUCKETS - 1);
}

//returns the bucket that a player is in
int getPlayerBucket(Player *player){
    double dist = calcDistance(player->x, player->y, circle.x, circle.y);
    return hashDistance(dist);
}

//update a single player's bucket
void updatePlayerBucket(Player *player){
    int old_bucket = player->bucket;
    int new_bucket = getPlayerBucket(player);
    if(old_bucket != new_bucket){
        if(old_bucket >= 0){
            buckets[old_bucket].remove(player);
        }
        buckets[new_bucket].push_back(player);
        player->bucket = new_bucket;
    }
}

//brute force update all player's buckets
void updateAllPlayers(Player *players, int num_players){
    for(int i = 0; i < num_players; i++){
        updatePlayerBucket(&players[i]);
    }
}

//prints all of the players in the circle
void printPlayersInCircle(){
    int max_bucket = hashDistance(circle.radius) - 1;

    int total = 0;

    //we can assume that players in these buckets are inside the circle
    for(int i = 0; i < max_bucket - 1; i++){
        for(Player *player: buckets[i]){
            total++;
            printf("[%d] %d: (%f, %f)\n", player->bucket, player->ID, player->x, player->y);
        }
    }

    //we can't assume that all players in the last bucket are in the circle
    //need to double-check their distances to be sure
    for(Player *player: buckets[max_bucket]){
        float dist = calcDistance(player->x, player->y, circle.x, circle.y);
        if(dist <= circle.radius){
            total++;
            printf("[%d] %d: (%f, %f)\n", player->bucket, player->ID, player->x, player->y);
        }
    }

    printf("Total players in circle: %d\n", total);
}

int main(int argc, char **argv){
    //init players
    srand(time(0));
    int num_players = 10'000;
    Player *players = (Player*) malloc(sizeof(Player) * num_players);
    for(int i = 0; i < num_players; i++){
        players[i].ID = i;
        players[i].x = ((double)(rand() % (int)WORLD_RADIUS)) - (WORLD_RADIUS / 2.0);
        players[i].y = ((double)(rand() % (int)WORLD_RADIUS)) - (WORLD_RADIUS / 2.0);
        players[i].bucket = -1;
    }

    //init circle
    circle.x = 0;
    circle.y = 0;
    circle.radius = WORLD_RADIUS / 4.0;

    //place all players into buckets
    updateAllPlayers(players, num_players);

    printPlayersInCircle();
    return 0;
}

Things to consider:

  • If the circle origin (not radius) ever changes, all buckets need to be recalculated
  • WORLD_RADIUS and NUM_BUCKETS should be tuned to improve the distribution of players into buckets (if you need that; it's not important for simply querying players in the circle)
  • Any players outside of WORLD_RADIUS will fall into the outermost bucket
  • You can optimize this by calling updatePlayerBucket only when a player actually moves
  • This algorithm can be parallelized relatively easily, such as by storing buckets in thread local storage to avoid locks/syncs, or something similar
  • You may be able to use the squared distance to avoid the sqrt operation (10'000 players isn't that huge though, so you probably don't need to bother. Profile as always)
  • If you profile this sample code, remember to disable the printfs to get an accurate measurement
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .