java-topology/defects/scummvm-0001/test/scummvm-0001-test.cpp

// scummvm-0001-test.cpp
// Unit test: CRAB engine PathfindingGrid::getNearestOpenNode O(N^2) BFS (CWE-407)
//
// DEFECT: In engines/crab/PathfindingGrid.cpp, getNearestOpenNode() performs a
// BFS over the pathfinding grid to find the nearest walkable node. The visited
// set is a Common::Array<PathfindingGraphNode*> named allUsedNodes. On each
// neighbor check the BFS calls:
//   Common::find(allUsedNodes.begin(), allUsedNodes.end(), neighbor)
// which is O(|visited|) per check. Over a BFS visiting N nodes with an average
// degree D, total work is O(N * D * N) = O(N^2 * D). On a 64x64 tile map this
// function can visit thousands of nodes per click.
//
// FIX: Replace allUsedNodes (Common::Array) with std::unordered_set<Node*>.
// Membership test drops from O(N) to O(1). Total BFS cost becomes O(N * D).
//
// BUILD: g++ -std=c++17 -O2 -o scummvm-0001-test scummvm-0001-test.cpp && ./scummvm-0001-test

#include <vector>
#include <list>
#include <unordered_set>
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <cassert>
#include <cmath>

// Minimal simulated node
struct Node {
    int x, y;
    bool blocked;
    std::vector<Node *> neighbors;
    Node(int x, int y, bool blocked) : x(x), y(y), blocked(blocked) {}
};

// Build a grid of W*H nodes; border nodes are blocked, inner nodes are open
static std::vector<std::vector<Node *>> build_grid(int W, int H) {
    std::vector<std::vector<Node *>> grid(W, std::vector<Node *>(H));
    for (int i = 0; i < W; i++)
        for (int j = 0; j < H; j++)
            grid[i][j] = new Node(i, j, (i == 0 || j == 0 || i == W-1 || j == H-1));

    // Connect 4-neighbors
    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H; j++) {
            if (i > 0)   grid[i][j]->neighbors.push_back(grid[i-1][j]);
            if (i < W-1) grid[i][j]->neighbors.push_back(grid[i+1][j]);
            if (j > 0)   grid[i][j]->neighbors.push_back(grid[i][j-1]);
            if (j < H-1) grid[i][j]->neighbors.push_back(grid[i][j+1]);
        }
    }
    return grid;
}

static void free_grid(std::vector<std::vector<Node *>> &grid) {
    for (auto &col : grid)
        for (auto *n : col)
            delete n;
}

// DEFECT: BFS with std::vector visited set = O(N^2)
static Node *get_nearest_open_defect(Node *start) {
    if (!start->blocked) return start;

    Node *returnNode = nullptr;
    float shortestDistance = 0.0f;

    std::list<Node *> checkNodes;
    checkNodes.push_back(start);

    std::vector<Node *> allUsedNodes;  // O(N) find on every neighbor check
    allUsedNodes.push_back(start);

    while (!checkNodes.empty()) {
        Node *front = checkNodes.front();

        if (!front->blocked) {
            float dx = (float)(front->x - start->x);
            float dy = (float)(front->y - start->y);
            float dist = dx*dx + dy*dy;
            if (shortestDistance == 0.0f || dist < shortestDistance) {
                shortestDistance = dist;
                returnNode = front;
            }
        } else {
            for (Node *nb : front->neighbors) {
                // Original O(N) membership check
                if (std::find(allUsedNodes.begin(), allUsedNodes.end(), nb) == allUsedNodes.end()) {
                    allUsedNodes.push_back(nb);
                    checkNodes.push_back(nb);
                }
            }
        }

        if (returnNode != nullptr) return returnNode;
        checkNodes.pop_front();
    }
    return nullptr;
}

// FIX: BFS with unordered_set visited = O(N)
static Node *get_nearest_open_fixed(Node *start) {
    if (!start->blocked) return start;

    Node *returnNode = nullptr;
    float shortestDistance = 0.0f;

    std::list<Node *> checkNodes;
    checkNodes.push_back(start);

    std::unordered_set<Node *> visitedNodes;  // O(1) find
    visitedNodes.insert(start);

    while (!checkNodes.empty()) {
        Node *front = checkNodes.front();

        if (!front->blocked) {
            float dx = (float)(front->x - start->x);
            float dy = (float)(front->y - start->y);
            float dist = dx*dx + dy*dy;
            if (shortestDistance == 0.0f || dist < shortestDistance) {
                shortestDistance = dist;
                returnNode = front;
            }
        } else {
            for (Node *nb : front->neighbors) {
                if (visitedNodes.find(nb) == visitedNodes.end()) {
                    visitedNodes.insert(nb);
                    checkNodes.push_back(nb);
                }
            }
        }

        if (returnNode != nullptr) return returnNode;
        checkNodes.pop_front();
    }
    return nullptr;
}

static void test_correctness() {
    // 10x10 grid, start at (0,0) which is blocked
    auto grid = build_grid(10, 10);
    Node *start = grid[0][0];

    Node *r_defect = get_nearest_open_defect(start);
    Node *r_fixed  = get_nearest_open_fixed(start);

    assert(r_defect != nullptr);
    assert(r_fixed  != nullptr);
    // Both should find same nearest open node (same distance)
    float dx_d = (float)(r_defect->x - start->x);
    float dy_d = (float)(r_defect->y - start->y);
    float dx_f = (float)(r_fixed->x  - start->x);
    float dy_f = (float)(r_fixed->y  - start->y);
    float dist_d = dx_d*dx_d + dy_d*dy_d;
    float dist_f = dx_f*dx_f + dy_f*dy_f;
    assert(dist_d == dist_f);

    free_grid(grid);
    printf("PASS correctness: both implementations find nearest open at same distance\n");
}

static long long bench(int W, int H, int repeats, bool fixed) {
    auto grid = build_grid(W, H);
    // Block everything; no open node is found so BFS visits all N*W nodes
    for (int i = 0; i < W; i++)
        for (int j = 0; j < H; j++)
            grid[i][j]->blocked = true;
    Node *start = grid[0][0];

    auto t0 = std::chrono::high_resolution_clock::now();
    for (int r = 0; r < repeats; r++) {
        Node *result = fixed ? get_nearest_open_fixed(start) : get_nearest_open_defect(start);
        (void)result;
    }
    auto t1 = std::chrono::high_resolution_clock::now();

    free_grid(grid);
    return std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
}

int main() {
    printf("scummvm-0001: CRAB PathfindingGrid::getNearestOpenNode O(N^2) BFS (CWE-407)\n\n");

    test_correctness();

    // Benchmark: fully-blocked grid forces BFS to visit ALL N nodes before returning
    // null. This maximizes the visited-set membership checks, exposing the O(N^2) scan.
    const int W = 80, H = 80;  // 6400 nodes
    auto grid = build_grid(W, H);
    for (int i = 0; i < W; i++)
        for (int j = 0; j < H; j++)
            grid[i][j]->blocked = true;

    Node *start = grid[0][0];
    const int REPS = 20;

    printf("\nBenchmark: %dx%d fully-blocked grid, %d reps from (0,0)\n", W, H, REPS);

    auto t0 = std::chrono::high_resolution_clock::now();
    for (int r = 0; r < REPS; r++) {
        auto *result = get_nearest_open_defect(start);
        (void)result;
    }
    auto t1 = std::chrono::high_resolution_clock::now();
    long long us_defect = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();

    auto t2 = std::chrono::high_resolution_clock::now();
    for (int r = 0; r < REPS; r++) {
        auto *result = get_nearest_open_fixed(start);
        (void)result;
    }
    auto t3 = std::chrono::high_resolution_clock::now();
    long long us_fixed = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count();

    free_grid(grid);

    printf("  Defect (O(N^2) BFS): %lld us\n", us_defect);
    printf("  Fixed  (O(N)   BFS): %lld us\n", us_fixed);

    if (us_fixed > 0 && us_defect > 0) {
        double ratio = (double)us_defect / (double)us_fixed;
        printf("  Speedup ratio: %.1fx\n", ratio);
    }

    printf("\nPASS\n");
    return 0;
}