Voronoi-based Client-side Lag Compensation and Interaction Offload

Massive multiplayer, and even more so megaserver, architecture is a war of tradeoffs. There are plenty of problems and much fewer solutions. When scaling to the numbers involved in a megaserver, there are new problems and variations on the old ones. Peer-to-peer is generally treated as a non-starter, and rightfully so, in discussions regarding multiplayer games. When the topic is broached, peer-to-peer is normally and regretfully seen as some kind of silver bullet panacea answer to all the gaming industries problems. It is not. It should not be, however, a taboo. WebRTC does enable the offloading of chat and voice to the browser. Peer-to-peer does have its place in the gaming world, albeit a highly restricted place. So, then, Lag compensation techniques, along with the N-squared interaction and the Never-trust-client problems are the topic of this post.

Client-side prediction is a thorn is the side of player in many-a-game. Many players complain of being shoot while behind cover, around walls, after jumping etc. It is not an ideal solution. Scaling a game into hundreds and even thousands of players in an area only makes this problem worse. With Pikkoserver and other player-server migration technologies hitting the playing field, this is a thorny problem nearing its blooming season. (Couldn't help the pun, forgive me.)

Voronoi-based Overlay Network

“A VON is a fully-distributed overlay network that allows neighbors to be discovered on a Voronoi-partitioned virtual space. Each node in VON has a coordinate point and specifies an Area of Interest (AOI) within which the node is constantly aware of all AOI neighbors. Nodes are allowed to move continuously in space and connect with new AOI neighbors. For simplicity, we assume a 2D space but note that VON is generalizable to 3D spaces. To discover new AOI neighbors, each node organizes the coordinates of itself and its AOI neighbors in a Voronoi diagram.”

http://vastlib.wikispaces.com/VON

The vastlib is defunct(an assumption) and used for another purpose, but the Voronoi-based Overlay Network is none-the-less interesting in the context of the N-squared interaction problem. The authoritative server could offload much of the workload of keeping track of player interactions to the peer network if workable safeguards could be constructed. The advent and adoption of the WebRTC protocol world very helpful in this new world of WebGL browser games with ported game engines like Unreal 4 and Unity 5.

One of the main risks involved with trusting the client with this task is that some will certainly cheat to know the location of other players. The solution, though simple, is a tradeoff. Radar. If you willingly give the players what they want rather than keeping it from them, the value of a hack is negated. Is it more valuable to the game to have a shot a discrete peer-to-peer task offloaded to the client-side and the resulting reduction in server traffic or to have the near-space location of players be hidden from other players?

Of course, then, there is the problem of aim bots. This has been dealt with, to varying degrees of success, with techniques that revovle around the sight location at time of firing checks and invisible mobs to reveal and ban users of this type of software. Another answer, if applicable to the genre (i.e. Scifi) is target locking, a hybrid of tab targeting and twitch targeting. Once targeted manually the target tracks the NPC or player. This, again, helps to negate the value of cheating and further reduces the needed interchange of information between clients and authoritative server.

Further, confirmations, like those of Bitcoin, could be used to enforce a certain level of honesty. This, backed up by the revocation of peer-delag services to those found to manipulating their location data, or an outright banning.

Further Information:

http://vast.sourceforge.net/publication.php

(Much is on the topic spatial publish subscribe: SPS)

You know, you should probably make your marketing pitch a little more straightforward. I have a fair background in most of these topics, and it me 10 minutes to decipher all the buzzwords and figure out what your post is getting at.

Marketing? Im not sure I understand. I am unaware of a company that is doing anything similar. Please post a link if they are.

Peer-to-peer is a complicated topic. Trusting the client is sketchy at best. I was looking for something on the client-side to work with Project Tunguska(Comet-based, node.js) that could push off as much from the server as was possible when I found VAST. With server bandwidth and hardware constraints being what they are, it would be an innovative costcutting measure. I have, as of yet, not heard back from the academics with the SPEX project, which is similar in nature, whose source code is not readily avilable. VAST appears to be a dead project, but the concepts they are working with seem sound. I am unsure if the concept is transferrable to this use case... I.e frontend rather than backend.

I am imagining an abstraction of a tipped over hourglass where the bottle neck is the internet and the packets are the sand, though concurrently bi-directional sand. The backend has always been a large base of internal network traffic and message passing. The client-side has not. If a topography could be engineered as an hourglass(on its side) via the normal backend and the new frontend using a constrained peer-to-peer over WebRTC concept(like Peer.js with load-balacning), the game could be far more efficient. Bandwidth costs money; server hardware scaling costs money. Obivously transational data could not be offloaded; exp, items... etc etc

It doesn't seem like marketing to me -- the VAST project is an older peer-to-peer virtual world project, that used voronoi maps.

One of the weaknesses of that project was the fact that there either needs to be one global voronoi map server, OR there is a risk that different clients will end up "splitting" the view of the world, such that two players at the same coordinates will not see each other, because of difference in ordering of seeing other player updates and generating voronoi cells.

Also: Why is voronoi cells interesting here, as opposed to generalized area-of-interest measurements? Full voronoi cells have rather non-linear update characteristics when neighbors move, and because they are calculated based on knowledge of entity positions, because that knowledge is delayed by latency, the map will be delayed by latency, and each participant will be differently delayed on each participating node, and thus each client's voronoi map will have a different set of neighbors for each node! If you rely on nearest-neighbors to update you about new possible neighbors, you will have to support a very low maximum movement rate, as well as a minimum allowed entity distance -- no entities can get closer than X meters to each other -- for the solution to be well behaved.

I don't think it's marketing

I didn't mean it in the sense of an actual sales attempt. I meant 'marketing pitch' in the sense of selling a concept or idea (as in an academic paper).

Is a Voronoi mapping system even applicable to a Internet Network network-type mapping ??

The internet is not a continuous 2D(or3D) surface, its a bunch of paths with delays and bandwidth (and quality) defining its edges. Because of the differences in the paths the relations often dont for cohesive 'surfaces'.

They may have come up with some analysis of such network to employ, but is it still a Voronoi method ?

Defining neighbor sets for some low security Peer-to-peer processing being a seperate issue (no matter what mapping system is used)

Is a Voronoi mapping system even applicable to a Internet Network network-type mapping ??

No, but the problem he's trying to solve is "when I have X entities in a game world, which physical server instances should simulate which entities."

I was not writing an essay for homework or a paper for academia, nor even searching for prior art in a particular context. I read several papers while researching a topic, and though it did not fit that topic, I tried to apply it to another seemingly related topic offhandedly. The concept does, indeed, appear flawed: But, a negative result is still a result.

Thanks for the replies.