feat: Support custom input prediction

[caspark]

Introduces a new associated type parameter for Config that controls the input prediction approach used.

See extensive documentation on InputPredictor and its implementations.

---

This addresses #69 (cc @johanhelsing, @aleksa2808) and accidentally also addresses #74 (cc @MaxCWhitehead ).

Some off the cuff design decisions I made when I hacked this together (before I got carried away writing documentation):

• A) I am using an associated type parameter to plumb the input predictor down to the input queue. I did this out of convenience/laziness originally because I want this change myself, but it does mean that user code would have to change to add in that extra associated type parameter. If there's interest in merging this, it should be totally possible to modify this to pass a function/closure to SessionBuilder instead and pass a pointer to that down the 2-3 layers to InputQueue (and that's probably a better approach).
• B) We still invoke the user provided prediction function for cases where there was no previous frame. I figure this is useful for those folks for whom zeroed() does not equate to "no input", like @MaxCWhitehead over in #74.
• C) I let folks opt out of providing a prediction by returning None, in which case we just fall back to using zeroed(). This makes it a tiny bit more convenient to implement a prediction function if you are okay with using zeroed() as your default in the case where there is no prior input to base your prediction on, but it's super minor. Might be better to just require a prediction to be made.
• D) There's no way to know what frame number the prediction is for, nor what the frame number of the last confirmed prediction is, nor what player it is for. I can imagine some advanced input predictor trying to guess what the next position of a player's joystick might be based on rate of change previously, but I don't have that use case so I am wary of going down that rabbit hole because without the real use case I'd probably design something that's useless.

I am not strongly opinionated about any of those, so please let me know what your preferences are and I will adjust the code to suit. If you are also not strongly opinionated, I recommend:

• A: convert to SessionBuilder param instead of associated type to reduce impact on existing codebases
• B: leave as-is (it's useful)
• C: require a prediction (don't let people opt out)
• D: leave as-is (can always make the predictor more flexible later by adding a second more capable type of input predictor)

But I haven't made those changes yet because they'd be wasted if you don't want to merge something along the lines of this PR! And also I've already spent a few hours on this today so I need to get back to actually implementing rollback in my game ;)

[gschup]

converted to draft as you stated (WIP) in the title.

[caspark]

Sure, makes sense to have this be a draft PR. But if I do spend the time to clean this up by addressing the points I suggested in the ways that I suggested, are you willing to merge it? (subject to further feedback from review then of course)

I don't want to spend some time polishing this if you're not happy with the approach I'm taking :)

[gschup]

In that case, please wait a little while until I find time to look at it properly. In general, I like the idea a lot, seems like a useful option for special cases.

[caspark]

FYI I intend to rebase & rework this PR once #82 has been merged (and ideally after I've merged a PR to add logging as per #89, assuming we're aligned on adding logging of some kind), since right now this PR is using bytemuck stuff that #82 removes.

[caspark]

I have rebased this onto current main, fixed conflicts, updated docs and fixed the remaining todos - so this should be ready to go now (edit: well, it should be ready to go now, since I just force pushed again to remove an unused import).

I decided to keep using the associated type for the input predictor function for now, as that makes it super easy to get at the input predictor from anywhere, and I have a further change in mind to use the input predictor to further optimize the delta encoding (probably a few PRs from now) - it might be a little more painful to thread an Fn to the delta encoding function vs just pulling the function out of the type. Once that's sorted then it should be clear to see whether a closure passed to the session builder or an associated type is the way to go.

[TarVK]

Since it has been some months since the last activity, I figured it would be worth showing my support. This feature would also be very handy for the game I'm working on! I also think the provided implementation of the feature looks nice and simple to use. I was however wondering, would it be much effort to add the "current" game-state to the prediction function? In my game, I would like to do a prediction based on what's going on in the game, so I can make a good guess of what the player might do.

[gschup]

Just want to leave a quick note: I am sorry for not looking into this for quite a while. Real life is keeping me busy atm 👶

[caspark]

would it be much effort to add the "current" game-state to the prediction function?

@TarVK I had a look and I think it would be tricky. The core issue in the current design is that when ggrs decides it needs to roll back, it builds up the list of GgrsRequests (which may include predicted input), so it can't access arbitrary game states to make predictions with - because in the case of a rollback, your game hasn't actually simulated that game state yet.

Here's an example (adjust_gamestate() if you want to follow along in the code), assuming we're at frame X+N and ggrs realizes it needs to roll back to frame X (e.g. because X+1 used incorrectly predicted input):

1. Ggrs enqueues a request to load frame X
2. Ggrs enqueues N requests to advance forward 1 frame based on the (either confirmed or predicted) input for that frame
3. Your game reads the list of requests from ggrs: it loads frame X, then does N frame advances.

Now let's zoom in on step 2, and let's say N=2:

• 2a. Ggrs enqueues request to advance to X+1, and it could access the game state of X to provide to an input prediction function
• 2b. Ggrs enqueues request to advance to X+2 - but here, the game state of X+1 cannot be accessed because your game hasn't simulated (and saved) it yet!

(In the GGPO reference implementation this issue wouldn't exist because the callback-based approach used there means GGPO can effect loading and advancing of state directly, so it knows that it can access current world state whenever it wants to.)

It might be possible to resolve this issue in ggrs by requiring the game to ask ggrs what the correct input is for a given advance request - something like:

for request in requests {
    match request {
        // old approach that doesn't support input prediction based on current world state
        // GgrsRequest::AdvanceFrame { inputs } => self.advance_frame(inputs),

        // new approach that might work for supporting input prediction based on current world state
        GgrsRequest::AdvanceFrame { frame_number } => {
            let inputs = ggrs_p2p_session.inputs_for_frame(frame_number);
            self.advance_frame(inputs)
        }
        // elided: handling other request types
    }
}

However actually implementing inputs_for_frame() will be a bit tricky as the code which handles predictions (in SyncLayer) relies a lot on being "driven" by an owning session that's managing rollbacks: there's currently no way to fetch an input for frame N unless the owning session is in the middle of effecting a rollback to frame N.

So: not super easy, probably doable with sufficient effort, but not something I'm likely to spend any time on.

[TarVK]

Hmm right, fair enough. Thanks for having a look anyway!