So for fun I've been playing Endless Sky. It's a nicely made re-implementation of the old EV Nova (which appears to be still available, although I'm not sure it would run in a current Mac OS).
Part of the early grind of Endless Sky, as it was for EV Nova, is to haul commodities from star to star, buying low and selling high, until you accumulate enough credits to buy a better ship. Each star has prices for ten different commodity types, and one of the first questions the player asks is, what route has the highest profit? (In EV Nova, there was one fabulously profitable one-hop route, the only problem being that you were almost guaranteed to be attacked by pirates every time through it.)
Endless Sky's galaxy is defined in a simple text file that is part of the game package (here's the source). I looked at it and thought, hmmm. The galaxy is an undirected graph; the commodity prices are properties of the nodes of the graph. This looks like a job for Python! So one morning I sat down in and in less than two hours, I had code to read and store the galaxy as a graph, and it worked first time! What follows is a slightly upgraded version, so it has about 2:30 invested in it.
import sys
try:
filename = sys.argv[1]
map_file = open( filename, 'rt', encoding='utf-8', errors='ignore' )
except:
print('usage: mapper <file path to the map file>')
exit(-1)
# map trade names to indexes in a system trade list
trade_indices = {
"Clothing" : 0,
"Electronics" : 1,
"Equipment" : 2,
"Food" : 3,
"Heavy Metals" : 4,
"Industrial" : 5,
"Luxury Goods" : 6,
"Medical" : 7,
"Metal" : 8,
"Plastic" : 9
}
trade_names = { d : n for n, d in trade_indices.items() }
# The galaxy is a dict of { 'system-name' : System } It is an undirected
# graph in which the edges are system-names in each system's links:
# for neighbor_name in Galaxy['some-name'].links:
# neighbor_system = Galaxy[neighbor_name]
Galaxy = dict()
class System( object ):
def __init__( self ):
self.trade = [0] * 10 # prices of 10 commodity types here
self.links = set() # names of connected systems
self.habitable = False # can trade here?
import regex
# The following matches to a pattern of either
# verb namestring [nnn]
# or
# verb "name string with spaces" [nnn]
rx_verb = regex.compile( '''^\s*(\w+)\s+((\w+)|['"]([\w\s]+)['"])(\s*\d+)?\s*$''', flags=regex.IGNORECASE )
# If the current line is "verb name [nnn]" return (verb, namestring, [nnn|None]).
# Otherwise return (None, None, None)
def match_line( line ):
match = rx_verb.match( line )
verb = None
namestring = None
number = None
if match is not None :
verb = match.group(1)
namestring = match.group(3) if match.group(4) is None else match.group(4)
number = match.group(5)
return (verb, namestring, number)
# Read the map, build the Galaxy
in_system = False
for line in map_file :
( verb, name_string, number ) = match_line( line )
if not in_system :
if verb == 'system' :
# Beginning a system block. Create a system and file it.
new_system = System()
Galaxy[name_string] = new_system
in_system = True
habitable = False
gov_not_Hai = True
continue
# Process "link", "trade", "government" and "object" statements
if verb == 'link' :
# new_system links to name_string. Note the map has reciprocal links,
# we do not need to add a reverse link. In fact we couldn't, because
# name_string may not be in the galaxy yet.
new_system.links.add( name_string )
continue
if verb == 'trade' :
# new system trade line found, store the price in the system list
commodity_index = trade_indices[ name_string ]
commodity_price = int( number )
new_system.trade[ commodity_index ] = commodity_price
continue
# Check "object name" statements. The regex only matches to "object
# name", not to the more common "object" statements. If a system has an
# object with a name, it is habitable. Except for Algiebra, which has
# a named moon but cannot be used for trade.
if verb == 'object' :
habitable = 'Watcher' != name_string #anywhere but Algiebra
continue
# Look for government starting with Hai, because those systems are not
# accessible until later in the game (this could be conditioned on a
# command-line option)
if verb == 'government' :
gov_not_Hai = not name_string.startswith( 'Hai' )
# if the current line is blank, we are at the end of this system.
if 0 == len(line.strip()) :
new_system.habitable = habitable and gov_not_Hai
in_system = False
continue
# Note the official map *ALWAYS* has a blank line at the end of a
# system block i.e. preceding a 'system' statement. If the map file
# is mis-edited to not have such a blank, this code will merge the
# trade etc. lines from the following system to the previous one.
# All map lines processed, the Galaxy is built.
With the galaxy as a graph, it took another hour to brute-force the best trade route of one, two, three or four hops. No longer route because the starter ship and the typical freighter can't go more than four hops without landing.
# Return the set of all system names that are n hops out from the given
# system.
def n_hop_targets( system, n ):
if n == 1 :
return set( system.links )
all_targets = set()
for target in system.links :
all_targets |= n_hop_targets( Galaxy[ target ], n-1 )
return all_targets
# Compare the trade price lists from two systems. Return the index
# of the most profitable commodity and the profit margin.
def compare_prices( buy_list, sell_list ):
profits = [ buy-sell for buy, sell in zip( buy_list, sell_list ) ]
p = max( profits )
return profits.index(p), p
# Find the most profitable trade route between a given system and any of a
# set of systems it can reach at some number of hops. Input is the system
# itself, and set of target names.
# return the system name and (outbound buy, profit, inbound buy, profit)
def best_trade_route( system, target_set ):
home_line = system.trade
out_p = in_p = 0 # outbound and inbound profits
out_c = in_c = None # outbound, inbound indexes
where = None # target system
for dest_name in target_set :
dest_sys = Galaxy[ dest_name ]
if dest_sys.habitable :
dest_line = dest_sys.trade
d_c, d_p = compare_prices( home_line, dest_line )
h_c, h_p = compare_prices( dest_line, home_line )
if (out_p + in_p) < (d_p + h_p) :
out_p, out_c = d_p, d_c
in_p, in_c = h_p, h_c
where = dest_name
return (where, out_c, out_p, in_c, in_p )
def best_n_hop(n):
best_name = None # name of winning start point
best_targ = None # name of its trade partner
best_info = (0, 0, 0, 0)
best_rt = 0 # round-trip profit
pdict = dict()
for name, system in Galaxy.items() :
if system.habitable :
where, out_c, out_p, in_c, in_p = best_trade_route(
system,
n_hop_targets( system, n )
)
if (out_p + in_p) > best_rt :
best_name = name
best_targ = where
best_info = ( out_c, out_p, in_c, in_p )
best_rt = out_p + in_p
pdict[best_rt] = (best_name,best_targ,best_info)
print( '\n\nBest', n, 'hop trade route is' )
print( best_name, 'to', best_targ )
print( 'outbound take', trade_names[ best_info[0] ], 'earning', best_info[1] )
print( 'inbound bring', trade_names[ best_info[2] ], 'earning', best_info[3] )
print( 'round-trip profit is', best_rt )
best_n_hop(1)
best_n_hop(2)
best_n_hop(3)
best_n_hop(4)
So before lunch I knew that I should trade Metals and Luxury Goods between Alphard and Delta Velorum. I took a certain amount of pleasure in having all that work quickly and easily.
My pleasure was rather lessened when I googled "Endless Sky best trade route" and found a forum post with exactly that route, found by some non-programmer weeks ago.
Oh, well.
