logo enkisoftware
Independent game developer making AVOYD
en  fr

Octree streaming - part 3

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.

2023
 › Moving from FastSpring to Itch.io as a Payment Provider
 › Optimising Voxel Meshes for Games Using Blender
 › Implementing a GPU Voxel Octree Path Tracer
 › Avoyd Release Streams and Minecraft Lit Materials
 › Avoyd Beta Stream
2022
 › Isometric Render of a Minecraft Map in Avoyd Voxel Editor
2021
 › Importing Minecraft maps in Avoyd Voxel Editor improved
2020
 › Runtime Compiled C++ Dear ImGui and DirectX11 Tutorial
2019
 › Boxes in Space: procedural generation of abstract worlds in Avoyd
 › Procedural python word generator: making user names out of 4 syllables
 › In-game building
 › Player-deployable turrets in Avoyd
2018
 › Avoyd Game Singleplayer and Coop Multiplayer Test
 › Voxel Editor Evolved
2017
 › Speeding up Runtime Compiled C++ compile times in MSVC with d2cgsummary
 › Multiplayers toxic last hit kill and how to heal it
 › Avoyd Editor Prototype
2016
 › Black triangles and Peter Highspot
 › Colour palettes and lighting
 › Concept art by Rebecca Michalak
2015
 › Internals of a lightweight task scheduler
 › Implementing a lightweight task scheduler
 › Feral Vector
 › Normal generation in the pixel shader
2014
 › Python Google App Engine debugging with PyCharm CE
 › Lighting voxel octrees and procedural texturing
 › Patterns and spheres
 › Python Google App Engine debugging with PyTools
 › Interview
 › Domain masking using Google App Engine
 › Octree streaming - part 4
 › Black triangles and nervous_testpilot
 › Presskit for Google App Engine
 ›› Octree streaming - part 3 
 › Octree streaming - part 2
 › Octree streaming
2013
 › LAN discovery with multiple adapters
 › Playing with material worlds
 › Developer Diary archive
 › Website redesign
 › First Person Editor
 › First Avoyd tech update video
 › Implementing a static website in Google App Engine
 › Multiplayer editing
 › First screenshots
 › Thoughts on gameplay modes
 › Back in 1999
2002
 › ECTS 2002
 › Avoyd Version 1.6.1 out
 › Avoyd Version 1.6 out
2001
 › Biting the bullet
 › Avoyd version 1.5 out
 › Monday Mayhem
 › Avoyd version 1.5 alpha 1 out
 › Avoyd version 1.4 out
 › ECTS 2001
 › Fun with Greek letters
 › Closer just a little closer
 › Back already
 › Artificial Humanity
 › Products and promises
 › Ecommerce
 › Explosions galore
 › Spring fixes
 › Open source and ports to other operating systems
 › Avoyd LAN Demo Version 1.1 is out
 › Thanks for the support
 › Avoyd LAN Demo Ready
 › Game Tech
 › Optimising Voxel Meshes for Games Using Blender
 › Implementing a GPU Voxel Octree Path Tracer
 › Importing Minecraft maps in Avoyd Voxel Editor improved
 › Runtime Compiled C++ Dear ImGui and DirectX11 Tutorial
 › Boxes in Space: procedural generation of abstract worlds in Avoyd
 › Procedural python word generator: making user names out of 4 syllables
 › Speeding up Runtime Compiled C++ compile times in MSVC with d2cgsummary
 › Internals of a lightweight task scheduler
 › Implementing a lightweight task scheduler
 › Normal generation in the pixel shader
 › Lighting voxel octrees and procedural texturing
 › Octree streaming - part 4
 ›› Octree streaming - part 3 
 › Octree streaming - part 2
 › Octree streaming
 › LAN discovery with multiple adapters
 › enkiTS
 › Internals of a lightweight task scheduler
 › Implementing a lightweight task scheduler
 › RCC++
 › Runtime Compiled C++ Dear ImGui and DirectX11 Tutorial
 › Speeding up Runtime Compiled C++ compile times in MSVC with d2cgsummary
 › Web Tech
 › Moving from FastSpring to Itch.io as a Payment Provider
 › Procedural python word generator: making user names out of 4 syllables
 › Python Google App Engine debugging with PyCharm CE
 › Python Google App Engine debugging with PyTools
 › Domain masking using Google App Engine
 › Presskit for Google App Engine
 › Implementing a static website in Google App Engine
 › Avoyd
 › Moving from FastSpring to Itch.io as a Payment Provider
 › Implementing a GPU Voxel Octree Path Tracer
 › Avoyd Release Streams and Minecraft Lit Materials
 › Avoyd Beta Stream
 › Isometric Render of a Minecraft Map in Avoyd Voxel Editor
 › Importing Minecraft maps in Avoyd Voxel Editor improved
 › Boxes in Space: procedural generation of abstract worlds in Avoyd
 › In-game building
 › Player-deployable turrets in Avoyd
 › Avoyd Game Singleplayer and Coop Multiplayer Test
 › Voxel Editor Evolved
 › Multiplayers toxic last hit kill and how to heal it
 › Avoyd Editor Prototype
 › Black triangles and Peter Highspot
 › Colour palettes and lighting
 › Concept art by Rebecca Michalak
 › Feral Vector
 › Patterns and spheres
 › Interview
 › Black triangles and nervous_testpilot
 › Playing with material worlds
 › Website redesign
 › First Person Editor
 › First Avoyd tech update video
 › Multiplayer editing
 › First screenshots
 › Thoughts on gameplay modes
 › Back in 1999
 › Avoyd 1999
 › Developer Diary archive
 › Back in 1999
 › ECTS 2002
 › Avoyd Version 1.6.1 out
 › Avoyd Version 1.6 out
 › Biting the bullet
 › Avoyd version 1.5 out
 › Monday Mayhem
 › Avoyd version 1.5 alpha 1 out
 › Avoyd version 1.4 out
 › ECTS 2001
 › Fun with Greek letters
 › Closer just a little closer
 › Back already
 › Artificial Humanity
 › Products and promises
 › Ecommerce
 › Explosions galore
 › Spring fixes
 › Open source and ports to other operating systems
 › Avoyd LAN Demo Version 1.1 is out
 › Thanks for the support
 › Avoyd LAN Demo Ready