Signed integer overflow (UB) in dtProximityGrid::hashPos2 for crowds far from the origin

Background

We run our test suite under GCC's UndefinedBehaviorSanitizer as part of CI. Our engine has a floating-origin / large-world coordinate system, so dtCrowd legitimately runs at large world coordinates (agents a few kilometres from the origin, either while the player is far out or immediately after an origin rebase relocates the mesh + crowd). UBSan halts on the first finding, and it consistently trips inside dtProximityGrid:

DetourProximityGrid.cpp:45:12: runtime error: signed integer overflow:
    -684 * 73856093 cannot be represented in type 'int'

The agent sat at world position ≈ (-4088, …, 2048), which maps to grid cell index x ≈ -684. -684 * 73856093 = -50,517,567,612, far outside int's [-2147483648, 2147483647] range.

Environment

• recastnavigation: v1.6.0 (6dc1667f580357e8a2154c28b7867bea7e8ad3a7). The code is unchanged on main as of this writing.
• Compiler: GCC 14, x86-64 Linux (GitHub-hosted ubuntu runner).
• Flags: -fsanitize=undefined -fno-sanitize-recover=signed-integer-overflow,null,alignment,float-divide-by-zero,return,unreachable,vla-bound,shift.

UBSan report

DetourProximityGrid.cpp:45:12: runtime error: signed integer overflow: -684 * 73856093 cannot be represented in type 'int'
    #0 hashPos2(int, int, int)                        DetourCrowd/Source/DetourProximityGrid.cpp:45:12
    #1 dtProximityGrid::addItem(unsigned short, ...)  DetourCrowd/Source/DetourProximityGrid.cpp:122:19
    #2 dtCrowd::update(float, dtCrowdAgentDebugInfo*) DetourCrowd/Source/DetourCrowd.cpp:1071:11
    ...
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior DetourProximityGrid.cpp:45:12

Root cause

dtProximityGrid::addItem derives an absolute grid cell index straight from the agent's world position (DetourProximityGrid.cpp:106):

const int iminx = (int)dtMathFloorf(minx * m_invCellSize);

and feeds it to the spatial hash (DetourProximityGrid.cpp:43-46):

inline int hashPos2(int x, int y, int n)
{
    return ((x*73856093) ^ (y*19349663)) & (n-1);
}

x, y, and the constants are all int, so the products are computed in int. x * 73856093 overflows a 32-bit int for any |x| > 2147483647 / 73856093 ≈ 29 — i.e. once an agent is more than ~30 cells from the origin. With the default proximity-grid cell size (dtCrowd initialises it from the max agent radius), that is only a few hundred metres of absolute world distance. Because the cell index is absolute (not relative to any grid origin), the overflow is unavoidable for any crowd that operates far from (0,0) — floating-origin worlds, large open worlds, or games that simply place their playable area away from the origin.

Signed integer overflow is undefined behaviour in C/C++. In practice on two's-complement hardware it wraps to a well-defined value that & (n-1) then masks into a valid bucket, so the crowd behaves correctly — but it is UB by the standard, so UBSan (correctly) flags and, under -fno-sanitize-recover, aborts it. Any downstream project running Detour under UBSan hits this.

Notably, Detour's navmesh tile hash already does this the safe way — dtNavMesh's computeTileHash (Detour/Source/DetourNavMesh.cpp:114) multiplies through unsigned int, where wraparound is well-defined:

inline int computeTileHash(int x, int y, const int mask)
{
    const unsigned int h1 = 0x8da6b343;
    const unsigned int h2 = 0xd8163841;
    unsigned int n = h1 * x + h2 * y;   // unsigned multiply — no UB
    return (int)(n & mask);
}

hashPos2 predates or simply diverged from that convention.

(Secondary, lower-severity: addItem also truncates the same absolute cell index into a short a few lines down — item.x = (short)x; at DetourProximityGrid.cpp:126 — which silently wraps for |x| > 32767. Not what UBSan caught here, but it's the same "absolute cell index assumed small" assumption and worth a look while in this code.)

Suggested fix

Make hashPos2 multiply through unsigned int, exactly as computeTileHash already does. The masked low bits are bit-identical to the current result on two's-complement targets, so this is a zero-behaviour-change fix that only removes the UB:

 inline int hashPos2(int x, int y, int n)
 {
-	return ((x*73856093) ^ (y*19349663)) & (n-1);
+	const unsigned int h1 = 73856093u;
+	const unsigned int h2 = 19349663u;
+	const unsigned int h = (h1 * (unsigned int)x) ^ (h2 * (unsigned int)y);
+	return (int)(h & (unsigned int)(n - 1));
 }

This keeps the hash distribution identical (same constants, same XOR, same mask) and makes it consistent with computeTileHash. Happy to open a PR if that's helpful.

Thanks for Recast/Detour — it's excellent.