How do I check array values against other array values without O(N^2) complexity-CodePudding

I am building a multiplayer game, qne I am trying to have the server send data about ONLY the players that are being displayed on a player's screen, to avoid unneeded player data being sent.

Say I have an array like this

var players = [
{ x: 100, y: 100, range: 50, id: 1},
{ x: 150, y: 100, range: 100, id: 2},
{ x: 250, y: 150, range: 50, id: 3},
....
]

(Note: the data doesn't need to be in an array, it can be in any type of storage based on what would be efficient)

To calculate if a player is in another player's range, I just need to check the distance between the 2 players, and if the distance is less than the range of the player, then the other player is in range with the first player.

Code example:

const distance = (x1, y1, x2, y2) => Math.hypot(x2 - x1, y2 - y1); 

function isPlayerInRange(player,checkPlayer) {
  return distance(player.x, player.y, checkPlayer.x, checkPlayer.y) < player.range
}

Now my goal is to find what player's are in which players range. An example out would be like this:

[
{id: 1, inRange: [3,4]},
{id: 2, inRange: []},
{id: 3, inRange: [1]}
]

Where inRange is the list of id's of the player's that are in range.

Each player has a different range because in my game, players can grow causing them to see more of the map.

Now my initial solution was somewhat like this:

result = [];
players.forEach((player)=>{
   result[player.id].push({ id: player.id, inRange: [] })
   players.forEach((checkPlayer)=>{
       if(isPlayerInRange(player, checkPlayer)) 
           result[result.length-1].inRange.push(checkPlayer.id)
   });
});

Now while this solution does technically work, it is very inefficient, having a O(N^2) complexity.

What does this mean? Well basically the more players there are, the exponentially complex this loop gets

For example:

2 players - 4 calculations
3 players - 9 calculations
4 players - 16 calculations
and so on... until
100 players - 10,000 calculations

For a game that should handle many hundred players in a single server, this is not a valid solution.

Is it possible to do this operation with a O(N), O(2N) or even better O(log N) complexity, and if so, how would it be done in pseudocode?

Thanks.

CodePudding user response：

tl;dr: Key word for this answer is Quadtree

Theoretically, you can't. Because the number of players in range of a player i is proportional to the total number of players (on average: if surface of a disk centered at player i and with radius player[i].range, is α% of the surface of the whole game, then, on average, listing the players in range of player i is O(α/100×N)=O(N). And doing that for all players is therefore O(N²).

I mean, when the simple fact to print the result cost O(N²), then, there can't be any algorithm faster than O(N²). And the expected result you've shown has a size O(N²)

[
{id: 1, inRange: [3,4]},
{id: 2, inRange: []},
{id: 3, inRange: [1]}
]

You have N lines in there, and each line has a fraction of N columns. So any way to create this O(N²) sized result has to cost at least O(N²) operations. Even just hard coding the result :)

Now, in practice, if the game is scaled so that the number of other players in range is not, most of the time, expected to be more than a given constant, then, you could consider that listing players in range is O(1) (not really, from a theoretical point of view, since the postulate can't hold if N grows enough. But in practice, you may know that it doesn't. Exactly like using a hash table to search for a symbol doesn't change in theory the complexity of the search, but changes it in practice, if hash table has been scales so that there are almost never more than 2 or 3 collisions)

To simplify, if your problem had been a 1D problem (just x), then you would have sorted players by x. So search for boundaries [x-range, x range] in the list of players would have been O(log(N)) (and then the listing of all players in that boundaries would have been in theory O(N), but in practice O(1). So, O(log(N)) prevails. Or O(N.log(N)) for all players).

In 2D, it is harder to sort your array. But there is an equivalent, that are quad-trees (look it up in Google. I am even pretty sure there are libraries in JS)

Quadtrees are the 2D equivalent of binary search tree in 1D.

If game universe is (x,y)∈[0,1000)², then it split your player list in 4 sublists: the one for players in [0,500)×[0,500), the one for player in [500,1000)×[0,500), the one for players in [0,500)×[500,1000) and the one for players in [500,1000)×[500,1000). And each of these sublists are themselves divided in 4 sublists. Etc. In each branch until sublist contains less than k players.

(k being a constant. 1 if you want leaves sublist to contain only one player. But in practice, we use higher values, because once a sublist is reduced to a small list of players, it is sometimes faster to use a O(N) algorithm than a O(log(N)) one. So, let say k=5)

Then, on this quadtrees representation you have many possible operations. For example, inserting a new player (start from roots, and decide at each stage in which of the 4 nodes you will insert your player. Until you reach a leaf, that you may decide to subdivise in 4 new leaves. O(log(N))). Moving one (either you just delete it, and insert a new one. Or you move it up to the first ancestor that have correct bounds, and then move it down to its leaf. O(log(N)) also, but smaller).

Or, what is your concern here: searching for players in range: you explore every branches whose square area (size 1000×1000 for root, 500×500 for level 1 branches, 250×250 for level 2, ...) intersect the circle. O(log(N)) if the size of the circle can be considered negligible before the size of the area. O(N) otherwise (see previous comment).

I don't think it would be pertinent in this answer to start writing algorithm. You should first look it up on Google. All information can't fit in an answer. And, of course, ask other questions if needed for implementation.

But, although, in theory, it would not avoid the O(N) per player, O(N²) for all players cost, that is not avoidable anyway, in practice, if the search area is considered negligible, it is a O(log(N)) search algorithm.

And anyways, quad-trees are the way to go when trying to get 2D things by their position in a 2D map.

CodePudding user response：

A reasonably simple implementation that should reduce your complexity closer to O(N) would be to start with an empty array of players. Every time a player is added, make the computation of which players they are in range to. This will be O(N). Note I would use an object rather than an array so that testing for in range is O(1). For example:

const addPlayer = (id) => {
  // create a player object
  // ...
  player.inRange = {}
  // check range to all existing players
  players.forEach((checkPlayer)=>{
    const inRange = isPlayerInRange(checkPlayer, player)
    checkPlayer.inRange[player.id] = inRange 
    player.inRange[checkPlayer.id] = inRange 
  })
  players.push(player)
}

You can determine if two players are in range by player1.inRange[player2.id].

Then, whenever a player moves by more than a certain amount (set the amount higher to limit the rate of computations, lower to decrease the detection time for when players come into/go out of range), update the inRange values for that player and the others. Again, this is O(N). For example:

const movePlayer = (player, newx, newy) => {
  if (distance(player.x, player.y, newx, newy) > <some value>) {
    player.x = newx
    player.y = newy
    players.forEach((checkPlayer)=>{
      const inRange = isPlayerInRange(checkPlayer, player)
      checkPlayer.inRange[player.id] = inRange 
      player.inRange[checkPlayer.id] = inRange
    })
    // do whatever other updates you need
    // ...
}