Stupid latency compensation rollback system

Cargo.toml

[package]
name = "game-state-recomputation"
version = "0.1.0"
authors = ["luna <selenologist@users.noreply.github.com>"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
im = "15.0"

src-main.rs

use im::OrdMap;
use std::collections::{BTreeMap, BTreeSet};
use std::ops::Bound::{Included, Unbounded};

#[derive(Debug)]
enum Input {
//    Up,
    Down,
//    Left,
    Right,
    Create,
//    Destroy
}

type Tick = usize;

type PlayerId = usize;

type PlayerInputs = BTreeMap<(Tick, PlayerId), Input>;

type VariableId = usize;

type VariableValue = usize;

type ChangeId = (PlayerId, VariableId);

type Changes = BTreeSet<ChangeId>;

type ChangesByTick = BTreeMap<Tick, Changes>;

type Values = OrdMap<ChangeId, VariableValue>;

type State = OrdMap<Tick, Values>;

// maximum amount a player input can be behind the server tick
const MAX_STALE_STATE: usize = 4;

fn main() {
    let mut state = State::new();
    let mut changes_by_tick: ChangesByTick = BTreeMap::new();
    let mut sorted_inputs = PlayerInputs::new();
    
    let mut server_tick: Tick = 0;
    let mut recompute_from = 0;

    let mut last_values = Values::new();
    
    let mut player_tick = BTreeMap::new();

    enum Event {
        Advance, // Advance server tick
        ReceivedInput(Tick, PlayerId, Input) // inputs as they come off the wire
    }

    let events: Vec<Event> = vec![
        Event::ReceivedInput(0, 0, Input::Create),
        Event::ReceivedInput(0, 1, Input::Create),
        Event::Advance, // ST 1
        Event::Advance, // ST 2
        Event::Advance, // ST 3
        Event::Advance, // ST 4
        Event::ReceivedInput(1, 0, Input::Down),
        Event::Advance, // ST 5
        Event::ReceivedInput(2, 0, Input::Right),
        Event::Advance, // ST 6
    ];

    fn eval(current_values: &mut Values, tick_changes: &mut Changes,
            tick: Tick, pid: PlayerId, input: &Input)
    {
        println!("eval  tick {} pid {} input {:?}", tick, pid, input);
            
        match input {
            Input::Create => {
                tick_changes.insert((pid, 0)); // changed x coordinate
                tick_changes.insert((pid, 1)); // changed y coordinate
                current_values.insert((pid, 0), 0);
                current_values.insert((pid, 1), 0);
            },
            Input::Right => {
                tick_changes.insert((pid, 0)); // changed x coordinate
                // the above should happen regardless if the next update actually fails
                current_values.entry((pid, 0)).and_modify(|x| { *x += 1 });
            },
            Input::Down => {
                tick_changes.insert((pid, 1)); // changed y coordinate
                current_values.entry((pid, 1)).and_modify(|y| { *y += 1 });
            },
            _ => unimplemented!()
        }
    }

    let mut advance = |sorted_inputs: &PlayerInputs, server_tick: Tick, mut recompute_from: Tick|
    {
        println!("Computing server tick {} from {}", server_tick, recompute_from); 
        
        // cleanup bad states
        state = {
            // invalidate any more recent states
            let (keep_state, _discarded) = state.split(&(recompute_from + 1));
            // and also any older than permitted
            if server_tick > MAX_STALE_STATE+3 {
                let oldest_tick = server_tick.saturating_sub(MAX_STALE_STATE + 3);
                let (_discarded, keep_state) = keep_state.split(&oldest_tick);
                keep_state
            }
            else {
                keep_state
            }
        };
        
        // dirty values during this Advance, including dirty values from last tick
        let mut current_changes = Changes::new();
        
        // changes made in a previous computation of this tick should also be considered
        // changes this time, so that values that change as a result of recomputation can
        // be invalidated and replaced.
        fn load_previous_dirty(changes_by_tick: &ChangesByTick,
                               current_changes: &mut Changes,
                               previous_tick: Tick)
        {
            if let Some(last_advance_changes) = changes_by_tick.get(&previous_tick) {
                println!("load  tick {} dirty {:?}", previous_tick, last_advance_changes);
                // append these changes only to the Advance-wide changes, not to the
                // current tick's changes
                for changes in last_advance_changes.iter() {
                    current_changes.insert(*changes);
                }
            }
            else {
                println!("load  tick {} dirty failed", previous_tick); // this is normal
            }
        };

        fn store_dirty(changes_by_tick: &mut ChangesByTick,
                       current_changes: &mut Changes,
                       tick: Tick, tick_changes: Changes)
        {
            // add this tick's changes to the changes made this Advance
            for change in tick_changes.iter() {
                current_changes.insert(*change);
            }
          
            println!("store tick {} dirty {:?}", tick, tick_changes);
            // finally store those changes so the next Advance knows what to change
            changes_by_tick.insert(tick, tick_changes);
        };

        // current values during this Advance
        let mut current_values: Values =
            if let Some((actual_last_tick, old_values)) = state.get_max() {
                println!("Actually computing from state on tick {}: {:?}", actual_last_tick, old_values);
                load_previous_dirty(&changes_by_tick, &mut current_changes, *actual_last_tick);
                
                recompute_from = std::cmp::min(recompute_from, *actual_last_tick);

                old_values.clone()
            }
            else {
                println!("Actually computing from blank state");
                Values::new()
            };

        let mut store_state = |tick, current_values|
        {
            println!("store tick {} values {:?}", tick, current_values);

            // and store the current state for this tick
            state.insert(tick, current_values);
        };

        let mut tick_changes = Changes::new(); // changes made during currently processed tick
        let mut previous_tick = recompute_from; // tick on last iteration of this loop
        
        for ((tick, pid), input) in sorted_inputs.range((Included((recompute_from, 0)), Unbounded)) {
            // probably a better way to do these deref in the destructure above but I can't do it
            let tick = *tick;
            let pid  = *pid;

            if tick > previous_tick {
                load_previous_dirty(&changes_by_tick, &mut current_changes, tick);
                
                // get the changes for the previous tick this Advance by replacing
                // tick_changes with an empty one
                let previous_tick_changes = std::mem::replace(&mut tick_changes, Changes::new());
             
                // store changes for the previous tick, adding them to current_changes too
                store_dirty(&mut changes_by_tick, &mut current_changes,
                            previous_tick, previous_tick_changes);

                // store the state at the end of the last tick,
                // as the the start of this new tick
                store_state(tick, current_values.clone());

                previous_tick = tick;
            }
            
            eval(&mut current_values, &mut tick_changes, tick, pid, input);
        }

        // handle any changes made in the final tick.
        store_dirty(&mut changes_by_tick, &mut current_changes, previous_tick, tick_changes);

        // store current state as current server tick
        store_state(server_tick, current_values.clone());

        println!("Dirty values: {:?}", current_changes);
        
        println!("Actual changes:");
        let mut changes_count = 0;
        for (pid, vid) in current_changes.iter() {
            let (pid, vid) = (*pid, *vid);
            let last = last_values.get(&(pid, vid));
            let current = current_values.get(&(pid, vid));
            if last != current {
                println!(" {} {}: {:?} -> {:?}", pid, vid, last, current);
                changes_count += 1;
            }
        }
        println!(" ({} changes / {} dirty)", changes_count, current_changes.len());

        last_values = current_values;
    };
    
    for event in events.into_iter() {
        match event {
            Event::ReceivedInput(tick, pid, input) => {
                let oldest_tick = server_tick.saturating_sub(MAX_STALE_STATE + 2);

                // remove inputs older than permitted
                sorted_inputs = sorted_inputs.split_off(&(oldest_tick, 0));

                if tick > server_tick {
                    panic!("Player {} sent tick {} ahead of server tick {}", pid, tick, server_tick);
                }
                else if tick < oldest_tick {
                    panic!("Player {} sent tick {} that was {} frames older than limit {} st {}",
                           pid, tick, 
                           oldest_tick - tick, oldest_tick, server_tick);
                }

                let player_last_tick = player_tick
                    .entry(pid)
                    .or_insert(0);

                if tick <= *player_last_tick && tick > 0 {
                    panic!("Player {} sent out of order or duplicate tick {} after last tick {}",
                           pid, tick, *player_last_tick);
                }
                else {
                    *player_last_tick = tick;
                }

                sorted_inputs.insert((tick, pid), input);

                if tick <= recompute_from {
                    // recompute next Advance from the oldest tick received since the last Advance
                    recompute_from = tick;
                }
            },
            Event::Advance => {
                server_tick += 1;
                advance(&sorted_inputs, server_tick, recompute_from);
                // default to latest server tick for next recompute tick
                recompute_from = server_tick;
            },
        }
    }
}