Re:Game designer designs a game for 2,000 years from now, hi...
by ghshephard on Saturday May 25, 2013 @10:11PM
(#5769741)
TSP is relevant to graph traversal. "Something buried in the desert" has no (or at least, very little) restriction on how you move from node to node.
[T]he sheets of GPS coordinates were collected by GDC volunteers at the door in an attempt to collate the data, hopefully leading to the game's earlier discovery.
Gentlemen, start your Travelling Salesman algorithms. From a quick skim of the wikipedia page, 1M nodes is probably too many to solve exactly, but (might?) be within 1% via heuristic methods.
Then again, depending on the area the entire set of coordinates covers, dividing it into zones and computing TSP over each would be much more practical, and allow parallel searches by multiple groups.
I wonder if the creator wouldn't have been better off with a Geohashing[1] type location clue, but I'm struggling to think of a useful time-specific seed that is both resistant to precomputation, and likely to survive 2k+ years hence. The XKCD one uses the value of the Dow Jones average for industrial stocks, but I doubt it could be relied on for more than a few decades, or a century or three in a best case.
[1] http://wiki.xkcd.com/geohashing/Algorithm