russell@unturf.com fcab3d630b regamedll-0002: CLocalNav::NodeExists O(N) linear scan in hostage BFS, 31.1x ...

Hostage pathfinding CLocalNav::FindPath() calls NodeExists() inside BFS
expansion loop. NodeExists() linearly scans all existing nodes to check
if coordinate pair already exists. With MAX_NODES=100, this is O(N^2)
per FindPath() call (8 AddPathNode calls per expansion, each scanning
all N nodes).

Fix: unordered_set keyed on packed (offsetX, offsetY) for O(1) lookup.
Reduces FindPath() from O(N^2) to O(N). 31.1x op-count reduction at
N=100, 4/4 PASS.

MOAD-0002 (intertangle): gpGlobals is standard GoldSrc engine state, CLEAN.
MOAD-0003 (leaked context): single-threaded game DLL, no thread_local, CLEAN.
MOAD-0004 (logged secret): no RCON/auth handling in game DLL, CLEAN.
MOAD-0005 (thundering herd): single-threaded, no concurrent cache, CLEAN.

2026-03-31 13:05:24 -04:00

18 KiB

Executable file

Raw Permalink History

View raw