Some information

Inside World of Warcraft, one can engage in several different professions. These include professions that require you to go around the world and collect certain types of resources (Iron, Tin, Copper, etc for Mining, and different kinds of herbs for Herbalism for example).

While I enjoy the core-gameplay loop of World of Warcraft, I also find some piece in flying around the map gathering these resources (mining in my case). The game teaches us that certain resources are found in area’s linked to certain levels (Copper is found in low-levels, while Mithril is found in higher level zones). These resources are a one-time use: If you gathered it, it disappears. But, after a while, they can respawn in roughly the same location. The respawn location is random, but it’s always around the same spot. Let’s call the resource deposit a node.

The game allows for addons to be installed. One addon in particular is helpful for this: GatherMate2. Everytime I collect resources from a (mining)node (or any other node for that fact), GatherMate will log it to a file on disk. Over the course of multiple loops around the map, I’m left with a file that contains x-y coordinates of all the nodes I gathered inside a certain area. The other addon is TomTom. TomTom allows you to create in-game routes yourself.

The “problem”

As a human being, I can take a good guess as to what the optimal route would be to traverse, but is it correct? As a challenge for myself I decided to build a route planner to find out. The goal was simple: Build an application that is able to calculate the best route and return it into a format I can import into TomTom.

The solution

As a start I created an WPF application that would import the file from GatherMate2(GM). This was fairly easy to do and now I had, for each zone, a list of x-y coordinates for each different type of resource. Then I build up a simple UI where you could choose for which resource type you want to calculate the route. The options were made available based on the resources the application found within the imported GM file. Then I created a simple map that showed all the nodes that were loaded in.

I quickly realized that a potential issue was the amount of nodes. Because every node I gathered would be added to the collection, it potentially could grow to a map with thousands of nodes. For this I quickly implemented 2 types of node-grouping: one that simply checks if there are any other nodes withing a said amount of distance and one that does the same thing, but based on the Euclidean distance. The distance would be able to control with a slider. Say D=1, then:
x=10, y=10
x=10.8, y=9.4
x=11.4, y=10.9

Would result in 2 nodes:
x=10, y=10
x=11.4, y=10.9

This cleared up the map a lot. After this I implemented the most rudimentary form of route planning I could think of: the Nearest Neighbor. The concept is easy: Take the first node from the list. Look up all other nodes and return the node that is closest. Rinse and repeat. This resulted in a route that would be somewhat useful, but was far from optimal.

As you can see, it somewhat works, but it crosses over itself multiple times and provides long stretches of travel time without any nodes. To fix this we can implement another algorithm, to work alongside Nearest Neighbor: Two-Opt. The basic concept is that it will check the path between a certain node and the next. If the path crosses another path, it will swap two nodes around. Now that particular path will never cross over the other path again. It will do this for every node, over the entire list. This is a fairly expensive operation.

In theory we could keep doing this forever. To prevent this, we will record the length of the path every time we looped over all the nodes. After every loop, we will check the new distance against the previous one. If it’s shorter, we will run again. If the distance is the same, looping again won’t do much, so we know we can stop. This improves the route immensely:

Last thoughts

As you might see, I’ve also implemented some other algorithms to play around with, but none of these improved the results significantly. At least, not in relation to the performance cost.

On thing I also learned: Grouping might be one of the most important things. The saying is: Garbage in – Garbage out. This is also very true here. I have implemented a really simple method of grouping, which could be greatly improved and would deserve a separate project of it’s own. The same is for the value I use when grouping: To large and I will miss out on resource nodes. To small and the route that will be produce will be very impractical.

One final closing note: I want to revisit this project soon and try out something completely different: ant-simulation. When I get to it I will update this post with the results.