From: mdw Date: Wed, 22 Sep 2004 17:52:04 +0000 (+0000) Subject: Add elite-tantalus. Add a developer guide. X-Git-Tag: 1.1.5~1 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/rocl/commitdiff_plain/74bdd262742db2f0b2b97375ece36f2962bfeb52?hp=c53e2dd3a5c32cb945a0a68dd96161badb4d14eb Add elite-tantalus. Add a developer guide. --- diff --git a/DEVGUIDE b/DEVGUIDE new file mode 100644 index 0000000..6561dc7 --- /dev/null +++ b/DEVGUIDE @@ -0,0 +1,269 @@ +RIGHT ON COMMAND LINE + Developer's guide + + +Package `elite' + + elite-nextworld SEED + Given a world seed, compute and return the seed of the next + world in the galaxy. + + elite-nextgalaxy + Given a galaxy seed, compute and return the seed of the next + galaxy. + + elite-worldinfo ARR SEED + Given a world seed, compute information about the world and + return it in the array ARR. Any existing stuff in the variable + ARR is destroyed. Information is written to the elements of ARR + as follows. + + x in decilightyears from galaxy left + y in decilightyears from galaxy top + government as integer: 0 .. 7 are anarchy .. corp-state + economy as integer: 0 .. 7 are rich-ind .. poor-agri + techlevel the tech level, + population in 100 million + productivity in M Cr + radius in km + seed for the sake of competeness + inhabitants as a string + name capitalized + description a complete sentence + + The array `government' maps integers 0 to 7 to human-readable + strings describing the various government types; `gov' maps them + to short space-free tokens. Similarly, the arrays `economy' and + `eco' map integers to economy types. + + elite-market ARR SEED [FLUC] + Given a world seed and an optional fluctuation (0 .. 255; + default is 0) compute the market prices at the world and store + then in the array ARR. Existing stuff in ARR is destroyed. + The indices of the array are product symbols; the values are + two-element lists containing the price and quantity available. + Product names are: + + food textiles radioactives slaves liquor-wines + luxuries narcotics computers machinery alloys + firearms furs minerals gold platinum gem-stones + alien-items + + The list `products' alternates these symbols with human-readable + product names. + + elite-unpackcmdr [-force] ARR DATA + Unpack a commander file into an array. If `-force' is given, + don't complain about bad checksums or nonzero trailing bytes. + DATA is a string containing the file's data. ARR is an array to + write to; it is destroyed beforehand. Values are stashed as + follows: + + mission mission status code + world-x in dly from left + world-y in dly from top + gal-seed + credits in tenths of a credit + fuel in tenths of a lightyear + gal-number 1 .. 8 seem sensible + + front-laser bits 0 .. 6 are power; bit 7 is + rear-laser rapid-fire. none = 0; pulse = 15; + left-laser beam = 15 + rapid; mil = 23 + rapid; + right-laser mining = 50 + + cargo capacity in tonnes + + market-fluc 0 .. 255; determines prices + hold-PRODUCT quantity of product in hold + station-PRODUCT quantity of product at station + + ecm just true or false + fuel-scoop + energy-bomb + energy-unit + docking-computer + gal-hyperdrive + escape-pod + + missiles number; 0 .. 4 are usual + legal-status 0 = clean; 1 .. 49 = offender; + 50+ = fugitive + + score number + 0 .. 7 harmless + 8 .. 15 mostly harmless + 16 .. 31 poor + 32 .. 63 average + 64 .. 127 above average + 128 .. 511 competent + 512 .. 2559 dangerous + 2560 .. 6399 deadly + 6400+ elite + + elite-packcmdr ARR + Given an unpacked array, as described above, construct and + return the packed commander file. + + elite-distance X Y XX YY + Compute the distance between two points (X, Y) and (XX, YY), + expressed in decilightyears, according to the slightly strange + algorithm used by the game. The answer is in decilightyears. + + elite-galaxylist SEED + Return a list of 768 elements which are the seed/x/y for each + world in the galaxy whose seed is SEED. + + elite-adjacency ADJ LIST [DIST] + Given a list in the form returned by `elite-galaxylist', store + an adjacency map in ADJ. The DIST (by default 70) is the + maximum distance between two worlds for them to be considered + adjacent. On exit, ADJ is an array mapping seeds to seed/x/y + lists of adjacent worlds. + + galaxy N [SEED] + Returns the seed of the Nth galaxy, starting counting with SEED + as galaxy 1. The default SEED is the standard galaxy 1. + + foreach-world GAL ARR SCRIPT + For each world in the galaxy GAL, set ARR to information about + the world (see elite-worldinfo) and evaluate script. + + find-world GAL PAT + Return a list of the worlds in galaxy GAL whose names match the + glob-pattern PAT. + + destructure PAT LIST + Destructure LIST according to PAT. If PAT is a single name, set + the variable PAT to be LIST; otherwise if PAT is a list, + destructure each element of LIST according to the corresponding + element of PAT. If PAT is `.' then do nothing. It is not an + error if PAT is shorter than LIST -- trailing elements are + simply ignored. + + write-file NAME CONTENTS [TRANS] + Safely write CONTENTS to the named FILE using the given + TRANSlation (default binary). The file is replaced atomically; + if there is an error then the file is not damaged. + + read-file NAME [TRANS] + Return the contents of the named FILE according to the given + TRANSlation (default binary). + + nearest-planet WW X Y + Return the seed of the `nearest' planet given in the seed/x/y + list WW to the point (X, Y). + + worldname W + Return the name of the world with seed W. + + shortest-path ADJ FROM TO WEIGHT + Computes the shortest path and shortest distance between the + worlds FROM and TO (both seeds). ADJ must be an adjacency table + (e.g., as computed by elite-adjacency) for the galaxy containing + both worlds. WEIGHT is a command such that WEIGHT A B returns + the weighting (`distance') for a hop from A to B (both seeds). + The return value is a list P D, where D is the total path + weight, and P is a list of seeds, starting with FROM and ending + with TO, for the route. This uses Dijkstra's shortest-path + algorithm. For the Floyd-Warshall all-points shortest-path + algorithm, see graph-shortest-path below. + + weight-hops, weight-fuel, weight-safety, weight-encounters, + weight-trading + Various standard weighting functions. + + parse-galaxy-spec G + Parses a galaxy-spec G and returns a list containing a + description of the galaxy and the seed. If G is not a valid + galaxy-spec then return an empty list. + + parse-planet-spec G P + Parses a planet-spec P relative to a galaxy seed G, and returns + the planet seed or an empty string if P is invalid. + + in-galaxy-p G PP + G is a galaxy; PP is a list of planet seeds. Return true if all + seeds in PP are in G. It's not a problem if the seeds in PP + aren't valid. + + world-summary P + Produce a standard one-line summary of information about the + world P (a seed). + + jameson ARR + Populate ARR with the standard Commander Jameson. + +Package `vector' + + A `vector' is a fixed-size multidimensional array with integer + indices, whose values may be arbitrary Tcl objects. + + vector LIST [INIT] + Construct and return a new vector whose dimensions are in LIST, + and whose initial contents are INIT. The vector is a command; + you can mess with it further using its subcommands. + + VEC get INDEX ... + VEC lget LIST + VEC rget INDEX + Return the element at the given index. The first form reads + indices from successive arguments; the second collects a list of + arguments; the final takes a single `raw' index. Vectors use + row-major indexing. + + VEC set INDEX ... VALUE + VEC lset LIST VALUE + VEC rset INDEX VALUE + Store VALUE in the given place in the vector. + + VEC destroy + Destroy the vector VEC. Equivalent to saying rename VEC {}. + + VEC bounds + Returns the dimension list for VEC. + + VEC size + Returns the upper (exclusive) limit on raw indices (to rset or + rget). + +Package `graph' + + graph-shortest-path VEC + Compute the all-points shortest-paths for VEC, which is an + adjacency matrix: i.e., VEC get I J is the distance from node I + to node J, or -1 if there is no direct route from I to J. The + adjacency matrix can be asymmetric -- the distance from I to J + need not be equal to the distance from J to I. + + The return value is a pair of vectors, named LEN and PATH. The + length of the shortest path from I to J is then vec LEN I J; the + first hop is to vec PATH I J -- if we say that's node K then the + shortest path from I to J is I, K, and then the shortest path + from K to J. + + graph-travelling-salesman [-OPTIONS] ADJ LIST + Find a short route touring all the nodes in LIST. ADJ is an + adjacency matrix as for graph-shortest-path, except that it must + be complete -- no -1 entries. (graph-shortest-path is a handy + way of arranging this.) + + -cycle / -nocycle If -cycle (the default) then find a + cyclic path; if -nocycle then start at + the first node in LIST, and end wherever + is convenient. + + Simulated annealing parameters: + + -cool FACTOR Cooling factor. [1.001] + -dead COUNT Give up after COUNT cycles. [200] + -inner COUNT Do COUNT loops for each cooling cycle. + [10000] + -temp TEMP Start at this temperature. [unhelpful] + + +$Id$ + +Local variables: +mode: text +End: diff --git a/Makefile b/Makefile index d146436..de93b6f 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ # Makefile for RIGHT ON COMMAND-LINE # -# $Id: Makefile,v 1.14 2003/11/29 23:47:33 mdw Exp $ +# $Id$ #----- Configuration stuff -------------------------------------------------- @@ -30,11 +30,12 @@ RM = rm # Shouldn't need to fiddle with thiis stuff. PACKAGE = rocl -VERSION = 1.1.4 +VERSION = 1.1.5 TCLSCRIPTS = \ elite-editor elite-pairs elite-path elite-find elite-map \ - elite-prices elite-describe elite-reach elite-cmdr elite-salesman + elite-prices elite-describe elite-reach elite-cmdr elite-salesman \ + elite-tantalus SRCFILES = elite.c vec.c vec.h graph.c diff --git a/Makefile.NT b/Makefile.NT index 9938b13..93f82ee 100644 --- a/Makefile.NT +++ b/Makefile.NT @@ -1,6 +1,6 @@ # Makefile for RIGHT ON COMMAND-LINE # -# $Id: Makefile.NT,v 1.3 2003/03/24 08:27:18 mdw Exp $ +# $Id$ #----- Configuration stuff -------------------------------------------------- @@ -32,11 +32,12 @@ RM = rm # Shouldn't need to fiddle with thiis stuff. PACKAGE = rocl -VERSION = 1.1.4 +VERSION = 1.1.5 TCLSCRIPTS = \ elite-editor elite-pairs elite-path elite-find elite-map \ - elite-prices elite-describe elite-reach elite-cmdr elite-salesman + elite-prices elite-describe elite-reach elite-cmdr elite-salesman \ + elite-tantalus SRCFILES = elite.c vec.c vec.h graph.c diff --git a/README b/README index 36c94a4..e03f7e8 100644 --- a/README +++ b/README @@ -473,6 +473,17 @@ RIGHT ON COMMAND-LINE applicable to a wide variety of optimization problems. There are some decent descriptions on the 'net -- try asking Google about it. + + + elite-tantalus [-maxdist DIST] [-minratio RATIO] [GALAXY] ... + + Finds pairs of worlds for which there is a large disparity + between the distance between them and the corresponding shortest + path. It reports pairs such that the distance between them is + less than DIST (default 8 LY -- making this large just makes the + program slower) and where the shortest path is more than RATIO + times the distance in each GALAXY specified -- by default the + eight standard ones. 3. The graphical editor @@ -568,7 +579,7 @@ RIGHT ON COMMAND-LINE unrewarding) or pirates (risky and tedious), and start trading food and other cheap items. -$Id: README,v 1.10 2003/03/13 10:29:21 mdw Exp $ +$Id$ Local variables: mode: text diff --git a/debian/changelog b/debian/changelog index a812ff3..29464e2 100644 --- a/debian/changelog +++ b/debian/changelog @@ -1,3 +1,7 @@ +rocl (1.1.5) experimental; urgency=low + + * Add elite-tantalus. + rocl (1.1.4) experimental; urgency=low * Debianization! diff --git a/elite-editor b/elite-editor index 9689db8..360f05b 100755 --- a/elite-editor +++ b/elite-editor @@ -1,6 +1,6 @@ #! /usr/bin/wish # -# $Id: elite-editor,v 1.9 2003/03/18 10:40:32 mdw Exp $ +# $Id$ package require "elite" "1.0.1" @@ -1108,7 +1108,7 @@ proc cmdr-open {seq} { set cmdr(bogus) 0 foreach {tag label kind} [list \ mission "Mission" { entry 2 255 } \ - score "Rating" { dropbox 65535\ + score "Rating" { dropbox 65535 \ "Harmless" 0 \ "Mostly harmless" 8 \ "Poor" 16 \ diff --git a/elite-tantalus b/elite-tantalus new file mode 100755 index 0000000..8a29191 --- /dev/null +++ b/elite-tantalus @@ -0,0 +1,80 @@ +#! /usr/bin/tclsh +# +# $Id$ + +package require "elite" "1.0.1" +package require "vector" "1.0.0" +package require "graph" "1.0.0" + +set gg {1 2 3 4 5 6 7 8} +set maxdist 80 +set minratio 10 + +for {set i 0} {$i < [llength $argv]} {incr i} { + set a [lindex $argv $i] + switch -glob -- $a { + "-maxdist" { + incr i + set maxdist [expr {int([lindex $argv $i] * 10)}] + } + "-minratio" { + incr i + set minratio [lindex $argv $i] + } + "--" { + incr i + break + } + "-*" { + puts stderr "usage: $argv0 \[-maxdist DIST\] \[-minratio RATIO\] \[GALAXY\] ..." + exit 1 + } + default { + break + } + } +} + +if {[llength $argv] > $i} { + set gg [lrange $argv $i end] +} + +foreach g $gg { + destructure {. gs} [parse-galaxy-spec $g] + set l [elite-galaxylist $gs] + set i 0 + foreach {w x y} $l { + set index($w) $i + incr i + } + elite-adjacency a $l + set v [vector {256 256} -1] + foreach {w x y} $l { + set i $index($w) + foreach {ww xx yy} $a($w) { + set j $index($ww) + $v set $i $j [elite-distance $x $y $xx $yy] + } + $v set $i $i 0 + } + destructure {lv pv} [graph-shortest-path $v] + + elite-adjacency b $l $maxdist + foreach {w x y} $l { + set i $index($w) + foreach {ww xx yy} $b($w) { + set d [elite-distance $x $y $xx $yy] + if {$d <= 70 || [string compare $w $ww] > 0} { continue } + set j $index($ww) + set dd [$lv get $i $j] + set r [expr {$dd/"$d.0"}] + if {$r >= $minratio} { + puts "$g: [worldname $w] -> [worldname $ww]: $d $dd ($r)" + } + } + } + $v destroy + $lv destroy + $pv destroy +} +