1 //#define BOOST_TEST_ALTERNATIVE_INIT_API
2 #define BOOST_TEST_MODULE LagDetector
3 #include <boost/test/unit_test.hpp>
4
5
6 #include "InputSource.h"
7 #include "LagDetectionSystem.h"
8 #include <boost/circular_buffer.hpp>
9 #include "CrossCorrelation.h"
10 #include <fstream>
11 #include <cmath>
12 #include <iostream>
13
14 #include <boost/accumulators/accumulators.hpp>
15 #include <boost/accumulators/statistics/stats.hpp>
16 #include <boost/accumulators/statistics/count.hpp>
17 #include <boost/accumulators/statistics/max.hpp>
18 #include <boost/accumulators/statistics/mean.hpp>
19 #include <boost/accumulators/statistics/variates/covariate.hpp>
20 using namespace boost::accumulators;
21
randomInputGen()22 PlayerInput randomInputGen()
23 {
24 return PlayerInput( rand() % 2, rand() % 2, rand() % 2);
25 }
26
randomInput(int p=1)27 PlayerInput randomInput(int p = 1)
28 {
29 static PlayerInput last = randomInputGen();
30 if(rand() % p == 0)
31 {
32 last = randomInputGen();
33 }
34 return last;
35 }
36
37 /// \todo add parameters: lag, packet loss, input randomness
38 struct LaggingNetworkInputSimulator
39 {
LaggingNetworkInputSimulatorLaggingNetworkInputSimulator40 LaggingNetworkInputSimulator(int p)
41 {
42 lag_simulator.resize(p + 1);
43 srand(5011);
44 }
45
sendInputLaggingNetworkInputSimulator46 void sendInput( PlayerInput ip)
47 {
48 lag_simulator.push_back(ip);
49 }
50
changePingLaggingNetworkInputSimulator51 void changePing(int p)
52 {
53 lag_simulator.set_capacity(p + 1);
54
55 // we must ensure that this is full, otherwise
56 // back and front do not work as expected?
57 while(!lag_simulator.full())
58 {
59 lag_simulator.push_front(getRemote());
60 }
61 }
62
getLocalLaggingNetworkInputSimulator63 PlayerInput getLocal() const
64 {
65 return lag_simulator.back();
66 }
67
getRemoteLaggingNetworkInputSimulator68 PlayerInput getRemote() const
69 {
70 return lag_simulator.front();
71 }
72
73 private:
74 boost::circular_buffer<PlayerInput> lag_simulator;
75 };
76
77 /// Fixture for creating a LagDetector
78 struct LagDetectionSetup
79 {
LagDetectionSetupLagDetectionSetup80 LagDetectionSetup() : D (LagDetector()), NetworkSimulator(LaggingNetworkInputSimulator( 0 ))
81 {
82 }
83
LagDetectionSetupLagDetectionSetup84 LagDetectionSetup(int l) : D (LagDetector()), NetworkSimulator(LaggingNetworkInputSimulator( l ))
85 {
86 }
87
88
~LagDetectionSetupLagDetectionSetup89 ~LagDetectionSetup() { };
90
91
reset_simulatorLagDetectionSetup92 void reset_simulator(int l)
93 {
94 *this = LagDetectionSetup(l);
95 }
96
simulateLagDetectionSetup97 void simulate( int steps = 1, int p = 1)
98 {
99 for(int i = 0; i < steps; ++i)
100 {
101 PlayerInput ip = randomInput(p);
102 NetworkSimulator.sendInput(ip);
103 D.insertData(NetworkSimulator.getLocal(), NetworkSimulator.getRemote());
104 }
105 }
106
107 LagDetector D;
108 LaggingNetworkInputSimulator NetworkSimulator;
109 };
110
111
112 // -------------------------------------------------------------------------------------------------
113 //
114 // T E S T S
115 //
116 // -------------------------------------------------------------------------------------------------
117
118 /// file which logs additional debug data
119 std::fstream file ("debug.txt", std::fstream::out);
120
121 /// file which logs quality data
122 std::fstream result ("results.txt", std::fstream::out);
123
124 /// how many steps do we simulate each test
125 const int SIMULATION_DURATION = 500;
126
127 /// \todo add a test which looks how good the algorithm performs on periodic data
128
129 BOOST_AUTO_TEST_SUITE( lag_detector )
130
131 // correlation
BOOST_AUTO_TEST_CASE(self_correlation)132 BOOST_AUTO_TEST_CASE( self_correlation )
133 {
134 boost::circular_buffer<PlayerInput> buf;
135 buf.resize(100);
136 // insert zero lag data
137 for(int i=0; i < 100; ++i)
138 {
139 PlayerInput ip = randomInput();
140 buf.push_back(ip);
141 }
142 int t = crossCorrelation(buf, buf).offset;
143 BOOST_REQUIRE(t == 0);
144
145 }
146
147
148 // test that checks wether LagDetector finds zero lag when no lag is present
BOOST_FIXTURE_TEST_CASE(zero_lag,LagDetectionSetup)149 BOOST_FIXTURE_TEST_CASE( zero_lag, LagDetectionSetup )
150 {
151 // insert zero lag data
152 simulate(10);
153
154 // now we do 50 steps and check for lag
155 for(int i = 0; i < SIMULATION_DURATION; ++i)
156 {
157 simulate();
158 int lag = D.getLag();
159 if( lag != 0 )
160 {
161 char errormsg[1024];
162 sprintf(errormsg, "lag of %d detected when simulating zero lag", lag);
163 BOOST_FAIL("");
164 };
165 }
166 }
167
168
169 // test that checks wether LagDetector finds constant lags
170 /// \todo use http://www.boost.org/doc/libs/1_48_0/libs/test/doc/html/utf/user-guide/test-organization/unary-test-case.html
BOOST_FIXTURE_TEST_CASE(constant_lag,LagDetectionSetup)171 BOOST_FIXTURE_TEST_CASE( constant_lag, LagDetectionSetup )
172 {
173 file << "\nconstant lag" << "\n";
174 // test for all small constant lags
175 for(int clag = 1; clag < 10; clag++)
176 {
177 reset_simulator(clag);
178 simulate(25);
179
180 // now we do 50 steps and check for lag
181 for(int i = 0; i < SIMULATION_DURATION; ++i)
182 {
183 simulate();
184 int lag = D.getLag();
185
186 if( lag != clag )
187 {
188 file << D.getDebugString() << "\n";
189 char errormsg[1024];
190 sprintf(errormsg, "detected lag of %d when constant lag of %d was simulated", lag, clag);
191 BOOST_FAIL(errormsg);
192 };
193 }
194 }
195 }
196
197 // CONFIGURE:
198 const int REAL_INPUT_PATTERN_LENGTH = 40;
199 const int INPUT_CHANGE_STEP_WIDTH = 5;
200
201 // check constant lag with bad input data
BOOST_FIXTURE_TEST_CASE(constant_lag_real_input,LagDetectionSetup)202 BOOST_FIXTURE_TEST_CASE( constant_lag_real_input, LagDetectionSetup )
203 {
204 file << "\nconstant lag - real input" << "\n";
205 result << "constant lag - real input\n";
206 result << "In\tF%\tsig\n";
207
208 for(int input_quality = 10; input_quality <= REAL_INPUT_PATTERN_LENGTH; input_quality += INPUT_CHANGE_STEP_WIDTH )
209 {
210 // determine a random lag and set up the simulation
211 int clag = rand() % 4 + 4;
212 reset_simulator(clag);
213
214 // start
215 simulate(25, input_quality);
216
217 // now we do 500 steps and check for lag
218 int errors = 0;
219 int cum_err = 0;
220 for(int i = 0; i < SIMULATION_DURATION; ++i)
221 {
222 simulate(1, input_quality);
223
224 int lag = D.getLag();
225 //
226 if( lag != clag )
227 {
228 file << D.getDebugString() << "\n";
229 errors++;
230 cum_err += (lag - clag) * (lag - clag);
231 };
232 }
233
234 result << input_quality << ",\t" << (int)((100.f * errors / SIMULATION_DURATION)) << ",\t" << std::sqrt(cum_err / (float)SIMULATION_DURATION) << "\n";
235
236 // we consider this test failed if more than 20% of our results are incorrect
237 if(errors / (float)SIMULATION_DURATION > 0.2)
238 {
239 char errormsg[1024];
240 sprintf(errormsg, "realisitc input and constant lag: %d %% not correct", (int)(100.f * errors / SIMULATION_DURATION) );
241 BOOST_ERROR(errormsg);
242 }
243 }
244 }
245
246
247 const int LAG_CHANGE_RATE = 10;
248
249 // test with high quality data but changing lags
250 // in this test, we can see how fast die algorithm can detect changing lag
251 // in this test, the lag changes are only slight, so more than 1frame per change
252 // does not happen
BOOST_FIXTURE_TEST_CASE(changing_lag,LagDetectionSetup)253 BOOST_FIXTURE_TEST_CASE( changing_lag, LagDetectionSetup )
254 {
255 file << "\nchanging lag - real input" << "\n";
256 result << "changing lag - real input - small change\n";
257
258 // test for all small constant lags
259 int clag = rand() % 8 + 4;
260 NetworkSimulator.changePing(clag);
261
262 // start a game
263 simulate(100);
264
265 // accumulator for collecting statistical data of our run
266 accumulator_set< int, features< tag::count, tag::max, tag::mean, tag::mean_of_variates<int, tag::covariate1> > > acc;
267
268 int lag = 0;
269 int errors = 0;
270 int timer = 0;
271 int cum_timer = 0;
272
273 // now we do 500 steps and check for lag
274 for(int i = 0; i < 500; ++i)
275 {
276 // randomly change lags. we are friendly for now.
277 // only change lag after system has adapted to new lag
278 if(rand() % LAG_CHANGE_RATE == 0 && clag == lag)
279 {
280 int nclag = (rand() % 2) * 2 - 1 + clag;
281 nclag = std::max(5, std::min(15, nclag));
282
283 clag = nclag;
284 NetworkSimulator.changePing(clag);
285 timer = 0;
286 }
287 simulate();
288
289 lag = D.getLag();
290
291 if( lag != clag )
292 {
293 errors++;
294 timer++;
295 } else if(timer != 0) {
296 result << "took " << timer << " steps to recognice lag of "<< lag << std::endl;
297 file << lag << " " << timer << "\n" << D.getDebugString() << "\n";
298
299 // calculate cum timer
300
301 cum_timer += timer;
302 acc(std::max(0, timer - lag), covariate1 = timer);
303 timer = 0;
304 }
305 }
306
307 // when we take longer than 10ms to detect the lag change after the first packet with new lag arrived
308 // we are too slow.
309 // when we take longer than 15ms once, it is bad, too
310 if( mean(acc) > 5 || max(acc) > 15)
311 {
312 char errormsg[1024];
313 sprintf(errormsg, "LagDetector takes too long to detect lag change of 1ms. Add: %d, Avg: %d, Max: %d", (int)mean(acc), (int)boost::accumulators::mean_of_variates<int, tag::covariate1>(acc), max(acc));
314 BOOST_ERROR(errormsg);
315 }
316
317 result << "maximum reaction time: " << max(acc) << std::endl;
318 result << "average reaction time: " << boost::accumulators::mean_of_variates<int, tag::covariate1>(acc) << std::endl;
319 result << "average additional reaction time: " << mean(acc) << std::endl;
320 }
321
322 // test with high quality data but changing lags
323 // in this test, we can see how fast die algorithm can detect changing lag
324 // in this test, the lag changes are only slight, so more than 1frame per change
325 // does not happen
BOOST_FIXTURE_TEST_CASE(changing_lag_real,LagDetectionSetup)326 BOOST_FIXTURE_TEST_CASE( changing_lag_real, LagDetectionSetup )
327 {
328 file << "\nchanging lag - good input" << "\n";
329 result << "changing lag - good input - small change\n";
330
331 for(int input_quality = 10; input_quality <= REAL_INPUT_PATTERN_LENGTH; input_quality += INPUT_CHANGE_STEP_WIDTH )
332 {
333 result << "data quality: " << input_quality << std::endl;
334 // test for all small constant lags
335 int clag = rand() % 8 + 4;
336 NetworkSimulator.changePing(clag);
337
338 // start a game
339 simulate(100, input_quality);
340
341 // accumulator for collecting statistical data of our run
342 accumulator_set< int, features< tag::count, tag::max, tag::mean, tag::mean_of_variates<int, tag::covariate1> > > acc;
343
344 int lag = 0;
345 int errors = 0;
346 int timer = 0;
347 int cum_timer = 0;
348
349 // now we do 500 steps and check for lag
350 for(int i = 0; i < 500; ++i)
351 {
352 // randomly change lags. we are friendly for now.
353 // only change lag after system has adapted to new lag
354 if(rand() % LAG_CHANGE_RATE == 0 && clag == lag)
355 {
356 int nclag = (rand() % 2) * 2 - 1 + clag;
357 nclag = std::max(5, std::min(15, nclag));
358
359 clag = nclag;
360 NetworkSimulator.changePing(clag);
361 timer = 0;
362 }
363 simulate(1, input_quality);
364
365 lag = D.getLag();
366
367 if( lag != clag )
368 {
369 errors++;
370 timer++;
371 } else if(timer != 0) {
372 // don't do any reporting here, as we would get too much messags
373 // result << "took " << timer << " steps to recognice lag of "<< lag << std::endl;
374 // file << lag << " " << timer << "\n" << D.getDebugString() << "\n";
375
376 // calculate cum timer
377
378 cum_timer += timer;
379 acc(std::max(0, timer - lag), covariate1 = timer);
380 timer = 0;
381 }
382 }
383
384 // when we take longer than 10ms to detect the lag change after the first packet with new lag arrived
385 // we are too slow.
386 // when we take longer than 15ms once, it is bad, too
387 if( mean(acc) > 10 || max(acc) > 25)
388 {
389 char errormsg[1024];
390 sprintf(errormsg, "LagDetector takes too long to detect lag change of 1ms. Add: %d, Avg: %d, Max: %d", (int)mean(acc), (int)boost::accumulators::mean_of_variates<int, tag::covariate1>(acc), max(acc));
391 BOOST_ERROR(errormsg);
392 }
393
394 result << "maximum reaction time: " << max(acc) << std::endl;
395 result << "average reaction time: " << boost::accumulators::mean_of_variates<int, tag::covariate1>(acc) << std::endl;
396 result << "average additional reaction time: " << mean(acc) << std::endl;
397 }
398 }
399
400
401 BOOST_AUTO_TEST_SUITE_END()
402