Game Killer/Game_Killer.bin/109.DISTANCE.INC

Text File | 1992-07-22 | 4KB | 142 lines

procedure SetUpInverseArray;
var
  i : sector;
  t : warpindex;
  target : sector;
begin
  if invdone then exit;
  writeln('Setting up inverse array...');
  invdone := true;
  for i := 1 to MaxSector do
    inverses[i].number := 0;
  for i := 1 to MaxSector do
    begin
      for t := 1 to Space.sectors[i].number do
        begin
          target := space.sectors[i].data[t];
          inc( inverses[ target ].number );
          with inverses[ target] do
            data[ number ] := i;
        end;
    end;
  invdone := true;
end;

procedure TwoWayDistances( sec : sector; var D : distanceArray;
                           inward, outward : boolean );
{ inward = accept TOWARD sec; outward = accept LEAVING sec }
{ D[j].d = distance from sec;
  D[j].s = one node close }
var
  si : sectorIndex;
  wi : invIndex;
  breadth : queue;
  s,
  daddy, sonny : sector;
  i : warpindex;
  entered : array [ sector ] of boolean;
begin
  if inward then
    SetUpInverseArray;
  writeln('Computing distances...');
  for s := 1 to maxSector do
    begin
      D[s].d := -1;
      entered[ s ] := false;
    end; {for}
  breadth.front := 0;
  enqueue( breadth, sec, sec );
  entered[sec] := true;
  while breadth.front > 0 do
    begin
      serve( breadth, daddy, sonny );
      if D[ sonny ].d = -1 then {haven't hit him before:}
        begin
          D[ sonny ].d := D[ daddy ].d + 1;
          D[ sonny ].s := daddy;
          if outward then
            with space.sectors[ sonny ] do if number > 0 then
              if (space.sectors[sonny].etc and avoid) = Nothing then
                for wi := 1 to number do
                  if not entered[ data[wi] ] then
                    begin
                      enqueue( breadth, sonny, data[ wi ] );
                      entered[ data[wi] ] := true;
                    end; {if with for if}
          if inward then
            with inverses[ sonny ] do
              if (number > 0) and ((space.sectors[sonny].etc and avoid) = Nothing) then
                for wi := 1 to number do
                  if not entered[ data[wi] ] then
                    begin
                      enqueue( breadth, sonny, data[ wi ] );
                      entered[ data[wi] ] := true;
                    end; {if with for if}
        end; {if}
    end; {while}
  for s := 1 to maxSector do if D[s].d = -1 then D[s].d := maxint;
end; {FixDistances}

function CountDist(var D : distancearray; howfar : integer ):integer;
var
  c : integer;
  s : sector;
begin
  c := 0;
  for s := 1 to maxSector do
    if D[ s ].d <= howfar then
      c := c + 1;
  countDist := c;
end; {CountDist}

procedure quick( start, finish : sector; var X : distancearray );
{ This uses C.M. Hoare's quicksort algorithm to sort the distance array
  based on ".d" field. }
var
    left, right   : sectorindex;
    starter, temp : dist;

begin
    left := start;
    right := finish;
    starter := x[(start + finish) div 2];    {middle of array}
    repeat
      while x[left].d < starter.d do
          left := left + 1;        {find a bigger value on the left}
      while starter.d < x[right].d do
          right := right -1;        {and find a smaller value on the right}
      if left <= right then        {we haven't gone too far, so}
        begin
          temp := x[left];        {swap the two}
          x[left] := x[right];
          x[right] := temp;
          left := left + 1;
          right := right -1;    {and update the pointers}
        end; {{if}
    until right < left;
    if start < right then quick(start, right, x);
    if left < finish then quick(left, finish, x);
end;  {quicksort}

procedure SortDistances( var D : distancearray; largest : sector );
{ sort, based upon "d" field.  }
begin
  quick( 1, largest, d );
end; {Sort Distances}

function SetupDistances : boolean;
{ return false if they aborted }
var
  s, n : integer;
begin
  s := GetSector;
  if s <> 0 then
    begin
      TwoWayDistances( s, distances, false, true );
      for n := 1 to maxSector do distances[ n ].s := n;
      SetUpDistances := true;
    end {if}
  else
    SetUpDistances := false;
end; {SetUpDistances}