I’m posting my ideas here because my knowledge of the client/protocol is quite limited and I’m trying to figure out whether it will work or not.
I’ve noticed that current servers exclusively use polling for player updating, my idea is to use an event system instead:
There would be a typical region system. I propose 16x16 regions, and as a player needs to see events in a 32x32 area, they would be ‘subscribed’ to 9 regions at a time.
Player updates will be done per region, save for the player specific initial packet. When an event occurs in a region, it notifies every adjacent region. During player update, each region constructs the necessary update packets based on the events received since the previous server tick.
Possible events include player movement, player added/removed to region, player appearance change, chat messages, etc…
In this example, a player leaves region B, and every adjacent region is notified. Since that player’s new region is not adjacent to region A, all players in region A will be sent a packet indicating that said player should be removed. This packet would only need to be constructed once.
I think that is a sufficient description, what I want is for you to challenge the design so I can figure out if it is flawed or not before I attempt to implement it.
I have already done that a few years ago and it works pretty well. I even released the source, but not many even looked at it, so it never really got a lot of attention. It was a new concept here at this site back then.
However, I didn’t get time to fix some synchronization problems with the subscriptions etc. but they wouldn’t be that hard to fix.
Actually there are two ways I see possible for no duplicate events to occur:
Have all players send their events to the region they are in at the time of the event and let all players in surrounding regions receive it from that region if they are close enough.
Have all players send their events to the (at most 4) closest regions and let all players only receive events from their own region.
For your information; it is an RSC private server, so if you were looking for an RS private server I really cannot help you with that. But I assume the concepts would be pretty much the same. Although your concepts might not be 100% accurate to what I did back then. Plus, don’t blame me for my bad design and / or architecture - I know it sucks and that was the reason I stopped working on it.
I have a feeling its not going to be any good because the server has to keep track of a list of players that every players sees and keep it in the correct order
[quote=“object, post:2, topic:337921”]I have already done that a few years ago and it works pretty well. I even released the source, but not many even looked at it, so it never really got a lot of attention. It was a new concept here at this site back then.
However, I didn’t get time to fix some synchronization problems with the subscriptions etc. but they wouldn’t be that hard to fix.[/quote]
Well, with a proper thread model, no synchronization should be required during player updating…
Also, yeah this will work. Instead of broadcasting an event to every player to do the updating, maybe you could broadcast an event to the region which prepares a ‘sector’ of the packet that gets cached for the region and all other players just use that ‘sector’ (as player updating order is different among different players, so you can’t just cache one huge packet).
It would be a pretty cool design. I recommend you use a quadtree for the region system.
Each region could maintain two collections – a collection of all players that are currently in the region, and a collection of players that have just left the region. When either of these lists is modified, any player subscribed to the region gets updated. Once that’s done, the list of players recently removed can be cleared.
i just discovered that upon movement only the direction needs to be sent, that makes this quite a bit better than i first imagined.
anyway lothy i dont think thats necessary. every tick i will loop through all active regions, and tell them to update all their players. it will give each player a list of all the events, then at the end clear the queue. also that doesnt help with the problem, the point was to avoid keeping an array of local players per player
I might get my hands on some of the code tomorrow (probably from Graham’s release). A part of me thinks that the ordering isn’t overly essential, so I’m keen to check on it.
As far as I know, the client only renders the entities that have / has (whatever) been sent to it since the last tick-update - and removes all the others. Atleast that’s what I discovered in RSC. So this means, you don’t have to keep track of whom will be removed (out of range) etc. Just update what’s currently there. I might have missed some stuff, so if that is the case - please enlighten me.
Also, why would you need to keep your players and / or other entities ordered? What must be ordered is the events sent from different players and / or other entities.
When I wrote my server, I had one event-queue for each player and one event-queue for the region (area) in which that player (well, every player had that, not just one :)) was located. The one the player had was a private one, for things that do not need to be shown to everyone else. And the other one was used for public access. It was made out of an array with a fixed length and had itself overwritten everytime a new event was added (with a nulled event as delimiter between the last one and the first one - because of the circularity). When a player grabbed an event from the two event-queues, it increased its last-grabbed event-index (one for the private one and one for the public one) and therefore was always up to date on both.
To get the next event would just be to use a simple remainder operation.
Hopefully you understand what I am talking about, but I am at work, so I can’t spend a lot of time fixing potential spelling mistakes and whatever else I did to this text.
I don’t know much about servers but that sounds like alot of objects/threads.
With a 377 cache that would be 11,120 “regions” over the entire map.
Even with inactive regions, it’s still seems too many, are you actually reducing the ammount of packets sent to players?
Like the idea, just think your regions are too small, processing time is cheap, bandwidth isn’t.
[quote=“MrPotatoHead, post:12, topic:337921”]I don’t know much about servers but that sounds like alot of objects/threads.
With a 377 cache that would be 11,120 “regions” over the entire map.
Even with inactive regions, it’s still seems too many, are you actually reducing the ammount of packets sent to players?
Like the idea, just think your regions are too small, processing time is cheap, bandwidth isn’t.[/quote]
memory is cheap, processing time isn’t. this doesnt save bandwidth in any way, no, it only saves processing time
[quote=“object, post:11, topic:337921”]As far as I know, the client only renders the entities that have / has (whatever) been sent to it since the last tick-update - and removes all the others. Atleast that’s what I discovered in RSC. So this means, you don’t have to keep track of whom will be removed (out of range) etc. Just update what’s currently there. I might have missed some stuff, so if that is the case - please enlighten me.
Also, why would you need to keep your players and / or other entities ordered? What must be ordered is the events sent from different players and / or other entities.
When I wrote my server, I had one event-queue for each player and one event-queue for the region (area) in which that player (well, every player had that, not just one :)) was located. The one the player had was a private one, for things that do not need to be shown to everyone else. And the other one was used for public access. It was made out of an array with a fixed length and had itself overwritten everytime a new event was added (with a nulled event as delimiter between the last one and the first one - because of the circularity). When a player grabbed an event from the two event-queues, it increased its last-grabbed event-index (one for the private one and one for the public one) and therefore was always up to date on both.
To get the next event would just be to use a simple remainder operation.
Hopefully you understand what I am talking about, but I am at work, so I can’t spend a lot of time fixing potential spelling mistakes and whatever else I did to this text. :)[/quote]
im not sure if thats true for rs2, the server sends when to remove players so i dunno
MrPotatoHead: You could always remove unused regions from their repository. And when it comes to threads; you don’t really need a lot of them. I used one thread per client - but that is overkill (not to talk about thread context-switches). To use one thread may also not be the best option. Perhaps use a few, but not too many. The amount of objects doesn’t really matter as long as you do not run out of RAM. It won’t as long as you keep the memory consumption somewhat stable.
Just trying to get head around the region size and how that effects how many packets are sent. Why use 16x16 and not 8x8 or 32x32?
You’ve said, this is based on visible area, but i’m not sure you understand the visible area.
The visible region is 50x50, NORMALLY reduced by the camera calculations to 16 in front of the player at ground level (it’s dependant on height). So the player at the top of A, say 2 spaces from top, can see everything in the 16x16 region above it since the 2+16 spaces are greater than that player can normally see from the ground. However when higher up the player will see up to 25 tiles in front so with a 16x16 region the player at the top of a will have 7 tiles missing.
I just checked, it’s possible to click 20 tiles in front of the player with an unmodified client.
So now i’ve completely screwed up your 16x16 region system, i’m going to try and work out the packet usage for both bigger AND smaller regions (you can simply subscibe to more regions).
I really do like the idea btw.
I don’t know about with RSC, but with RS2 you must explicitly add a player to the local player’s list (there is a whole segment of the update packet where you do that), and you must explicitly remove from the player’s local list. You must also retain the proper order of players added to the list because when you’re not adding/removing players all you’re doing is sending individual blocks (the only way the client knows which player it is is the order in which it received the block).
Also, why would you need to keep your players and / or other entities ordered? What must be ordered is the events sent from different players and / or other entities.
Because the client uses the ordering of which players were added/removed when updating players already in the local list.
[quote=“MrPotatoHead, post:15, topic:337921”]Just trying to get head around the region size and how that effects how many packets are sent. Why use 16x16 and not 8x8 or 32x32?
You’ve said, this is based on visible area, but i’m not sure you understand the visible area.
The visible region is 50x50, NORMALLY reduced by the camera calculations to 16 in front of the player at ground level (it’s dependant on height). So the player at the top of A, say 2 spaces from top, can see everything in the 16x16 region above it since the 2+16 spaces are greater than that player can normally see from the ground. However when higher up the player will see up to 25 tiles in front so with a 16x16 region the player at the top of a will have 7 tiles missing.
I just checked, it’s possible to click 20 tiles in front of the player with an unmodified client.
So now i’ve completely screwed up your 16x16 region system, i’m going to try and work out the packet usage for both bigger AND smaller regions (you can simply subscibe to more regions).
I really do like the idea btw.[/quote]
I’m pretty sure the viewing range is limited to 32x32 (16 tiles in any direction), I haven’t explicitly checked though.
Also, if you’re worried about sizing/etc., just use a quadtree data structure which can resize (by increasing or decreasing the branch depth) regions by splitting one into four equal regions.
The biggest problem would be the ordered list clientside. You could add/remove each player every time manually (as when you add, you automatically update the appearance and other shit of that player immediately after) but that would be using quite a bit more bandwidth and would sort of be “hacking” the player updating system, plus it’d look pretty icky and I’m not sure how well it’d perform. The biggest performance loss of the mainstream (winterlove) implementation of player updating is the add-checking, where it loops through every player in the world (for every player, so it’s worse than O(n^2) performance when you take into account the other looping shit that has to be done) to check if they are within distance and are not in our player list (in which case they need to be added). Most proposed solutions to this include a region or tile system of some sort where every player loops through smaller localized regions instead of the entire game world.
If you PM me, I can hook you up with some highly object-oriented/polymorphic player updating code which operates via update “requests” for the #459 revision that should help you better understand how everything works (as object orientation in programming is pretty much about designing things and making them work the way we think about stuff). It’s pretty cool :P. The ordering is, however, essential. The client has no other way to keep track of which player is which. When you send the update packets for other players, you just loop through every player in the list and send their updated movement and “blocks” (I prefer to call them sectors :P) and there is no other identifying information except for that your list and the client’s list retains the order in which they were added.
To me personally, it makes more sense to use a number based on the visible terrain that the player sees. With that said, I’d personally use 32x32 regions.
In that case, you’d have to handle map region loading (sent to the client as a packet) separately from server-side region changing.
It wouldn’t be that big of a deal, but it’d be nice to have the server-side map region changing associated with loading new map regions client-side.
