Waypoint Travelling Salesman Variation

[Kamien.3865]

Travelling salesman is an old problem. Getting around Tyria without waypoints is too. I was thinking about how to come up with something that allows a user to enter a starting waypoint and ending waypoint and then gives them the shortest path to the end waypoint. I was thinking a good way to do this was in to incorporate a version of routing tables and ARP discovery. I don't know, maybe SQL would be better. All of this would be done outside of the game, so no interface would be needed or EULA concerns should apply. I am aware that waypoints unlock packages are for sale, but I would like to think that there are very smart people that play this game and could figure something like this out.

Any takers / thoughts?

Thanks.

[starlinvf.1358]

Talk to the developers of GW2timer.com. The site has a route planner for WP and event sequences, so its mostly a matter of creating nodes along areas that foot traffic uses as routes, and setting up the algorithm to use them to draw a path. One thing I would recommend is including height into your data set, so the algorithm can have an easier time of recognizing switch back routes and bridges via distance. You also want the ability to black list routes between nodes that have impassible obstacles, with the option to disable or tag it as needing something, such as Griffon or Skimmer, to be a valid route option. That probably needs more manual tweaking of route and node parameters, but would be a major selling point if made a feature.

[Steve The Cynic.3217]

@"Kamien.3865" said:Travelling salesman is an old problem. Getting around Tyria without waypoints is too. I was thinking about how to come up with something that allows a user to enter a starting waypoint and ending waypoint and then gives them the shortest path to the end waypoint. I was thinking a good way to do this was in to incorporate a version of routing tables and ARP discovery. I don't know, maybe SQL would be better. All of this would be done outside of the game, so no interface would be needed or EULA concerns should apply. I am aware that waypoints unlock packages are for sale, but I would like to think that there are very smart people that play this game and could figure something like this out.

Technological critique:

• ARP is a "flat" non-routable protocol(1), so it would have no place in an routing calculation.
• The routing tables themselves are the output of a routing calculation. The routing calculation might be interesting as an element in the solution, though.
• SQL is a database query language, originally "Structured Query Language", and is not well-suited to this kind of work. (It might be useful as a way of managing storage, but not in the actual calculations.)
• The most likely possibility is to look at things like Dijkstra's route-finding algorithms, as these take into account measures of "cost".
• Another source of inspiration would be the class of calculations made by e.g. Google Maps when you ask for a route from one address to another.
• Route calculations for crossing Verdant Brink are likely to be difficult owing to the fragmented nature of the terrain.

(1) The purpose of the Address Resolution Protocol is to find the Ethernet ("MAC") address associated with an IP address in your immediate area. If the "real" target address is outside the immediate numbering scheme (e.g. the message is going to 8.8.8.8 - Google DNS - and your local network is 192.168.1.stuff), then you first find the "gateway" that lets you exit from the local area network (often, in this schema, 192.168.1.1), and use ARP to find its Ethernet address. Routers do not forward ARP requests because there isn't enough information in them or the responses to allow the request-response sequence to be "routed" back to the originator.