Performance fixes

[jocopa3]

Optimized pathfinding as much as I could without making any major refactors:

• Preloads all transports at startup and filters transports based on config settings before pathfinding rather than during. This saves a bit of time for each search and makes adding more transports a bit less expensive.
  • Transport options still function the same; PathfinderConfig.useTransport already checked if it should use various modes of transport so the checks in Transport.fromResources were redundant.
• Optimize data structures:
  • Using a HashSet for tracking visited nodes was expensive taking up 50% of the total execution time. I've replaced this with VisitedTiles which behaves the same but with significantly less overhead (and fewer allocations :) ).
  • Replaced LinkedList with ArrayDeque. ArrayDeque uses a circular array so inserting elements to the front or back of the queue is free. I've set conservative initial capacities for both queues that should avoid the need to grow either queue during the search.
• Remove SplitFlagMap.Position and used a packed Integer instead. Doesn't help performance all too much but significantly cuts back on the amount of data being allocated per search.
  • Using a sparse array instead of a HashMap for the compressedRegion map would likely speed up lookups but I don't think it's necessary as the cache lookups are the main performance cost.
• Cache OrdinalDirection.values() as every call makes an array copy despite the values never changing. This hurt both runtime performance and made many unnecessary allocations.
• PathfinderConfig.isInWilderness() is moderately expensive and makes many allocations so I avoid calculating it or cache the target wilderness status when possible.

Results

Ran through a bunch of different paths short and long in-game to make sure the resulting path is still the same as OSRS's pathfinding.

Worst-Case test: from GE to top-left corner of the map in the middle of the ocean Short-Case test: from GE to a point just west 105 tiles away

Ran a few paths before-hand to warm-up the JVM before recording results. Screenshots are of the Intellij profiler of both CPU Samples and Memory Allocations

System used is an Intel i9-13900K with 64GB DDR5 RAM, OpenJDK 11.0.12.0 (a bit out of date). While not the average system by far, results should scale similarly on other machines.

Metric	Before (1740a91)	After (6137611)	Difference
Worst-Case Time	2200.5582ms	1224.3621ms	976.1961ms
Short-Case Time	44.2161ms	28.5745ms	15.6416ms
Allocations	3,741,112,192 bytes	1,314,359,520 bytes	2,426,752,672 bytes

Before Optimizations

Worst-Case: 2200.5582ms Short-Case: 44.2161ms

CPU Samples (Worst-Case):

Memory Allocations (Worst-Case):

After Optimizations

Worst-Case: 1224.3621ms Short-Case: 28.5745ms

CPU Samples (Worst-Case):

Memory Allocations (Worst-Case):

[Skretzo]

I fixed two small bugs in a1f5ed56ff329663fa2cc62eebd15a63e6462463 and 1f0f115cedb05c528fa0fbb8d0343681d1321a3b, so there are a few conflicts you will need to resolve.

[jocopa3]

Addressed comments and cleaned up a few minor things.

[Skretzo]

Could you please resolve the conflicts in ShortestPathPlugin.java, Pathfinder.java and PathfinderConfig.java so that this PR is up to date with your threading fixes that I merged

[Skretzo]

I can't seem to spot exactly where, but when testing this PR the Avoid wilderness option in the config no longer makes any difference for the pathfinding. When this option is enabled the path should not use the wilderness lever to go from Edgeville to Ardougne.

[jocopa3]

the Avoid wilderness option in the config no longer makes any difference for the pathfinding

I've found and fixed this though there are some weird results like below; I'm not sure if this is expected or not but it seems like a quirk of the closest-point heuristic:

Performance wise in the worst-case, runtime speed is the same with/without due to the reduction in search space while allocations rose to 1,402,018,656 bytes from 1,314,359,520 bytes. Allocation impact can be eliminated with the WorldPoint packing optimization I've mentioned but I'm not going to do that in this PR.

[Skretzo]

I'm not sure if this is expected or not but it seems like a quirk of the closest-point heuristic

Believe it or not, but the path you got right there is more or less correct. You probably had Avoid wilderness enabled and Use fairy rings disabled. I have not added all agility shortcuts and teleports in the game yet, so the closest dungeon to the location you picked out in the ocean (cyan mark) was therefore Tarn's Lair (green circle), which requires a bit of a winding path through Morytania and the Haunted Mine when starting at the GE (blue circle) and with the Wilderness being forbidden (red cross).

If you want a better map than the world map in-game I would highly recommend https://mejrs.github.io/osrs. That map allows you to see all the dungeons up north of the main world, as well as displaying coordinates, labels, crowdsourced transport locations, objects, nomove tiles and npc information.