Last active
December 30, 2022 19:14
-
-
Save apocalyptech/7029b93c71ab5bd58744cac9f64bb934 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/env python3 | |
| # vim: set expandtab tabstop=4 shiftwidth=4: | |
| # Copyright 2022 Christopher J. Kucera | |
| # <cj@apocalyptech.com> | |
| # <https://apocalyptech.com/contact.php> | |
| # | |
| # This script is free software: you can redistribute it | |
| # and/or modify it under the terms of the GNU General Public License | |
| # as published by the Free Software Foundation, either version 3 of | |
| # the License, or (at your option) any later version. | |
| # | |
| # This script is distributed in the hope that it will | |
| # be useful, but WITHOUT ANY WARRANTY; without even the implied | |
| # warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
| # See the GNU General Public License for more details. | |
| # | |
| # For a full copy of the GNU General Public License, see | |
| # <https://www.gnu.org/licenses/>. | |
| import os | |
| import sys | |
| import argparse | |
| try: | |
| import colorama | |
| have_colorama = True | |
| except ModuleNotFoundError: | |
| have_colorama = False | |
| # I'm sure this code is stupid in tons of ways, but it should hopefully | |
| # be mostly comprehensible. | |
| class System: | |
| """ | |
| A single system in Gemini sector. Includes a `cur_count` attr which we | |
| use to find the shortest paths; that needs to be None'd out inbetween | |
| runs if computing more than one path. (The Gemini class takes care of | |
| that.) | |
| """ | |
| def __init__(self, name, label): | |
| self.name = name | |
| self.label = label | |
| self.links = set() | |
| self.cur_count = None | |
| def __repr__(self): | |
| return f'System<{self.name}>' | |
| def __lt__(self, other): | |
| return self.label.casefold() < other.label.casefold() | |
| def do_count(self, count=0): | |
| """ | |
| Recursively compute distances from ourselves, starting from the given | |
| `count` distance. If `count` is zero, we're computing distances from | |
| ourselves. Make sure that all Systems' `cur_count` attrs are set to | |
| `None` before running this, or you'll get nonsensical results! | |
| """ | |
| self.cur_count = count | |
| count += 1 | |
| set_links = set() | |
| for link in self.links: | |
| if link.cur_count is None or link.cur_count > count: | |
| link.cur_count = count | |
| set_links.add(link) | |
| for link in set_links: | |
| link.do_count(count) | |
| def trace_back(self, history=None): | |
| """ | |
| Yields a list of systems describing the shortest paths from the system | |
| with a `cur_count` of zero to ourselves. This is the other half of our | |
| pathfinding -- basically you'd call `do_count()` on the system you're | |
| going *from*, and then loop through the results of `trace_back()` on | |
| the system you're going *to*, to get the shortest routes between them. | |
| So, would yield nonsensical results if `do_count()` hasn't been run | |
| prior to running this. | |
| """ | |
| if history is None: | |
| history = [] | |
| else: | |
| history = list(history) | |
| history.append(self) | |
| if self.cur_count == 0: | |
| yield list(reversed(history)) | |
| else: | |
| for link in self.links: | |
| if link.cur_count < self.cur_count: | |
| for path in link.trace_back(history): | |
| yield path | |
| class Gemini: | |
| """ | |
| Class to hold info about the whole sector. Basically just a glorified dict | |
| with a few other methods attached. | |
| """ | |
| def __init__(self): | |
| self.systems = {} | |
| def __getitem__(self, val): | |
| return self.systems[val] | |
| def __contains__(self, val): | |
| return val in self.systems | |
| def __iter__(self): | |
| return iter(self.systems.values()) | |
| def add(self, *args): | |
| """ | |
| Add a new System | |
| """ | |
| new_system = System(*args) | |
| self.systems[new_system.name] = new_system | |
| def link(self, from_sys_name, to_sys_name): | |
| """ | |
| Add a jump link between two Systems (by name) | |
| """ | |
| from_sys = self[from_sys_name] | |
| to_sys = self[to_sys_name] | |
| from_sys.links.add(to_sys) | |
| to_sys.links.add(from_sys) | |
| def count_from(self, from_sys_name): | |
| """ | |
| Computes distances from the specified System name. Will populate all | |
| System `cur_count` attrs, starting with `0` for the given system. | |
| """ | |
| # Clear out counts and run a new one | |
| for system in self.systems.values(): | |
| system.cur_count = None | |
| from_sys = self[from_sys_name] | |
| from_sys.do_count() | |
| def paths(self, from_sys_name, to_sys_name): | |
| """ | |
| Returns a list of shortest-paths between the two named Systems. The | |
| paths themselves will be lists of Systems, and should all be of the | |
| same length. Obvs. many routes will only have a single shortest route, | |
| so you may very well see only a single list returned. | |
| """ | |
| # Count | |
| self.count_from(from_sys_name) | |
| # Now go backwards | |
| to_sys = self[to_sys_name] | |
| return list(to_sys.trace_back()) | |
| def report_paths(self, from_name, to_name, do_color=False): | |
| """ | |
| Report the shortest path(s) between the two named systems, to the terminal. | |
| If we've been told to colorize, will use colorama to provide some visual | |
| embellishment. Start+end will be bold, any shared system between all | |
| possible paths will be green, and any steps which differ between any paths | |
| will be yellow. | |
| Since I highly doubt anyone but myself will ever use this, the colors are | |
| hardcoded to look good on my usual black-text-on-white-background terminals. | |
| I realize this makes me a social pariah. They'll probably look too dim on | |
| black-background terminals. | |
| """ | |
| if do_color: | |
| endpoint = colorama.Style.BRIGHT | |
| same = colorama.Fore.GREEN + colorama.Style.DIM | |
| different = colorama.Fore.YELLOW + colorama.Style.DIM | |
| else: | |
| # These'll never get used so we could omit 'em, but whatever. | |
| endpoint = '' | |
| same = '' | |
| different = '' | |
| paths = self.paths(from_name, to_name) | |
| # Figure out which colors to display at each step | |
| colors = [] | |
| for step in zip(*paths): | |
| if do_color: | |
| if len(colors) == 0: | |
| colors.append(endpoint) | |
| elif len(colors) == len(paths[0])-1: | |
| colors.append(endpoint) | |
| else: | |
| step_set = set(step) | |
| if len(step_set) == 1: | |
| colors.append(same) | |
| else: | |
| colors.append(different) | |
| else: | |
| colors.append('') | |
| if len(paths) == 1: | |
| path_plural = '' | |
| else: | |
| path_plural = 's' | |
| if len(paths[0]) == 2: | |
| jump_plural = '' | |
| else: | |
| jump_plural = 's' | |
| print('Got {} path{} with {} jump{}:'.format( | |
| len(paths), | |
| path_plural, | |
| len(paths[0])-1, | |
| jump_plural, | |
| )) | |
| for path in paths: | |
| print('') | |
| first = True | |
| for color, system in zip(colors, path): | |
| if first: | |
| first = False | |
| prefix = '' | |
| else: | |
| prefix = '-> ' | |
| print(f'{prefix}{color}{system.label}') | |
| print('') | |
| def report_nums(self): | |
| """ | |
| Report the current `cur_count` attrs for all Systems, to the terminal. | |
| """ | |
| for system in sorted(self.systems.values()): | |
| print(f'{system.label}: {system.cur_count}') | |
| def populate_gemini(): | |
| """ | |
| Base map data. Does *not* include Exploratory Services or Righteous Fire | |
| systems! Those just get added in by hand in main() | |
| """ | |
| # Obj | |
| gemini = Gemini() | |
| # Systems | |
| gemini.add('rygannon', "Rygannon") | |
| gemini.add('xytani', "Xytani") | |
| gemini.add('palan', "Palan") | |
| gemini.add('new_caledonia', "New Caledonia") | |
| gemini.add('17_ar', "17-AR") | |
| gemini.add('telar', "Telar") | |
| gemini.add('j900', "J900") | |
| gemini.add('sherwood', "Sherwood") | |
| gemini.add('regallis', "Regallis") | |
| gemini.add('crab_12', "Crab-12") | |
| gemini.add('capella', "Capella") | |
| gemini.add('famine', "Famine") | |
| gemini.add('death', "Death") | |
| gemini.add('valhalla', "Valhalla") | |
| gemini.add('pestilence', "Pestilence") | |
| gemini.add('war', "War") | |
| gemini.add('castor', "Castor") | |
| gemini.add('nexus', "Nexus") | |
| gemini.add('km_252', "KM-252") | |
| gemini.add('freyja', "Freyja") | |
| gemini.add('pyrenees', "Pyrenees") | |
| gemini.add('cm_n1054', "CM-N1054") | |
| gemini.add('prasepe', "Prasepe") | |
| gemini.add('pollux', "Pollux") | |
| gemini.add('troy', "Troy") | |
| gemini.add('penders_star', "Pender's Star") | |
| gemini.add('junction', "Junction") | |
| gemini.add('119ce', "119CE") | |
| gemini.add('pentonville', "Pentonville") | |
| gemini.add('padre', "Padre") | |
| gemini.add('varnus', "Varnus") | |
| gemini.add('blockade_point_alpha', "Blockade Point Alpha") | |
| gemini.add('tr_pakh', "Tr'Pakh") | |
| gemini.add('sumn_kpta', "Sumn-Kp'ta") | |
| gemini.add('hyades', "Hyades") | |
| gemini.add('ragnarok', "Ragnarok") | |
| gemini.add('perry', "Perry") | |
| gemini.add('tingerhoff', "Tingerhoff") | |
| gemini.add('midgard', "Midgard") | |
| gemini.add('rikel', "Rikel") | |
| gemini.add('cmf_a', "CMF-A") | |
| gemini.add('nitir', "Nitir") | |
| gemini.add('blockade_point_tango', "Blockade Point Tango") | |
| gemini.add('mah_rahn', "Mah'Rahn") | |
| gemini.add('lisacc', "Lisacc") | |
| gemini.add('blockade_point_charlie', "Blockade Point Charlie") | |
| gemini.add('surtur', "Surtur") | |
| gemini.add('new_constantinople', "New Constantinople") | |
| gemini.add('44_p_1m', "44-P-1M") | |
| gemini.add('41_gs', "41-GS") | |
| gemini.add('newcastle', "Newcastle") | |
| gemini.add('new_detroit', "New Detroit") | |
| gemini.add('nd_57', "ND-57") | |
| gemini.add('manchester', "Manchester") | |
| gemini.add('raxis', "Raxis") | |
| gemini.add('auriga', "Auriga") | |
| gemini.add('metsor', "Metsor") | |
| gemini.add('aldebaran', "Aldebaran") | |
| gemini.add('hinds_variable_n', "Hind's Variable N.") | |
| gemini.add('dn_n1912', "DN-N1912") | |
| gemini.add('xxn_1957', "XXN-1957") | |
| gemini.add('oxford', "Oxford") | |
| gemini.add('shangri_la', "Shangri La") | |
| gemini.add('saxtogue', "Saxtogue") | |
| # Links | |
| gemini.link('rygannon', 'xytani') | |
| gemini.link('xytani', 'palan') | |
| gemini.link('j900', 'telar') | |
| gemini.link('telar', '17_ar') | |
| gemini.link('17_ar', 'new_caledonia') | |
| gemini.link('telar', 'valhalla') | |
| gemini.link('new_caledonia', 'sherwood') | |
| gemini.link('sherwood', 'regallis') | |
| gemini.link('new_caledonia', 'crab_12') | |
| gemini.link('crab_12', 'capella') | |
| gemini.link('capella', 'nexus') | |
| gemini.link('nexus', 'km_252') | |
| gemini.link('sherwood', 'capella') | |
| gemini.link('sherwood', 'famine') | |
| gemini.link('famine', 'death') | |
| gemini.link('death', 'pestilence') | |
| gemini.link('pestilence', 'war') | |
| gemini.link('famine', 'capella') | |
| gemini.link('freyja', 'pyrenees') | |
| gemini.link('pyrenees', 'cm_n1054') | |
| gemini.link('pyrenees', 'troy') | |
| gemini.link('troy', 'penders_star') | |
| gemini.link('penders_star', 'junction') | |
| gemini.link('junction', '119ce') | |
| gemini.link('119ce', 'pentonville') | |
| gemini.link('119ce', 'padre') | |
| gemini.link('regallis', 'freyja') | |
| gemini.link('j900', 'junction') | |
| gemini.link('sherwood', 'pollux') | |
| gemini.link('castor', 'junction') | |
| gemini.link('nexus', 'junction') | |
| gemini.link('new_caledonia', 'prasepe') | |
| gemini.link('war', 'troy') | |
| gemini.link('regallis', 'troy') | |
| gemini.link('tingerhoff', 'cmf_a') | |
| gemini.link('cmf_a', 'nitir') | |
| gemini.link('nitir', 'blockade_point_tango') | |
| gemini.link('blockade_point_tango', 'mah_rahn') | |
| gemini.link('blockade_point_tango', 'lisacc') | |
| gemini.link('tingerhoff', 'perry') | |
| gemini.link('perry', 'midgard') | |
| gemini.link('midgard', 'rikel') | |
| gemini.link('perry', 'ragnarok') | |
| gemini.link('ragnarok', 'blockade_point_alpha') | |
| gemini.link('blockade_point_alpha', 'tr_pakh') | |
| gemini.link('tr_pakh', 'sumn_kpta') | |
| gemini.link('sumn_kpta', 'hyades') | |
| gemini.link('hyades', 'blockade_point_charlie') | |
| gemini.link('blockade_point_charlie', 'surtur') | |
| gemini.link('surtur', 'perry') | |
| gemini.link('perry', 'nitir') | |
| gemini.link('palan', 'tingerhoff') | |
| gemini.link('nexus', 'tingerhoff') | |
| gemini.link('44_p_1m', 'new_constantinople') | |
| gemini.link('new_constantinople', 'newcastle') | |
| gemini.link('newcastle', 'auriga') | |
| gemini.link('new_constantinople', 'aldebaran') | |
| gemini.link('aldebaran', 'hinds_variable_n') | |
| gemini.link('hinds_variable_n', 'dn_n1912') | |
| gemini.link('new_constantinople', 'xxn_1957') | |
| gemini.link('xxn_1957', 'oxford') | |
| gemini.link('oxford', 'shangri_la') | |
| gemini.link('new_constantinople', 'new_detroit') | |
| gemini.link('new_detroit', 'manchester') | |
| gemini.link('newcastle', 'metsor') | |
| gemini.link('metsor', 'xxn_1957') | |
| gemini.link('new_detroit', 'raxis') | |
| gemini.link('new_detroit', 'saxtogue') | |
| gemini.link('saxtogue', 'oxford') | |
| gemini.link('new_detroit', 'nd_57') | |
| gemini.link('new_detroit', 'xxn_1957') | |
| gemini.link('perry', 'newcastle') | |
| gemini.link('perry', 'new_detroit') | |
| gemini.link('surtur', '41_gs') | |
| gemini.link('rikel', 'new_detroit') | |
| gemini.link('rikel', '44_p_1m') | |
| gemini.link('varnus', 'new_constantinople') | |
| gemini.link('junction', 'new_constantinople') | |
| gemini.link('119ce', 'xxn_1957') | |
| # return | |
| return gemini | |
| def main(): | |
| """ | |
| Here we go! | |
| """ | |
| # Populate the system, and define our "extra" systems which might be added in | |
| gemini = populate_gemini() | |
| exploratory_systems = [ | |
| ('delta', 'Delta', ['rygannon']), | |
| ('beta', 'Beta', ['delta']), | |
| ('gamma', 'Gamma', ['beta']), | |
| ('delta_prime', 'Delta Prime', ['gamma']), | |
| ] | |
| rf_systems = [ | |
| ('eden', 'Eden', ['valhalla', 'rikel']), | |
| ] | |
| system_choices = sorted( | |
| [s.name for s in gemini] + | |
| [s[0] for s in exploratory_systems] + | |
| [s[0] for s in rf_systems] | |
| ) | |
| # Arguments | |
| if have_colorama: | |
| extra_epilog = '' | |
| else: | |
| extra_epilog = 'Install colorama to get some prettier output when showing paths' | |
| parser = argparse.ArgumentParser( | |
| description='Compute optimal routes in Wing Commander: Privateer / Righteous Fire', | |
| epilog=""" | |
| Requires setting either --from *and* --to, or just --max. (If | |
| --from or --to are specified at the same time as --max, they will | |
| be ignored.) By default this excludes the Exploratory Services | |
| systems (Delta, Beta, Gamma, and Delta Prime), and Righteous Fire | |
| systems (just Eden), but those can be included with the --exploratory, | |
| --rf, or --all options. | |
| """ + extra_epilog, | |
| ) | |
| parser.add_argument('-d', '--debug', | |
| action='store_true', | |
| help='Show extra debugging output', | |
| ) | |
| if have_colorama: | |
| help_txt = "Don't use color in path outputs (if applicable)" | |
| else: | |
| help_txt = "Don't use color in path outputs (color is already disabled since colorama is not available)" | |
| parser.add_argument('-n', '--no-color', | |
| action='store_false', | |
| dest='color', | |
| help=help_txt, | |
| ) | |
| parser.add_argument('-e', '--exploratory', | |
| action='store_true', | |
| help='Include Exploratory Services systems', | |
| ) | |
| parser.add_argument('-r', '--rf', | |
| action='store_true', | |
| help='Include Righteous Fire system (Eden)', | |
| ) | |
| parser.add_argument('-a', '--all', | |
| action='store_true', | |
| help='Include all "extra" systems', | |
| ) | |
| parser.add_argument('-f', '--from', | |
| dest='from_system', | |
| choices=system_choices, | |
| help='System to travel from', | |
| ) | |
| parser.add_argument('-t', '--to', | |
| dest='to_system', | |
| choices=system_choices, | |
| help='System to travel to', | |
| ) | |
| parser.add_argument('-m', '--max', | |
| action='store_true', | |
| help='Instead of finding a path, find the most distant systems', | |
| ) | |
| # Parse and check args | |
| args = parser.parse_args() | |
| if not args.max: | |
| if not args.from_system or not args.to_system: | |
| raise argparse.ArgumentTypeError('Either -m or both -f/-t are required') | |
| # Init color, if we have it | |
| if args.color and have_colorama: | |
| colorama.init(autoreset=True) | |
| # Add stuff to the sector, if asked to | |
| for arg, systems in [ | |
| (args.exploratory, exploratory_systems), | |
| (args.rf, rf_systems), | |
| ]: | |
| if args.all or arg: | |
| for name, label, links in systems: | |
| gemini.add(name, label) | |
| for link in links: | |
| gemini.link(name, link) | |
| if args.max: | |
| # This got pretty messy because I ended up adding a bunch of extra debug | |
| # output. It's also a bit messy because sets and lists aren't hashable, | |
| # so I have an intermediate string for the `results` keys. c'est la vie! | |
| results = {} | |
| starts = {} | |
| for system in gemini: | |
| gemini.count_from(system.name) | |
| max_inner = system | |
| full_inners = set() | |
| for inner in gemini: | |
| if inner.cur_count > max_inner.cur_count: | |
| max_inner = inner | |
| full_inners = {inner} | |
| elif inner.cur_count == max_inner.cur_count: | |
| full_inners.add(inner) | |
| if args.debug: | |
| print('Starting from {}, max is: {}'.format( | |
| system.label, | |
| max_inner.cur_count, | |
| )) | |
| if max_inner.cur_count not in results: | |
| results[max_inner.cur_count] = set() | |
| starts[max_inner.cur_count] = set() | |
| starts[max_inner.cur_count].add(system) | |
| for inner in full_inners: | |
| to_add = '|'.join([s.name for s in sorted([system, inner])]) | |
| if args.debug and to_add in results[inner.cur_count]: | |
| print(f'NOTICE: {to_add} already exists in set...') | |
| results[inner.cur_count].add(to_add) | |
| max_result = max(results.keys()) | |
| print(f'Furthest-apart systems are at distance: {max_result}') | |
| print('') | |
| print('Instances:') | |
| for result in sorted(results[max_result]): | |
| from_name, to_name = result.split('|') | |
| print(' * {} <-> {}'.format( | |
| gemini[from_name].label, | |
| gemini[to_name].label, | |
| )) | |
| print('') | |
| if args.debug: | |
| print('Full results:') | |
| print('--------------') | |
| print('') | |
| for val, paths in sorted(results.items()): | |
| print(val) | |
| print(paths) | |
| print('') | |
| print('Systems by how far you have to go to get Everywhere:') | |
| print('----------------------------------------------------') | |
| print('') | |
| for val, systems in sorted(starts.items()): | |
| print(val) | |
| print(', '.join(sorted([s.label for s in systems]))) | |
| print('') | |
| else: | |
| if args.from_system not in gemini: | |
| print(f'ERROR: {args.from_system} is not a valid system name') | |
| sys.exit(1) | |
| if args.to_system not in gemini: | |
| print(f'ERROR: {args.to_system} is not a valid system name') | |
| sys.exit(1) | |
| if args.debug: | |
| print('Immediate links from "from" map') | |
| print('-------------------------------') | |
| print('') | |
| print(gemini[args.from_system].links) | |
| print('') | |
| gemini.report_paths(args.from_system, args.to_system, args.color and have_colorama) | |
| if args.debug: | |
| print('Computed distances:') | |
| print('-------------------') | |
| print('') | |
| gemini.report_nums() | |
| print('') | |
| if __name__ == '__main__': | |
| main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment