ts

3 files changed, 559 insertions, 0 deletions

diff --git a/client/src/net/game.ts b/client/src/net/game.ts
new file mode 100644
index 0000000..c8e5991
--- /dev/null
+++ b/client/src/net/game.ts
@@ -0,0 +1,186 @@
+import { Frame, GameState, Input, Key, KeyMap, PlayerInput } from "../types.js";
+import { startInputListener } from "./input.js";
+import { multiplayer } from "./multiplayer.js";
+
+/**
+ * @author tint
+ * @template Data, Input
+ */
+export class Game {
+
+    historysize: number
+    history: Frame[]
+    historyStart: number
+    currentFrame: number
+    advance: (pastData: GameState, input: Input, frame: number) => GameState
+
+	constructor(history: number) {
+		this.historysize = history;
+		
+		this.history = [];
+		this.historyStart = 0;
+		
+		// the game may have inputs from the "future"
+		// (local input delay to make sure inputs play at the same time on all machines)
+		// so the "present" isn't always the latest frame
+		// the game loop should set this every frame
+		this.currentFrame = 0;
+	}
+	
+	startHistory(frame: number, data: GameState) {
+		this.historyStart = frame;
+		this.history = [{ data, input: { players: {} }}];
+		this.currentFrame = frame;
+	}
+	
+	getHistory(frame: number): Frame {
+		return this.history[frame - this.historyStart];
+	}
+	
+	getFrame(): number {
+		return this.historyStart + this.history.length - 1;
+	}
+	
+	getCurrentData(): GameState {
+		const entry = this.history[this.history.length - 1];
+		return entry && entry.data;
+	}
+	
+	/**
+	 * Sets the input at a specific frame. If that frame is in history,
+	 * the game will be rewound, the input applied, and then fast-forwarded to the current head.
+	 * If the frame is ahead of the current latest frame, the game will be run until that frame.
+	 */
+	setInput(frame: number, input: Input) {
+        console.log('input', frame, input)
+		this.editFrame(frame, (index: number): void => {
+			let past = this.history[index - 1];
+			if(index === 0) {
+				past = { data: undefined, input: undefined };
+			}
+			this.history[index] = {
+				input,
+				data: this.advance(past ? past.data : undefined, input, frame),
+			};
+		});
+	}
+	
+	setData(frame: number, data: GameState) {
+        console.log('data', frame, data)
+		this.editFrame(frame, (index: number): void => {
+			this.history[index] = {
+				data,
+				input: this.history[index] && this.history[index].input,
+			}
+		});
+	}
+	
+	editFrame(frame: number, edit: (index: number) => void) {
+		const head = this.historyStart + this.history.length;
+		if(frame < head) {
+			if(frame < this.historyStart) {
+				throw new Error("Tried to edit a past frame not in history: " + frame);
+			}
+			
+			edit(frame - this.historyStart);
+			// fast forward back to the present with the new data
+			for(let i = frame + 1; i < head; i++) {
+				const past = this.history[i - this.historyStart - 1];
+				this.history[i - this.historyStart].data = this.advance(
+					past ? past.data : undefined,
+					this.history[i - this.historyStart].input,
+					i
+				);
+			}
+		} else {
+			// fast forward the inbetween frames with no input
+			for(let i = head; i < frame; i++) {
+				const entry = this.history[i - this.historyStart - 1];
+				this.history[i - this.historyStart] = {
+					input: undefined,
+					data: this.advance(entry ? entry.data : undefined, undefined, i),
+				};
+			}
+			edit(frame - this.historyStart);
+		}
+		
+		while(this.history.length > this.historysize) {
+			this.history.shift();
+			this.historyStart++;
+		}
+	}
+
+    start (
+        code: string,
+        keymap: KeyMap, 
+        onLoad: (startFrame: Frame) => boolean,
+        onFrame: (data: Frame, frame: number) => void,
+        onLogic: (pastData: GameState, input: Input, frame: number) => GameState, 
+        data: PlayerInput = { start: false, key: Key.NOTHING }
+    ): void {
+        
+	    const fps = 60;
+	    let delay = 3;
+
+        this.advance = onLogic
+
+        const onStart = (
+            startFrame: number, 
+            latency: number,
+            _connection: number,
+            update: (input: PlayerInput, frame: number) => void, 
+            _ping: () => Promise<number>, 
+            _desyncCheck: (frame: number) => Promise<boolean>,
+        ) => { 
+		    console.log("started game at frame", startFrame);
+		    // window.desyncCheck = () => desyncCheck(this.currentFrame - 5);
+            
+		    let startTs = performance.now() - latency;
+		    let lastFrame = startFrame;
+		    update(data, startFrame + 1);
+
+            let getInput = startInputListener(keymap)
+            
+            const startData = this.getHistory(startFrame)
+
+            if (!onLoad(startData)) return false
+
+		    let lastTs = performance.now();
+            
+            let loop = (ts: number) => {
+                
+			    const frame = Math.floor((ts - startTs) / 1000 * fps) + startFrame;
+
+			    if(frame !== lastFrame) { // update input once per frame, regardless of the display refresh rate
+			    	lastFrame = frame;
+			    	
+			    	// gather input
+			    	const input: PlayerInput = getInput();
+			    	
+			    	// apply input
+			    	update(input, frame + delay);
+			    }
+
+                this.currentFrame = frame
+                const data = this.getHistory(frame)
+
+                onFrame(data, frame)
+
+                lastTs = ts
+
+                requestAnimationFrame(loop)
+            }
+
+            requestAnimationFrame(loop)
+
+		    if(startFrame === -1) {
+			    update(data, 0);
+		    }
+
+            return true
+        }
+
+        multiplayer(this, code, onStart)
+
+    }
+}
diff --git a/client/src/net/input.ts b/client/src/net/input.ts
new file mode 100644
index 0000000..75be3e6
--- /dev/null
+++ b/client/src/net/input.ts
@@ -0,0 +1,70 @@
+import { Key, KeyMap, PlayerInput } from "../types.js"
+
+let pressed = {}
+
+const updateRecent = (keymap: KeyMap) => {
+    let max = -1
+    let key = undefined
+    for (let code in pressed) {
+        let weight = pressed[code]
+        if (weight < max) continue
+        max = weight
+        key = keymap[code]
+    }
+
+    return key
+}
+
+export const startInputListener = (keymap: KeyMap): () => PlayerInput => {
+	let key: Key = Key.NOTHING;
+	let start = false;
+	
+    document.getElementById("start").onclick = function() {
+        start = true
+    }
+
+	window.addEventListener("keydown", ev => {
+		if(ev.repeat) {
+			return;
+		}
+		if(!(ev.code in keymap)) {
+			return;
+		}
+		pressed[ev.code] = Object.keys(pressed).length
+        key = updateRecent(keymap)
+	});
+
+    window.addEventListener("keyup", ev => {
+        if (ev.repeat) {
+            return;
+        }
+        if (!(ev.code in keymap)) {
+            return
+        }
+        delete pressed[ev.code]
+        key = updateRecent(keymap)
+    })
+
+	let last = {
+		key: Key.NOTHING,
+	}
+	
+	return (): PlayerInput => {
+
+		if(key === last.key && !start) {
+			return;
+		}
+
+		last = {
+			key,
+		};
+
+		let s = start;
+		start = false;
+
+		return {
+            key,
+			start: s,
+		}
+	}
+}
diff --git a/client/src/net/multiplayer.ts b/client/src/net/multiplayer.ts
new file mode 100644
index 0000000..e9f3057
--- /dev/null
+++ b/client/src/net/multiplayer.ts
@@ -0,0 +1,303 @@
+/**
+ * @author tint
+ */
+
+import { GameState, Message, PlayerInput } from "../types.js";
+import { Game } from "./game";
+
+export function multiplayer(
+    game: Game, 
+    code: string, 
+    onStart: (
+        startFrame: number,
+        latency: number,
+        connection: number,
+        update: (input: PlayerInput, frame: number) => void,
+        ping: () => Promise<number>,
+        desyncCheck: (frame: number) => Promise<boolean>,
+    ) => boolean
+) {
+	const url = new URL("api/join/" + encodeURIComponent(code), window.location.toString());
+	url.protocol = url.protocol.replace("http", "ws");
+	
+	const socket = new WebSocket(url);
+	
+	let requestStateTime: number;
+	let hasState = false;
+	let connectionId: number;
+	let cachedInputs = [];
+	let connections = [];
+	
+	let pingPromise: (type: Promise<number>) => void;
+	
+	function send(obj: any) {
+		socket.send(JSON.stringify(obj));
+	}
+	
+	function applyInput(input: Message) {
+		let prev = game.getHistory(input.frame);
+		let newInput = prev && prev.input ? {...prev.input} : { players: {} };
+		
+		if(input.type === "input") {
+			if(input.connection === undefined) { // local input
+				if(input.data) {
+					// send it to the server
+					send(input);
+					
+					// then apply it
+					newInput.players[connectionId] = input.data;
+				}
+			} else {
+				newInput.players[input.connection] = input.data;
+			}
+		} else if(input.type === "connections") {
+			if(input.added !== null) {
+				newInput.added = (newInput.added || []).concat([input.added]);
+			}
+			if(input.removed !== null) {
+				if(newInput.added) {
+					newInput.added = newInput.added.filter(n => n !== input.removed);
+				}
+				newInput.removed = (newInput.removed || []).concat([input.removed]);
+			}
+		}
+		game.setInput(input.frame, newInput);
+	}
+	
+	function flushCachedInputs(latency = 0): boolean {
+		for(const input of cachedInputs) {
+			// only care about inputs after the new state
+			if(input.frame <= game.historyStart) {
+				continue;
+			}
+			
+			applyInput(input);
+		}
+		cachedInputs = [];
+		return onStart(game.getFrame(), latency, connectionId, update, ping, desyncCheck);
+	}
+	
+	function update(input: PlayerInput, frame: number) {
+		if(input === undefined) { // used to update the game locally
+			if(hasState) {
+				applyInput({})
+			}
+			return;
+		}
+
+		const data = {
+			type: "input",
+			data: input,
+			frame: frame,
+		};
+		
+		if(!hasState) {
+			cachedInputs.push(data);
+		} else {
+			applyInput(data);
+		}
+	}
+	
+	async function ping() {
+		send({
+			type: "ping",
+			frame: Math.max(0, game.currentFrame),
+		});
+		const frame: number = await new Promise(r => pingPromise = r);
+		return game.currentFrame - frame;
+	}
+	
+	async function desyncCheck(frame: number): Promise<boolean> {
+		const history = game.getHistory(frame);
+		if(!history) {
+			console.error("tried to check for desyncs on a frame not in memory", frame);
+			return true;
+		}
+		// const localstate = history.data;
+		const proms = connections
+			.filter(n => n !== connectionId)
+			.map(connection => {
+				send({
+					type: "requeststate",
+					frame,
+					connection,
+				});
+				return new Promise(r => {
+					stateRequests[frame + "," + connection] = (state: GameState) => {
+						r({
+							state,
+							connection,
+						});
+					}
+				});
+			});
+		
+		if(!proms.length) {
+			return false; // this is the only connection, no check necessary
+		}
+		// const states = await Promise.all(proms);
+		// if(!states.every(({ state }) => objeq(localstate, state))) {
+		// 	console.error("desync! remote states:", states, "local state:", localstate);
+		// 	return true;
+		// }
+		return false;
+	}
+	
+	let stateRequests = {};
+	
+	socket.onmessage = message => {
+		const data = JSON.parse(message.data.toString());
+		
+		switch(data.type) {
+			case "error":
+				console.error(data);
+				break;
+			case "framerequest":
+				send({
+					type: "frame",
+					frame: Math.max(game.currentFrame, 1),
+				});
+				break;
+			case "state":
+				if(data.frame + "," + data.connection in stateRequests) {
+					stateRequests[data.frame + "," + data.connection](data.state);
+				}
+				if(!hasState) {
+					game.startHistory(data.frame, data.state);
+					hasState = true;
+					
+					// this state is from the past
+					// i want to find out exactly how far in the past
+					// the sequence of requests looks like:
+					// client -[staterequest]-> server -[staterequest]-> client2
+					// client2 -[state]-> server -[state]-> client
+					// and the time i'm concerned with is the second half,
+					// how long it takes the state to come from client2
+					let delta = 0;
+					if(requestStateTime !== undefined) {
+						delta = performance.now() - requestStateTime;
+					}
+					if (!flushCachedInputs(delta / 2)) {
+                        socket.close()
+                        document.getElementById("lobby").style.display = "none"
+                        document.getElementById("join").style.display = ""
+                        return
+                    }
+				}
+				break;
+			case "requeststate":
+				// wait until there's some state to send
+				const startTime = performance.now();
+				const check = () => {
+					if(performance.now() - startTime > 5000) {
+						return; // give up after 5s
+					}
+					const state = game.getHistory(data.frame);
+					if(!state) {
+						return;
+					}
+					
+					send({
+						type: "state",
+						frame: data.frame,
+						state: state.data,
+					});
+					clearInterval(interval);
+				}
+				const interval = setInterval(check, 100);
+				check();
+				break;
+			case "connections":
+				connections = data.connections;
+				if(connectionId === undefined) {
+					console.log("setting connection id", data.id);
+					connectionId = data.id;
+					if(data.connections.length === 1) { // no need to request state
+						hasState = true;
+						applyInput(data);
+						flushCachedInputs(); // just in case, also it calls onStart
+						break;
+					}
+					
+					// grab the state from another client
+					console.log("requesting state");
+					// measure the time it takes for state to be delivered
+					requestStateTime = performance.now();
+					send({
+						type: "requeststate",
+						frame: data.frame,
+					});
+				}
+				
+				if(!hasState) {
+					cachedInputs.push(data);
+				} else {
+					applyInput(data);
+				}
+				
+				break;
+			case "input":
+				if(!hasState) {
+					cachedInputs.push(data);
+				} else {
+					applyInput(data);
+				}
+				break;
+			case "pong":
+				if(pingPromise) {
+					pingPromise(data.frame);
+					pingPromise = undefined;
+				}
+				break;
+			default:
+				console.warn("unknown server message", data);
+				break;
+		}
+	}
+}
+
+// compare two plain objects (things that can be JSON.stringified)
+function objeq(a: any, b: any) {
+	if(typeof(a) !== typeof(b)) {
+		return false;
+	}
+	// array diff
+	if(Array.isArray(a) && Array.isArray(b)) {
+		if(a.length !== b.length) {
+			return false;
+		}
+		for(let i = 0; i < a.length; i++) {
+			if(!objeq(a[i], b[i])) {
+				return false;
+			}
+		}
+		return true;
+	}
+	switch(typeof(a)) {
+		// primitives can be compared directly
+		case "number":
+		case "boolean":
+		case "string":
+		case "undefined": return a === b;
+		
+		case "object":
+			// typeof(null) = "object" but null can be compared directly
+			if(a === null || b === null) {
+				return a === b;
+			}
+			// object diff
+			for(let k in a) {
+				if(!(k in b) || !objeq(a[k], b[k])) {
+					return false;
+				}
+			}
+			for(let k in b) {
+				if(!(k in a)) {
+					return false;
+				}
+			}
+			return true;
+		default: // incomparable things
+			return false;
+	}
+}