home *** CD-ROM | disk | FTP | other *** search
/ Game Killer / Game_Killer.bin / 092.ROBPATH.INC < prev    next >
Text File  |  1992-07-23  |  9KB  |  235 lines
  1. function AddSectorToVector( var sv : sectorVector; s : sector ) : boolean;
  2. { try to add new sector.  If duplicated, return false; otherwise add. }
  3. var
  4.   i : 0..MaxMPS;
  5.   ok : boolean;
  6. begin
  7.   ok := true;
  8.   for i := 0 to sv.size do
  9.     if sv.data[i] = s then
  10.       ok := false;
  11.   AddSectorToVector := ok;
  12.   if ok then
  13.     begin
  14.       sv.size := sv.size  + 1;
  15.       sv.data[ sv.size ] := s;
  16.     end;
  17. end;
  18.  
  19. procedure FindRobPath( var path  : sectorvector;{ initialized with start  }
  20.                           ports  : portindex;   { number of ports we want }
  21.                       var turns  : integer;     { max turns allowed       }
  22.                           base   : sectorindex; { starting point for path }
  23.                           closed : boolean);    { if "turns" includes back}
  24. { greedy algorithm }
  25. {
  26.   path is the sequence of ports we are trying to find.  Its preloaded with
  27.   "base", our start point.  "ports" is the maximum number of ports we are
  28.   looking for.  "Turns" is the maximum number of turns we are allowed to use
  29.   in path. Return turns set to any turns remaining.  "closed" is true if we
  30.   have to add the turns back from the last point to base, and pclass is
  31.   true/false depending on if we are looking for ports buying
  32.   equipment/selling equipment or organics.
  33. }
  34. var
  35.   DistToPorts: distanceArray;
  36.   PortOK     : array [ sector ] of boolean;
  37.   PortsAvail : boolean;
  38.   top,
  39.   NumPorts   : sectorindex;
  40.   current    : sector;
  41.   n          : integer;
  42.   outgoing   : integer;
  43.  
  44. begin
  45.   PortsAvail := true;
  46.   current := base;
  47.   for n := 1 to 1000 do
  48.     PortOK[n] := false;
  49.   TwoWayDistances( base, distances, true, false );
  50.   for n := 1 to maxSector do distances[ n ].s := n;
  51.   DistToPorts := distances;           { distances will store the return path }
  52.   write('sifting... ');
  53.   EliminateUnwanted( distToPorts, RobHolds, NumPorts, 0 );
  54.   for n := 1 to NumPorts do
  55.     PortOK[ distToPorts[ n ].s ] := true;
  56.   writeln('Ports to avoid (in addition to busted ports):');
  57.   n := GetSector;
  58.   while n <> 0 do
  59.     begin
  60.       PortOK[ n ] := false;
  61.       n := GetSector;
  62.     end;
  63.   while PortsAvail and (turns > 0) and (ports > 0) do
  64.     begin
  65.       TwoWayDistances( current, distToPorts, false, true );
  66.       for n := 1 to maxSector do distToPorts[ n ].s := n;
  67.       writeln('sorting... ');
  68.       SortDistances( distToPorts, maxSector );
  69.       PortsAvail := false;
  70.       n := 1;
  71.       while (n <= MaxSector) and (distToPorts[n].d <= turns) do
  72.         if portOK[ disttoports[n].s ] then
  73.           begin
  74.             outgoing := distToPorts[n].d;
  75.             if not closed
  76.                or (turns >= outgoing + Distances[ DistToPorts[n].s ].d) then
  77.               begin
  78.                 top := path.size;                     { okay, see length    }
  79.                 if AddSectorToVector( path, distToPorts[n].s )  then               { successful?         }
  80.                   begin
  81.                     PortsAvail := true;               { yes.  Keep going    }
  82.                     current := distToPorts[n].s;      { here is our next    }
  83.                     turns := turns - outgoing;        { update turns, ports }
  84.                     ports := ports - 1;
  85.                     n := MaxSector;                   { but exit this while }
  86.                   end;
  87.               end;
  88.             n := n + 1;
  89.           end {while}
  90.         else
  91.           n := n + 1;
  92.     end; {while more ports}
  93.   if closed then
  94.     turns := turns - distances[current].d;
  95. end;
  96.  
  97. procedure TradingSpree( var path  : sectorvector; { initialized with start  }
  98.                             ports  : portindex;   { number of ports we want }
  99.                         var turns  : integer;     { max turns allowed       }
  100.                             base   : sectorindex; { starting point for path }
  101.                             closed : boolean );   { if "turns" includes back}
  102. { greedy algorithm }
  103. {
  104.   path is the sequence of ports we are trying to find.  Its preloaded with
  105.   "base", our start point.  "ports" is the maximum number of ports we are
  106.   looking for.  "Turns" is the maximum number of turns we are allowed to use
  107.   in path. Return turns set to any turns remaining.  "closed" is true if we
  108.   have to add the turns back from the last point to base, and pclass is
  109.   true/false depending on if we are looking for ports buying
  110.   equipment/selling equipment or organics.
  111. }
  112. var
  113.   DistToPorts: distanceArray;
  114.   PortsAvail : boolean;
  115.   top,
  116.   NumPorts   : sectorindex;
  117.   current    : sector;
  118.   n          : sector;
  119.   outgoing   : integer;
  120.   buyequip   : boolean;
  121. begin
  122.   PortsAvail := true;
  123.   current := base;
  124.   buyEquip := true;
  125.   TwoWayDistances( base, distances, true, false );
  126.   for n := 1 to maxSector do distances[ n ].s := n;
  127.   DistToPorts := distances;
  128.   while PortsAvail and (turns > 0) and (ports > 0) do
  129.     begin
  130.       TwoWayDistances( current, distToPorts, false, true );
  131.       for n := 1 to maxSector do distToPorts[ n ].s := n;
  132.       write('sifting... ');
  133.       if buyEquip then
  134.         EliminateUnwanted( distToPorts, BuyEquipSellOrganic, NumPorts, 0 )
  135.       else
  136.         EliminateUnwanted( distToPorts, BuyOrganicSellEquip, NumPorts, 0 );
  137.       buyEquip := not buyEquip;
  138.       writeln('sorting... ');
  139.       SortDistances( distToPorts, NumPorts );
  140.       PortsAvail := false;
  141.       n := 1;
  142.       while (n <= NumPorts) and (distToPorts[n].d <= turns) do
  143.         begin
  144.           outgoing := distToPorts[n].d;
  145.           if not closed
  146.              or (turns >= outgoing + FixPath( DistToPorts[n].s, base, turns - outgoing)) then
  147.             begin
  148.               top := path.size;                     { okay, see length    }
  149.               if AddSectorToVector( path, distToPorts[n].s )  then               { successful?         }
  150.                 begin
  151.                   PortsAvail := true;               { yes.  Keep going    }
  152.                   current := distToPorts[n].s;      { here is our next    }
  153.                   turns := turns - outgoing;        { update turns, ports }
  154.                   ports := ports - 1;
  155.                   n := NumPorts;                    { but exit this while }
  156.                 end;
  157.             end;
  158.           n := n + 1;
  159.         end; {while}
  160.     end; {while}
  161.   if closed then
  162.     turns := turns - FixPath( current, base, turns );
  163. end;
  164.  
  165. procedure RobPath;
  166. {
  167.   A person provides the base point, a max number of ports, and a max number
  168.   of turns.  The computer computes a sequence of ports at which the player
  169.   has not been busted, such that the number of turns or ports is not
  170.   exceeded.
  171.  
  172.   The algorithm will just use the greedy algorithm.  Its not optimal, but
  173.   it should suffice.
  174. }
  175.  
  176. var
  177.   targets    : sectorvector;     { our sequence                         }
  178.   maxtargets : portindex;        { maximum places sought                }
  179.   turnsleft,                     { turns left over returned from proc   }
  180.   maxturns   : integer;          { maximum turns allowed                }
  181.   s1, s2     : sectorindex;      { variables for short path displays    }
  182.   i,                             { generic loop index                   }
  183.   currsector : sectorindex;      { used for input                       }
  184.   closed,                        { should we use a closed path?         }
  185.   equiponly  : boolean;          { buying equipment, or stealing holds? }
  186. begin
  187.   repeat
  188.     write('Maximum number of targets? [max ', MaxMPS, '] ');
  189.     maxtargets := ReadNumberFromTerminal;
  190.   until (maxtargets >= 0) and (maxTargets <= MaxMPS);
  191.   if maxTargets = 0 then
  192.     exit;
  193.   write('Maximum number of turns? ');
  194.   maxturns := readNumberFromTerminal;
  195.   if maxTargets = 0 then
  196.     exit;
  197.   write('Starting ');
  198.   currsector := GetSector;
  199.   if currsector = 0 then
  200.     exit;
  201.   closed := prompt('Closed path? ');
  202.   equiponly := prompt('Trading spree path?  (alternate trading equip/organic) ');
  203.   if not equiponly then
  204.     writeln('Okay, will choose ports to "rob holds".');
  205.   targets.size := 0;
  206.   targets.data[0] := currsector;
  207.   turnsleft := maxturns;
  208.   if equiponly then
  209.     TradingSpree( targets, maxtargets, turnsleft, currsector, closed )
  210.   else
  211.     FindRobPath( targets, maxtargets, turnsleft, currsector, closed );
  212.   for i := 0 to targets.size - 1 do
  213.     write( targets.data[i] : 4, ' > ');
  214.   write( targets.data[ targets.size ] );
  215.   if closed then
  216.     write( ' > ', currsector );
  217.   writeln(' of length ', maxturns - turnsleft );
  218.   writeln('Here are the intermediate paths:');
  219.   for i := 1 to Targets.size do
  220.     begin
  221.       s1 := targets.data[ i-1 ];
  222.       s2 := targets.data[ i ];
  223.       writeln( s1, ' to ', s2, ' of length ', fixpath( s1, s2, maxturns) );
  224.       printpath( s1, s2 );
  225.       readln;
  226.     end; {for}
  227.   if closed then
  228.     begin
  229.       s1 := targets.data[ targets.size ];
  230.       s2 := targets.data[ 0 ];
  231.       writeln( s1, ' to ', s2, ' of length ', fixpath( s1, s2, maxturns) );
  232.       printpath( s1, s2 );
  233.       readln;
  234.     end;
  235. end; {rob path}