anchor.diff: -unit KM_NavMesh;
  -{$I KaM_Remake.inc}
  -interface
  -uses
  -  KM_PolySimplify,
  -  KM_CommonClasses, KM_CommonTypes, KM_Defaults, KM_Points, Contnrs,
  -  KM_NavMeshDefences,
  -  KromUtils, KM_CommonUtils,
  -  KM_NavMeshGenerator, KM_NavMeshFloodPositioning, KM_NavMeshPathFinding;// TimeGet
  -
  -
  -type
  -
  -  //NavMesh is used to acess the map on a higher level than tiles
  -  //terrain is represented as a mesh interconnected polygons
  -  TKMNavMesh = class
  -  private
  -    fMapX, fMapY: Word;               // Limits of arrays
  -    fNodeCount, fPolyCount: Integer;  // Thresholds
  -    fNodes: TKMPointArray;            // Nodes
  -    fPolygons: TPolygonArray;         // Polygons
  -    fPoint2PolygonArr: TKMWordArray;  // KMPoint -> Polygon index
  -    //fPolygon2PointArr: TKMPointArray; // Polygon index -> KMPoint
  -
  -    fDefences: TForwardFF; //Defences class
  -    fPathfinding: TNavMeshPathFinding; // NavMesh Pathfinding
  -    fPositioning: TNavMeshFloodPositioning; // NavMesh Positioning
  -
  -    fNavMeshGenerator: TKMNavMeshGenerator; // NavMesh generator
  -
  -    //Building the navmesh from terrain
  -    procedure FindClosestPolygon();
  -    procedure TieUpTilesWithPolygons();
  -    procedure TieUpPolygonsWithTiles();
  -
  -    function GetPolygonFromPoint(const aY,aX: Integer): Word;
  -    function GetPolygonFromKMPoint(const aPoint: TKMPoint): Word;
  -
  -  public
  -    constructor Create();
  -    destructor Destroy(); override;
  -    procedure Save(SaveStream: TKMemoryStream);
  -    procedure Load(LoadStream: TKMemoryStream);
  -
  -    property Point2Polygon[const aY,aX: Integer]: Word read GetPolygonFromPoint;
  -    property KMPoint2Polygon[const aPoint: TKMPoint]: Word read GetPolygonFromKMPoint;
  -    //property Polygon2Point: TKMPointArray read fPolygon2PointArr;
  -    property Polygons: TPolygonArray read fPolygons;
  -    property Nodes: TKMPointArray read fNodes;
  -    property Defences: TForwardFF read fDefences write fDefences;
  -    property Pathfinding: TNavMeshPathFinding read fPathfinding write fPathfinding;
  -    property Positioning: TNavMeshFloodPositioning read fPositioning write fPositioning;
  -
  -    procedure AfterMissionInit();
  -
  -    procedure UpdateState(aTick: Cardinal);
  -    procedure Paint(const aRect: TKMRect);
  -  end;
  -
  -
  -implementation
  -uses
  -  SysUtils, Math, Delaunay,
  -  KM_Terrain, KM_HandsCollection, KM_RenderAux, KM_Outline,
  -  Dialogs;
  -
  -
  -{ TKMNavMesh }
  -constructor TKMNavMesh.Create();
  -begin
  -  inherited Create;
  -
  -  fNavMeshGenerator := TKMNavMeshGenerator.Create();
  -  fDefences := TForwardFF.Create(True);
  -  fPathfinding := TNavMeshPathFinding.Create();
  -  fPositioning := TNavMeshFloodPositioning.Create();
  -end;
  -
  -
  -destructor TKMNavMesh.Destroy();
  -begin
  -  FreeAndNil(fDefences);
  -  FreeAndNil(fPathfinding);
  -  FreeAndNil(fPositioning);
  -  FreeAndNil(fNavMeshGenerator);
  -  inherited;
  -end;
  -
  -
  -procedure TKMNavMesh.Save(SaveStream: TKMemoryStream);
  -var
  -  K: Integer;
  -begin
  -  fNavMeshGenerator.Save(SaveStream);
  -  SaveStream.WriteA('NavMesh');
  -  SaveStream.Write(fMapX);
  -  SaveStream.Write(fMapY);
  -
  -  SaveStream.Write(fNodeCount);
  -  SaveStream.Write(fNodes[0], SizeOf(fNodes[0]) * fNodeCount);
  -
  -  SaveStream.Write(fPolyCount);
  -  SaveStream.Write(fPolygons[0], SizeOf(fPolygons[0]) * fPolyCount);
  -  // Maybe this code will save work in future
  -  //for K := 0 to fPolyCount - 1 do
  -  //begin
  -  //  SaveStream.Write(fPolygons[K].CenterPoint);
  -  //  SaveStream.Write(fPolygons[K].Indices, SizeOf(fPolygons[I].Indices));
  -  //  SaveStream.Write(fPolygons[K].NearbyCount);
  -  //  SaveStream.Write(fPolygons[K].Poly2PointStart);
  -  //  SaveStream.Write(fPolygons[K].Poly2PointCnt);
  -  //  SaveStream.Write(fPolygons[K].Nearby, SizeOf(fPolygons[I].Nearby));
  -  //  SaveStream.Write(fPolygons[K].NearbyPoints, SizeOf(fPolygons[I].NearbyPoints));
  -  //end;
  -
  -  K := Length(fPoint2PolygonArr);
  -  SaveStream.Write( K );
  -  SaveStream.Write(fPoint2PolygonArr[0], SizeOf(fPoint2PolygonArr[0]) * K );
  -
  -  //K := Length(fPolygon2PointArr);
  -  //SaveStream.Write( K );
  -  //SaveStream.Write(fPolygon2PointArr[0], SizeOf(fPolygon2PointArr[0]) * K );
  -
  -  // The following does not requires save
  -  // fDefences
  -  // fPathfinding
  -  // fPositioning
  -end;
  -
  -
  -procedure TKMNavMesh.Load(LoadStream: TKMemoryStream);
  -var
  -  K: Integer;
  -begin
  -  fNavMeshGenerator.Load(LoadStream);
  -  LoadStream.ReadAssert('NavMesh');
  -  LoadStream.Read(fMapX);
  -  LoadStream.Read(fMapY);
  -
  -  LoadStream.Read(fNodeCount);
  -  SetLength(fNodes, fNodeCount);
  -  LoadStream.Read(fNodes[0], SizeOf(fNodes[0]) * fNodeCount);
  -
  -  LoadStream.Read(fPolyCount);
  -  SetLength(fPolygons, fPolyCount);
  -  LoadStream.Read(fPolygons[0], SizeOf(fPolygons[0]) * fPolyCount);
  -  //for K := 0 to fPolyCount - 1 do
  -  //begin
  -  //  LoadStream.Read(fPolygons[K].CenterPoint);
  -  //  LoadStream.Read(fPolygons[K].Indices, SizeOf(fPolygons[I].Indices));
  -  //  LoadStream.Read(fPolygons[K].NearbyCount);
  -  //  LoadStream.Read(fPolygons[K].Poly2PointStart);
  -  //  LoadStream.Read(fPolygons[K].Poly2PointCnt);
  -  //  LoadStream.Read(fPolygons[K].Nearby, SizeOf(fPolygons[I].Nearby));
  -  //  LoadStream.Read(fPolygons[K].NearbyPoints, SizeOf(fPolygons[I].NearbyPoints));
  -  //end;
  -
  -  LoadStream.Read(K);
  -  SetLength(fPoint2PolygonArr,K);
  -  LoadStream.Read(fPoint2PolygonArr[0], SizeOf(fPoint2PolygonArr[0]) * K );
  -
  -  //LoadStream.Read(K);
  -  //SetLength(fPolygon2PointArr,K);
  -  //LoadStream.Read(fPolygon2PointArr[0], SizeOf(fPolygon2PointArr[0]) * K );
  -end;
  -
  -
  -procedure TKMNavMesh.AfterMissionInit();
  -begin
  -  fMapX := gTerrain.MapX;
  -  fMapY := gTerrain.MapY;
  -
  -  fNavMeshGenerator.GenerateNewNavMesh();
  -
  -  fNodeCount := fNavMeshGenerator.NodeCount;
  -  fPolyCount := fNavMeshGenerator.PolygonCount;
  -  fNodes := fNavMeshGenerator.Nodes;
  -  fPolygons := fNavMeshGenerator.Polygons;
  -
  -  //Mapp all map tiles to its polygons and vice versa
  -  TieUpTilesWithPolygons();
  -  TieUpPolygonsWithTiles();
  -end;
  -
  -
  -procedure TKMNavMesh.UpdateState(aTick: Cardinal);
  -begin
  -
  -end;
  -
  -function TKMNavMesh.GetPolygonFromPoint(const aY,aX: Integer): Word;
  -var
  -  Idx: Integer;
  -begin
  -  Result := 0;
  -  Idx := aY*(fMapX+1) + aX;
  -  if (Length(fPoint2PolygonArr) > Idx) then
  -    Result := fPoint2PolygonArr[Idx];
  -end;
  -
  -function TKMNavMesh.GetPolygonFromKMPoint(const aPoint: TKMPoint): Word;
  -var
  -  Idx: Integer;
  -begin
  -  Result := 0;
  -  Idx := aPoint.Y*(fMapX+1) + aPoint.X;
  -  if (Length(fPoint2PolygonArr) > Idx) then
  -    Result := fPoint2PolygonArr[Idx];
  -end;
  -
  -procedure TKMNavMesh.FindClosestPolygon();
  -var
  +unit KM_NavMesh;
  +{$I KaM_Remake.inc}
  +interface
  +uses
  +  KM_PolySimplify,
  +  KM_CommonClasses, KM_CommonTypes, KM_Defaults, KM_Points, Contnrs,
  +  KM_NavMeshDefences,
  +  KromUtils, KM_CommonUtils,
  +  KM_NavMeshGenerator, KM_NavMeshFloodPositioning, KM_NavMeshPathFinding;// TimeGet
  +
  +
  +type
  +
  +  //NavMesh is used to acess the map on a higher level than tiles
  +  //terrain is represented as a mesh interconnected polygons
  +  TKMNavMesh = class
  +  private
  +    fMapX, fMapY: Word;               // Limits of arrays
  +    fNodeCount, fPolyCount: Integer;  // Thresholds
  +    fNodes: TKMPointArray;            // Nodes
  +    fPolygons: TPolygonArray;         // Polygons
  +    fPoint2PolygonArr: TKMWordArray;  // KMPoint -> Polygon index
  +    //fPolygon2PointArr: TKMPointArray; // Polygon index -> KMPoint
  +
  +    fDefences: TForwardFF; //Defences class
  +    fPathfinding: TNavMeshPathFinding; // NavMesh Pathfinding
  +    fPositioning: TNavMeshFloodPositioning; // NavMesh Positioning
  +
  +    fNavMeshGenerator: TKMNavMeshGenerator; // NavMesh generator
  +
  +    //Building the navmesh from terrain
  +    procedure FindClosestPolygon();
  +    procedure TieUpTilesWithPolygons();
  +    procedure TieUpPolygonsWithTiles();
  +
  +    function GetPolygonFromPoint(const aY,aX: Integer): Word;
  +    function GetPolygonFromKMPoint(const aPoint: TKMPoint): Word;
  +
  +  public
  +    constructor Create();
  +    destructor Destroy(); override;
  +    procedure Save(SaveStream: TKMemoryStream);
  +    procedure Load(LoadStream: TKMemoryStream);
  +
  +    property Point2Polygon[const aY,aX: Integer]: Word read GetPolygonFromPoint;
  +    property KMPoint2Polygon[const aPoint: TKMPoint]: Word read GetPolygonFromKMPoint;
  +    //property Polygon2Point: TKMPointArray read fPolygon2PointArr;
  +    property Polygons: TPolygonArray read fPolygons;
  +    property Nodes: TKMPointArray read fNodes;
  +    property Defences: TForwardFF read fDefences write fDefences;
  +    property Pathfinding: TNavMeshPathFinding read fPathfinding write fPathfinding;
  +    property Positioning: TNavMeshFloodPositioning read fPositioning write fPositioning;
  +
  +    procedure AfterMissionInit();
  +
  +    procedure UpdateState(aTick: Cardinal);
  +    procedure Paint(const aRect: TKMRect);
  +  end;
  +
  +
  +implementation
  +uses
  +  SysUtils, Math, Delaunay,
  +  KM_Terrain, KM_HandsCollection, KM_RenderAux, KM_Outline,
  +  Dialogs;
  +
  +
  +{ TKMNavMesh }
  +constructor TKMNavMesh.Create();
  +begin
  +  inherited Create;
  +
  +  fNavMeshGenerator := TKMNavMeshGenerator.Create();
  +  fDefences := TForwardFF.Create(True);
  +  fPathfinding := TNavMeshPathFinding.Create();
  +  fPositioning := TNavMeshFloodPositioning.Create();
  +end;
  +
  +
  +destructor TKMNavMesh.Destroy();
  +begin
  +  FreeAndNil(fDefences);
  +  FreeAndNil(fPathfinding);
  +  FreeAndNil(fPositioning);
  +  FreeAndNil(fNavMeshGenerator);
  +  inherited;
  +end;
  +
  +
  +procedure TKMNavMesh.Save(SaveStream: TKMemoryStream);
  +var
  +  K: Integer;
  +begin
  +  fNavMeshGenerator.Save(SaveStream);
  +  SaveStream.WriteA('NavMesh');
  +  SaveStream.Write(fMapX);
  +  SaveStream.Write(fMapY);
  +
  +  SaveStream.Write(fNodeCount);
  +  SaveStream.Write(fNodes[0], SizeOf(fNodes[0]) * fNodeCount);
  +
  +  SaveStream.Write(fPolyCount);
  +  SaveStream.Write(fPolygons[0], SizeOf(fPolygons[0]) * fPolyCount);
  +  // Maybe this code will save work in future
  +  //for K := 0 to fPolyCount - 1 do
  +  //begin
  +  //  SaveStream.Write(fPolygons[K].CenterPoint);
  +  //  SaveStream.Write(fPolygons[K].Indices, SizeOf(fPolygons[I].Indices));
  +  //  SaveStream.Write(fPolygons[K].NearbyCount);
  +  //  SaveStream.Write(fPolygons[K].Poly2PointStart);
  +  //  SaveStream.Write(fPolygons[K].Poly2PointCnt);
  +  //  SaveStream.Write(fPolygons[K].Nearby, SizeOf(fPolygons[I].Nearby));
  +  //  SaveStream.Write(fPolygons[K].NearbyPoints, SizeOf(fPolygons[I].NearbyPoints));
  +  //end;
  +
  +  K := Length(fPoint2PolygonArr);
  +  SaveStream.Write( K );
  +  SaveStream.Write(fPoint2PolygonArr[0], SizeOf(fPoint2PolygonArr[0]) * K );
  +
  +  //K := Length(fPolygon2PointArr);
  +  //SaveStream.Write( K );
  +  //SaveStream.Write(fPolygon2PointArr[0], SizeOf(fPolygon2PointArr[0]) * K );
  +
  +  // The following does not requires save
  +  // fDefences
  +  // fPathfinding
  +  // fPositioning
  +end;
  +
  +
  +procedure TKMNavMesh.Load(LoadStream: TKMemoryStream);
  +var
  +  K: Integer;
  +begin
  +  fNavMeshGenerator.Load(LoadStream);
  +  LoadStream.ReadAssert('NavMesh');
  +  LoadStream.Read(fMapX);
  +  LoadStream.Read(fMapY);
  +
  +  LoadStream.Read(fNodeCount);
  +  SetLength(fNodes, fNodeCount);
  +  LoadStream.Read(fNodes[0], SizeOf(fNodes[0]) * fNodeCount);
  +
  +  LoadStream.Read(fPolyCount);
  +  SetLength(fPolygons, fPolyCount);
  +  LoadStream.Read(fPolygons[0], SizeOf(fPolygons[0]) * fPolyCount);
  +  //for K := 0 to fPolyCount - 1 do
  +  //begin
  +  //  LoadStream.Read(fPolygons[K].CenterPoint);
  +  //  LoadStream.Read(fPolygons[K].Indices, SizeOf(fPolygons[I].Indices));
  +  //  LoadStream.Read(fPolygons[K].NearbyCount);
  +  //  LoadStream.Read(fPolygons[K].Poly2PointStart);
  +  //  LoadStream.Read(fPolygons[K].Poly2PointCnt);
  +  //  LoadStream.Read(fPolygons[K].Nearby, SizeOf(fPolygons[I].Nearby));
  +  //  LoadStream.Read(fPolygons[K].NearbyPoints, SizeOf(fPolygons[I].NearbyPoints));
  +  //end;
  +
  +  LoadStream.Read(K);
  +  SetLength(fPoint2PolygonArr,K);
  +  LoadStream.Read(fPoint2PolygonArr[0], SizeOf(fPoint2PolygonArr[0]) * K );
  +
  +  //LoadStream.Read(K);
  +  //SetLength(fPolygon2PointArr,K);
  +  //LoadStream.Read(fPolygon2PointArr[0], SizeOf(fPolygon2PointArr[0]) * K );
  +end;
  +
  +
  +procedure TKMNavMesh.AfterMissionInit();
  +begin
  +  fMapX := gTerrain.MapX;
  +  fMapY := gTerrain.MapY;
  +
  +  fNavMeshGenerator.GenerateNewNavMesh();
  +
  +  fNodeCount := fNavMeshGenerator.NodeCount;
  +  fPolyCount := fNavMeshGenerator.PolygonCount;
  +  fNodes := fNavMeshGenerator.Nodes;
  +  fPolygons := fNavMeshGenerator.Polygons;
  +
  +  //Mapp all map tiles to its polygons and vice versa
  +  TieUpTilesWithPolygons();
  +  TieUpPolygonsWithTiles();
  +end;
  +
  +
  +procedure TKMNavMesh.UpdateState(aTick: Cardinal);
  +begin
  +
  +end;
  +
  +function TKMNavMesh.GetPolygonFromPoint(const aY,aX: Integer): Word;
  +var
  +  Idx: Integer;
  +begin
  +  Result := 0;
  +  Idx := aY*(fMapX+1) + aX;
  +  if (Length(fPoint2PolygonArr) > Idx) then
  +    Result := fPoint2PolygonArr[Idx];
  +end;
  +
  +function TKMNavMesh.GetPolygonFromKMPoint(const aPoint: TKMPoint): Word;
  +var
  +  Idx: Integer;
  +begin
  +  Result := 0;
  +  Idx := aPoint.Y*(fMapX+1) + aPoint.X;
  +  if (Length(fPoint2PolygonArr) > Idx) then
  +    Result := fPoint2PolygonArr[Idx];
  +end;
  +
  +procedure TKMNavMesh.FindClosestPolygon();
  +var
     Len,MaxIdx: Word;
     Queue: array[0..255*255] of Integer;
     procedure AddToQueue(aIdx, aPolygon: Integer);
  
positive.code:     if (fPoint2PolygonArr[K - fMapX - 1] = 0) then AddToQueue(K - fMapX - 1, fPoint2PolygonArr[K]);
      if (fPoint2PolygonArr[K + fMapX + 1] = 0) then AddToQueue(K + fMapX + 1, fPoint2PolygonArr[K]);
    end;
  end;
  
  procedure TKMNavMesh.TieUpTilesWithPolygons();
    procedure GetNodesSortedByY(aIdx: Integer; var a,b,c: TKMPoint);
    begin
      a := fNodes[ fPolygons[aIdx].Indices[0] ];
      b := fNodes[ fPolygons[aIdx].Indices[1] ];
  
negative.code:   // Get starting index of each polygon
    for X := 1 to fPolyCount - 1 do // 0. polygon is reserved / unused
      fPolygons[X].Poly2PointStart := fPolygons[X-1].Poly2PointStart + fPolygons[X-1].Poly2PointCnt;
    //}
  end;
  
  //Render debug symbols
  procedure TKMNavMesh.Paint(const aRect: TKMRect);
  const
    COLOR_WHITE = $FFFFFF;
    COLOR_BLACK = $000000;
    COLOR_GREEN = $00FF00;
    COLOR_RED = $7700FF;
    COLOR_YELLOW = $00FFFF;
    COLOR_BLUE = $FF0000;
  
    function GetCommonPoints(aIdx1, aIdx2: Word; var aPoint1, aPoint2: TKMPoint): Boolean;
    var
      FirstPoint: Boolean;
      K,L: Integer;
    begin
      Result := False;
      FirstPoint := True;
      for K := 0 to 2 do
      for L := 0 to 2 do
        if (fPolygons[aIdx1].Indices[K] = fPolygons[aIdx2].Indices[L]) then
        begin
          if FirstPoint then
            aPoint1 := fNodes[ fPolygons[aIdx2].Indices[L] ]
          else
          begin
            aPoint2 := fNodes[ fPolygons[aIdx2].Indices[L] ];
            Result := True;
            Exit;
          end;
          FirstPoint := False;
        end;
    end;
  
  var
    K, L: Integer;
    p1,p2: TKMPoint;
  
    Owner: TKMHandID;
    DefLines: TKMDefenceLines;
    DefencePosArr: TKMDefencePosArr;
    FFF: TForwardFF;
  begin
    //AfterMissionInit();
    if not AI_GEN_NAVMESH OR not OVERLAY_NAVMESH then
      Exit;
    //{
    if fNavMeshGenerator.Paint(aRect) then
      Exit;
    //}
    //fNavMeshGenerator.Paint(aRect);
    // EXTRACT POLYGONS
    //{ Triangles and connection of NavMesh
    for K := 1 to fPolyCount - 1 do
      with fPolygons[K] do
      begin
        gRenderAux.TriangleOnTerrain(
          fNodes[ Indices[0] ].X,
          fNodes[ Indices[0] ].Y,
          fNodes[ Indices[1] ].X,
          fNodes[ Indices[1] ].Y,
          fNodes[ Indices[2] ].X,
          fNodes[ Indices[2] ].Y, $50000000 OR COLOR_BLACK);
        for L := 0 to NearbyCount - 1 do
          if GetCommonPoints(K, Nearby[L], p1, p2) then
            gRenderAux.LineOnTerrain(p1, p2, $50000000 OR COLOR_BLUE)
          else
          begin
            gRenderAux.TriangleOnTerrain(
              fNodes[ Indices[0] ].X,
              fNodes[ Indices[0] ].Y,
              fNodes[ Indices[1] ].X,
              fNodes[ Indices[1] ].Y,
              fNodes[ Indices[2] ].X,
              fNodes[ Indices[2] ].Y, $90000000 OR COLOR_WHITE);
          end;
        p1.X := Round( (fNodes[ Indices[0] ].X + fNodes[ Indices[1] ].X + fNodes[ Indices[2] ].X) / 3 );
        p1.Y := Round( (fNodes[ Indices[0] ].Y + fNodes[ Indices[1] ].Y + fNodes[ Indices[2] ].Y) / 3 );
        gRenderAux.Text(p1.X, p1.Y + 1, IntToStr(K), $FFFFFFFF);
      end;
    //}
    { Center points and transitions of polygons
    for K := 0 to fPolyCount - 1 do
      with fPolygons[K] do
      begin
        gRenderAux.Quad(CenterPoint.X, CenterPoint.Y, $AAFFFFFF);
        for L := 0 to NearbyCount - 1 do
          gRenderAux.Quad(NearbyPoints[L].X, NearbyPoints[L].Y, $AA000000);
      end;
    //}
  
    //{ DEFENCE SYSTEM
    // Show this defences only in case that show combat AI is not enabled;
    // when it is we need existing results not the actual (defences are updated each 1 min so it may be different)
    if OVERLAY_NAVMESH AND OVERLAY_DEFENCES AND not OVERLAY_AI_COMBAT then
    begin
      Owner := gMySpectator.HandID;
      FFF := TForwardFF.Create(true);
      try
        if FFF.FindDefenceLines(Owner, DefLines) then
          for K := 0 to DefLines.Count - 1 do
          begin
            L := DefLines.Lines[K].Polygon;
            gRenderAux.TriangleOnTerrain(
              fNodes[fPolygons[L].Indices[0]].X,
              fNodes[fPolygons[L].Indices[0]].Y,
              fNodes[fPolygons[L].Indices[1]].X,
              fNodes[fPolygons[L].Indices[1]].Y,
              fNodes[fPolygons[L].Indices[2]].X,
              fNodes[fPolygons[L].Indices[2]].Y, $300000FF);
          end;
        if FFF.FindDefensivePolygons(Owner, DefencePosArr) then
          for K := 0 to Length(DefencePosArr) - 1 do
          begin
            p1 := DefencePosArr[K].DirPoint.Loc;
            gRenderAux.CircleOnTerrain(p1.X, p1.Y, 2, $0900FFFF, $FFFFFFFF);
          end;
      finally
        FreeAndNil(FFF);
      end;
    end;
    //}
  end;
  
  
  end.
  