tests/gdx-tests/src/com/badlogic/gdx/tests/SelectTest.java

   1
   2 package com.badlogic.gdx.tests;
   3
   4 import com.badlogic.gdx.Gdx;
   5 import com.badlogic.gdx.math.MathUtils;
   6 import com.badlogic.gdx.math.Vector2;
   7 import com.badlogic.gdx.tests.utils.GdxTest;
   8 import com.badlogic.gdx.utils.Array;
   9 import com.badlogic.gdx.utils.GdxRuntimeException;
  10 import com.badlogic.gdx.utils.PerformanceCounter;
  11
  12 import java.util.Comparator;
  13
  14 /** For testing and benchmarking of gdx.utils.Select and its associated algorithms/classes
  15  * @author Jon renner */
  16 public class SelectTest extends GdxTest {
  17         static PerformanceCounter perf = new PerformanceCounter("bench");
  18         static boolean verify; // verify and report the results of each selection
  19         private static boolean quiet;
  20
  21         @Override
  22         public void create () {
  23                 int n = 100;
  24                 player = createDummies(n);
  25                 enemy = createDummies(n);
  26
  27                 int runs = 100;
  28                 // run correctness first to warm up the JIT and other black magic
  29                 quiet = true;
  30                 allRandom();
  31                 print("VERIFY CORRECTNESS FIND LOWEST RANKED");
  32                 correctnessTest(runs, 1);
  33                 print("VERIFY CORRECTNESS FIND MIDDLE RANKED");
  34                 correctnessTest(runs, enemy.size / 2);
  35                 print("VERIFY CORRECTNESS FIND HIGHEST RANKED");
  36                 correctnessTest(runs, enemy.size);
  37
  38                 runs = 1000;
  39                 quiet = true;
  40                 print("BENCHMARK FIND LOWEST RANKED");
  41                 performanceTest(runs, 1);
  42                 print("BENCHMARK FIND MIDDLE RANKED");
  43                 performanceTest(runs, enemy.size / 2);
  44                 print("BENCHMARK FIND HIGHEST RANKED");
  45                 performanceTest(runs, enemy.size);
  46
  47                 print("TEST CONSISTENCY FOR LOWEST RANKED");
  48                 consistencyTest(runs, 1);
  49                 print("TEST CONSISTENCY FOR MIDDLE RANKED");
  50                 consistencyTest(runs, enemy.size / 2);
  51                 print("TEST CONSISTENCY FOR HIGHEST RANKED");
  52                 consistencyTest(runs, enemy.size);
  53
  54                 // test that selectRanked and selectRankedIndex return the same
  55                 print("TEST selectRanked AND selectRankedIndex RETURN MATCHING RESULTS - LOWEST RANKED");
  56                 testValueMatchesIndex(runs, 1);
  57                 print("TEST selectRanked AND selectRankedIndex RETURN MATCHING RESULTS - MIDDLE RANKED");
  58                 testValueMatchesIndex(runs, enemy.size / 2);
  59                 print("TEST selectRanked AND selectRankedIndex RETURN MATCHING RESULTS - HIGHEST RANKED");
  60                 testValueMatchesIndex(runs, enemy.size);
  61
  62                 print("ALL TESTS PASSED");
  63         }
  64
  65         public static void correctnessTest (int runs, int k) {
  66                 String msg = String.format("[%d runs with %dx%d dummy game units] - ", runs, player.size, enemy.size);
  67                 verify = true;
  68                 test(runs, k);
  69                 print(msg + "VERIFIED");
  70         }
  71
  72         public static void performanceTest (int runs, int k) {
  73                 verify = false;
  74                 test(runs, k);
  75                 String msg = String.format("[%d runs with %dx%d dummy game units] - ", runs, player.size, enemy.size);
  76                 print(msg
  77                         + String.format("avg: %.5f, min/max: %.4f/%.4f, total time: %.3f (ms), made %d comparisons", allPerf.time.min,
  78                                 allPerf.time.max, allPerf.time.average * 1000, allPerf.time.total * 1000, comparisonsMade));
  79         }
  80
  81         public static void consistencyTest (int runs, int k) {
  82                 verify = false;
  83                 Dummy test = player.get(0);
  84                 Dummy lastFound = null;
  85                 allRandom();
  86                 for (int i = 0; i < runs; i++) {
  87                         Dummy found = test.getKthNearestEnemy(k);
  88                         if (lastFound == null) {
  89                                 lastFound = found;
  90                         } else {
  91                                 if (!(lastFound.equals(found))) {
  92                                         print("CONSISTENCY TEST FAILED");
  93                                         print("lastFound: " + lastFound);
  94                                         print("justFound: " + found);
  95                                         throw new GdxRuntimeException("test failed");
  96                                 }
  97                         }
  98                 }
  99         }
 100
 101         public static void testValueMatchesIndex (int runs, int k) {
 102                 verify = false;
 103                 for (int i = 0; i < runs; i++) {
 104                         allRandom();
 105                         player.shuffle();
 106                         enemy.shuffle();
 107                         originDummy = player.random();
 108                         int idx = enemy.selectRankedIndex(distComp, k);
 109                         Dummy indexDummy = enemy.get(idx);
 110                         Dummy valueDummy = enemy.selectRanked(distComp, k);
 111                         if (!(indexDummy.equals(valueDummy))) {
 112                                 throw new GdxRuntimeException("results of selectRankedIndex and selectRanked do not return the same object\n"
 113                                         + "selectRankedIndex -> " + indexDummy + "\n" + "selectRanked      -> " + valueDummy);
 114                         }
 115
 116                 }
 117         }
 118
 119         public static void test (int runs, int k) {
 120                 // k = kth order statistic
 121                 comparisonsMade = 0;
 122                 perf.reset();
 123                 allPerf.reset();
 124                 allRandom();
 125                 enemy.shuffle();
 126                 player.shuffle();
 127                 for (int i = 0; i < runs; i++) {
 128                         getKthNearestEnemy(quiet, k);
 129                 }
 130         }
 131
 132         public static void allRandom () {
 133                 for (Dummy d : player) {
 134                         d.setRandomPos();
 135                 }
 136                 for (Dummy d : enemy) {
 137                         d.setRandomPos();
 138                 }
 139         }
 140
 141         private static PerformanceCounter allPerf = new PerformanceCounter("all");
 142
 143         public static void getKthNearestEnemy (boolean silent, int k) {
 144                 Dummy kthDummy = null;
 145                 perf.reset();
 146                 allPerf.start();
 147                 for (Dummy d : player) {
 148                         Dummy found = d.getKthNearestEnemy(k);
 149                 }
 150                 allPerf.stop();
 151                 allPerf.tick();
 152                 if (silent) return;
 153                 print(String.format("found nearest. min: %.4f, max: %.4f, avg: %.4f, total: %.3f ms", perf.time.min * 1000,
 154                         perf.time.max * 1000, perf.time.average * 1000, perf.time.total * 1000));
 155         }
 156
 157         public static void verifyCorrectness (Dummy d, int k) {
 158                 enemy.sort(distComp);
 159                 int idx = enemy.indexOf(d, true);
 160                 // remember that k = min value = 0 position in the array, therefore k - 1
 161                 // if (idx != k - 1) {
 162                 // print("verified - idx: " + idx + ", (k - 1): " + (k - 1));
 163                 if (enemy.get(idx) != enemy.get(k - 1)) {
 164                         System.out.println("origin dummy: " + originDummy);
 165                         System.out.println("TEST FAILURE: " + "idx: " + idx + " does not equal (k - 1): " + (k - 1));
 166                         throw new GdxRuntimeException("test failed");
 167                 }
 168         }
 169
 170         static class Dummy {
 171                 public Vector2 pos;
 172                 public int id;
 173
 174                 public Dummy () {
 175                         // set the position manually
 176                 }
 177
 178                 @Override
 179                 public boolean equals (Object obj) {
 180                         if (!(obj instanceof Dummy)) {
 181                                 throw new GdxRuntimeException("do not compare to anything but other Dummy objects");
 182                         }
 183                         Dummy d = (Dummy)obj;
 184                         // we only care about position/distance
 185                         float epsilon = 0.0001f;
 186                         float diff = Math.abs(d.pos.x - this.pos.x) + Math.abs(d.pos.y - this.pos.y);
 187                         if (diff > epsilon) return false;
 188                         return true;
 189
 190                 }
 191
 192                 public Dummy getKthNearestEnemy (int k) {
 193                         perf.start();
 194                         originDummy = this;
 195                         Dummy found = enemy.selectRanked(distComp, k);
 196                         // print(this + " found enemy: " + found);
 197                         perf.stop();
 198                         perf.tick();
 199                         if (verify) {
 200                                 verifyCorrectness(found, k);
 201                         }
 202                         return found;
 203                 }
 204
 205                 public void setRandomPos () {
 206                         float max = 100;
 207                         this.pos.x = -max + MathUtils.random(max * 2);
 208                         this.pos.y = -max + MathUtils.random(max * 2);
 209                         float xShift = 100;
 210                         if (player.contains(this, true)) {
 211                                 this.pos.x -= xShift;
 212                         } else if (enemy.contains(this, true)) {
 213                                 this.pos.x += xShift;
 214                         } else {
 215                                 throw new RuntimeException("unhandled");
 216                         }
 217                 }
 218
 219                 @Override
 220                 public String toString () {
 221                         return String.format("Dummy at: %.2f, %.2f", pos.x, pos.y);
 222                 }
 223         }
 224
 225         public static int nextID = 1;
 226         public static Array<Dummy> player;
 227         public static Array<Dummy> enemy;
 228
 229         public static Array<Dummy> createDummies (int n) {
 230                 float variance = 20;
 231                 Array<Dummy> dummies = new Array<Dummy>();
 232                 for (int i = 0; i < n; i++) {
 233                         Dummy d = new Dummy();
 234                         dummies.add(d);
 235                         d.pos = new Vector2();
 236                         d.id = nextID++;
 237                 }
 238                 return dummies;
 239         }
 240
 241         static Dummy originDummy;
 242         static long comparisonsMade = 0;
 243         static Comparator<Dummy> distComp = new Comparator<Dummy>() {
 244                 @Override
 245                 public int compare (Dummy o1, Dummy o2) {
 246                         comparisonsMade++;
 247                         float d1 = originDummy.pos.dst2(o1.pos);
 248                         float d2 = originDummy.pos.dst2(o2.pos);
 249                         float diff = d1 - d2;
 250                         if (diff < 0) return -1;
 251                         if (diff > 0) return 1;
 252                         return 0;
 253                 }
 254         };
 255
 256         public static void print (Object... objs) {
 257                 for (Object o : objs) {
 258                         System.out.print(o);
 259                 }
 260                 System.out.println();
 261         }
 262 }