home *** CD-ROM | disk | FTP | other *** search
/ Game Killer / Game_Killer.bin / 083.MULTPATH.INC < prev    next >
Text File  |  1992-07-15  |  5KB  |  176 lines
  1. procedure GetDistanceTableData( var D : distanceTable;
  2.                                 var V : SectorVector );
  3. { read n sectors, and specify the n^2 distances between pairs in D }
  4. var
  5.  i, j : 0..MaxMPS;
  6.  temp : sectorindex;
  7. begin
  8.   writeln('First sector specified is your home sector.');
  9.   writeln;
  10.   writeln('Please enter your sector values: ');
  11.   for i := 0 to V.size do
  12.     begin
  13.       if i = 0 then
  14.         write('Home ')
  15.       else
  16.         write('Target ', i, ' ');
  17.       temp := getsector;
  18.       if temp = 0 then
  19.         begin
  20.           v.size := 0;
  21.           exit;
  22.         end {if temp}
  23.       else
  24.         v.data[i] := temp;
  25.     end; {for i}
  26.   for i := 0 to V.size do
  27.     for j := 0 to V.size do
  28.       if i <> j then
  29.         D[ i, j ] := FixPath( V.data[i], V.data[j], maxint - 1 );
  30.   for i := 0 to V.size do
  31.     D[i,i] := 0;
  32.   writeln('Distance Table');
  33.   write(' ':4);
  34.   for i := 0 to V.size do
  35.     write( i : 4 );
  36.   writeln;
  37.   for i := 0 to V.size do
  38.     begin
  39.       write( i : 4 );
  40.       for j := 0 to V.size do
  41.         write( d[i,j] : 4 );
  42.       writeln;
  43.     end;
  44. end;
  45.  
  46. var
  47.   totalcount : longint;
  48.  
  49. function RouteDist( closed : boolean;
  50.                          p : sectorvector;
  51.                          d : distancetable ) : integer;
  52. var
  53.   sum, i : integer;
  54. begin
  55.   if closed then
  56.     sum := d[ p.data[p.size], 0 ]
  57.   else
  58.     sum := 0;
  59.   for i := 1 to p.size do
  60.     sum := sum + d[ p.data[ i-1 ], p.data[i] ];
  61.   RouteDist := sum;
  62.   inc( totalcount );
  63. end;
  64.  
  65.  
  66. procedure HeapPermute(   closed : boolean;
  67.                               n : integer;
  68.                        var perm : SectorVector;
  69.                        var dists: distanceTable;
  70.                    var bestdist : integer;
  71.                    var bestrout : sectorvector );
  72. {B.R.Heap's permutation generator for contiguous lists}
  73. var
  74.   c, t, thisdist : integer;
  75. begin
  76.   c := 1;
  77.   if n > 2 then
  78.     HeapPermute( closed, n-1, perm, dists, bestdist, bestrout )
  79.   else
  80.     begin
  81.       ThisDist := RouteDist( closed, perm, dists );
  82.       if ThisDist < BestDist then
  83.         begin
  84.           BestDist := ThisDist;
  85.           BestRout := perm;
  86.         end;
  87.     end; {else}
  88.   while c < n do
  89.     begin
  90.       if odd(n) then
  91.         begin
  92.           t := perm.data[n];
  93.           perm.data[n] := perm.data[1];
  94.           perm.data[1] := t;
  95.         end
  96.       else
  97.         begin
  98.           t := perm.data[n];
  99.           perm.data[n] := perm.data[c];
  100.           perm.data[c] := t;
  101.         end;
  102.       c := c + 1;
  103.       if n > 2 then
  104.         HeapPermute( closed, n-1, perm, dists, bestdist, bestrout )
  105.       else
  106.         begin
  107.           ThisDist := RouteDist( closed, perm, dists );
  108.           if ThisDist < BestDist then
  109.             begin
  110.               BestDist := ThisDist;
  111.               BestRout := perm;
  112.             end;
  113.         end; {else}
  114.     end; {while}
  115. end;
  116.  
  117.  
  118. procedure MultiPassSector;
  119. { accept a small number of sectors, and find the best path that hits these
  120. sectors (possibly returning to the base sector}
  121. var
  122.   s1, s2     : sectorindex;
  123.   Table      : DistanceTable;
  124.   targets    : SectorVector;
  125.   routes     : SectorVector;
  126.   numsectors : integer;
  127.   i          : integer;
  128.   bestdist   : integer;
  129.   bestroute  : sectorVector;
  130.   closed     : boolean;
  131.   ch         : char;
  132. begin
  133.   totalcount := 0;
  134.   repeat
  135.     write('How many targets? (max ', maxMPS, ', enter 0 to abort)  ');
  136.     NumSectors := ReadNumberFromTerminal;
  137.   until (NumSectors >= 0) and (NumSectors <= MaxMPS );
  138.   if NumSectors = 0 then
  139.     exit;
  140.   targets.size := NumSectors;
  141.   GetDistanceTableData( Table, targets );
  142.   if targets.size = 0 then {they aborted routine}
  143.     exit;
  144.   BestDist := maxint;
  145.   Routes.size := NumSectors;
  146.   for i := 0 to NumSectors do routes.data[i] := i;
  147.   bestroute := routes;
  148.   closed := prompt('Closed path? ');
  149.   HeapPermute( closed, NumSectors, routes, table, bestdist, bestroute );
  150.   writeln('Considered ', totalcount, ' possible routes.');
  151.   writeln('Best distance is ', bestdist );
  152.   write('The best route is: ', targets.data[0] : 4);
  153.   for i := 1 to NumSectors do
  154.     write( ' > ', targets.data[bestroute.data[i]] : 4 );
  155.   if closed then
  156.     write( ' > ', targets.data[0] : 4 );
  157.   writeln;
  158.   readln;
  159.   writeln('Here are the intermediate paths:');
  160.   for i := 1 to NumSectors do
  161.     begin
  162.       s1 := targets.data[ bestroute.data[i-1] ];
  163.       s2 := targets.data[ bestroute.data[i] ];
  164.       writeln( s1, ' to ', s2, ' of length ', fixpath( s1, s2, maxint - 1 ) );
  165.       printpath( s1, s2 );
  166.       readln;
  167.     end; {for}
  168.   if closed then
  169.     begin
  170.       s1 := targets.data[ bestroute.data[ NumSectors] ];
  171.       s2 := targets.data[ 0 ];
  172.       writeln( s1, ' to ', s2, ' of length ', fixpath( s1, s2, maxint - 1 ) );
  173.       printpath( s1, s2 );
  174.       readln;
  175.     end;
  176. end;