The Travelling Gatherer (TTG) is a route optimization tool for herbalism and mining in World of Warcraft (WoW) Classic.
This site has come about because it was not satisfying to loosely draw a loop on a map mentally for my herbing routes. The desire was to not have an "OK" herbing route, but the mathematically perfect route. Turns out this is actually a difficult problem.
The problem is known as the "Traveling Salesman Problem" (TSP) in mathematics and is an "NP Complete" problem making it one of the most fundamental unsolved problems in computer science today. Put simply, the only way to truly know if you have the shortest path between each point is to calculate every possible path and check them, but this number gets big very, very quickly. For n nodes the number of paths to check is (n-1)!/2. For example, there are 50 Dreamfoil nodes in Ungoro and therefor over 30,414,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible paths between nodes to check.
This problem is made harder by the fact we don't want to ride to the exact point the herb spawns, that would be a waste of time. We only need to ride close enough to the node to see if it has spawned. So we don't want to find a path to each point, but a path to areas around the point. Extending the TSP problem to areas instead of points is pretty cutting edge maths (that I don't understand).
To get around these complications, first this tool doesn't find paths between areas but simply points. Each node has a packet of points the algorithm searchers, the center point where the herb is and a number of points (k) on a circle with radius of (r). By default k = 6 in this tool and the radius is 80 yards because after testing, this is a conservative estimate of when a node will have popped on your mini map. You can change both these values in the advanced settings. Increasing k will give you slightly shorter/smoother routes but the computation cost goes up and returns start to fall relative to computation costs.
To avoid checking the still astronomical amount of possible paths the tool uses 3 algorithms. Starting from the bottom right node it will first run a Nearest Neighbor algorithm. You can read about this on the wiki but its an "OK" path that is a good first shot and very cheap to calculate. (You can view this path in the advanced settings). Second, the tool then runs a restricted 3-Opt algorithm to optimize the nearest neighbor path. For something like Dreamfoil in Ungoro this algorithm ends up checking only 71,000 paths and has been found to generally return the shortest route, or something very close to it. FInally, we tweak the optimized route to the edge of the spawn visibility circles instead of directly on the node spawn.
Once an optimal path is found, the tool can then drop the "worst" nodes in order to speed up your farming route. Worst nodes here are defined as nodes that drag up the average distance you have to run between nodes. E.g. in an Ungoro Dreamfoil run there are 3 extreme nodes to the north, south and east that drag up the average run time of the route. By dropping them from the route the nodes visited per hour rises from 303 to 316. (You should still check all nodes occasionally to prompt re-spawns on the faster sections of the route).
Big thanks to Nevceiriel for maintaining GatherMate2, standing on shoulders of giants here.
Importantly, the node coordinates are currently taken from the "Spinx GatherMate 2 Data (Classic)" addon. It has come to my attention that this dataset is (a) missing some nodes (b) full of retail nodes that don't actually spawn in classic. This is a problem, not just for this tool but the classic community in general that we don't have a clean data set of classic nodes. Please get in touch if you believe you have a superior node dataset.
This tool was developed by Tunder on Alliance Whitemane US. If you happen to like the tool you can send appreciation or suggestions there.
02.01.2020 - Initial launch.
05.01.2020 - Updated algorithm, tests show its about 5% slower but finds routes that are 0.5% shorter. Implemented node dropping feature to increase node/hour while farming by dropping farthest nodes, use the "Trim" button that appears after finding a route. Added options for selecting different speed buffs in advanced settings. Fixed how the map renders on smaller screens (I wouldn't run this on your phone though it needs too much compute).