diff options
| -rw-r--r-- | main/tests/test_astar.cpp | 159 |
1 files changed, 142 insertions, 17 deletions
diff --git a/main/tests/test_astar.cpp b/main/tests/test_astar.cpp index b2002cd5d9..4b60a3e94a 100644 --- a/main/tests/test_astar.cpp +++ b/main/tests/test_astar.cpp @@ -31,8 +31,10 @@ #include "test_astar.h" #include "core/math/a_star.h" +#include "core/math/math_funcs.h" #include "core/os/os.h" +#include <math.h> #include <stdio.h> namespace TestAStar { @@ -165,18 +167,14 @@ bool test_add_remove() { ok = ok && (a.get_closest_position_in_segment(Vector3(-1, 0.2, 0)) == Vector3(0, 0, 0)); ok = ok && (a.get_closest_position_in_segment(Vector3(3, 2, 0)) == Vector3(2, 1, 0)); - int seed = 0; + Math::seed(0); // Random tests for connectivity checks for (int i = 0; i < 20000; i++) { - seed = (seed * 1103515245 + 12345) & 0x7fffffff; - int u = (seed / 5) % 5; - int v = seed % 5; - if (u == v) { - i--; - continue; - } - if (seed % 2 == 1) { + int u = Math::rand() % 5; + int v = Math::rand() % 4; + 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); ok = ok && (a.are_points_connected(u, v, false) == true); @@ -195,14 +193,10 @@ bool test_add_remove() { // Add or remove random edges for (int j = 0; j < 10; j++) { - seed = (seed * 1103515245 + 12345) & 0x7fffffff; - int u = (seed / 5) % 5; - int v = seed % 5; - if (u == v) { - j--; - continue; - } - if (seed % 2 == 1) + int u = Math::rand() % 5; + int v = Math::rand() % 4; + if (u == v) v = 4; + if (Math::rand() % 2 == 1) a.connect_points(u, v, false); else a.disconnect_points(u, v, false); @@ -220,12 +214,143 @@ bool test_add_remove() { return ok; } +bool test_solutions() { + // Random stress tests with Floyd-Warshall + + const int N = 30; + Math::seed(0); + + for (int test = 0; test < 1000; test++) { + AStar a; + Vector3 p[N]; + bool adj[N][N] = { { false } }; + + // Assign initial coordinates + for (int u = 0; u < N; u++) { + p[u].x = Math::rand() % 100; + p[u].y = Math::rand() % 100; + p[u].z = Math::rand() % 100; + a.add_point(u, p[u]); + } + + // Generate a random sequence of operations + for (int i = 0; i < 1000; i++) { + // Pick two different vertices + int u, v; + u = Math::rand() % N; + v = Math::rand() % (N - 1); + if (u == v) v = N - 1; + + // Pick a random operation + int op = Math::rand(); + switch (op % 9) { + case 0: + case 1: + case 2: + case 3: + case 4: + case 5: + // Add edge (u, v); possibly bidirectional + a.connect_points(u, v, op % 2); + adj[u][v] = true; + 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) adj[v][u] = false; + break; + case 8: + // Remove point u and add it back; clears adjacent edges and changes coordinates + a.remove_point(u); + p[u].x = Math::rand() % 100; + p[u].y = Math::rand() % 100; + p[u].z = Math::rand() % 100; + a.add_point(u, p[u]); + 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++) + 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]) + 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]) 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])) 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++) + if (u != v) { + PoolVector<int> route = a.get_id_path(u, v); + if (!Math::is_inf(d[u][v])) { + // Reachable + if (route.size() == 0) { + printf("From %d to %d: A* did not find a path\n", u, v); + match = false; + goto exit; + } + float astar_dist = 0; + for (int i = 1; i < route.size(); i++) { + if (!adj[route[i - 1]][route[i]]) { + printf("From %d to %d: edge (%d, %d) does not exist\n", + u, v, route[i - 1], route[i]); + match = false; + goto exit; + } + astar_dist += p[route[i - 1]].distance_to(p[route[i]]); + } + if (!Math::is_equal_approx(astar_dist, d[u][v])) { + printf("From %d to %d: Floyd-Warshall gives %.6f, A* gives %.6f\n", + u, v, d[u][v], astar_dist); + match = false; + goto exit; + } + } else { + // Unreachable + if (route.size() > 0) { + printf("From %d to %d: A* somehow found a nonexistent path\n", u, v); + match = false; + goto exit; + } + } + } + + exit: + if (!match) return false; + } + return true; +} + typedef bool (*TestFunc)(void); TestFunc test_funcs[] = { test_abc, test_abcx, test_add_remove, + test_solutions, NULL }; |