# Its been months, but I am back to my MMO!

This topic is 2983 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
Also, mind you, as stated they are lists. So, if anyone else has a way to limit around the lists that would be great. What if I limit to 200 then alternate set 1, 2, 3, 4 each time so im only spending time updating 200 max each loop.

Mind you, these conditions are very very rare. I highly doubt there will ever be this many online at all, but I like to know im coding right.

##### Share on other sites
Is the game 3D or 2D? What's the sight range for each client? What spatial partitioning are you using? A grid with a 2D rectangle for the camera and cull outside the client's view?

Everything past this sentence you already know, but I just want to make sure. If your map is say 100000x100000 units and you use a grid of 500x500 cells and 4K players are evenly distributed throughout the map that's 0.1 players per cell. Basically you'll define a viewing rectangle or circle and grab all of the entities in the cells that overlap the rectangle/circle. Since you inserted all the entities into their corresponding cells that means you'll be able to get a list of adjacent entities very quickly. (All of this can be implement with O(1) algorithms if you're clever with a linked list + observer pattern). Also look into hashed grids.

I also use full state updates and delta state updates. Store the known entities and objects for a client. Obviously if you go to insert something into that known entity list and it's not in there the player doesn't know about it and a full state update is required. If the client gets really out of sync? Remove all of the entities in the container and it does a full state update to them. These algorithms can also be implemented extremely cheaply. You can even run the checks for updating this list every 100 ticks or something if you want to and cut the cost down so low that it becomes almost free. >_>

Is that basically what you have?

About the problem at hand limiting the packets updates is a good idea. You can even drop the field of view if that's possible especially for populated areas. 800 players in an area is going to be insane. I'd be more worried trying to stop such traffic in one area. I mean it's not like players can do anything meaningful in such a dense region.

##### Share on other sites
Some of what you mention have to do with the client.

This is just server side. Simple.

Its the MMO server. Players just need to know about other players near it.

Some what you have mentioned I will look into, I have heard Trees is where I need to be, just never really worked with them.

Ken

##### Share on other sites
Quote:
 These algorithms can also be implemented extremely cheaply. You can even run the checks for updating this list every 100 ticks or something if you want to and cut the cost down so low that it becomes almost free. >_>

This is probably what I am looking for. How can I run checks quickly? From my knowledge, I would have the cycle the entire List<> and check if a player has run to far from another player.

Another problem could come into play is .Broadcasting() packets. For each person that knows of this person, broadcast. If the list is 400, that could be a large broadcast.

Ken

##### Share on other sites
Dont worry!
I got time vehicle, and i already know, your mmo will be release in future!
and will be better than WoW, and everything else, you will be pionier of MMO's. :)

then dont forget about me. I know your in future earns alot of money from mmo, then you should give me some. :D

##### Share on other sites
(You can edit a post by the way. No need to double post).

When you register a player to a cell in the grid you register the cell with the player. Removing the player from the cell is then instant since you have the cells the entity is in and can just call entity.RemoveFromSpatialPartitioning() or something. So you have a region around the player where you check for adjacent cells. Something like:
int minX = (int)((entity.Position.X - Player.SightRadius) / CellSize);int minY = (int)((entity.Position.Y - Player.SightRadius) / CellSize);int maxX = (int)((entity.Position.X + Player.SightRadius) / CellSize);int maxY = (int)((entity.Position.Y + Player.SightRadius) / CellSize); for (int x = minX; x <= maxX; ++x){	for (int y = minY; y <= maxY; ++y)	{		// try to add the grid[x][y].entities to a HashSet of known entities if possible. If the entity isn't already known then a full state is needed 	}}

So you have the known entities and a fullStateEntities hashset. You don't have to run the above code every frame. You just need to run it enough so that the known entity list is reasonably up to date. You mentioned how do you know if an entity is moving far away? There's a trick. When building delta packets for the known entities for any entity that is X distance away remove them from the hashset and skip them. If they come back within range they will automatically be picked up for a full state update by the above code. :)

##### Share on other sites
Sir,

Sorry I didn't mention before, it is a 3D game. Basically, those grids I have are not just 1 set away. Since its a 3D game, I think your formula wouldn't work. The grids I stated could be as big as town. (I wouldn't say that big but they are not blocks). Its not like chess.

So, when people get into the game, they go into a cell. That cell then is used when the update process goes through. When people move, if they are within range, they are added into the KnownList of the entity.

Ken

##### Share on other sites
Use smaller cell sizes then? Is there a reason you made them so large? This method applies to both 2D and 3D games though. You could be use a 3D grid if needed, but then the hash grid idea becomes much more important due to the memory needed.

##### Share on other sites
The lines are followed by the client. And I dont have the source to that anymore.

As you speak of HashTables, I currently have all known entities in a List<> The problem is cycling through that list. I need to find the quickest way to either A) Go through the entire list, B) If the list is large, only do X amount. Problem with this is I have to ensure that the next time around, we do the rest. Personally, I think A is the way. But in what order is best.

##### Share on other sites
Quote:
 Original post by KensterAfter spending well over 500 hours on my MMO. I stopped months ago. I figure, if I am going to use it to get a job, I should finish it.-Client is fully working. Not an issue.

Quote:
 Original post by KensterThe lines are followed by the client. And I dont have the source to that anymore.

Server emulation of another client? It's not "your" mmo then is it? Isn't that a bit like misrepresentation?

Quote:
 Original post by KensterThe lines are followed by the client.
I'm not talking about the client. I'm talking about a spatial partitioning system that exists solely on the server. You would use that to cull the clients that each client sends packets to like I described above.

##### Share on other sites
Sirisian is right, store all your entities in some kind of spatial strucutre ( octree comes to mind ). When an entity enters a new node, it sends a message to all clients in the nodes it is leaving AOI. Given your A-I example, if the entity moves to node F, it sends a message to all entities in nodes ADG that it is no longer in their AOI. Conversely, it then sends a message to all entities in the new nodes JKL ( for sake of argument ) that it is now in their AOI.

Secondly, a std::list<> is not going to cut it for storing your entities. This is one of those instances where you really need to come up with your own data structures ( or at least a combination of std:: data structures ). What comes to mind that I would do is have each entity belong to a variety of lists ( or psuedo hash tables optimized based on data type )that are all sorted based on some common selection criteria. You take a process hit on insertion and removal of entities, but gain on searcing since you have strucures optimized for that particular query. Think of it like creating indexes on a table in a database. You create an index for the columns you query often, and it speeds look ups. If you need to search by name, then you have a list sorted by name with a two char hash index, so based on the first two letters of the name you can quickly seek into the list and begin comparing looking for the entity. If you search by ID, than you have a second list sorted by ID with a hash consisting of the upper 16 bits or something. If all else fails you can walk any of these lists entry by entry looking for your entity. Basically you trade memory for speed, and since memory is cheap, it's worth it.

On your question about packet overload, I would use a priority based queue. Basically you queue up all the packets for that client and begin sending them as fast as you can. When a new packet comes in that is more important than some pending packets, it gets queued up for transmission sooner. Have a prioirty level that is low enough that if the packet is not sent, it is not an issue, then as your queue grows, you can kick these low importance packets. An example is player movement. If you miss a player position update, you'll get another one later. Others, such as entity presence, should not be dropped.

Initial packet load is not always a bad thing. It sucks, but players will bear it. The example I give is Dalaran. If you know anyone who plays WoW, ask them how much it sucks to be in Dalaran during peak times. When I login it takes upwards of 30 seconds for the client to get all the data it needs from the server before I feel that my client is fully loaded. Also notice how other players will jump from place to place. The client does direction based interpolation, but sometimes it just doesn't get an update and their is a major correction.

--Z

##### Share on other sites
So when's l2-paradise coming back? Lol.

##### Share on other sites
Quote:
 Original post by phear-So when's l2-paradise coming back? Lol.

Eh? lol

Yes. I have started using QuadTree. Of course this isn't a one day task but I already have it splitting the users between regions, but I have to work on the 2nd part that was stated about packets being sent via movement of the areas. Thanks all for the help, ill keep updated.

Ken

##### Share on other sites
I'm sorry, I assumed you were Ken from a lineage 2 private server called L2-Paradise. He was working on his own emu in C# a long time ago. You fit the description so I was giving it a go, ha. =)

##### Share on other sites
Ok. So as stated before I have already preset regions. Now each region has its own Octree. My problem is ghosting the regions near it. When a play is on the edge of a zone line, we have an issue of having no data in that Octree because of it. How should I go about it? Should I ghost in all Entities within X reach of the entrance of the Octree or should I make the world one large Octree and process that way. I can see it be very easy to manage, but would I see a huge performance issue with processing 12000 Mobs, + 4000 Players in one Octree?

Thanks,

Ken

**EDIT**

OR!

I had looked at a few peoples theory's such as Bigworld and what not. I could each region and its surrounding regions (8) are included as the QuadTree. So for example, if I was in E then ABCDFGHI would all have the same point in E's QuadTree. So, I would be able to limit the amount yet still see close regions. The problem I forsee here is, during my UpdateMove method, I will have to be worried about updating more than just 1 Quadtree, but 8 more to go with it.

##### Share on other sites
Quote:
 Original post by KensterI can see it be very easy to manage, but would I see a huge performance issue with processing 12000 Mobs, + 4000 Players in one Octree?

Why not just profile it? There is more than one way to implement a tree of this type, and in my experience in-place implementation may outperform dynamically allocated one.

Perhaps introduce heuristics - measure how many objects you can move before it becomes cheaper to just scrap the tree and rebuild it from scratch, which can be done very efficiently and even concurrently.

Also, if you don't need perfect accuracy, insert spheres (pseudo objects, perhaps 5 times the maximum distance a unit can move in one second). Then, when an object moves, check if it moved outside of its sphere. If yes, reinsert it, if no, do nothing. This requires a single less-than test, vs. logn reinsertion.

Considering that most objects will not move far enough, this should save majority of reinsertions.

For proximity queries simply add the extra sphere radius and then filter the resulting set if you need accurate results.

And if you end up with 160000 objects inside same query, then you're in trouble anyway.

##### Share on other sites
A simpler approach may be to reduce the size of your zones to that of your AOI. Then as a player moves, you at most need to traverse 4 zones ( current, east, south, and southeast etc.. ). Players will always congregate in certain areas, so no matter what you do you will have cases where there is a region where 400 players are all hanging out. In UO it was the bank in Britain ( the cool people hung out in Magincia ), in Warcraft it is Dalaran. So once you trim the list down to the smallest set based on the simplest criteria, the only thing left is to traverse the remaining entities.

--Nate

##### Share on other sites

I now query the amount of people around me and determine by that, how far I can see in front of me. I also slow down so that each run I only update 15 people instead of all at once, like the busy WoW town effect.

1) I do still have a CPU issue but this is because of the Garbage collector. Still trying to find some good documentation on what causes it, how to solve it.

2) Anyone have a suggestion for Broadcasts to the Knownlist? Example, I have everything in a ThreadSafeList. If I could find a way to broadcast without Locking, I could remove all locks and I really wouldn't need to lock anything. So, should I try to like do all the work without the thread, then do a CopyTo or something that I can broadcast the packets X to all players in Y list. (For example, sit, run/walk, move, talk in area, ect).

My one friend suggested a pool allocator for byte[]s.

##### Share on other sites
Don't allocate at all at runtime; instead, pre-allocate stuff at start-up (or when a player logs in), and re-use those allocations for all processing you do.

For broadcast, you can put numbered items in a cyclic array. Each player connection has a number for what the last broadcast it's seen is. Whenever an item in the list is higher than the last number, the user knows to send the broadcast.

Something like this (in C#, but if you're in Java, translating should be easy):

[source language="C#"]public class Message {  public static Message[] brList = new Message[64];  public static int nextBr;  public int serial;  public string text;  public Message(string s) {    text = s;    serial = nextBr;  }  public void AddBroadcast(string msg) {    lock (brList) {      brList[nextBr & 63] = new Message(s);      ++nextBr;    }  }}public class User {  int lastBr;  public void CheckForBroadcast() {    Message br = brList[lastBr & 63];    if (br != null) {      if (br != null && br.serial >= lastBr) {        ++lastBr;        SendMessage(br.text);      }    }  }}

Note: the User CheckForBroadcast does not need to lock anything; it is totally safe. The trade-off is that a user may lose entire chunks of 64 broadcasts at once, if the rate of adding broadcasts is higher than the rate of users polling for broadcasts to send. This is basically the simplest kind of lock-less data structure there is, and is often quite good enough for these cases.

If only one thread is allowed to queue broadcasts, then the lock() around enqueuing isn't needed, either.

##### Share on other sites

When you are limiting the updates and have regular 'turn' cycles and with smaller zones where you may need to use not a 3x3 window but 5x5 7x7 etc.. the further out you get the lower the update frequency. Objects that can directly interact need full updates, but further away where its mostly tracking can be much lower frequency. Of course significant events would be made to get thru (not discarded like incremental movements might be).

You would marshal your updates to be sub messages in larger packets to cut down the overhead (UDP you have direct control of this).

As mentione by others, a subscription system would be used to maintain lists of who gets updates for each zone (and now multiple lists if a high/low update frequency system is used).