diff options
Diffstat (limited to 'main/tests/test_astar.cpp')
| -rw-r--r-- | main/tests/test_astar.cpp | 77 |
1 files changed, 51 insertions, 26 deletions
diff --git a/main/tests/test_astar.cpp b/main/tests/test_astar.cpp index 3cc754e230..fe335589b0 100644 --- a/main/tests/test_astar.cpp +++ b/main/tests/test_astar.cpp @@ -173,8 +173,9 @@ bool test_add_remove() { for (int i = 0; i < 20000; i++) { int u = Math::rand() % 5; int v = Math::rand() % 4; - if (u == v) + if (u == v) { v = 4; + } if (Math::rand() % 2 == 1) { // Add a (possibly existing) directed edge and confirm connectivity a.connect_points(u, v, false); @@ -189,19 +190,22 @@ bool test_add_remove() { // Random tests for point removal for (int i = 0; i < 20000; i++) { a.clear(); - for (int j = 0; j < 5; j++) + for (int j = 0; j < 5; j++) { a.add_point(j, Vector3(0, 0, 0)); + } // Add or remove random edges for (int j = 0; j < 10; j++) { int u = Math::rand() % 5; int v = Math::rand() % 4; - if (u == v) + if (u == v) { v = 4; - if (Math::rand() % 2 == 1) + } + if (Math::rand() % 2 == 1) { a.connect_points(u, v, false); - else + } else { a.disconnect_points(u, v, false); + } } // Remove point 0 @@ -241,8 +245,9 @@ bool test_solutions() { int u, v; u = Math::rand() % N; v = Math::rand() % (N - 1); - if (u == v) + if (u == v) { v = N - 1; + } // Pick a random operation int op = Math::rand(); @@ -256,16 +261,18 @@ bool test_solutions() { // Add edge (u, v); possibly bidirectional a.connect_points(u, v, op % 2); adj[u][v] = true; - if (op % 2) + if (op % 2) { adj[v][u] = true; + } break; case 6: case 7: // Remove edge (u, v); possibly bidirectional a.disconnect_points(u, v, op % 2); adj[u][v] = false; - if (op % 2) + if (op % 2) { adj[v][u] = false; + } break; case 8: // Remove point u and add it back; clears adjacent edges and changes coordinates @@ -274,42 +281,55 @@ bool test_solutions() { p[u].y = Math::rand() % 100; p[u].z = Math::rand() % 100; a.add_point(u, p[u]); - for (v = 0; v < N; v++) + for (v = 0; v < N; v++) { adj[u][v] = adj[v][u] = false; + } break; } } // Floyd-Warshall float d[N][N]; - for (int u = 0; u < N; u++) - for (int v = 0; v < N; v++) + for (int u = 0; u < N; u++) { + for (int v = 0; v < N; v++) { d[u][v] = (u == v || adj[u][v]) ? p[u].distance_to(p[v]) : INFINITY; + } + } - for (int w = 0; w < N; w++) - for (int u = 0; u < N; u++) - for (int v = 0; v < N; v++) - if (d[u][v] > d[u][w] + d[w][v]) + for (int w = 0; w < N; w++) { + for (int u = 0; u < N; u++) { + for (int v = 0; v < N; v++) { + if (d[u][v] > d[u][w] + d[w][v]) { d[u][v] = d[u][w] + d[w][v]; + } + } + } + } // Display statistics int count = 0; - for (int u = 0; u < N; u++) - for (int v = 0; v < N; v++) - if (adj[u][v]) + for (int u = 0; u < N; u++) { + for (int v = 0; v < N; v++) { + if (adj[u][v]) { count++; + } + } + } printf("Test #%4d: %3d edges, ", test + 1, count); count = 0; - for (int u = 0; u < N; u++) - for (int v = 0; v < N; v++) - if (!Math::is_inf(d[u][v])) + for (int u = 0; u < N; u++) { + for (int v = 0; v < N; v++) { + if (!Math::is_inf(d[u][v])) { count++; + } + } + } printf("%3d/%d pairs of reachable points\n", count - N, N * (N - 1)); // Check A*'s output bool match = true; - for (int u = 0; u < N; u++) - for (int v = 0; v < N; v++) + for (int u = 0; u < N; u++) { + for (int v = 0; v < N; v++) { if (u != v) { Vector<int> route = a.get_id_path(u, v); if (!Math::is_inf(d[u][v])) { @@ -344,10 +364,13 @@ bool test_solutions() { } } } + } + } exit: - if (!match) + if (!match) { return false; + } } return true; } @@ -367,11 +390,13 @@ MainLoop *test() { int passed = 0; while (true) { - if (!test_funcs[count]) + if (!test_funcs[count]) { break; + } bool pass = test_funcs[count](); - if (pass) + if (pass) { passed++; + } OS::get_singleton()->print("\t%s\n", pass ? "PASS" : "FAILED"); count++; |