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