scribble

Oasis

About     Blog     LinkedIn     GitHub    

20 Jul 2015
Remaking Tradewars - Part IV
Shortest Path Search

Shortest Path

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):

Dijkstra's Algorithm

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.


-B

scribble

About     Blog     LinkedIn     GitHub