Event based future prediction engine

[TheJJ]

We have some ideas to make the game engine completely tickless. That means there will be no regular update interval in the simulation. It becomes event based!

Basically, on each event we always try to predict it's influence to the world as much into the future as "it makes sense". For that, we have a space-time model of the game state, that is, all the data is time-relative. We can then align the event into the spacetime and make required adjustments to the predictions.

The differences to the standard ticked-approach are not that big, especially in the simulation logic itself. Just the approach and data storage is totally different.

• As our world is 3d (we do want to have terrain height..), we have to store spacetime in 4d
• An entity has a 2d or even 3d hitbox, which, dragged over time is a Tube (i.e. curve with volume)
• The movement and the changing properties of the entity is a Curve

Questions to solve:

• How far do we calculate into the future?
  • Probably depends on the event (pathfinding, research start, attacking, ...)
  • Many events are easy to predict for t -> ∞ (building progress, research, ...)
  • Can account server load to abort further recursion
• Which influence in the spacetime wins?
  • Events that would be anticipated by a intelligent being can already be accounted
  • Events that can't be anticipated or the entity to be influenced is dumb must always win
• When do we continue calculating at points where we aborted further prediction calculation?
  • Could be done by seting up a "continue calculation" keyframe at the point where calculation was stopped before

Yes, it sounds crazy, but it may work. More info to come... 🔥

https://0fps.net/2014/02/26/replication-in-networked-games-spacetime-consistency-part-3/

[Wandalen]

Intrigued.

[janisozaur]

Interesting. What benefits going tickless brings? To me it sounds like complexity of code and network protocol increases by a lot, while not really bringing such substantial improvements. If I recall correctly, vanilla used variable-length ticks which addressed the issue of network latency to some extent.

[Tomatower]

Maybe "Tickless" is the wrong word to describe the intentions behind this concept - maybe "predicting" is more accurate.

The Idea is more to evaluate the consequences of each action and predict it as far as possible into the future. The Idea of "Ticks" like "I have to transmit ~10 Updates per Second to the Clients" is not affected by this model, as well as the 30/60/144 Hz renderings.

The benefit of having everything run in predictions is, that you just have to define certain key frames, that may even be some 30 seconds in the future, and in terms of networking and even simulation they do not have to be touched anymore, so no wasted CPU and Network load for them. The only things that may change a prediction are inputs by the user, that will then change a few predictions, these changes are transmitted, and violá - everything is back in sync.

[VelorumS]

Shortest TODO entry I can make of it:

Unit actions have an update() methods that change attributes of the units.

Instead, unit actions must generate predictions and corrections to these predictions. There must be another entity that will read these predictions/corrections and mutate attributes of the rendered objects. That entity must be able to seek backwards in history.

There were 16 unit actions last time I've checked.

[Tomatower]

Yes - every action done by a user is evaluated in the beginning and its consequences are calculated.

The Unit, that draws/renders animation and needs to have a static snapshot for that, can do so by interpolating (linear or step-wise) between keyframes. On a very abstract level, this should be seen like no time exists at all, even for rendering.

Internally, this can be implemented by just walking over a double-linked-list indexed by timestamp, and storing a "active-element" reference for every value.

Keep in Mind - this is not only done for Unit's locations, but also for their HP, for buildings, and their bulding progress, for the lists of existing units - for every single value that might be changing within every single game entity.

[Tomatower]

I created a test project for this concept. It is basically Pong, but running with tubes and more or less stateless - for testing how this concept can work. Feel free to test it: https://github.com/Tomatower/tubepong

[Tomatower]

void Physics::update_ball(PongBall &ball, const tube::tube_time_t &now, int recursion_limit) { 
    auto speed = ball.speed.get(now); 
    auto pos = ball.position.get(now);
    float ty = 0;
    if (speed[1] > 0) { // the ball is travelling downwards
        ty = (1 - pos[1]) / speed[1];
    } else {
        ty = (pos[1] - 1) / speed[1];
    }
    auto hit_pos = pos + speed * ty;
    ball.position.set_drop(now + ty, hit_pos);
    speed[1] *= -1;
    ball.speed.set_drop(now + ty, speed);

    if (recursion_limit > 1) {
        update_ball(ball, now + ty, recursion_limit - 1);
    }
}

Used methods:

set_drop(time, value): Set the value at the given time time and drop all following ones.

What does it?

It bounces the ball between the upper and the lower boundary (in the example 0 and 1).

1. Calculate the time, when the ball will cross a wall boundary (ty) (y-position / y-speed = y-time-to-collission)
2. Calculate the point, where the ball will hit: position + speed * ty
3. Insert the hit point as keyframe (at now + ty)
4. Revert the y-speed at this point (at now + ty)
5. Go To 1

Why!

Do you see how simple and straight-forward the whole pall prediction was? From this point on pyhsics is going to sleep. (btw - we can exactly know the point in time when this will happen - just calculate the tx the way we did ty - and then check it with the paddels, whenever a paddel movement of the player we are currently moving toward happens)

[Wandalen]

quantum mechanics :)

[TheJJ]

A formalization of what we will be doing is this: https://0fps.net/2014/02/26/replication-in-networked-games-spacetime-consistency-part-3/

Just discovered it. We will basically perform dead-reckoning with player input to create the contents of the uncertainty cones.

[darkcoderrises]

Is someone working on this?, If not, could I pick this up?

[TheJJ]

@darkcoderrises the current implementation is in #744, so if you like you can add remarks and suggestions there.