In the game Lord of the Rings Online (https://www.lotro.com) there are lots of quest that can be stacked for the proximity of the goals to one another. Many of the Exploration and Treasure Chest locations are like that. I use the resources from Lotro-Wiki (https://lotro-wiki.com) to assist in check listing and making sure I hit all the right spots.
Many times I get the results in separate list and I get to mentally make sure to keep track of the paths I need to take to get to them all. I decided to do a bit of exercise and see if it were possible to list the coordinates of the locations from the image, stack the locations of multiple images, make a (potentially shortest) route from the coordinate list and plot that path on the map.
This is the result.
Quick outline...
- Get and prep data.
- Use ImageStack.py to create combined places on a map.
- Use PlotShortestPath.py to find x,y coordinates and add a path to a new map image.
- Go travel the route! : )
Get and prep data
I started with two screen captured images. From https://lotro-wiki.com/wiki/New_Threats_in_Adag%C3%ADm you can mouse over the coordinates table (lower in the page) and capture the map image. I saved this as map1.png
Then I got a second map from https://lotro-wiki.com/wiki/Treasure-seeker_of_Adag%C3%ADm similarly. I saved this as map2.png
A bit of manual adjustment of the images to align the images so that they overlap as accurately as possible. I used Microsoft's Paint to move the images to 0,0, and resized the images to match.
Use ImageStack.py
source: https://github.com/LesleyPhillips/py-ImageStack
I put map1 and map 2 in to a directory with ImageStack.py an from the shell prompt executed the code to produce combined_map.png
Use PlotShortestPath.py
Source: https://github.com/LesleyPhillips/py-PlotShortestPath
I made a copy of combined_map.png to map.png and ran the code creating nearest_neighbor_path.png.
Pick a starting point and do the route! : )
Some follow up items
I was hoping to get the swirlies.
The proximity of near dots appear as one.
A Note on Code
In PlotShortestPath there is a rem'd bit for a suggested Traveling Salesman Problem (TSP) solver. Given my plot of 27 points, the number of permutation is 27!. Even at about a billion routes per second it will take about 3.4*10^11 years. So... I'm not doing that.
27!/10^9per sec ≈ 3.4*10^11
However, working by walking through the list of plot points, as start points, and going to the next nearest unvisited point in the plot point list, you get a list of routes. Pick the shortest of routes from the list and you'll be pretty close. I feel that there are some folks much better at maths that may have a suggestion or two. : )
