anchor.diff:  interface
   uses
     KM_PolySimplify,
  -  KM_CommonClasses, KM_CommonTypes, KM_Defaults, KM_Points,
  +  KM_CommonClasses, KM_CommonTypes, KM_Defaults, KM_Points, Contnrs,
     KM_NavMeshDefences,
     KromUtils, KM_CommonUtils,
     KM_NavMeshFloodPositioning, KM_NavMeshPathFinding;// TimeGet
   
   
   type
  -  TKMWeightSegments = array of record
  -    A,B: TKMPoint;
  -    Weight: Single;
  -  end;
  -
  -  TNode = record
  -      Loc: TKMPoint;
  -      Nearby: array of Word; //Indexes of connected nodes
  -    end;
  +
  +  TKMNavMeshByteArray = array[-1..257,-1..257] of Byte;
  +  TKMNavMeshWordArray = array[-1..257,-1..257] of Word;
  +
  +  // Borders
  +  TKMBord = record
  +    Node, Prev, Next, NextY: Word;
  +  end;
  +  TKMBordInfo = record
  +    Count: Word;
  +    Borders: array[0..6000] of TKMBord;
  +  end;
  +
  +  // PolyLines
  +  PPolyLine = ^TKMPolyLine;
  +  TKMPolyLine = record
  +    Node,Polygon: Word;
  +    Next: PPolyLine;
  +  end;
  +  PPolyLines = ^TKMPolyLines;
  +  TKMPolyLines = record
  +  	LeftEdge, RightEdge, FutureLeftEdge, FutureRightEdge: Word;
  +    FirstLine, LastLine: PPolyLine;
  +  end;
  +
  +
  +  TDebugLines = record // Only for debug
  +    Count: Word;
  +    Lines: array[0..15000] of record
  +      P1,P2: TKMPoint;
  +    end;
  +  end;
   
     TPolygon = record
         CenterPoint: TKMPoint;
  
positive.code:         gRenderAux.Quad(NearbyPoints[K].X, NearbyPoints[K].Y, $AA000000);
      end;//}
  
    {Raw obstacle outlines
    if OVERLAY_NAVMESH then
      for I := 0 to fRawOutlines.Count - 1 do
      for K := 0 to fRawOutlines.Shape[I].Count - 1 do
      with fRawOutlines.Shape[I] do
        gRenderAux.LineOnTerrain(Nodes[K], Nodes[(K + 1) mod Count], $FFFF00FF);//}
  
    {NavMesh polys coverage
    if OVERLAY_NAVMESH then
      for I := 0 to fPolyCount - 1 do
        //if fPolygons[I].NearbyCount = 3 then
        gRenderAux.TriangleOnTerrain(
          fNodes[fPolygons[I].Indices[0]].Loc.X,
          fNodes[fPolygons[I].Indices[0]].Loc.Y,
          fNodes[fPolygons[I].Indices[1]].Loc.X,
          fNodes[fPolygons[I].Indices[1]].Loc.Y,
          fNodes[fPolygons[I].Indices[2]].Loc.X,
          fNodes[fPolygons[I].Indices[2]].Loc.Y, $90FF0000);//}
  
    //NavMesh edges
    if OVERLAY_NAVMESH then
      for I := 0 to fPolyCount - 1 do
      with fPolygons[I] do
      for K := 0 to 2 do
      begin
        T1 := KMPointF(fNodes[Indices[K]].Loc);
        J := (K + 1) mod 2;
        T2 := KMPointF(fNodes[Indices[J]].Loc);
        gRenderAux.LineOnTerrain(T1, T2, $80FF8000, $F0F0);
      end;
  
    {//NavMesh vertice ids
    if OVERLAY_NAVMESH then
      for I := 0 to High(fVertices) do
        gRenderAux.Text(fVertices[I].X,fVertices[I].Y, IntToStr(I), $FF000000); //}
  
    //{//NavMesh polys ids
    if OVERLAY_NAVMESH then
      for I := 0 to fPolyCount - 1 do
      with fPolygons[I] do
      begin
        T1.X := (fNodes[Indices[0]].Loc.X + fNodes[Indices[1]].Loc.X + fNodes[Indices[2]].Loc.X) / 3;
        T1.Y := (fNodes[Indices[0]].Loc.Y + fNodes[Indices[1]].Loc.Y + fNodes[Indices[2]].Loc.Y) / 3;
        gRenderAux.Text(Round(T1.X), Round(T1.Y) + 1, IntToStr(I), $FF000000);
      end;//}
  
    {//Simplified obstacle outlines
    if OVERLAY_NAVMESH then
      for I := 0 to fSimpleOutlines.Count - 1 do
      for K := 0 to fSimpleOutlines.Shape[I].Count - 1 do
      with fSimpleOutlines.Shape[I] do
        gRenderAux.Line(Nodes[K], Nodes[(K + 1) mod Count], $FF00FF00, $FF00);//}
  
    {//NavMesh influences
    if OVERLAY_NAVMESH then
      for I := 0 to fNodeCount - 1 do
      begin
        K := GetBestOwner(I);
        if K <> PLAYER_NONE then
        begin
          //Col := fPlayers[K].FlagColor or $FF000000;
          Col := $FF000000;
          Col2 := IfThen(fNodes[I].Owner[K] = 255, $FFFFFFFF);
          Sz := Max(fNodes[I].Owner[K] - 128, 0) / 64;
  
          gRenderAux.CircleOnTerrain(
            fNodes[I].Loc.X,
            fNodes[I].Loc.Y, Sz, Col, Col2);
        end;
      end;//}
  
    {//Defence outlines
    if OVERLAY_DEFENCES then
      for I := 0 to gHands.Count - 1 do
      begin
        fAI.Setup.NewAI
        GetDefenceOutline(I, Outline1, Outline2);
  
        for K := 0 to High(Outline1) do
          gRenderAux.LineOnTerrain(Outline1[K].A, Outline1[K].B, $FF00FFFF, $FF00);
  
        for K := 0 to High(Outline2) do
        begin
          gRenderAux.LineOnTerrain(Outline2[K].A, Outline2[K].B, $A000FF00);
          T1 := KMPointF(Outline2[K].A);
          T2 := KMPerpendecular(Outline2[K].A, Outline2[K].B);
          gRenderAux.LineOnTerrain(T1.X, T1.Y, T2.X, T2.Y, $A000FF00);
        end;
      end;//}
  end;
  
  
  
  
  //function GetOwnerPolys(aOwner: TKMHandIndex): TKMWordArray;
  //function ConvertPolysToEdges(aPolys: TKMWordArray): TKMEdgesArray;
  //function RemoveInnerEdges(const aEdges: TKMEdgesArray): TKMEdgesArray;
  //function EdgesToWeightOutline(const aEdges: TKMEdgesArray; aOwner: TKMHandIndex): TKMWeightSegments;
  
  //function GetBestOwner(aIndex: Integer): TKMHandIndex;
  //function NodeEnemyPresence(aIndex: Integer; aOwner: TKMHandIndex): Word;
  //function PolyEnemyPresence(aIndex: Integer; aOwner: TKMHandIndex): Word;
  
  {
  function TKMNavMesh.GetBestOwner(aIndex: Integer): TKMHandIndex;
  var
    I: Integer;
    Best: Byte;
  begin
    Best := 0;
    Result := PLAYER_NONE;
    for I := 0 to gHands.Count - 1 do
    if fNodes[aIndex].Owner[I] > Best then
    begin
      Best := fNodes[aIndex].Owner[I];
      Result := I;
    end;
  end;
  
  
  function TKMNavMesh.NodeEnemyPresence(aIndex: Integer; aOwner: TKMHandIndex): Word;
  var I: Integer;
  begin
    Result := 0;
    for I := 0 to gHands.Count - 1 do
    if (I <> aOwner) and (gHands.CheckAlliance(aOwner, I) = at_Enemy) then
      Result := Result + fNodes[aIndex].Owner[I];
  end;
  
  
  function TKMNavMesh.PolyEnemyPresence(aIndex: Integer; aOwner: TKMHandIndex): Word;
  var I: Integer;
  begin
    Result := 0;
    for I := 0 to gHands.Count - 1 do
    if (I <> aOwner) and (gHands.CheckAlliance(aOwner, I) = at_Enemy) then
      Result := Result + (fNodes[fPolygons[aIndex].Indices[0]].Owner[I]
                        + fNodes[fPolygons[aIndex].Indices[1]].Owner[I]
                        + fNodes[fPolygons[aIndex].Indices[2]].Owner[I]) div 3;
  end;
  
  
  function TKMNavMesh.GetOwnerPolys(aOwner: TKMHandIndex): TKMWordArray;
  var I,K: Integer;
  begin
    //Collect polys that are well within our ownership area
    K := 0;
    SetLength(Result, fPolyCount);
  
    for I := 0 to fPolyCount - 1 do
    with fPolygons[I] do
    if ((fNodes[Indices[0]].Owner[aOwner] >= OWN_MARGIN)
     or (fNodes[Indices[1]].Owner[aOwner] >= OWN_MARGIN)
     or (fNodes[Indices[2]].Owner[aOwner] >= OWN_MARGIN))
    and (fNodes[Indices[0]].Owner[aOwner] >= OWN_THRESHOLD)
    and (fNodes[Indices[1]].Owner[aOwner] >= OWN_THRESHOLD)
    and (fNodes[Indices[2]].Owner[aOwner] >= OWN_THRESHOLD)
    and (GetBestOwner(Indices[0]) = aOwner)
    and (GetBestOwner(Indices[1]) = aOwner)
    and (GetBestOwner(Indices[2]) = aOwner) then
    begin
      Result[K] := I;
      Inc(K);
    end;
    SetLength(Result, K);
  end;
  
  
  function TKMNavMesh.ConvertPolysToEdges(aPolys: TKMWordArray): TKMEdgesArray;
  var I: Integer;
  begin
    Result.Count := Length(aPolys) * 3;
    SetLength(Result.Nodes, Length(aPolys) * 3);
    for I := 0 to High(aPolys) do
    begin
      Result.Nodes[I * 3 + 0, 0] := fPolygons[aPolys[I]].Indices[0];
      Result.Nodes[I * 3 + 0, 1] := fPolygons[aPolys[I]].Indices[1];
      Result.Nodes[I * 3 + 1, 0] := fPolygons[aPolys[I]].Indices[1];
      Result.Nodes[I * 3 + 1, 1] := fPolygons[aPolys[I]].Indices[2];
      Result.Nodes[I * 3 + 2, 0] := fPolygons[aPolys[I]].Indices[2];
      Result.Nodes[I * 3 + 2, 1] := fPolygons[aPolys[I]].Indices[0];
    end;
  end;
  
  
  function TKMNavMesh.RemoveInnerEdges(const aEdges: TKMEdgesArray): TKMEdgesArray;
  var
    I,K: Integer;
    Edges: TKMEdgesArray;
  begin
    //Duplicate to avoid spoiling (we need to copy arrays manually)
    Edges.Count := aEdges.Count;
    SetLength(Edges.Nodes, Edges.Count);
    for I := 0 to aEdges.Count - 1 do
    begin
      Edges.Nodes[I][0] := aEdges.Nodes[I][0];
      Edges.Nodes[I][1] := aEdges.Nodes[I][1];
    end;
  
    //Remove duplicate Edges, that will leave us with an outline
    for I := 0 to Edges.Count - 1 do
      if (Edges.Nodes[I, 0] > -1) and (Edges.Nodes[I, 1] > -1) then
        for K := I + 1 to Edges.Count - 1 do
          if (Edges.Nodes[K, 0] > -1) and (Edges.Nodes[K, 1] > -1) then
            if (Edges.Nodes[I, 0] = Edges.Nodes[K, 1]) and (Edges.Nodes[I, 1] = Edges.Nodes[K, 0]) then
            begin
              Edges.Nodes[I, 0] := -1;
              Edges.Nodes[I, 1] := -1;
              Edges.Nodes[K, 0] := -1;
              Edges.Nodes[K, 1] := -1;
            end;
  
    //3. Detect and dismiss inner Edges
    //Separate Edges into open (having 2 polys) and closed (only 1 poly)
    //Once again we take advantage of the fact that polys built in CW order
    for I := 0 to fPolyCount - 1 do
      with fPolygons[I] do
        for K := 0 to Edges.Count - 1 do
          if (Edges.Nodes[K, 0] <> -1) then
            if ((Edges.Nodes[K, 0] = Indices[1]) and (Edges.Nodes[K, 1] = Indices[0]))
            or ((Edges.Nodes[K, 0] = Indices[2]) and (Edges.Nodes[K, 1] = Indices[1]))
            or ((Edges.Nodes[K, 0] = Indices[0]) and (Edges.Nodes[K, 1] = Indices[2])) then
            begin
              //Mark outer Edges
              Edges.Nodes[K, 0] := -1000 - Edges.Nodes[K, 0];
              Edges.Nodes[K, 1] := -1000 - Edges.Nodes[K, 1];
            end;
    K := 0;
    for I := 0 to Edges.Count - 1 do
      if (Edges.Nodes[I, 0] >= 0) then
      begin //Dismiss inner Edges
        Edges.Nodes[I, 0] := -1;
        Edges.Nodes[I, 1] := -1;
      end
      else if (Edges.Nodes[I, 0] < -1) then
      begin //Promote marked outer Edges back
        Edges.Nodes[I, 0] := -Edges.Nodes[I, 0] - 1000;
        Edges.Nodes[I, 1] := -Edges.Nodes[I, 1] - 1000;
        Inc(K);
      end;
  
    //4. Now we can assemble suboptimal outline from kept Edges
    Result.Count := K;
    SetLength(Result.Nodes, K);
    K := 0;
    for I := 0 to Edges.Count - 1 do
      if (Edges.Nodes[I, 0] >= 0) then
      begin
        Result.Nodes[K, 0] := Edges.Nodes[I, 0];
        Result.Nodes[K, 1] := Edges.Nodes[I, 1];
        Inc(K);
      end;
  end;
  
  
  function TKMNavMesh.EdgesToWeightOutline(const aEdges: TKMEdgesArray; aOwner: TKMHandIndex): TKMWeightSegments;
  var I: Integer;
  begin
    SetLength(Result, aEdges.Count);
    for I := 0 to aEdges.Count - 1 do
    begin
      Result[I].A := fNodes[aEdges.Nodes[I,0]].Loc;
      Result[I].B := fNodes[aEdges.Nodes[I,1]].Loc;
      Result[I].Weight := NodeEnemyPresence(aEdges.Nodes[I,0], aOwner)
                        + NodeEnemyPresence(aEdges.Nodes[I,1], aOwner);
    end;
  end;
  
  
  procedure TKMNavMesh.GetDefenceOutline(aOwner: TKMHandIndex; out aOutline1, aOutline2: TKMWeightSegments);
  const
    AP_CLEAR = 0;
    AP_SEED = 255;
  var
    AreaID: Byte;
    AreaPolys: array of Byte;
    AreaEnemy: array [1..254] of Word;
  
    procedure FloodFillPolys(aIndex: Integer);
    var I: Integer;
    begin
      with fPolygons[aIndex] do
      for I := 0 to NearbyCount - 1 do
      if (AreaPolys[Nearby[I]] = AP_CLEAR) then
      begin
        AreaPolys[Nearby[I]] := AreaID; //Mark as explored
        AreaEnemy[AreaID] := Max(AreaEnemy[AreaID], PolyEnemyPresence(Nearby[I], aOwner));
        FloodFillPolys(Nearby[I]);
      end;
    end;
  
  var
    I,K: Integer;
    Polys: TKMWordArray;
    Edges: TKMEdgesArray;
  
    diff: Cardinal;
    Sdiff: String;
  
  begin
  
    diff := TimeGet;
  
  
    //1. Get ownership area
    Polys := GetOwnerPolys(aOwner);
  
    Edges := ConvertPolysToEdges(Polys);
  
    //Obtain suboptimal outline of owned polys
    Edges := RemoveInnerEdges(Edges);
  
    aOutline1 := EdgesToWeightOutline(Edges, aOwner);
  
    //5. Remove spans that face isolated areas
    SetLength(AreaPolys, fPolyCount);
    for I := Low(AreaEnemy) to High(AreaEnemy) do
      AreaEnemy[I] := 0;
  
    for I := 0 to High(Polys) do
      AreaPolys[Polys[I]] := AP_SEED;
  
    //Floodfill outer polys skipping inner ones, remember best enemy influence
    AreaID := 0;
    for I := 0 to High(Polys) do
      with fPolygons[Polys[I]] do
        for K := 0 to NearbyCount - 1 do
        if (AreaPolys[Nearby[K]] = AP_CLEAR) then
        begin
          Inc(AreaID);
          FloodFillPolys(Polys[I]);
        end;
  
    //if enemy influence < 128 then mark as isolated
    K := Length(Polys);
    SetLength(Polys, fPolyCount);
    for I := 0 to fPolyCount - 1 do
      if (AreaPolys[I] <> AP_CLEAR)
      and (AreaPolys[I] <> AP_SEED)
      and (AreaEnemy[AreaPolys[I]] < 128) then
      begin
        Polys[K] := I;
        Inc(K);
      end;
    SetLength(Polys, K);
  
    Edges := ConvertPolysToEdges(Polys);
  
    Edges := RemoveInnerEdges(Edges);
  
    aOutline2 := EdgesToWeightOutline(Edges, aOwner);
  
    diff := GetTimeSince(diff);
    Str(diff,Sdiff);
    //ShowMessage(Sdiff);
  
    //6. See if we can expand our area while reducing outline length
  
    //7. Deal with allies
    //   Two players could be on same island and share defence lines,
    //   also they dont need defence line between them
  end;
  //}
  
  
  {
  // The following code was removed and replaced by NavMesh alternative
  TNode = record
      Loc: TKMPoint;
      Nearby: array of Word; //Indexes of connected nodes
      Owner: array [0..MAX_HANDS-1] of Byte;
    end;
  //Copy ownership values from influence map
  //  for now those values are more accurate
  procedure TKMNavMesh.UpdateOwnership;
  var
    I, K: Integer;
  begin
    if not AI_GEN_NAVMESH then Exit;
  
    for I := 0 to fNodeCount - 1 do
      for K := 0 to gHands.Count - 1 do
        fNodes[I].Owner[K] := Min(255, Max(
          Max(fInfluences.Ownership[K, Max(fNodes[I].Loc.Y, 1), Max(fNodes[I].Loc.X, 1)],
              fInfluences.Ownership[K, Max(fNodes[I].Loc.Y, 1), Min(fNodes[I].Loc.X+1, gTerrain.MapX - 1)]),
          Max(fInfluences.Ownership[K, Min(fNodes[I].Loc.Y+1, gTerrain.MapY - 1), Max(fNodes[I].Loc.X, 1)],
              fInfluences.Ownership[K, Min(fNodes[I].Loc.Y+1, gTerrain.MapY - 1), Min(fNodes[I].Loc.X+1, gTerrain.MapX - 1)])
              ));
  end;
  //}
  
  end.
  
negative.code:       NearbyPoints: array [0..2] of TKMPoint; // Center points
      end;
  
    TPolygonArray = array of TPolygon;
  
    //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
      //Keep a copy of these temp arrays for debug rendering
      fInnerPointStartIdx, fInnerPointEndIdx: Word;
      fBordByY, fIdxArr: array[0..256] of Word;
      fBord: TKMBordInfo;
      fDL, fDL2: TDebugLines;
  
      //Working data
      fNodeCount: Integer;
      fPolyCount: Integer;
      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
  
      //Building the navmesh from terrain
      procedure ExtractPolygons();
      procedure PolygonTriangulation();
      procedure PrettyPoly();
      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
  