alrecenk/jstimelinesync

A quick and dirty prototype for testing generalized rollback networking.

jstimelinesync's Issues

Don't resend hashes you've verified recently

Currently synchronize sends all hashes of base objects and manually created events every network update, but this is not necessary. Once a hash has been sent, verified to match, and returned without an update we could not send that hash for a while.

For instance if a base object hash is verified to be identical on both sides we could cache it, when synchronize receives a set of hashes all of those cached hashes will be functionally added to the received list, if the object hasn't changed then no new hash will be sent and the old one used instead.

Ability to actually delete objects

Currently missing the D in CRUD. Can fudge it by marking things deleted, but the hashes still clog up the sync packets. Need a proper way to actually delete things, and synchronize those deletions without sending a deleted item hash back and forth forever.

Object deletion can desynchronize and crash server

A few times when I've left the chat application open for a while I've seen the "Deleting object which doesn't exist at the time it is being deleted!" error followed by a server crash. I don't know what causes it, but I'm guessing it has to do with delayed packets from minimized browser windows. It's a show stopping issue, but I've never seen it happen when I'm actively using the server.

Switch to UDP sockets

Websockets are always TCP, which adds some error checking overhead, but this library already error checks, so it would be better to use UDP to reduce perceived latency. WebRTC might be an option to get UDP sockets. Current latency simulation in the app is not capable of measuring the effect of WebSockets and neither is Chrome's networking profiler, so also need to find a way to measure the effect before committing to a change of socket type.

Allow overriding TObject copy

TObject copy currently serializes and deserializes an object to perform a copy without caching, but it's only used in cases where the real object is available. We could allow users to manually implement copy of their custom objects to improve performance.

Cache hashing of timeline objects

Hashes of objects are computed in a few places, but objects are immutable once placed in the timeline, so they should not need to recompute hashes. These extra hashes make up a significant chunk of CPU overhead caused by the timeline.

Don't rerun spawned events that haven't changed after rollback

Currently if an event is rerun all events it has spawned will be rerun as well regardless of if it's necessary. There's a specific case that comes up in collision detection where performance could be improved dramatically by being more precise in what needs to be rerun on a rollback:

If event_1 reads data_1 and data2 and spawns event_2 which reads only data_2. If data_1 changes before event_1 causing it to rerun, but event_2 is generated identically and data_2 does not change then don't rerun event_2.

Currently, if collisions detection reads all objects in a cell and creates events for each collision detected. All of those events and everything after will be rerun if any object in the cell changes, even if it doesn't effect the resulting collisions.

There may be similar logic for when objects result the same out of a recomputed events, but it's trickier.

Possible desync if two events have exactly the same time

Currently, the placement in the timeline for identical times depends on which is added first which could be different between clients. If the two events read and write to the same object at the same time it could cause divergent behavior between client.s Need to either disallow this completely, or find a way to deterministically pick which event happens first. Tie breaking by hash is probably fine.

Build example collision detection

A demo showing how to perform collision detection and resolution needs to be built because it needs to be done a certain way to be efficient, and it's not obvious.

Resolution should not be done in the same event as detection because it creates a densely connected graph of data dependencies that make catching up from rollback more expensive. Once #21 is completed it should be possible to spawn events for collision resolution (which you'd probably want to do anyway fr hooks) that won't be rerun unless they are actually changed.

A uniform grid or tree is also likely to perform better than a fancier sweep and prune technique because it can be built into the system in a way that creates fewer dependencies.

Investigate interval events(ticks) as a special type

Interval events or ticks are a common pattern where you have an event that spawns itself after a fixed time (typically one frame). For instance, any object acting in real-time is likely to have its own tick event. These events make up the bulk of the events on the timeline. There is already some logic around internally spawned events that prevents hashes and updates being sent over the network for ticks, but they still clog up and slowdown the internal logic for network updates and rollbacks. Given their structured nature and prevalence it might be worth it to create a special type (TIntervalEvent) with custom logic to handle this type of event more efficiently.

Build webserver into node server for convenience

Could use the Express module for Node JS:

var express = require('express')
var app = express()
app.use(express.static('./'))
app.listen(3000)

Multiple calls to getObserved can break interpolation

getObserved relies on the last thing it returned for interpolation, but if you call it more than once for an object within a frame then it will affect the interpolation speed. This should not be the case.

As an example, I created bullets, that have a shooter id, and then then to draw them they fetch their shooter and duplicate its color. With a naive implementation this results in many calls to player's getObserved interpolation, completely defeating the point of interpolation. getObserved should not execute interpolation 8unless the time on he timeline has changed.

Add overridable visual interpolation

Time skewing works pretty well up to about 200 ping, but there's still a case to be made for optionally allowing manual control over how objects are visually interpolated from previous frames if they differ too much.

ID creation could easily cause race condition

Need to create a way for clients to reserve IDs, so there can't be collisions when creating new objects.

Invert spawned event graph edges

Events currently save the event that spawned them, and this information is used to squash them if the spawning event is rolled back. However, the information needed is "what events did a changing event spawn" and never "what event was a given event spawned by". Sets are built and maintained to reverse this relationship, but it would be simpler and faster if the graph were stored with edges going the right way in the first place (i.e. each event as a list of everything it has spawned).

There's a similar situation with events storing what data they read and write. The information needed is always "what events are affected by a change in data?", and never "what data did a given event read?". Once again resulting in the building of a set to invert the relationship at run-time.

Percompute maps of hashes

There are a few places where a map of hashes of events or objects is needed for quick look-ups, and it is built on demand. This O(n) map building is a significant CPU overhead that will get dramatically worse as the number of objects increases. These maps should be precomputed and cached, or if that's not practical their use should be avoided entirely.

Remove included ws node module from git

Self explanatory.

Add built-in pseudo-random number generator

Any randomness in events has to be deterministic and rollback-able, so it makes sense to have a built in timeline.random() that "just works" without a user having to think about what the timeline is doing underneath.

Add built-in functions for time offsets

The chat demo uses 3 time offsets: visual_buffer, action_delay, and player_ahead to provide a smooth experience. This functionality should be built into the timeline in a way that doesn't require the constants to be sprinkled throughout user code.

I could add as function getRender(id) to get an object at its render time which has a default offset setDefaultRenderDelay(visual_buffer), and also allows times to be set for specific objects setRenderDelay(player_id, player_ahead) .

It would also be good if you could set a default event delay and events added without time specified would be set to current_time + delay.