Doug Binks - 16 Jan 2014
The post follows on from the earlier post on Octree Streaming. You should be able to read them out of order, but you get cake if you read part 1 first, then part 2.
This tech update video shows off multiple players rapidly and smoothly editing fairly large sections of the environment whilst in edit mode. Materials and rendering are all still simple debug visuals for clarity rather than beauty, but there's still a fair degree of artistic freedom available. It's a real pleasure being able to carve and paint geometry fluidly in a connected online world.
Getting this to work, and work well, took a fair amount of effort and I'll explain some of the technical details here.
The first critical part is ensuring correctness - we need to ensure the combination of edit messages and octree data messages combine to produce the same result as on the server at the time they were sent. This is complicated by the fact that the client may or may not have the prior data for the volume. There are quite a few ways to handle this, but first I need to add some more detail to how we transmit the octree data.
We can thus potentially send our requests for data and the data itself using an unreliable network protocol, and if we don't receive a response to our request we simply re-send it if it's still a priority. An alternative is to send the data with a reliable protocol built on top of a UDP networking layer, such as Raknet (which I use). This simplifies the request code, but has the disadvantage that any lost packets will be retransmitted with potentially old data. This would seem to point to using an unreliable transport protocol for the octree request and data packets.
If we add edits into the mix we get a problem - how do we ensure that any transmitted changes are kept consistent with the octree data being sent? Sending octree requests, octree data and edit messages reliably and in order on the same ordering channel proved to be the simplest approach, so that's what I currently use.
Clients send edit requests to the server, and the server then sends all edits to all clients in the order in which they are processed on the server. On each client, edits are handled in order with incoming octree data, and decomposed into edits on missing and available nodes. All edits to missing nodes are discarded as the client may later request the entire branch below this node, thus getting up to date data for it.
As we add game-play and more complex editing (such as copy-paste), I'll need to revisit this approach. The current plan is to send complex change data as an octree patch if it's close to the players position, and if not send a message to invalidate the node above the edit. Copy-pastes can be initially sent as the entire data set with an identifier, so they can be re-used with a simple re-paste message in future. A palette of known pre-existing brush sets should also help.
For extremely large worlds with large numbers of players further work is needed to allow the system to scale. Distant edits could be accumulated, and transmitted as an invalidate message for a node above all edits in that volume. The accumulation period can be set to be a fraction of the travel time for edits, which should permit the server memory and network transmission requirements to scale.