Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (562)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Client side prediction and delayed interpolation  (Read 5789 times)
0 Members and 1 Guest are viewing this topic.
Offline tom
« Posted 2012-01-04 12:19:12 »

Here is a test application I wrote to test out client side prediction and world interpolation for networked games.

It simulates a client and a server. Each with their own game loop in separate threads. The socket connection is emulated by putting the messages in a delayed fifo queue.

The client side prediction works roughly as this:
1) the client sends timestamped input to the server at 60z
2) the server runs at 10hz. Each tick it applies all the input since last tick and sends a timestamped state back. In a real game it would send this to all clients. It uses a time delta calculated from the client side input packets. This can be used to cheat. The timestamp sent back is that of the last input.
3) when the client receives a timed state from the server it will rewind its state to that time. If the rewinded state don't match roughly with what sent from the server it will use the server state at that time and re-apply all the inputs.

You control the player with the arrow keys. The player is rendered as 4 dots:
-The black is the clients predicted position
-The blue is the most recent position as seen by the server
-The red is the most recent position as seen by another client
-The green is the interpolated position as seen by another client

The black line on the right is a wall that is only enforced by the server. It is there to check that the client respects the authority of the server.

Some limitations of this code:
-The server trusts the timestamp of the client. It needs to performs some checks so the client don't cheat by speeding the time up or down.
-The predicted state snaps when client state don't match server. There should be some easing in.
-No bullets. The server should maybe have "headshot" correction. Rewinding the target to the time of the shooter before doing the intersection test.
-The interpolation could have better time adjustement

Hope this will be helpful for people that want to write networked games. I find it easier to start with a stripped down example like this than to add this functionality directly in an existing code base.

Any comments are appreciated.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
239  
240  
241  
242  
243  
244  
245  
246  
247  
248  
249  
250  
251  
252  
253  
254  
255  
256  
257  
258  
259  
260  
261  
262  
263  
264  
265  
266  
267  
268  
269  
270  
271  
272  
273  
274  
275  
276  
277  
278  
279  
280  
281  
282  
283  
284  
285  
286  
287  
288  
289  
290  
291  
292  
293  
294  
295  
296  
297  
298  
299  
300  
301  
302  
303  
304  
305  
306  
307  
308  
309  
310  
311  
312  
313  
314  
315  
316  
317  
318  
319  
320  
321  
322  
323  
324  
325  
326  
327  
328  
329  
330  
331  
332  
333  
334  
335  
336  
337  
338  
339  
340  
341  
342  
343  
344  
345  
346  
347  
348  
349  
350  
351  
352  
353  
354  
355  
356  
357  
358  
359  
360  
361  
362  
363  
364  
365  
366  
367  
368  
369  
370  
371  
372  
373  
374  
375  
376  
377  
378  
379  
380  
import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import javax.swing.JComponent;
import javax.swing.JFrame;

/**
 * Tests client side prediction by emulating client/server with delayed packages.
 */

public class PredictTest extends JComponent {

    static final float TRESHOLD = 0.2f;
    static final boolean[] keyState = new boolean[0xffff];
    static Server server = new Server();
    static Client client = new Client();
    static JComponent renderer = new JComponent() {

        @Override
        public void paintComponent(Graphics g) {
            g.setColor(Color.WHITE);
            g.fillRect(0, 0, getWidth(), getHeight());
            drawPlayer(g, server.currentState.state, Color.BLUE.darker());
            drawPlayer(g, client.interpolatedState.newestState.state, Color.RED.darker());
            drawPlayer(g, client.interpolatedState.currentState.state, Color.GREEN.darker());
            drawPlayer(g, client.predictedState.currentState.state, Color.BLACK);
            g.drawLine(400, 0, 400, getHeight());
        }

        void drawPlayer(Graphics g, State state, Color color) {
            g.setColor(color);
            g.fillOval((int) state.x - 10, (int) state.y - 10, 20, 20);
        }
    };

    public static void main(String[] args) {
        renderer.addKeyListener(new KeyAdapter() {

            @Override
            public void keyPressed(KeyEvent e) {
                keyState[e.getKeyCode()] = true;
            }

            @Override
            public void keyReleased(KeyEvent e) {
                keyState[e.getKeyCode()] = false;
            }
        });

        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setBounds(100, 100, 640, 480);
        frame.add(renderer);
        frame.setVisible(true);

        renderer.requestFocusInWindow();

        new Thread(new Runnable() {

            public void run() {
                server.gameLoop();
            }
        }).start();
        client.gameLoop(server);
    }

    static void sleep(long millis) {
        try {
            Thread.sleep(millis);
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    /** Updates state using input to the specified time */
    static TimedState updateState(TimedState state, TimedInput timedInput, boolean doCollisions) {
        long timeDeltaMillis = timedInput.time - state.time;
        float x = state.state.x + timedInput.input.vx * timeDeltaMillis / 1000f;
        float y = state.state.y + timedInput.input.vy * timeDeltaMillis / 1000f;
        // do only on server
       if (doCollisions) {
            x = Math.min(400, x);
        }
        TimedState newState = new TimedState(timedInput.time, new State(x, y));
        return newState;
    }


    static class Client {
        PredictedState predictedState = new PredictedState(new TimedState(0, new State(0, 0)));
        InterpolatedState interpolatedState = new InterpolatedState();

        void gameLoop(Server server) {
            predictedState = new PredictedState(new TimedState(System.currentTimeMillis(), server.currentState.state));
            while (true) {
                float dx = (keyState[KeyEvent.VK_LEFT] ? -150 : 0) + (keyState[KeyEvent.VK_RIGHT] ? 150 : 0);
                float dy = (keyState[KeyEvent.VK_UP] ? -150 : 0) + (keyState[KeyEvent.VK_DOWN] ? 150 : 0);
                long now = System.currentTimeMillis();
                TimedInput timedInput = new TimedInput(now, new Input(dx, dy));
                server.in.add(timedInput);
                TimedState timedStateFromServer = server.out.remove();
                predictedState.update(timedInput, timedStateFromServer);
                interpolatedState.update(now, timedStateFromServer);
                renderer.repaint();
                sleep(16);
            }
        }
    }


    static class Server {
        DelayedFifo<TimedInput> in = new DelayedFifo();
        DelayedFifo<TimedState> out = new DelayedFifo();

        TimedState currentState;

        Server() {
            currentState = new TimedState(0, new State(100, 100));
        }

        void gameLoop() {
            while (true) {
                tick();
                renderer.repaint();
                // run server at 10hz
               sleep(100);
            }
        }

        private void tick() {
            while (true) {
                TimedInput timedInput = in.remove();
                if (timedInput == null) {
                    break;
                }
                currentState = updateState(currentState, timedInput, true);
            }

            out.add(currentState);
        }
    }


    static class DelayedFifo<T> {
        List<TimedEntry> list = Collections.synchronizedList(new ArrayList());

        void add(final T object) {
            list.add(new TimedEntry(System.currentTimeMillis() + getDelay(), object));
        }

        T remove() {
            if (list.isEmpty()) {
                return null;
            }

            TimedEntry entry = list.get(0);
            if (System.currentTimeMillis() > entry.time) {
                return (T) list.remove(0).object;
            }
            return null;
        }

        private long getDelay() {
            return 300 + (int) (Math.random() * 100);
        }

        class TimedEntry {

            long time;
            Object object;

            TimedEntry(long time, Object object) {
                this.time = time;
                this.object = object;
            }
        }
    }
   

    static class Input {
        final float vx;
        final float vy;

        public Input(float vx, float vy) {
            this.vx = vx;
            this.vy = vy;
        }
    }
   

    static class State {
        final float x;
        final float y;

        public State(float x, float y) {
            this.x = x;
            this.y = y;
        }

        public float distance(State s) {
            float dx = s.x - x;
            float dy = s.y - y;
            return (float) Math.sqrt(dx*dx + dy*dy);
        }

        @Override
        public String toString() {
            return "State("+x+","+y+")";
        }
    }
   

    static class TimedState {
        final long time;
        final State state;

        public TimedState(long time, State state) {
            this.time = time;
            this.state = state;
        }

        @Override
        public String toString() {
            return "TimedState(" + time + "," + state.toString() + ")";
        }
    }


    static class TimedInput {

        final long time;
        final Input input;

        public TimedInput(long time, Input input) {
            this.time = time;
            this.input = input;
        }
    }

   
    static class PredictedState {
        InputAndStateList moveList = new InputAndStateList();
        TimedState currentState;

        PredictedState(TimedState startState) {
            this.currentState = startState;
        }

        void update(TimedInput timedInput, TimedState correctState) {
            currentState = updateState(currentState, timedInput, false);
            InputAndState move = new InputAndState(timedInput.input, currentState);
            moveList.add(move);
            currentState = moveList.correct(currentState, correctState);
        }
    }


    static class InputAndState {
        final Input input;
        final TimedState timedState;

        public InputAndState(Input input, TimedState timedState) {
            this.input = input;
            this.timedState = timedState;
        }

        TimedInput getTimedInput() {
            return new TimedInput(timedState.time, input);
        }
    }


    static class InputAndStateList {
        List<InputAndState> list = new ArrayList();

        void add(InputAndState move) {
            list.add(move);
        }

        TimedState correct(TimedState currentState, TimedState serverState) {
            if (serverState != null) {
                removeBefore(serverState.time);
                if (!isOldestWithinThresholdTo(serverState.state)) {
                    System.out.println("perform correction " + list.get(0).timedState + " != " + serverState);
                    return update(serverState);
                }
            }
            return currentState;
        }

        private void removeBefore(long time) {
            while (list.size() > 0 && list.get(0).timedState.time < time) {
                list.remove(0);
            }
        }

        private boolean isOldestWithinThresholdTo(State state) {
            return (list.size() > 0 && list.get(0).timedState.state.distance(state) <= TRESHOLD);
        }

        private TimedState update(TimedState currentState) {
            for (InputAndState oldMove : list) {
                currentState = updateState(currentState, oldMove.getTimedInput(), false);
            }
            return currentState;
        }
    }


    static class InterpolatedState {
        List<TimedState> timedStateList = new ArrayList();
        long prevStateTime = 0;
        TimedState prevState = new TimedState(0, new State(0, 0));
        long newestStateTime = 0;
        TimedState newestState = new TimedState(0, new State(0, 0));
        TimedState currentState = new TimedState(0, new State(0, 0));
        long currentTime = 0;
        long prevTime = 0;
        float averageTimeBetweenPackets = 150;
        long timeCorrection = 0;
        float averageJitter = 50;

        void update(long now, TimedState timedState) {
            long delta = now - prevTime;
            prevTime = now;
           
            if (timedState != null) {
                timedStateList.add(timedState);
                prevState = newestState;
                prevStateTime = newestStateTime;
                newestState = timedState;
                newestStateTime = now;

                if (prevState.time != 0 && newestState.time != 0) {
                    if (currentTime == 0) {
                        currentTime = newestState.time;
                    }
                    if (Math.abs(newestState.time - prevState.time) < 1000) {
                        float timeBetweenPackets = newestState.time - prevState.time;
                        averageTimeBetweenPackets += (timeBetweenPackets - averageTimeBetweenPackets) * 0.1f;

                        long recieveDelta = newestStateTime - prevStateTime;
                        long sendDelta = newestState.time - prevState.time;
                        long jitter = recieveDelta - sendDelta;
                        averageJitter += (jitter - averageJitter) * 0.1f;

                        long currentTimeBehindNewestState = newestState.time - currentTime;
                        long targetTimeBehindNewestState = (long) (averageTimeBetweenPackets + averageJitter * 2);
                        timeCorrection = targetTimeBehindNewestState - currentTimeBehindNewestState;
                    }
                }
            }

            long correction = 0;
            if (Math.abs(timeCorrection) > 0) {
                correction = timeCorrection / Math.abs(timeCorrection);
            }
            timeCorrection -= correction;
            currentTime += (delta - correction);
            if (timedStateList.size() >= 2) {
                currentTime = Math.min(timedStateList.get(timedStateList.size() - 1).time, currentTime);
                currentTime = Math.max(timedStateList.get(timedStateList.size() - 1).time - 500, currentTime);

                while (timedStateList.size() >= 2 && timedStateList.get(1).time < currentTime) {
                    timedStateList.remove(0);
                }
                TimedState s1 = timedStateList.get(0);
                TimedState s2 = timedStateList.get(1);
                float t = (currentTime - s1.time) / (float) (s2.time - s1.time);
                currentState = new TimedState(currentTime, new State(
                        s1.state.x + t * (s2.state.x - s1.state.x),
                        s1.state.y + t * (s2.state.y - s1.state.y)
                        ));
            }
        }
    }
}

Offline theagentd
« Reply #1 - Posted 2012-01-04 12:57:04 »

I didn't read through all the code you posted, but remember that the clocks will not be synchronized with millisecond precision between two computers. I don't know if this breaks anything, but you might want to take this into consideration...

Myomyomyo.
Offline teletubo
« League of Dukes »

JGO Ninja


Medals: 48
Projects: 4
Exp: 8 years



« Reply #2 - Posted 2012-01-04 13:28:54 »

I didn't read through all the code you posted, but remember that the clocks will not be synchronized with millisecond precision between two computers. I don't know if this breaks anything, but you might want to take this into consideration...

Yes, they will not be synchronized. And this breaks lots of things, since the code relies on this.

The way I use to calculate delay is to ping the client every N seconds, and the delay is responseTime/2. This is the delta I apply in every message from this specific client.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline tom
« Reply #3 - Posted 2012-01-04 14:17:17 »

I didn't read through all the code you posted, but remember that the clocks will not be synchronized with millisecond precision between two computers. I don't know if this breaks anything, but you might want to take this into consideration...

Yes, they will not be synchronized. And this breaks lots of things, since the code relies on this.

The way I use to calculate delay is to ping the client every N seconds, and the delay is responseTime/2. This is the delta I apply in every message from this specific client.

My code do not rely on any clock synchronization. The only time System.currentTimeMillis() is used is is on the client when reading the input. From that point on the time stored with the input is used. Both on the server and other clients. As mentioned this can be used to cheat and the server should check for this. However it does not break anything.

Offline lesto

Senior Newbie





« Reply #4 - Posted 2012-02-04 20:29:01 »

i have some question:

1.
Quote
-The red is the most recent position as seen by another client
-The green is the interpolated position as seen by another client
seems like your interpolation is working backward?  Grin

2. you are calculating only the jitter only from server to others client. maybe you should use all the jitter, and also add the jitter from the "action" client to server. I say maybe because if i change something seems like the point 12 is breaking somethings
Offline tom
« Reply #5 - Posted 2012-02-05 00:37:56 »

1.
Quote
-The red is the most recent position as seen by another client
-The green is the interpolated position as seen by another client
seems like your interpolation is working backward?  Grin

What do you mean?

2. you are calculating only the jitter only from server to others client. maybe you should use all the jitter, and also add the jitter from the "action" client to server. I say maybe because if i change something seems like the point 12 is breaking somethings
It calculates the jitter between the sending client and the receiving client. The server does not mater since the receiving client uses the sending clients timestamps.

Offline tom
« Reply #6 - Posted 2012-02-05 13:58:14 »

This is a version with two clients. One is controlled by the keyboard the other moves back and forth by an "AI". The space key shoots an instant hit bullet. The server resolves the hit, and it is a hit if the shooting client saw it as a hit. This is visualized. So the server rewinds the targets to the time seen by the shooter. This i is kind of a hack here since the shooter sends the time of targets as it saw it. A real game will probably have to do it differently but principle should be the same.

Btw, you should aim at the green dot.
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
193  
194  
195  
196  
197  
198  
199  
200  
201  
202  
203  
204  
205  
206  
207  
208  
209  
210  
211  
212  
213  
214  
215  
216  
217  
218  
219  
220  
221  
222  
223  
224  
225  
226  
227  
228  
229  
230  
231  
232  
233  
234  
235  
236  
237  
238  
239  
240  
241  
242  
243  
244  
245  
246  
247  
248  
249  
250  
251  
252  
253  
254  
255  
256  
257  
258  
259  
260  
261  
262  
263  
264  
265  
266  
267  
268  
269  
270  
271  
272  
273  
274  
275  
276  
277  
278  
279  
280  
281  
282  
283  
284  
285  
286  
287  
288  
289  
290  
291  
292  
293  
294  
295  
296  
297  
298  
299  
300  
301  
302  
303  
304  
305  
306  
307  
308  
309  
310  
311  
312  
313  
314  
315  
316  
317  
318  
319  
320  
321  
322  
323  
324  
325  
326  
327  
328  
329  
330  
331  
332  
333  
334  
335  
336  
337  
338  
339  
340  
341  
342  
343  
344  
345  
346  
347  
348  
349  
350  
351  
352  
353  
354  
355  
356  
357  
358  
359  
360  
361  
362  
363  
364  
365  
366  
367  
368  
369  
370  
371  
372  
373  
374  
375  
376  
377  
378  
379  
380  
381  
382  
383  
384  
385  
386  
387  
388  
389  
390  
391  
392  
393  
394  
395  
396  
397  
398  
399  
400  
401  
402  
403  
404  
405  
406  
407  
408  
409  
410  
411  
412  
413  
414  
415  
416  
417  
418  
419  
420  
421  
422  
423  
424  
425  
426  
427  
428  
429  
430  
431  
432  
433  
434  
435  
436  
437  
438  
439  
440  
441  
442  
443  
444  
445  
446  
447  
448  
449  
450  
451  
452  
453  
454  
455  
456  
457  
458  
459  
460  
461  
462  
463  
464  
465  
466  
467  
468  
469  
470  
471  
472  
473  
474  
475  
476  
477  
478  
479  
480  
481  
482  
483  
484  
485  
486  
487  
488  
489  
490  
491  
492  
493  
494  
495  
496  
497  
498  
499  
500  
501  
502  
503  
504  
505  
506  
507  
508  
509  
510  
511  
512  
513  
514  
import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.KeyAdapter;
import java.awt.event.KeyEvent;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import javax.swing.JComponent;
import javax.swing.JFrame;

/**
 * Tests client side prediction by emulating client/server with delayed packages.
 */

public class PredictTest extends JComponent {

    static final float TRESHOLD = 0.2f;
    static final int RADIUS = 10;
    static final boolean[] keyState = new boolean[0xffff];
    static final Client[] clients = {new Client(0) , new Client(1)};
    static final Server server = new Server(clients);
    static boolean aiGoingLeft = false;
    static State shooterState = new State(0, 0);
    static State targetState = new State(0, 0);
    static final JComponent renderer = new JComponent() {

        @Override
        public void paintComponent(Graphics g) {
            g.setColor(Color.WHITE);
            g.fillRect(0, 0, getWidth(), getHeight());
            drawPlayer(g, shooterState, Color.CYAN);
            drawPlayer(g, targetState, Color.CYAN);
            for (int i=0; i<clients.length; i++) {
                Client client = clients[i];
                drawPlayer(g, server.currentState[i].newest().state, Color.BLUE.darker());
                drawPlayer(g, server.shooterState, Color.PINK);
                drawPlayer(g, server.targetState, Color.PINK);
                g.drawLine((int)server.shooterState.x, (int)server.shooterState.y
                        , (int)server.shooterState.x, (int)server.targetState.y);
                drawPlayer(g, client.interpolatedState[i].newestState.state, Color.RED.darker());
                drawPlayer(g, client.interpolatedState[i].currentState.state, Color.GREEN.darker());
                drawPlayer(g, client.predictedState.currentState.state, Color.BLACK);
            }
            g.drawLine(400, 0, 400, getHeight());
        }

        void drawPlayer(Graphics g, State state, Color color) {
            g.setColor(color);
            g.fillOval((int) state.x - RADIUS, (int) state.y - RADIUS, RADIUS * 2, RADIUS * 2);
        }
    };

    public static void main(String[] args) {
        renderer.addKeyListener(new KeyAdapter() {

            @Override
            public void keyPressed(KeyEvent e) {
                keyState[e.getKeyCode()] = true;
            }

            @Override
            public void keyReleased(KeyEvent e) {
                keyState[e.getKeyCode()] = false;
            }
        });

        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setBounds(100, 100, 640, 480);
        frame.add(renderer);
        frame.setVisible(true);

        renderer.requestFocusInWindow();

        for (final Client client : clients) {
            new Thread(new Runnable() {
                public void run() {
                    client.gameLoop(server);
                }
            }).start();
        }
        server.gameLoop();
    }

    static Input getInput(Client client) {
        if (client == clients[0]) {
            float dx = (keyState[KeyEvent.VK_LEFT] ? -150 : 0) + (keyState[KeyEvent.VK_RIGHT] ? 150 : 0);
            float dy = (keyState[KeyEvent.VK_UP] ? -150 : 0) + (keyState[KeyEvent.VK_DOWN] ? 150 : 0);
            boolean fire = keyState[KeyEvent.VK_SPACE];
            keyState[KeyEvent.VK_SPACE] = false;
            return new Input(dx, dy, fire);
        }

        if (aiGoingLeft && (clients[1].predictedState.currentState.state.x < 50)
                || !aiGoingLeft && (clients[1].predictedState.currentState.state.x > 350)) {
            aiGoingLeft = !aiGoingLeft;
        }
        return new Input(aiGoingLeft ? -150 : 150, 0, false);
    }

    static void sleep(long millis) {
        try {
            Thread.sleep(millis);
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    /** Updates state using input to the specified time */
    static TimedState updateState(TimedState state, TimedInput timedInput, boolean doCollisions) {
        long timeDeltaMillis = timedInput.time - state.time;
        float x = state.state.x + timedInput.input.vx * timeDeltaMillis / 1000f;
        float y = state.state.y + timedInput.input.vy * timeDeltaMillis / 1000f;
        // do only on server
       if (doCollisions) {
            x = Math.min(400, x);
        }
        TimedState newState = new TimedState(timedInput.time, new State(x, y));
        return newState;
    }


    static class Client {
        private final int index;
        PredictedState predictedState = new PredictedState(new TimedState(System.currentTimeMillis(), new State(100, 100)));
        InterpolatedState[] interpolatedState = {new InterpolatedState(), new InterpolatedState()};
        DelayedFifo<TimedState[]> in = new DelayedFifo();
        DelayedFifo<PacketToServer> out = new DelayedFifo();

        Client(int index) {
            this.index = index;
        }

        void gameLoop(Server server) {
            while (true) {
                long now = System.currentTimeMillis();
                TimedInput timedInput = new TimedInput(now, getInput(this));
                TimedState[] timedStateFromServer = in.remove();
                timedStateFromServer = timedStateFromServer != null ? timedStateFromServer : new TimedState[2];
                predictedState.update(timedInput, timedStateFromServer[index]);
                for (int i = 0; i < interpolatedState.length; i++) {
                    interpolatedState[i].update(now, timedStateFromServer[i]);
                }
                out.add(new PacketToServer(timedInput, interpolatedState[0].currentTime, interpolatedState[1].currentTime));
                if (timedInput.input.fire) {
                    shooterState = clients[0].predictedState.currentState.state;
                    targetState = clients[0].interpolatedState[1].currentState.state;
                }

                renderer.repaint();
                sleep(16);
            }
        }
    }


    static class PacketToServer {
        TimedInput timedInput;
        // as seen by the sending client
       long[] clientTimes;

        PacketToServer(TimedInput timedInput, long... clientTimes) {
            this.timedInput = timedInput;
            this.clientTimes = clientTimes;
        }
    }


    static class Server {

        final Client[] clients;
        final AnimatedState[] currentState;

        State shooterState = new State(0, 0);
        State targetState = new State(0, 0);

        Server(Client[] clients) {
            this.clients = clients;
            currentState = new AnimatedState[] {
                new AnimatedState(clients[0].predictedState.currentState),
                new AnimatedState(clients[1].predictedState.currentState),
            };            
        }

        void gameLoop() {
            while (true) {
                tick();
                renderer.repaint();
                // run server at 10hz
               sleep(100);
            }
        }

        private void tick() {
            for (int clientIdx=0; clientIdx<clients.length; clientIdx++) {
                while (true) {
                    PacketToServer toServer = clients[clientIdx].out.remove();
                    if (toServer == null) {
                        break;
                    }

                    TimedState newState = updateState(currentState[clientIdx].newest(), toServer.timedInput, true);
                    currentState[clientIdx].add(newState);
                    currentState[clientIdx].removeOlderThan(newState.time-1000);
                    if (toServer.timedInput.input.fire) {
                        for (int targetIdx = 0; targetIdx < clients.length; targetIdx++) {
                            if (targetIdx != clientIdx) {
                                headShot(clientIdx, targetIdx, toServer.clientTimes);
                            }
                        }
                    }
                }
            }
            TimedState[] toClient = new TimedState[currentState.length];
            for (int i=0; i<toClient.length; i++) {
                toClient[i] = currentState[i].newest();
            };
            for (int i = 0; i < clients.length; i++) {
                clients[i].in.add(toClient.clone());
            }
        }


        void headShot(int shooterIdx, int targetIdx, long[] clientTimes) {
            shooterState = currentState[shooterIdx].newest().state;
            targetState = getClientStateAtTime(targetIdx, clientTimes[targetIdx]);
            if (Math.abs(targetState.x - shooterState.x) < RADIUS) {
                System.out.println("HIT");
            }
        }

        State getClientStateAtTime(int targetIdx, long time) {
            TimedState targetTimedState = currentState[targetIdx].interpolate(time);
            System.out.println("timeDelta at bullet check " + (targetTimedState.time - time));
            return targetTimedState.state;
        }
    }


    static class AnimatedState {

        List<TimedState> timedStateList = new ArrayList();

        AnimatedState() {}

        AnimatedState(TimedState initialState) {
            add(initialState);
        }

        public int size() {
            return timedStateList.size();
        }

        boolean isEmpty() {
            return timedStateList.isEmpty();
        }

        void add(TimedState state) {
            timedStateList.add(state);
        }

        void removeOlderThan(long oldestTime) {
            while (timedStateList.get(0).time < oldestTime) {
                timedStateList.remove(0);
            }
        }

        TimedState newest() {
            return timedStateList.get(timedStateList.size()-1);
        }

        TimedState interpolate(long time) {
            if (timedStateList.isEmpty()) {
                return new TimedState(time, new State(0, 0));
            }

            int i=0;
            while (i<timedStateList.size()) {
                if (time < timedStateList.get(i).time) {
                    break;
                }
                i++;
            }
            int i1 = Math.max(i-1, 0);
            int i2 = Math.min(i, timedStateList.size()-1);
            TimedState s1 = timedStateList.get(i1);
            TimedState s2 = timedStateList.get(i2);
            if (s1.time == s2.time) {
                return new TimedState(time, s2.state);
            }
            float t = (time - s1.time) / (float) (s2.time - s1.time);
            return new TimedState(time, s1.state.interpolate(t, s2.state));
        }
    }

    static class DelayedFifo<T> {
        List<TimedEntry> list = Collections.synchronizedList(new ArrayList());

        void add(final T object) {
            list.add(new TimedEntry(System.currentTimeMillis() + getDelay(), object));
        }

        T remove() {
            if (list.isEmpty()) {
                return null;
            }

            TimedEntry entry = list.get(0);
            if (System.currentTimeMillis() > entry.time) {
                return (T) list.remove(0).object;
            }
            return null;
        }

        private long getDelay() {
            return 300 + (int) (Math.random() * 100);
        }

        class TimedEntry {

            long time;
            Object object;

            TimedEntry(long time, Object object) {
                this.time = time;
                this.object = object;
            }
        }
    }
   
    static class Input {
        final float vx;
        final float vy;
        final boolean fire;

        Input(float vx, float vy, boolean fire) {
            this.vx = vx;
            this.vy = vy;
            this.fire = fire;
        }
    }
   

    static class State {
        final float x;
        final float y;

        State(float x, float y) {
            this.x = x;
            this.y = y;
        }

        float distance(State s) {
            float dx = s.x - x;
            float dy = s.y - y;
            return (float) Math.sqrt(dx*dx + dy*dy);
        }

        State interpolate(float t, State s2) {
            return new State(x + t * (s2.x - x), y + t * (s2.y - y));
        }
    }
   

    static class TimedState {
        final long time;
        final State state;

        TimedState(long time, State state) {
            this.time = time;
            this.state = state;
        }
    }


    static class TimedInput {

        final long time;
        final Input input;

        TimedInput(long time, Input input) {
            this.time = time;
            this.input = input;
        }
    }

   
    static class PredictedState {
        InputAndStateList moveList = new InputAndStateList();
        TimedState currentState;

        PredictedState(TimedState startState) {
            this.currentState = startState;
        }

        void update(TimedInput timedInput, TimedState correctState) {
            currentState = updateState(currentState, timedInput, false);
            InputAndState move = new InputAndState(timedInput.input, currentState);
            moveList.add(move);
            currentState = moveList.correct(currentState, correctState);
        }
    }


    static class InputAndState {
        final Input input;
        final TimedState timedState;

        public InputAndState(Input input, TimedState timedState) {
            this.input = input;
            this.timedState = timedState;
        }

        TimedInput getTimedInput() {
            return new TimedInput(timedState.time, input);
        }
    }


    static class InputAndStateList {
        List<InputAndState> list = new ArrayList();

        void add(InputAndState move) {
            list.add(move);
        }

        TimedState correct(TimedState currentState, TimedState serverState) {
            if (serverState != null) {
                removeBefore(serverState.time);
                if (!isOldestWithinThresholdTo(serverState.state)) {
                    System.out.println("perform correction " + list.get(0).timedState + " != " + serverState);
                    return update(serverState);
                }
            }
            return currentState;
        }

        private void removeBefore(long time) {
            while (list.size() > 0 && list.get(0).timedState.time < time) {
                list.remove(0);
            }
        }

        private boolean isOldestWithinThresholdTo(State state) {
            return (list.size() > 0 && list.get(0).timedState.state.distance(state) <= TRESHOLD);
        }

        private TimedState update(TimedState currentState) {
            for (InputAndState oldMove : list) {
                currentState = updateState(currentState, oldMove.getTimedInput(), false);
            }
            return currentState;
        }
    }


    static class InterpolatedState {
        AnimatedState animatedState = new AnimatedState();
        long prevStateTime = 0;
        TimedState prevState = new TimedState(0, new State(0, 0));
        long newestStateTime = 0;
        TimedState newestState = new TimedState(0, new State(0, 0));
        TimedState currentState = new TimedState(0, new State(0, 0));
        long currentTime = 0;
        long prevTime = 0;
        float averageTimeBetweenPackets = 150;
        long timeCorrection = 0;
        float averageJitter = 50;

        void update(long now, TimedState timedState) {
            long delta = now - prevTime;
            prevTime = now;
           
            if (timedState != null) {
                animatedState.add(timedState);
                prevState = newestState;
                prevStateTime = newestStateTime;
                newestState = timedState;
                newestStateTime = now;

                if (prevState.time != 0 && newestState.time != 0) {
                    if (currentTime == 0) {
                        currentTime = newestState.time;
                    }
                    if (Math.abs(newestState.time - prevState.time) < 1000) {
                        float timeBetweenPackets = newestState.time - prevState.time;
                        averageTimeBetweenPackets += (timeBetweenPackets - averageTimeBetweenPackets) * 0.1f;

                        long recieveDelta = newestStateTime - prevStateTime;
                        long sendDelta = newestState.time - prevState.time;
                        long jitter = recieveDelta - sendDelta;
                        averageJitter += (jitter - averageJitter) * 0.1f;

                        long currentTimeBehindNewestState = newestState.time - currentTime;
                        long targetTimeBehindNewestState = (long) (averageTimeBetweenPackets + averageJitter * 2);
                        timeCorrection = targetTimeBehindNewestState - currentTimeBehindNewestState;
                    }
                }
            }

            long correction = 0;
            if (Math.abs(timeCorrection) > 0) {
                correction = timeCorrection / Math.abs(timeCorrection);
            }
            timeCorrection -= correction;
            currentTime += (delta - correction);
            if (animatedState.size() > 0) {
                currentTime = Math.min(animatedState.newest().time, currentTime);
                currentTime = Math.max(animatedState.newest().time - 1000, currentTime);
                currentState = animatedState.interpolate(currentTime);
                animatedState.removeOlderThan(animatedState.newest().time - 1000);
            }
        }
    }
}

Offline lesto

Senior Newbie





« Reply #7 - Posted 2012-02-05 20:24:45 »

1.
Quote
-The red is the most recent position as seen by another client
-The green is the interpolated position as seen by another client
seems like your interpolation is working backward?  Grin

What do you mean?

green dot is always the last in my simulation to move, and remain the last dot. If it is the interpolate position, it should start to move together with red dot, but should come before red dot (near to real position of the "action" client)

I've done something really similar to your sistem, but based on the concept that other's client will keep moving like the last action.
So if you keep press "down" key, after some ms you will see red dot moving, and green dot "jump" in the actual real position(black dot). Obviously when you release the key, you will see green dot still move for some ms, and then fall back to real position.
Offline tom
« Reply #8 - Posted 2012-02-05 23:55:14 »

What you are doing is extrapolation. Have a look at Source Multiplayer Networking link someone posted on the prediction thread. The green dot is what is referred to as entity interpolation. Using only extrapolation may work in games where the trajectory of the object don't change much depending on the input. One example would be a flight simulator. However in a first person shooter game the player can change direction instantly. If you only use extrapolation then it would look like the player snaps around. Using interpolation it looks correct, only delayed.

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (25 views)
2014-09-21 02:42:18

BurntPizza (17 views)
2014-09-21 01:30:30

moogie (19 views)
2014-09-21 00:26:15

UprightPath (26 views)
2014-09-20 20:14:06

BurntPizza (29 views)
2014-09-19 03:14:18

Dwinin (44 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (100 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56

mitcheeb (71 views)
2014-09-08 06:06:29
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!