SCFA Explorations

platoon.org

lua/platoon.lua

Exploring coarse pathfinding code.

PlatoonGenerateSafePathToLOUD

Many internally lifted (e.g. local) functions here designed to leverage cached information from navgraphs and previous static path computations to prevent submitting path requests to the engine.

GetClosestSafePathNodeInRadiusByLayerLOUD

Observations

• Markers are sorted and re-sorted every time during

the initial sort (by closest to location).

• The sorting key is recomputed every time
  • VDist3Sq( a.position, location )
• O(nlogn)

• Markers are traversed again and distance is computed again (same key, VDist3Sq)
  • Markers are pruned by distance hueristic (<= radius)
  • eventually pruning continues through to an engine call: AIGetThreatLevelsAroundPoint( v.position, threatradius)
    • This is computed 2x for every marker if seeksafest or goalseek is true….
      • Engine calls are expensive per Jip’s microbenches.
    • It seems like this would be called many times on many static marker nodes per tick.
      • Information does not change per tick though (assumedly).
    • If we’re not goalseeking or looking for safest, we return the precomputed closest node (I’m guessing it’s cached during setup from the markers/navgraph).
    • If we’re goalseeking, we return a subset of the original markers and again sort them by a goalseeking node distance.
      • sort key is not cached, so we may have redundant invocations of VDist2Sq this time.

Ideas

Depending on the frequency of calls, and the accuracy of recent microbenches:

1. Can we memoize threat computations by point for the current sim tick?
   • AIGetThreatLevelsAroundPoint is a moho method, assumed to be called many times for the markers. If we cache this per tick (even using a little LRU cache or having some memoization logic that clears caches on each tick) that’s a possible cost savings point for repeated searches.

     Since the marker information is static, and the threat information is static for the tick (assumably), it seems likely safe from concurrency issues (unless the simulation state mutates “within” a tick, then we have concurrency issues).

2. Locally cache the distance function to avoid redundant calls during sorting and computing testdistance.
   • As it stands, we do O(n*nlogn) distance function invocations of VDist3Sq. Caching/memoization would reduce that to O(n).
3. Given that we are performing what amounts to many nearest neighbor / range queries on spatial information derived from the graph relative to a radiuscheck, it seems plausible to reduce the current O(n) process of sorting and filtering nodes based on radius to something O(logN) with a range tree or similar datastructure. Even a simple precomputed hashgrid (or grids) of varying coarseness would alleviate radius checks and sorting.