Player Visibility Problem

Pat S
  • Player Visibility Problem Pat S

    I'm looking into designing and implementing an online RPG (or more accurately, redesigning an existing piece of server software).

    One of the problems is that of managing visibility. Update data for other players should only be sent to a game client if their player is near the other players (i.e. you shouldn't get health updates for people you can't see on the other side of the map). The main problem is that if you had to compare all the players every time an update is sent, it would just take way too long as the number of players scales (think up to a few thousand players per map and each of them updating up to 3-5 times a second).

    If the players are in a 2D space (it's 3D but the z difference shouldn't affect visibility) what is the best way to manage the visibility of other players?

    My idea is to have a separate thread that compares the space difference of all the players every few seconds or so and stores references to all nearby players in the player's object for easy access when an update needs to be broadcasted.

    The existing system uses grids to organize players, and only uses only players in the current and neighbouring grids to do updates. There are some problems with the system though, as it isn't that efficient (besides knowing which grid they are in, no other caching) and sometimes visibility limits should extend beyond 2 grids of distance.

    Is there a better or easier way? If it can be multithreaded that would obviously be better, and the less main-thread calculation the better.

    (For anyone wondering, the project is in C++).

  • Your current grid system sounds like the spatial hashing system described here.

    In theory, the performance should be fine unless too many entities exist in the same grid block.

    However, the grid-based hashing isn't as commonly used as a Quadtree. The Quadtree is a bit more involved to implement, but it has a few nice features.

    • it costs O(log N) to find something. This is pretty graceful in terms of scaling up to thousands or millions of objects.

    • It isn't fixed at a particular scale. This means that it works just as well when you have 1000 really close to each other or 1000 objects really far apart. Obviously both these cases are not handled gracefully by the grid.

Tags
c++ optimization
Related questions and answers
  • from it. As an added touch i have made it so after you collide while traveling down the randomly generated map (or rather as the walls move uppward while your character stays put) the X chars you've... there is no collision, reseting "numb_coll" to 0 and screwing the lives/shields up. All this nonsense is located at the bottom of the main function Finally the Screen.Insert() *function and others like it simply... in the main function * not Finally.. but i believe that te numb_coll problem has something to do with the time and framrate. When running full speed i quickly die upon entering a wall as numb_coll

  • sort of designs other people used to overcome them, or would use. For a little background, I started working on it in my free time last summer. I was initially making the game in C#, but about 3 months... areas of concern I have and wanted to get some opinions on the proper way others have solved them or would solve them. 1. Cyclical Dependencies When I was doing the game in C#, I didn't really have... the active screen is owns the game input. I designed a screen manager that would push and pop screens based on user input. For instance, if you were on a map screen (an input handler/visualizer for a Tile

  • a problem with smoothness. If I reduce my physics updates to 25 per second which I have only done as an experiment then it is a bit jerky. But the game easily runs at higher rates than that so there may... second and 75 frame draws per second. Up until now, it is in the physics update routine that I do the collision detection and response. Your ship can collide with a rock. Your photons (bullets) can... out of the update routine and into the draw routine, seeing as I will be drawing these interpolated frames ? Bear in mind, my highest priority goal is to make this networked: multiple player ships

  • Suppose I have a Spacecraft object in 3D space, controllable by the player. I want it to update its own trajectory, so I give it a function for that (actually it might be inside a controller... of the number of loops and user input and calls the function when appropriate? Something else? Note that the same thing would happen for all the other bodies orbiting in space. However the other bodies would simply have to follow predefined trajectories, no need for an algorithm. The timer object could take care of updating all the trajectories at the right times. Also, if you think

  • I am studying entity indexed components and came up with a naive C++ implementation which just iterates over all entity "hash tables" and applies update/delete/insert functions in place. I'm having trouble maintaining a logical view of the game world (i.e. updates shouldn't be visible while iterating) and there is no attempt at maintaining spatial or temporal coherence of data. I wonder whether... components total. Or is this even feasible? How much I can accomplish with this approach? In essence I want to be able to do something like this with reasonable efficiency: moving_update(DB

  • to be moved then so be it), but i felt it would fit here just a bit, since its a game-dev type question. Anyways, My compiler is MinGW that uses the IDE Code::Blocks. also the operating system that im...I am using Ogre3D, and have been using it for a while. Also lately, I have been using the Opengl Rendering system that is included in Ogre, only because Directx will not compile correctly(Will post errors on request through comment). But as of now the main problem is when i render my model(it is a plane with simple, unblended pixelated texture), it looks like this on my Laptop(Left Image

  • . This way all I have to do is plug in the x and z values to the equation to get the y. However, this would require adding 4 floats to every vertex of the heightmap which is a little ridiculous memory... to calculate that point than digging up the plane's equation and then plugging in x and z? Should I store the plane equations and update them on vertex height change or should I just regenerate the plane equations for every triangle every time the player moves on that triangle? Is there a better way to do heightmap physics that maintains this simplicity? (this seems very simple to me as far as physics

  • components and that would require searching each other component's list at each step. Which approch do you think is better? is boost::fusion map suited to be used in that way? ... C++ application. Entities can be defined in an XML file (the IA part in a lua or python file). The main loop doesn't care a lot about entities: it only manages components. The software design should... : public Component {...}; class IA : public Component {... virtual void update() = 0; }; // I don't remember exactly the boost::fusion map syntax right now, sorry. class Entity { int id; // entity id

  • GameSubsystems) can implement registerComponent(Component*). pro. Components and GameSubystems know nothing about each other. con. In C++ it would look like ugly and slow typeid-switch... coupling. A. We can add new GameSubsystem. For example, let's add GameSubsystemTitles that registers all ComponentTitle and guarantees that every title is unique and provides interface to quering objects by title. Of course, ComponentTitle should not be rewrited or inherited in this case. B. We can reorganize existing GameSubsystems. For example, GameSubsystemAudio, GameSubsystemRender

Data information