Quote:Original post by Kenster
After 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 Kenster
The 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 Kenster
The 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.

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

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

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.

Quote:Original post by Kenster

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?

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.

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

Working flawless! I love QuadTrees!

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.