Refactor: Pack WorldPoint into ints

[jocopa3]

Yet another performance PR.

RuneLite's WorldPoint and WorldArea are immutable meaning any modifications to to them create an entirely new object. While that's good practice from an API design standpoint, it's not so good for performance-critical code like pathfinding. This PR packs all uses of WorldPoint in the hotpath into ints to prevent unnecessary allocations.

Changes made:

• New WorldPointUtil with various helper functions to pack/unpack world points
  • Moved Node.distanceBetween here since it makes sense for that to live in a util file.
  • WorldPointUtil.distanceToArea should be guaranteed to match WorldArea.distanceTo. Added an additional test for clarity.
• Made a copy of PathfinderConfig.transports that uses the packed world point as a key. Doesn't copy the underlying lists so both transports and transportsPacked hold the same list references.
• Pathfinder no longer stores the entire path each time it finds a better one but instead stores the best last node in the path.
  • The path is lazily reconstructed and cached as needed rather than during the search.
• Removed instant and replaced with System.currentTimeMillis() to avoid making new Instant allocations.
• Decoupled CollisionMap from SplitFlagMap; SplitFlagMap is what stores data and is allocated once, CollisionMap holds a reference to SplitFlagMap and can be allocated once per thread.
  • Doing this allows me to remove the extra boolean[] and ArrayList allocations in getNeighbors without risk to thread-safety.
  • ThreadLocal incurs a hashmap lookup every time get() is called so I've also removed redundant calls to plugin.getMap().

Main allocation cost now is making new nodes and a few-other more minor things (can store a single boolean[] rather than make a new one each time; same with the neighbors ArrayList) (I've gone ahead and made this optimization, see first comment below). In theory, the node allocation cost can be addressed with an Object Pool (e.x. Apache Commons' SoftReferenceObjectPool), but it'd come with a not-insignificant runtime performance penalty.

Results

Same setup as usual. See comment below for latest results with the CollisionMap changes.

Worst-Case: GE to top-left corner in the ocean Didn't measure short-case this time as it doesn't make a huge difference for a small amount of nodes.

Forgive me for not including a table here, wanting to save some time. Overall this change ends up ~20ms faster with about 50% less allocated bytes (exact numbers in screenshots below).

Before

Worst-Case Time (Avoid Wilderness): 156.9508ms Worst-Case Time: 179.8608ms

Memory Allocations:

Memory Allocations (Avoid Wilderness):

After

Worst-Case Time (Avoid Wilderness): 134.7586ms Worst-Case Time: 156.9396ms

Memory Allocations:

Memory Allocations (Avoid Wilderness):

[jocopa3]

Update: refactored CollisionMap and SplitFlagMap a bit. CollisionMap is now it's own thing while SplitFlagMap is what stores map data. This allows me to make CollisionMap thread-local which in-turn means the boolean[] and ArrayList allocations in getNeighbors can be made stateful while remaining thread-safe. This comes at no extra cost for performance while reducing allocations even further.

Results

Worst-Case Time (Avoid Wilderness): 136.8438ms Worst-Case Time: 160.6458ms

Note: I don't think this is actually any slower than the last commit, I think the few ms difference between this result and the previous commit comes down to different workloads running on my machine.

Memory Allocations:

Memory Allocations (Avoid Wilderness):

[jocopa3]

Heads up: turns out the isNear check is redundant. It's meant to cancel pathfinding if the player isn't near the path, but it's already checked with near identical logic in onGameTick which calls setTarget(null) and cancels pathfinding/restarts pathfinding anyway. It seems it was only added to the pathfinder as there was no way to cancel pathfinding thread, but my previous threading change addressed that.

Allocations in the worst-case with Avoid Wilderness off now looks like:

I don't think additional optimization is needed after this. The only way to reduce this is to reduce the search space a la bidirectional BFS, but it's not super critical in my opinion. It's at a point where any other suggestions for optimization require making a tradeoff between runtime performance and memory allocation.

[jocopa3]

Addressed feedback and cleaned up some things that become unused after this PR.