Sign in to follow this  
graveyard filla

partitioning the players / world into groups / zones in a 2D MORPG

Recommended Posts

hi, i'm working on a 2d persistant online action/RPG. it is in a futuristic setting with real time combat, which means when you fire a gun you actually see the bullet shoot towards the person, and you can dodge other people's bullets. my goal is to handle 30 people at once on a dedicated server running on a cable connection. the game is tile based, using 32x32 tiles. anyway, its come time for me to partition my world into groups. currently im just sending all players all data about all other players. now this is obviously a waste of bandwith since if a person is not visable to me, i shouldn't even care about them. i need to split the players into groups somehow and only send events about a player to all people in his own group, events like bullets firing, movement, etc. now, since this involves bullets firing, this means that one guy can suddenly enter another group, and since bullets are currently flying through the air, the guy who just enteres won't see them because he wasn't in the group when they were fired. this means that when a player enters a group, he should receive all "live" data that he "missed". i have come up with 3 solutions, but would like advice and comments and critisism from someone with experiance or knowledge about doing this. 1) split the world into groups based on their map. this is the easiest of the 3. that is, send player A's info to player B if they are both on the same map. this would work reasonably well, as i don't plan on making huge maps. probably an average map size would be 200x200 tiles. this would be the easiest to code (i think). another advantage is i could make a "loading" screen when switching maps, something i can't do in real time. the one possibly big problem with this is scalability. im just not sure how well it will scale. what if all the players are on the same map for some reason, but not visable or effecting each other? this would cause lag, unnessasary lag at that. 2) on the server, each player will have a list containing a list of players. this list is the people he sends data to. then, i just add and remove people based on location. something like this:
for(each player in list = a)
{
  for(each player in list = b)
  {
      if(a is not b AND a is in range of b)
      {
          a.AddToList(b);
          b.AddToList(a);
      }
      else
      {
          a.RemoveFromList(b);
          b.RemoveFromList(a);
      }
  }
    
}
the advantage here is that i only send data to people who absolutely need it. the disadvantage is im not sure how to send "live" data this way. im thinking i would have to send live data through a different system (e.g. the map based one), and i don't want to use 2 different methods if i don't have to... 3) partition each map into "zones". then only send data to players who are in the same or adjacent zones of one another. however i find this to be very complicated and im not sure if it will be the most efficent. thanks a lot for any help! [Edited by - graveyard filla on November 24, 2004 2:12:56 AM]

Share this post


Link to post
Share on other sites
3) is just an improvement on 1), it's mostly the same thing.
1) is what EQ did. It works fine for a game such as yours.
2) is what we're doing -- there's a send queue per player, and we have custom routers/filters that determine what to send at any one time. It's probably total overkill for your set-up.

Share this post


Link to post
Share on other sites
No 3 is what I'm doing. I think this is a good way for doing it in a 2-D-Environment.
This "zones" have to be at least half as big as that what the client can see. The zone where the client stands in width its eight bordered zones are then certainly bigger as that what the client see.

Share this post


Link to post
Share on other sites
thanks for the replies guys. im going to go with method 1.

the reason is this: if i go with 3, this might actually cause more lag. for example, lets say i have a 200x200 map that i split up into 8 "zones". now, only people who are in adjacent/same zones as each other will send data to each other.

the problem is sending "live" data. lets say im in zone 1, and i step into zone 2- well now, there could be bullets flying in the air, people in the middle of walking, etc, data that i didnt know about because i was in a different zone. so when i step into this new zone, i have to be sent all this data.

i think because of this, splitting the world into zones will actually cause more lag. since players could constantly be running into new zones, these live updates could be sent frequently, cause more lag then if i just sent all data to everyone on the same map as me.

any thoughts?

by the way, what do you think about cacheing / pre-loading players?

for example, when i first enter a map, i will be sent the data for all the players on that map. now, what about when i step into a new map? what happends to all those players? do i keep them in memory, or destroy them? should i cache certain, non-changable data such as the players name?

now, taking that thought a little further, perhaps when i first enter the game, i should be sent the static data for ALL players in the game, not just for the map im on. this way when i enter a new map, i'll only need to be sent the dynamic data for that person, and not the static data like their name. i could even keep them cached for maybe 5 minutes after they log out, in case they log back in again..

thanks again for any help.

[Edited by - graveyard filla on November 25, 2004 2:24:10 PM]

Share this post


Link to post
Share on other sites
im in the middle of implementing this, and starting to think it might be slower then i thought.

the problem is, this "your entering a new map" packet is pretty damn big, the biggest packet i've ever dealt with. this is the packet we send to a player when he switch's maps:


//CONTENTS: 1 byte ID_TIMESTAMP, 4 bytes TIMESTAMP, 1 byte MSGID
// 2 byte X pos, 2 byte Y pos, 1 byte MAPID
// 1 byte num players in the map, then for-each player -
// 1 byte ID, 1 bit saying if we've seen him or not
// if bit is false, encoded string of the players name
// 2 byte X pos , 2 byte Y pos, 1 bit saying if hes moving or not
// if bit is true, 2 byte X vel, 2 byte Y vel, 2 byte dest x, 2 byte dest y


this is a pretty big packet. best case, there are no players on the map and its only 12 bytes. worse case, there are players on the map AND i've never seen them before (need their static data) AND they are moving (need their velocity/destination). if this is all true, then the packet size is 12 bytes + playername*N + 13*N + 2 bits, N being the number of players on the map. best case with players on the map, i have seen them all before AND they are all standing still - 12 bytes + 5*N + 2 bits.

am i just being paranoid, or is this too much? i don't have much experiance, so maybe its not a big deal, but, it just seems like a big packet.. i mean, what if there is 5 guys on the map, all moving around and i've never seen them before? assuming that they each have 6 characters in their name, this is a 107 byte plus 2 bit packet! if theres 15 players on the map, and they are all moving and i've never seen them before, 297 bytes plus 2 bits! i dont even want to figure out what if there is 20+ players on the map moving around, never seen before..

will this choke up the server? is there any way around it?

i can think of 1 way to minimize the sending of this packet-
break the world into "zones". each map will have a zone ID. so, lets say i have a city map with 10 buildings in it. each building and the city will be given the same zone ID. hell, even the city next to it and it's buildings could get this zone ID. now, instead of sending map data to people in the same map, i do it based on zone.

another thing i could do is just make every map BIG. i store positions as unsigned shorts, so this allows me to have 65536/32 tile maps. thats a 2048x2048 map in tiles, which IMO is HUGE. however, i still deal with buildings being their own maps. that is, when a player steps into a building, a new map is loaded.. walking into a building real quick then stepping back into the city could potentially choke up the server...

the other thing to think about is this - in the game i plan on having a job system, where you can obtain jobs such as breaking into a building and stealing a package. now, this means that a player could enter this building with a buddy, and NPC's would start attacking him, projectiles will be flying, etc.. if i split the world into zones, then all the people in the city where this building is will be getting these packets - completely unnessasarily.

so, its kind of a screwed if i do, screwed if i don't situation. if i dont split it into zones, entering a city could choke up the server - if i do split it into zones, going on a mission and killing npc's inside a building could lag players who are absolutely no where near the action.


what do you think i should do? in the middle of code right now so any help is greatly appreciated! thanks!

[Edited by - graveyard filla on November 28, 2004 2:34:00 PM]

Share this post


Link to post
Share on other sites
That's not too big at all. It's pretty svelte, really. It's been said that a significant part of the "Loading Please Wait" time between zones in EQ is sending all the NPCs and PCs in a zone, rather than just loading geometry from disk. Thus, it's faster to zone into an empty zone than into a full zone. Don't know how true this is, but I could believe it.

300 bytes would take 1/10th of a second to send. Users don't re-zone all that often. I just wouldn't worry about it, as long as that's all the data you need to send. If you also need to send custom textures for player armor, and NCP inventories, and ... then it might start getting scary.

Share this post


Link to post
Share on other sites
well, that could be a problem them. i doubt it will only stay like this.. i do want to expand the game once i get the basic engine up and add things like customizable outfits, i figure that would be 1 byte per body part, or visable weapons, and who knows what else is (actually) nessasary that im not thinking of. but i really don't see any other way to do this though..

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this