hi, im working on a 2D action based futuristic MORPG. my goal is to handle 30 players on a dedicated server running on a cable connection. however, this is only my goal. i am aiming to make the game as scalable and efficent to hold as many players as possible, and im thinking that if i were to ever cap the amount of players it would be something like 150. however these are just rough estimates. i want to design and write the code to be as efficent and scalable as any MMO. anyway, i am looking for opinions on how i should handle storing and organizing all of the Players (and possibly NPCs) in the world on the server. currently i have this: a std::map<PlayerID,Player> players_in_world. this represents all the players logged in the game. now, when i get a packet, i just grab the PlayerID from the packet and i know who the sender was and stuff. then i just do a lookup into the map and do things with the player. now, before you see the problem with this, i have to explain how i "group" the players. all players are grouped by map. when a player fires his gun / moves / etc., i send the data only to the players who are on the same map as this player. and when a player enters a new map, he must be told about all the players/projectiles on that map, and everyone on that map are told about him. so when a player clicks to move, he sends to the server "i want to move here". the server then sends this to all other clients on his map. this operation looks something like this:

case MSGID_PLAYER_MOVING:
{
	for( each player in the world)
	{
    		if(this players . Get_Map() == player whos moving . Get_Map())
    		{
        			forward the packet to this player!
    		}	
	}
}

now, i do the same when a bullet is fired, and i will do the same when other things happen as i expand the game and add new messages. this seems like a problem. i have to loop through every player in the world and check what map they are on. currently the Get_Map() returns a std::string which says what map they are on - however, i plan on changing this for bandwith and CPU reasons. it will be switched to a single byte which represents the map. so, it is only a single byte comparison. now, is this cause for concern? is it slow? will it scale well? is it ugly? the only solution i see is to make 2 lookup tables, like this: //this is the same as the one i currently have, it represents ALL players logged in std::map<PlayerID,Player> players_in_world; //this maps a Map_ID to a list of players std::map<Map_ID,std::map<PlayerID,Player> > player_groups; when a player first joins the game, hes added to players in world and hes also added to player_groups. when a player leaves the map, we do this:

//remove him from his current std::map
it = player_groups.find(thisguysoldmap);
it->second.erase(thisguy);

//add him to his new std::map
it2 = player_groups.find(thisguysnewmap);
it2->second.insert(thisguy);

then, when receiving a "hey im moving message" from a client:

//grab this player from the master list
it1 = players_in_world.find(id);
//grab this players group from the groups list
it2 = player_groups.find(it1->Get_Map());

//loop through the groups list and send the data to everyoen in his group
for(std::map<Map_ID,std::map<PlayerID,Player>::iterator it3 = it2->second.begin();
    it3 != it2->second.end(); ++it3)
{
    send it to it3->second!!!
}

ok, so there are several problems 1) i have to manage multiple lists.... yuck 2) i have to do 2 lookups in 2 seperate maps when forwarding packets 3) i will have to be constantly doing deletetions and inserts! plus, im not using pointers, so there is a lot of copy'ing going on. pros: 1) i don't have to loop through every single player in the game and compare their map with the other guys map and with one giant list: pros: 1) i only have to manage one list. yay!!! 2) i only have to do 1 lookup 3) i need this list no matter what! cons: 1) have to loop through ALL players each time. (sorry for the redundancy) so, what do you think? what solution is cleaner, more scalable, etc? personally, i find having one giant list to be easier to maintain, probably cleaner, and possibly faster. however, i think that using the other method will scale better. however, like i said, my realistic goal is to handle 30 players, so maybe it will not scale better? the last (probably big) advantage i would like to point out about having one giant list, is that i will probably turn this into a boost multi index container. i find myself looping through this list and looking for a value all the time. sometimes i want to lookup a player based on their name (for example when the player wants to send a global private message), and other times i want to do a lookup for a player based on their network ID (as opposed to their PlayerID, which is how RakNet identifies connections). i was going to turn this big map into a boost multi index container, so i could do lookups based on any of the 3 keys. i guess i could do this with the other method too though, but im thinking it could get ugly. thanks a lot for any help!!

Uh, a long post!

I was wondering, couldn't you just do your own container class that holds the both lists and manages inserting/removing players from them? Not sure if it's any use though..

Have you done any tests on how slow the lookup would be on a one big list? Seems to me that using one list would be a better thing to do for you. More pros than cons, like you listed.

Ok, this probably wasn't a very helpful post afterall.

My thinking would be to just use pointers. That way you can have

std::map<PlayerID,Player *> players_in_world.

And for your different "maps" or "rooms"

std::map<MapId, vector<Player *>> players_in_map;

And just have code to maintain those lists adequately.

Mark

This is a general database design problem. You get the same issue when designing tables, relations, and indices.

Your basic data types seem to be "Map," "Player" and "Packet".

Your query attributes seems to be "any player by map," "one player by id" and "one player by name".

There are, of course, many ways of solving this. One is to store all players by player ID in a map, and then store the player ID everywhere else you need to refer to that player. You need two look-ups to actually find the player, but if it's done once or a few times per player per game loop, that's not so bad.

Another way is to allocate Players as objects with pointers, and store pointers to the player in a bunch of different indices, all of which go from queried-attribute to player-pointer. If you get something wrong, this is more likely to crash (because you're using pointers, not IDs), but it's likely a little bit faster.

A third option would be to make the "player ID" represent something physical, such as index into a fixed-size vector of all currently online players, so the look-up from player ID to player is free.

If the current problem is "I get a bunch of data from a player, and need to know where to echo it" then you could do it, for example, as such:

1) hash from source IP and port to player pointer; this lets you take the remote packet and map it to a player
2) player has a CurrentMap member, which could be a Map ID, or a pointer-to-Map
3) each packet received by the player is inserted into a chain of packets on that Map
4) each map also stores a vector or list of all players in that map, by player pointer
5) each game pulse, you iterate all the maps (if your server runs more than one map), and for each map, bake the pending messages into a single packet; then, for each player in that map, send the packet to that player. Then clear the pending messages for that map.

If you do reliable-UDP stuff, you might want to make "send the packet" in turn enqueue a copy of the packet on the player, and keep it until you know you don't have to re-send, but that's a lower-level operation (and I think you use RakNet for this, which does it for you).

Now, you have to be careful when players move between maps, so that all the data structures are properly linked/un-linked, and you have to be careful when a player logs out so that it's properly cleaned up. One good way of finding when you have problems, is to run (in debug mode) a loop that verifies that, for each player listed in each map, that the back pointer is the proper map; then verify, for each player, that there is a valid map pointer, and that the player is listed in that map's list of players.

However, most MMO games actually run one process per map, so a player would connect to another socket when zoning to a different map. That way, the "what map am I on" problem simplifies to "echo to all players within this process" which is curiously similar to the good-old MUD structure. Also, if each map is served by a different process, you could put different maps on different server hardware (build a cluster) if needed for scalability. The draw-back is that hand-off between different maps and global authentication is a little bit harder.

hey everyone,

thanks for the replies.

@hplus

thanks, this is what i was looking for. about the first part of your post, what do you think about boost multi index containers ?. it seems like boost has solved this problem for us. it also claims to be faster (and obviously easier) then any method we would code ourselves. this way we dont have to manage multiple containers. we simply have a single, multi index container. effectively giving us a std::map which we can do lookups using multiple keys (lookup using name,id,whatever..).

now, on to the other problem. so, you think its worth implementing a grouping system then? i actually started designing almost exactly what you describe before i read your post. i guess great minds think alike [grin]. theres a few things that i dont understand what your saying though..

step 3 and 5 both confused me. what do you mean by "the player is inserted into a "chain of packets""? also, what do you mean by "you iterate all the maps, and for each map, bake the pending messages into a single packet; then, for each player in that map, send the packet to that player. Then clear the pending messages for that map."

im confused by this. however this is what i planned.

when the player enters the game:

//grab the map hes onMap ↦ = map_manager.Get_Map(map_id);//add him to this mapmap.Add_Player(player_id);-- build a packet here called op --//tell everyone on this map about this playermap.Broadcast_Packet(op);std::map<PlayerID,Player> &tmp = map.Get_Players();-- send the new player all of these player's data --

now, when a player sends an "im moving" packet:

//Get_Map() also works with player IDs!!!Map &tmp = map_manager.Get_Map(player_id);tmp.Broadcast_Packet(packet);

it seems like a pretty slick solution to me. a few notes

-the Map class has a std::map<PlayerID,boost::weak pointer to Player> as a member. this represents all plakyers on his map. i will use boost:: weak pointers for this. the maps are not responsible for deleting the memory associated with these Players.

-besides this, we need a "global list of all players in game". this will be a std::map<PlayerID,boost:: shared pointer>. however, im actually most likely going to make this a boost multi index container. it uses shared pointers since this std::map will own the pointers.

(i have never used shared or weak pointers before, but they seem appropriate for this situation, im thinking otherwise i will have to find which Map the Player is in when removing Player's from the global list otherwise, which could be a hassle / slow. i would prefer not to use the boost pointers here just for familiarity reasons though, so if it sounds like its a waste, let me know..)

the last issue is this. i try to keep all of my protocol level code hidden from the rest of the server. that is, my Player will never call server.Send(position info). instead, he will call server.Send_Position_Info(). i do this just in case i ever switch networking API's, i dont have to go to a million different places and change the code, also it helps encapsulate things.

so, the problem is with Map::Broadcast_Packet(). for example, look at the first code i pasted. this code would be inside the Network_Server:: code. so in my Network_Server::Update() (or Proccess_Message(), or whatever), it looks like this:

Map ∓ = Get_Map();mp.Broadcast_Packet()

i call Broadcast_Packet() from my server code, and then my Map::Broadcast_Packet() will in turn call something like Network_Server::Send_Some_Specific_Data(). its kind of ugly, how we are just bouncing data back and fourth like that. however im not sure of any other way to do it....

thanks a lot for anymore help!

EDIT: lightbulb. perhaps the solution to the problem of the server and map code "bouncing back and forth" is simple. instead of having a Map::Broadcast_Packet() function, i simply have a Map::Get_Player_ID_List() function, which returned all the PlayerIDs on the map. then the server code could just loop through all these playerID's and send the packet to that player ID. i could even just give the server code a Broadcast_To_PlayerID_List() function. so instead of

map.Broadcast_Packet();

it looks like:

Broadcast_To(map.Get_PlayerID_List());

EDIT PART 2:
after thinking about it more, now i think i will not use boost shared or weak pointers. instead, when a player exits the game and therefore leaves the "master list", i find what map he is in and remove him from that maps list as well. so, when a player quits the game, it looks like this:

case MSGID_PLAYER_QUIT:{  //or just combine these 2 into a Remove_Player_From_World().....  Remove_From_Global_List(packet->playerID);  map_manager.Remove_Player_From_Map(packet->playerID);}//where Remove Player From Map looks like this:Map_Manager::Remove_Player_From_Map(const PlayerID &player_id){   Map &tmp = Get_Map(player_id);   tmp.Remove_Player(player_id);}Map &Get_Map(PlayerID player_id){   std::map<PlayerID,Player>::iterator it = players_in_world.find(player_id);      //call the Get_Map() function which takes a map ID   return Get_Map(it->second.Get_Map());}

also, the last thing i want to get your comment on is storing the Players in the master list. at first i thought i would use pointers for both list's (and i see in your step 1 and 4 you have the same idea). then i thought this might be a waste. why bother call new myself if im not using any polymorphism? instead, the "global list" (the one containing ALL players in the game) will be a std::map<PlayerID,Player>. it will hold actual Player instances. the list that each Map will have will be a std::map<PlayerID,Player*>. it will point to valid instances of Player contained in the global list.

so, watcha think? [smile].



[Edited by - graveyard filla on December 23, 2004 1:03:07 PM]

I've never used the multi-containers. If they work and you like the syntax, go for it! Trying new things is how you learn stuff.

Regarding storing a map of player id to Player rather than Player*, the difference is how you want to reference players in other structures. If you're OK with always going through a player ID when wanting to have the actual Player (i e, an extra look-up), then storing by ID is the way to go. If you want to cut out that one look-up for secondary indices, then storing a Player* in each index is better.

I'm not sure whether the std::map<> guarantees that items won't move -- in fact, I think they may move when you mutate the map, so taking the address of the item in the map is probably not a safe reference to keep around.

Thus, if you want something like a priority_queue<Score,Player*>, then you'd want to store a Player* in the map; if you want a priority_queue<Score,PlayerID> then you could store the Player in the map. However, this is based on some old experience with the map<> containers, and may no longer be up to the latest C++ standard -- I think there's a better forum than Network Programming for that specific question ;-) (I e: are map<> entries allowed to move in memory once inserted?)

Quote:

Original post by hplus0603 Regarding storing a map of player id to Player rather than Player*, the difference is how you want to reference players in other structures. If you're OK with always going through a player ID when wanting to have the actual Player (i e, an extra look-up), then storing by ID is the way to go. If you want to cut out that one look-up for secondary indices, then storing a Player* in each index is better.

im not sure i understand this. why would storing it by value cost an extra lookup? either way i will need to do the lookup, no? i guess i just cant see a situation where i would not need a lookup.

Quote:

I'm not sure whether the std::map<> guarantees that items won't move -- in fact, I think they may move when you mutate the map, so taking the address of the item in the map is probably not a safe reference to keep around.

im not positive, but i believe that any iterators pointing to an item in a std::map will never be made invalid, even when things are inserted or deleted. maybe use iterators instead?

Quote:

Thus, if you want something like a priority_queue<Score,Player*>, then you'd want to store a Player* in the map; if you want a priority_queue<Score,PlayerID> then you could store the Player in the map. However, this is based on some old experience with the map<> containers, and may no longer be up to the latest C++ standard -- I think there's a better forum than Network Programming for that specific question ;-) (I e: are map<> entries allowed to move in memory once inserted?)

couldnt i still use the pointer if i stored actual instances in the map?

thanks again. (ps, i never heard of priority_queue before, those are pretty cool, i could definetly see a situation for them).

All I'm saying is that if you store a pointer, rather than an ID, in all secondary indices, then you don't need a second look-up to get data out of the Player -- you just follow the pointer! If you store an ID in the secondary index, you then need to look up the actual Player to get Player data out.

I agree that iterators will not be invalidated. However, this doesn't necessarily mean that pointers will remain valid, although that's a likely implementation behavior. Storing specific iterators might work -- and it seems that most standard libraries have sizeof(map<>::iterator)==4, which means it's not much more expensive than a pointer.

Quote:

Original post by hplus0603 All I'm saying is that if you store a pointer, rather than an ID, in all secondary indices, then you don't need a second look-up to get data out of the Player -- you just follow the pointer! If you store an ID in the secondary index, you then need to look up the actual Player to get Player data out. I agree that iterators will not be invalidated. However, this doesn't necessarily mean that pointers will remain valid, although that's a likely implementation behavior. Storing specific iterators might work -- and it seems that most standard libraries have sizeof(map<>::iterator)==4, which means it's not much more expensive than a pointer.

hey hplus,

thanks again for the reply. i think we are mis-understanding each other. heres what i plan.

one big container holding ALL players currently logged in the game. the container will look like this:

std::map<PlayerID,Player> players_in_world.

then, i give my Map class a member.

std::map<PlayerID,Player*> players_on_map.

i have N instances of this Map class, where N is the number of maps in the game. now there will be lots of maps, since walking into a building will enter you into a new map, or walking to the next floor of a building will do the same as well.

when a player enters the game, i make an insert into players_in_world, creating this Player instance. i also make an insert into the Map object of whatever map that player is on, only that insert will be the address of the guy that i just inserted into the "main" std::map.

anyway, do you think this will be sufficent? theres one final concern i have. what about NPC's? should i store them in the same containers as the Players? or should they be in seperate containers? i was thinking about putting NPC's and Player's all in the same "ID pool". that is, a player will have ID # 42, and an NPC will have ID # 29, e.g., every Character will have a unique ID. then i was thinking that i could just do a "blind lookup" into one giant container and perform some generic action on that Character (e.g. call some virtual function that both NPC and Player over-ride), and not care weather its a player or an NPC. (get what i mean?) i was thinking this would be cleaner, possibly easier, and save on bandwith. what do you think?

thanks again.

(PS, sorry if i totally mis-understood you again [smile])

Yes, that will work -- assuming that the Player instances on the first map don't move when more items are inserted in that map. As you say, iterators are not invalidated, so it's likely the address of the items won't change, but I'm not sure whether the standard guarantees that behavior.

Seems like Windows and Linux standard libraries do provide this behavior, so I think you're good.

#include <map>#include <assert.h>#include <stdlib.h>struct X {  X * data;  char dummy[100];};std::map< int, X > xMap;int main() {  for( int q = 0; q < 10000; ++q ) {    int z = rand() & 255;    std::map< int, X >::iterator i = xMap.find( z );    if( i != xMap.end() ) {      assert( (*i).second.data == &(*i).second );      xMap.erase( i );    }    else {      X x;      xMap[z] = x;      xMap[z].data = &xMap[z];    }  }  std::map< int, X >::iterator j = xMap.begin();  while( j != xMap.end() ) {    assert( (*j).second.data == &(*j).second );    ++j;  }  return 0;}