Monday, December 28, 2015

Holiday in the Endless Sky

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.