20 Jul 2015
Remaking Tradewars - Part IV
Shortest Path Search
In the previous post, we generated a fully-connected graph of the universe that looks something like this.
Great, we have a fully connected graph!
In Tradewars, the goal is to travel from sector to sector, buying and selling goods. Some sectors might sell cheap Fuel, while others are willing to pay top dollar for Fuel. In that case, it would be wise to keep both sectors in mind for future reference. Next time you buy cheap fuel at Sector A, you can turn around and sell it at a high price at Sector B!
To make it slightly easier to travel from sector to sector, Tradewars offers a
jump command, whereupon it spits out the shortest path between Sector A and Sector B, then automatically pushes you along that path, pausing in each sector to give you time to stop the jump if you see something interesting. Incidentally, this is also a great way to explore the universe!
The first obstacle in the
jump command is finding the shortest path. There are a lot of ways to do this, but for now, we'll use something called Dijkstra's Algorithm. It's probably one of the better ways to find the shortest path in a graph like our universe, and it's relatively quick, too.
Here's the algorithm in pseudo-code, brazenly stolen from Wikipedia:
function Dijkstra(Graph, source): dist[source] ← 0 // Distance from source to source prev[source] ← undefined // Previous node in optimal path initialization for each vertex v in Graph: // Initialization if v ≠ source: // Where v has not yet been removed from Q (unvisited nodes) dist[v] ← infinity // Unknown distance function from source to v prev[v] ← undefined // Previous node in optimal path from source end if add v to Q // All nodes initially in Q (unvisited nodes) end for while Q is not empty: u ← vertex in Q with min dist[u] // Source node in first case remove u from Q for each neighbor v of u: // where v is still in Q. alt ← dist[u] + length(u, v) if alt < dist[v]: // A shorter path to v has been found dist[v] ← alt prev[v] ← u end if end for end while return dist, prev end function
In graphical form, it looks something like this (also stolen from Wikipedia):
There are some other variants of this, and I leave it as an experiment to the reader to try them out.
By passing in our Universe as the
Graph, and the starting sector as the
source, we can find all of the paths available. Finding the shortest path to a particular target is a matter of choosing the
target item from the resulting
dist that is returned from the function.
Tune in for Part V, when we talk about the next exciting module in Tradewars: outposts.