Ok, I''m writing a server for an MMORPG; it''s tilebased, but in a fully rotatable 3d world. In the way things work at the moment, the client receives a spawn notification every time that a monster outside of the radius of the client''s screen (an arbitrary radius) enters the client''s screen. Likewise, a remove notification is sent by the server when the monster exits the client''s viewable area. Now, I could test the distance of each entity from the client(s) every time that a client or monster moves, but this seems terribly inefficient. Someone suggested quadtrees to me, but the objects within my area are moving, which would mean that I would have to rebuild my quadtree every time that an entity moved. Would this be more efficient than the brute force method described earlier? Also, how would I find all the regions that overlap a circular area? I''m going to be dealing with entities in excess of 100 or so, which wouldn''t be a problem if I didn''t need to reconsider whether to send notifications to every connected client for every time an entity moves. Thanks in advance ^_^;

This isn''t really a networking related question if you think about it. You''ve got a certain problem, namely finding all entities within a certain radius.

You said that your game is tile-based. With tile-based games there are typically two ways to store entities: keeping them all in a global list, or maintaining a list of entities per tile (or per cluster of 4x4 tiles or whatever).
If you keep your entities in a global list, finding those within a certain radius is obviously an O(n) operation. If you store your entities in lists per tile (or per cluster of tiles), it''s an O(1) operation because you only need to look at the tiles/cluster within the searched for radius.

This has all got to do with world subdivision, and a quad tree could be used to solve this problem as well. However, since you''re already using a tile-based approach, i.e. a uniform grid, it makes sense to use a uniform grid for storing the entities as well.

cu,
Prefect

I''m wrting a tilebase MMORPG too.
First time i used a stupid method.

15 14 13 12
4 3 2 11
5 0 1 10
6 7 8 9

after doing this search for every client, i got a array containing some clients around it , just sorted by the distance.The number stands for order to search.and every number is a tile........before this , i set the clients on the map.

then I want to change to this method.

0 1 2
3 4 5
6 7 8
this time the number is stands for grid index...... the client pointers will change direction from one grid to another when change its position.

then the one who stand in Grid 4 will see some clients stand in 0 to 8.




i think getting distance is not a slow method.You can use max( x1-x2,y1-y2 )

I think my method is multitree....
Because the map is splited int pieces...........

Can i ask you the name of your Game?

I''m actually just writing a server for a game called Ragnarok Online, a Korean MMORPG. I don''t intend to release it or anything; it''s just for my personal research.