chiark / gitweb /
Add elite-tantalus. Add a developer guide.
authormdw <mdw>
Wed, 22 Sep 2004 17:52:04 +0000 (17:52 +0000)
committermdw <mdw>
Wed, 22 Sep 2004 17:52:04 +0000 (17:52 +0000)
DEVGUIDE [new file with mode: 0644]
Makefile
Makefile.NT
README
debian/changelog
elite-editor
elite-tantalus [new file with mode: 0755]

diff --git a/DEVGUIDE b/DEVGUIDE
new file mode 100644 (file)
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$
+\f
+Local variables:
+mode: text
+End:
index d146436..de93b6f 100644 (file)
--- 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
 
index 9938b13..93f82ee 100644 (file)
@@ -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 (file)
--- 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$
 \f
 Local variables:
 mode: text
index a812ff3..29464e2 100644 (file)
@@ -1,3 +1,7 @@
+rocl (1.1.5) experimental; urgency=low
+
+  * Add elite-tantalus.
+
 rocl (1.1.4) experimental; urgency=low
 
   * Debianization!
index 9689db8..360f05b 100755 (executable)
@@ -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 (executable)
index 0000000..8a29191
--- /dev/null
@@ -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
+}
+