java-topology/whitepaper/outreach/openmw-0002.md

OpenMW — CWE-407 Disclosure Brief (openmw-0002)

2026-04-13 · Patch available — awaiting upstream merge

Finding

One O(N²) defect in OpenMW's A* pathfinding open-set membership test. Patched. The A* implementation uses std::find() on a std::list for open-set membership checks, producing O(N²) behavior during pathfinding.

The Defect

openmw-0002 (PATCHED — HIGH): apps/openmw/mwmechanics/pathgrid.cpp:250

// In A* pathfinding — fires per neighbor per node explored:
std::list<size_t> openset;
// ...
bool isInOpenSet = std::find(openset.begin(), openset.end(), dest) != openset.end();
// O(N) per check

openset is std::list<size_t>. std::find() is O(N) on a list. Called for every edge relaxation in A*. With V vertices and E edges, total cost: O(E × V) instead of O(E × 1). The code even contains a TODO comment: "if this causes performance problems a hash table may help."

Complexity Proof

At V=500 vertices, E=2,000 edges:

• Defective: 2,000 × 250 avg = 500,000 comparisons
• Fixed: 2,000 × O(1) unordered_set lookups = 2,000 operations
• 250× op reduction at 500 vertices.

Impact

OpenMW is an open-source reimplementation of the Morrowind engine. A* pathfinding fires for every NPC and creature movement decision. Cities with hundreds of pathgrid nodes and many NPCs trigger the quadratic open-set scan repeatedly. This affects NPC responsiveness and contributes to frame hitches during pathfinding-heavy scenes.

The Fix

Add a parallel std::unordered_set<size_t> for O(1) open-set membership:

// Before
bool isInOpenSet = std::find(openset.begin(), openset.end(), dest) != openset.end();  // O(N)

// After
std::unordered_set<size_t> opensetMembership;
bool isInOpenSet = opensetMembership.count(dest) > 0;  // O(1)
// Maintained in sync: insert on add, erase on pop

Patch

Fix available: defects/openmw-0002/patch/openmw-0002.patch

Touches apps/openmw/mwmechanics/pathgrid.cpp. 250× speedup at 500 pathgrid vertices.

What We Ask

A patch is ready for review.

1. Confirm receipt and assign a GitLab issue reference (OpenMW/openmw).
2. Assess severity — fires on every NPC pathfinding query.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the OpenMW team in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.