How does BYOND handle networking so efficiently?

ID:2607690
 
Aug 25 2020, 6:38 am
Hello, It's been long time since I've been here. I don't create BYOND games anymore but I am still interested in how BYOND handles things internally.

Lately I've been working on my network multiplayer game in Python (tile based) and wanted to make networking more efficient, so that player only gets positions of objects in his view (view, just like BYOND's client.view is changeable in my game).

The first thing that came to my mind is to just have double for loop and scan map for objects that are in client's view, but I guess it isn't very efficient method :(

The next method is to divide map by multiple chunks (just like on the screenshot) and send to user info about all new objects and old objects updates (if they moved/ changed) from chucks overlapping client's view (red dotted area). It makes client to get more info than needed but you only need to look for objects in few places. I guess this is the correct approach, but it also gets more compliacated and less efficient if client's view can be changed (i.e from like 11x11 to 31x21 tiles). I wonder if BYOND does use this method and if so, what's the best size of chucks to create?



Last method is just to send all events to every client on the map level which is the easiest, but makes client to get a lot of unnecessary packets and also provides opportunity for making cheats (2d equivalents of wallhack... well previous method also does allow that but to much lesser extent).

How does BYOND handle it?
Aug 25 2020, 4:25 pm
I can't say how BYOND handles it, but I can speak to the first approach that comes to mind for me.

It's common practice to use quadtrees for collision detection. What you're asking for seems conceptually to me like a specialized version of collision detection: each player represents a rectangle on the map that is their viewport, and when an object updates you want a list of viewports it collides with. (Strictly speaking, you'll want a union of the viewports it collided with before updating, and viewports it collides with after updating.)
Aug 25 2020, 4:56 pm
I believe it's something along the lines of the client asking the server for a specific set of data as it needs it, with some overflow outside of the visual range to give a bit of a buffer between moving from a known and visible part of the map to another.

When the client needs a new piece of the map, it tells the server, with details like how much it can see, and the server responds with data based on what it knows about that client.

The server itself is always doing everything all the time, though. It's aware of everything happening regardless of whether a client is there to see it or not.

The client just becomes aware of these happenings as it asks, and discards old data as it goes.

When the server is notified of a change within a certain visual area, it determines if any other clients are also within that area and updates them as well.

This is how I've gathered it works (simplified heavily), based on what Lummox has said about it over the years, but it's really far more technical than that and there's a lot of edge cases and special stuff that has to be handled.

The chunk idea is pretty close, as the client does request a chunk of the map at a time, but the map itself isn't split into any specific chunks. The chunks are based on the client's visual range.
Aug 26 2020, 3:52 am
In response to Nadrew
Nadrew wrote:
I believe it's something along the lines of the client asking the server for a specific set of data as it needs it, with some overflow outside of the visual range to give a bit of a buffer between moving from a known and visible part of the map to another.

When the client needs a new piece of the map, it tells the server, with details like how much it can see, and the server responds with data based on what it knows about that client.

You sure it's client that sends info about which part of map he wants to see?
If user has view=6 (then probably wants to get info about 7 tiles in each direction [or sometimes even more (big icons)] because of movement), and is on position x=100, y=100, then he requests info about square from <-93, -93> to <107, 107>? I don't see why server wouldn't calculate these numbers. It also means that we need to loop through every tile in that rect, to look for objects and in result, performance will suffer.

for y in range(from_y, to_y):
    for x in range(from_x, to_x):
        # access map[y][x]



Also I guess it opens possibility for cheats when client asks for parts he's not entitled to currently see.


The chunk idea is pretty close, as the client does request a chunk of the map at a time, but the map itself isn't split into any specific chunks. The chunks are based on the client's visual range.

I don't see how chunks could be based on client's visual range.
My chunks idea was that you have (lets assume client.view = 6, so he can see 11x11 and chunks size will be like 13x13):
- map[y][x] variable which is 2d array holding info about tiles and their contents.
- chunks[y/13][x/13] variable which holds info about clients in these chunks.


When client move, you can easly add him to map array at map[client.y][client.x] and to chunks array at chunks[client.y%13][client.x%13] (or maybe to other chunks [that he's able to see] as well). Then when some event occurs on the server, server calculates on which chunk it occured and sends info about it to every client on that chunk.

This idea seems really good to me but as I mentioned before, I have no idea how to efficiently calculate chunk size and I don't see it can be efficient to have multipe chunk maps for every visual range configuration of every logged in client.


Aug 26 2020, 3:02 pm
In response to Hiead
Hiead wrote:
I can't say how BYOND handles it, but I can speak to the first approach that comes to mind for me.

It's common practice to use quadtrees for collision detection. What you're asking for seems conceptually to me like a specialized version of collision detection: each player represents a rectangle on the map that is their viewport, and when an object updates you want a list of viewports it collides with. (Strictly speaking, you'll want a union of the viewports it collided with before updating, and viewports it collides with after updating.)

This is quite interesting.

Aug 27 2020, 5:32 am
In response to Kisioj
Kisioj wrote:
Hiead wrote:
I can't say how BYOND handles it, but I can speak to the first approach that comes to mind for me.

It's common practice to use quadtrees for collision detection. What you're asking for seems conceptually to me like a specialized version of collision detection: each player represents a rectangle on the map that is their viewport, and when an object updates you want a list of viewports it collides with. (Strictly speaking, you'll want a union of the viewports it collided with before updating, and viewports it collides with after updating.)

This is quite interesting.


BYOND doesn't do this. I've talked to Lummox in the past about implementing a chunk observer approach similar to the one that Hiead references, rather than the tile-by-tile viewport gathering behavior that currently goes on.

But here's a really basic rundown of how BYOND works at its core. I'm only going to talk about the viewport here:

1) The server tells the client what it can see. I'm pretty sure that Nadrew is wrong here that the client asks for chunks of the map, but he's more right than he is wrong about everything else he said.

The server gathers up turfs(non-typed atoms are all turfs)->areas->objs(non-typed movable atoms are all objs)->mobs within range of the client eye plus a little extra past the edges, the client.screen list, and any image objects in client.images and sends their associated appearances plus location information to the client.

2) The client receives this information, sorts it, and draws it onto the screen. Then it waits for messages in the form of commands, or the repaint command from windows.

3) The client immediately forwards any commands to the server, and any repaint command is drawn from the last bundle of information the client received from the server. The client does do some minor work here, like handling animations, gliding, and icon state animations. The server doesn't know anything about these things, because they are inherently client behaviors.


The server also keeps track of appearances that clients care about. Any change to an appearance that the client is currently watching will trigger appearance updates to be sent to the client as soon as possible.


In short, BYOND is really not all that efficient when it comes to networking. It is and it isn't. It could be a lot more efficient than it is, but that would require the client to know more about the world before it connects to it, which means a heftier client and a more complex programming language built in to the engine.

Where it does happen to be very efficient, is that BYOND is little more than a mutant telnet client. Appearances can be thought of sort of like a character on a terminal with extra metadata. The entire dictionary of appearances being used in a world are sort of like a character set. Because BYOND is representing an entire appearance with a single id, it can communicate quite a lot of information to the client with very little overhead once the client has been made aware of what that id means.