0

I have an online game server that works as follows:

  1. Once a player connects, he is in one of predefined sessions (consider them physical location, e.g. Island, Underground location, etc.).
  2. Then any action (movement, attack) is always broadcasted to all other players in the same session. Also when he enters a session, all items dropped in that session are sent to him, as well as players who are there.

This is simple and easy but in the client, the concept of splitting the game into locations is ruining the experience of "one world", if you know what I mean. I am trying to figure out a way how to always broadcast/receive data only about objects that are close enough but I realize that iterating through all players/items everytime and comparing the distance would be a nonsense.

Is there any standard approach that I could use?

8
5

The standard approach is to divide your world up into large squares/cubes and keep track of which each player is in.

You can then iterate over the players in the square the player is in, rather than all the players in the world.

The problem comes near the edges of the square. Here you need to check adjacent squares. There are some clever tricks where you have two overlapping grids of squares if you need to optimise.

Boxes are efficient because your players/objects will have x,y(,z) coordinates. A simple comparison is all that's needed to know when they move out of one box and into another.

If required once you have the list of 'nearby' players, you can then calculate the actual distance to each other player and exclude the 'corner' ones

Here is a good article on the subject:

http://gameprogrammingpatterns.com/spatial-partition.html

For example a simplistic approach

List<Square> squares

class Square
{
    public int x; //grid position of square
    public int y; //grid position of square
    public double top; //game world limits of square
    public double bottom;
    public double left;
    public double right;
    List<Player> Players // players in the square
}

Player.Update()
{
    if(position.x > mySquare.right) { //move to next square }
}

Game.FindNearbyPlayers
{
    var players = player.MySquare.Players()
    players.AddRange(getSquareByLocation(player.MySquare.x -1, player.MySquare.y))... etc
}

I should note that if you are using a game engine it will probably have some built in ways of searching the game world in an efficient way.

4
  • I was thinking about that but as you say, the problem comes near the edges, or when switching from one to another. If player A is in the square 1, near the edge, and player B is in the square 2, near the edge of 1, they need to see each other. Hmm but maybe iterating through 5 quares (up, down, left, right, center) would still be good.
    – John V
    Sep 5 '18 at 15:39
  • ill see if i can add a diagram
    – Ewan
    Sep 5 '18 at 15:42
  • Thanks. I think a grid/two dimensional array could work, where the coordinates would be based on the required cell size: e.g. Grid X coordinate= player X / 1500. So a player with X=3100 would be in the second square. But then there would need to be some "super" list in each square, as I have 3 lists: for players, for items, and for NPCs.
    – John V
    Sep 5 '18 at 15:53
  • I would go with a dictionary.. let me add more
    – Ewan
    Sep 5 '18 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.