Changeset 165

Timestamp:

Nov 22, 2017, 4:48:33 PM (7 years ago)

Author:

chronos

Message:

• Added: Optimization phase for voronoi map generation.

Location:

trunk

Files:

• Packages/Common/UGeometry.pas (modified) (7 diffs)
• UGame.pas (modified) (10 diffs)
• UMap.pas (modified) (4 diffs)
• xtactics.lpr (modified) (1 diff)

trunk/Packages/Common/UGeometry.pas

@@ -14 +14 @@
 
   TLine = record
+  private
+    function GetDistance: Double;
+    procedure SetDistance(AValue: Double);
+  public
     P1: TPoint;
     P2: TPoint;
     function Create(P1, P2: TPoint): TLine;
-    function Distance: Double;
     function GetMiddle: TPoint;
     function GetAngle: Double;
@@ -25 +28 @@
     procedure Rotate(Angle: Double);
     class operator Equal(A, B: TLine): Boolean;
+    property Distance: Double read GetDistance write SetDistance;
   end;
 
@@ -56 +60 @@
 function PointInRect(P: TPoint; aRect: TRect): Boolean;
 function HalfDistancePoint(P1, P2: TPoint): TPoint;
+function NormalizeAngle(Angle: Double): Double;
+function SubAngle(A1, A2: Double): Double;
 
 implementation
@@ -208 +214 @@
 begin
   Result := Point(P1.X + (P2.X - P1.X) div 2, P1.Y + (P2.Y - P1.Y) div 2)
+end;
+
+function NormalizeAngle(Angle: Double): Double;
+begin
+  if Angle < 0 then Result := Angle + (Trunc(Angle / (2 * Pi)) + 1) * (2 * Pi)
+  else if Angle > 2 * Pi then Result := Angle - Trunc(Angle / (2 * Pi)) * (2 * Pi)
+  else Result := Angle;
+end;
+
+function SubAngle(A1, A2: Double): Double;
+begin
+  A1 := NormalizeAngle(A1);
+  A2 := NormalizeAngle(A2);
+  if A1 < A2 then Result := A1 + 2 * Pi - A2
+    else Result := A1 - A2;
 end;
 
@@ -310 +331 @@
       end else begin
         // Crossing line, end polygon. If point NewPolygonStarted, the use polygon as result
+        NewPoly.AddPoint(Points[I]);
         NewPoly.AddPoint(Intersection);
         if NewPoly.IsPointInside(PointInside) then begin
@@ -326 +348 @@
     if PointsChecked > 2 * Length(Points) then Break;
   end;
-  if Success then Points := NewPoly.Points
-    else Clear;
+  if Success then Points := NewPoly.Points;
 end;
 
 { TLine }
+
+function TLine.GetDistance: Double;
+begin
+  Result := Sqrt(Sqr(P2.X - P1.X) + Sqr(P2.Y - P1.Y));
+end;
+
+procedure TLine.SetDistance(AValue: Double);
+var
+  Angle: Double;
+begin
+  Angle := GetAngle;
+  P2 := Point(Round(P1.X + Cos(Angle) * AValue),
+    Round(P1.Y + Sin(Angle) * AValue));
+end;
 
 function TLine.Create(P1, P2: TPoint): TLine;
@@ -336 +371 @@
   Result.P1 := P1;
   Result.P2 := P2;
-end;
-
-function TLine.Distance: Double;
-begin
-  Result := Sqrt(Sqr(P2.X - P1.X) + Sqr(P2.Y - P1.Y));
 end;
 

trunk/UGame.pas

@@ -7 +7 @@
 uses
   Classes, SysUtils, ExtCtrls, Graphics, XMLConf, XMLRead, XMLWrite,
-  DOM, Math, LazFileUtils, UXMLUtils, Dialogs, Types, LCLType, LCLIntf, fgl;
+  DOM, Math, LazFileUtils, UXMLUtils, Dialogs, Types, LCLType, LCLIntf, fgl,
+  UGeometry;
 
 const
@@ -60 +61 @@
     Mark: Boolean; // Temporary value
     Weight: Integer; // Temporary value
+    Angle: Double; // Temporary value
     Links: TCellLinks;
+    procedure ConnectTo(Cell: TCell);
+    procedure DisconnectFrom(Cell: TCell);
     procedure Check;
     function NeighboringToVoid: Boolean;
@@ -93 +97 @@
     procedure ClearMark;
     procedure ClearWeight;
+    function ToString: ansistring; override;
   end;
 
@@ -115 +120 @@
     procedure LoadFromNode(Node: TDOMNode);
     procedure SaveToNode(Node: TDOMNode);
+  end;
+
+  { TCellLinkParams }
+
+  TCellLinkParams = class
+    Cell1: TCell;
+    Cell2: TCell;
+    Distance: Double;
+    Angle: Double;
   end;
 
@@ -187 +201 @@
     FNewCellId: Integer;
     function GetNewCellId: Integer; virtual;
+    procedure SortNeighborsByAngle;
   public
     Game: TGame;
@@ -1032 +1047 @@
         Player.Game.Map.PaintCell(Canvas, Cell.MapCell.PosPx, '', View, Cell.MapCell);
       end;
-
-      {// Draw links to neighbors
+    end;
+
+{    // Draw links to neighbors
+    for Cell in Cells do begin
       for NeighCell in Cell.MapCell.Neighbors do begin
         Pen.Color := clYellow;
@@ -1039 +1056 @@
         LineTo(View.CellToCanvasPos(NeighCell.PosPx));
       end;
-      }
-    end;
-
+
+      Font.Color := clRed;
+      Brush.Style := bsClear;
+      TextOut(View.CellToCanvasPos(Cell.MapCell.PosPx).X,
+        View.CellToCanvasPos(Cell.MapCell.PosPx).Y, IntToStr(Cell.MapCell.Id));
+    end;
+ }
     // Draw arrows
     Pen.Color := clCream;
@@ -1166 +1187 @@
 end;
 
+function TCells.ToString: ansistring;
+var
+  C: TCell;
+begin
+  Result := '';
+  for C in Self do
+    Result := Result + IntToStr(C.Id) + ', ';
+end;
+
 { TPlayers }
 
@@ -1353 +1383 @@
     FSize := AValue;
     if FUpdateCount = 0 then Generate;
+  end;
+end;
+
+function CompareCellAngle(const C1, C2: TCell): Integer;
+begin
+  if C1.Angle < C2.Angle then Result := -1
+  else if C1.Angle > C2.Angle then Result := 1
+  else Result := 0;
+end;
+
+procedure TMap.SortNeighborsByAngle;
+var
+  Cell: TCell;
+  NeighborCell: TCell;
+begin
+  for Cell in Cells do begin
+    for NeighborCell in Cell.Neighbors do
+      NeighborCell.Angle := ArcTan2Point(Point(
+        NeighborCell.PosPx.X - Cell.PosPx.X,
+        NeighborCell.PosPx.Y - Cell.PosPx.Y));
+
+    Cell.Neighbors.Sort(CompareCellAngle);
   end;
 end;
@@ -1896 +1948 @@
   FPower := AValue;
   //Check;
+end;
+
+procedure TCell.ConnectTo(Cell: TCell);
+begin
+  Cell.Neighbors.Add(Self);
+  Neighbors.Add(Cell);
+end;
+
+procedure TCell.DisconnectFrom(Cell: TCell);
+var
+  I: Integer;
+begin
+  I := Cell.Neighbors.IndexOf(Self);
+  if I >= 0 then Cell.Neighbors.Delete(I) else
+    raise Exception.Create('Can''t disconnect neigboring cells.');
+  I := Neighbors.IndexOf(Cell);
+  if I >= 0 then Neighbors.Delete(I)
+    else Exception.Create('Can''t disconnect neigboring cells.');
 end;
 

trunk/UMap.pas

@@ -271 +271 @@
   Intersection: TPoint;
   CellDistance: TCellsDistance;
-  R1, R2: TRect;
   Cell: TCell;
-  CellsAngle: TObjectList; // TObjecTList<TCellsDistance>
-  CellAngle: TCellsDistance;
-  NextCellAngle: TCellsDistance;
   L1, L2: TLine;
   MP: TPoint;
   LinkLine: TLine;
   Polygon: TPolygon;
+  //LeftLink: TCellsDistance;
+  //CenterLink: TCellsDistance;
+  //RightLink: TCellsDistance;
+  LeftClosingLine1: TLine;
+  LeftClosingLine2: TLine;
+  RightClosingLine1: TLine;
+  RightClosingLine2: TLine;
+  CurrentAngle: Double;
+  LeftAngle: Double;
+  RightAngle: Double;
+  CenterCell: TCell;
+  LeftCell: TCell;
+  RightCell: TCell;
+  LeftIndex: Integer;
+  RightIndex: Integer;
+  LeftCenterCell: TCell;
+  RightCenterCell: TCell;
+  ChangesCount: Integer;
+  LeftCellCommon: TCell;
+  RightCellCommon: TCell;
+  LeftText: string;
+  RightText: string;
 begin
   Clear;
-
-  // Allocate and init new
+  RandSeed := 1234;
+
+  // Allocate and init new cells
   Cells.Count := Size.Y * Size.X;
   for Y := 0 to Size.Y - 1 do
@@ -325 +344 @@
         TCellsDistance(SelectedCells[J]).Cell2.PosPx);
       if LineIntersect(L1, L2, Intersection) then begin
-          R1 := PointsToRect(TCellsDistance(CellsDistance[I]).Cell1.PosPx,
-            TCellsDistance(CellsDistance[I]).Cell2.PosPx);
-          R2 := PointsToRect(TCellsDistance(SelectedCells[J]).Cell1.PosPx,
-            TCellsDistance(SelectedCells[J]).Cell2.PosPx);
-          if PointInRect(Intersection, R1) and PointInRect(Intersection, R2) then begin
-            Intersected := True;
-            Break;
-          end;
+        if PointInRect(Intersection, L1.ToRect) and
+        PointInRect(Intersection, L2.ToRect) then begin
+          Intersected := True;
+          Break;
         end;
+      end;
     end;
     if not Intersected then SelectedCells.Add(CellsDistance[I]);
@@ -348 +364 @@
   FreeAndNil(SelectedCells);
   FreeAndNil(CellsDistance);
+  SortNeighborsByAngle;
+
+  while True do begin
+  ChangesCount := 0;
+  // Optimize link lines for lower angle
+  for Cell in Cells do begin
+    // Change link if lower angle can be achieved
+    for I := 0 to Cell.Neighbors.Count - 1 do begin
+      LeftCell := Cell.Neighbors[I];
+      RightCell := Cell.Neighbors[(I + 1) mod Cell.Neighbors.Count];
+      LeftText := LeftCell.Neighbors.ToString;
+      RightText := RightCell.Neighbors.ToString;
+      LeftIndex := LeftCell.Neighbors.IndexOf(Cell);
+      RightIndex := RightCell.Neighbors.IndexOf(Cell);
+      LeftCellCommon := LeftCell.Neighbors[(LeftIndex + LeftCell.Neighbors.Count - 1) mod LeftCell.Neighbors.Count];
+      RightCellCommon := RightCell.Neighbors[(RightIndex + 1) mod RightCell.Neighbors.Count];
+      if (LeftCellCommon = RightCell) and
+      (RightCellCommon = LeftCell) then begin
+        LeftCenterCell := LeftCell.Neighbors[(LeftIndex + LeftCell.Neighbors.Count - 2) mod LeftCell.Neighbors.Count];
+        RightCenterCell := RightCell.Neighbors[(RightIndex + 2) mod RightCell.Neighbors.Count];
+
+        if LeftCenterCell = RightCenterCell then begin
+          CenterCell := LeftCenterCell;
+
+          LeftClosingLine1 := TLine.Create(LeftCell.PosPx, Cell.PosPx);
+          LeftClosingLine2 := TLine.Create(LeftCell.PosPx,
+            CenterCell.PosPx);
+          LeftAngle := SubAngle(LeftClosingLine1.GetAngle,
+            LeftClosingLine2.GetAngle);
+
+          RightClosingLine1 := TLine.Create(RightCell.PosPx, Cell.PosPx);
+          RightClosingLine2 := TLine.Create(RightCell.PosPx,
+            CenterCell.PosPx);
+          RightAngle := SubAngle(RightClosingLine2.GetAngle,
+            RightClosingLine1.GetAngle);
+
+          LeftClosingLine1 := TLine.Create(Cell.PosPx, LeftCell.PosPx);
+          RightClosingLine1 := TLine.Create(Cell.PosPx, RightCell.PosPx);
+          CurrentAngle := SubAngle(RightClosingLine1.GetAngle,
+            LeftClosingLine1.GetAngle);
+          if (CurrentAngle > LeftAngle) and (CurrentAngle > RightAngle) then begin
+            LeftCell.DisconnectFrom(RightCell);
+            Cell.ConnectTo(CenterCell);
+            SortNeighborsByAngle;
+            Inc(ChangesCount);
+          end;
+        end;
+        //end;
+      end;
+    end;
+  end;
+  if ChangesCount = 0 then Break;
+  end;
 
   // Compute polygon around cells with sequence sorted by link angle
   for Cell in Cells do begin
-    CellsAngle := TObjectList.Create;
-    for I := 0 to Cell.Neighbors.Count - 1 do begin
-      CellAngle := TCellsDistance.Create;
-      CellAngle.Cell1 := Cell;
-      CellAngle.Cell2 := TCell(Cell.Neighbors[I]);
-      CellAngle.Distance := ArcTan2Point(Point(
-        CellAngle.Cell2.PosPx.X - CellAngle.Cell1.PosPx.X,
-        CellAngle.Cell2.PosPx.Y - CellAngle.Cell1.PosPx.Y));
-      CellsAngle.Add(CellAngle);
-    end;
-    CellsAngle.Sort(CompareDistance);
-
     // Use whole map first for cell polygon
-    if CellsAngle.Count > 0 then begin
+    if Cell.Neighbors.Count > 0 then begin
       Polygon := TPolygon.Create(Rect(0, 0,
         Size.X * DefaultCellSize.X, Size.Y * DefaultCellSize.Y));
-      for I := 0 to CellsAngle.Count - 1 do begin
-        CellAngle := TCellsDistance(CellsAngle[I]);
-        LinkLine := TLine.Create(CellAngle.Cell1.PosPx,
-          CellAngle.Cell2.PosPx);
+      for I := 0 to Cell.Neighbors.Count - 1 do begin
+        LinkLine := TLine.Create(Cell.PosPx,
+          Cell.Neighbors[I].PosPx);
+        LinkLine.Distance := LinkLine.Distance - 4;
         MP := LinkLine.GetMiddle;
         // Create half plane vector
-        L1 := TLine.Create(MP, Point(MP.X + LinkLine.GetSize.X, MP.Y + LinkLine.GetSize.Y));
+        L1 := TLine.Create(MP, Point(MP.X + LinkLine.GetSize.X,
+          MP.Y + LinkLine.GetSize.Y));
 
         Polygon.CutLine(L1, Cell.PosPx);
@@ -379 +437 @@
       Cell.Polygon := Polygon.Points;
     end else SetLength(Cell.Polygon, 0);
-
-    FreeAndNil(CellsAngle);
   end;
 

trunk/xtactics.lpr

@@ -8 +8 @@
   {$ENDIF}
   Interfaces, // this includes the LCL widgetset
-  Forms, tachartlazaruspkg, UGame, UCore, Common, CoolTranslator,
-  TemplateGenerics, UFormPlayer
+  Forms, tachartlazaruspkg, UGame, UCore, Common,
+  CoolTranslator, TemplateGenerics, UFormPlayer
   { you can add units after this },
   SysUtils, UFormMain, UFormMove, UFormNew, UFormCharts, UFormUnitMoves;