Changeset 175 for trunk/UMap.pas

Timestamp:

Nov 26, 2017, 9:06:01 PM (7 years ago)

Author:

chronos

Message:

• Modified: Simplified algorithm for generation of random mesh map.

File:

• trunk/UMap.pas (modified) (4 diffs)

trunk/UMap.pas

@@ -6 +6 @@
 
 uses
-  Classes, SysUtils, UGame, XMLRead, XMLWrite, DOM, UGeometryClasses,
+  Classes, SysUtils, UGame, XMLRead, XMLWrite, DOM,
   UGeometry, fgl;
 
@@ -249 +249 @@
 var
   X, Y: Integer;
-  I1, I2: Integer;
   NewCell: TCell;
-  CellsDistance: TFPGObjectList<TCellsDistance>;
-  NewCellDist: TCellsDistance;
-  SelectedCells: TFPGObjectList<TCellsDistance>;
   I, J: Integer;
-  Intersected: Boolean;
-  Intersection: TPoint;
-  CellDistance: TCellsDistance;
   Cell: TCell;
   Cell2: TCell;
-  L1, L2: TLine;
+  L1: TLine;
   MP: TPoint;
   LinkLine: TLine;
-  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;
 const
   CellGapWidth = 4;
@@ -300 +276 @@
   end;
 
-  // Calculate distance between all cells
-  CellsDistance := TFPGObjectList<TCellsDistance>.Create;
-  for I1 := 0 to Cells.Count - 1 do
-  for I2 := I1 + 1 to Cells.Count - 1 do begin
-    NewCellDist := TCellsDistance.Create;
-    NewCellDist.Cell1 := Cells[I1];
-    NewCellDist.Cell2 := Cells[I2];
-    NewCellDist.Distance := TLine.Create(NewCellDist.Cell1.PosPx, NewCellDist.Cell2.PosPx).Distance;
-    CellsDistance.Add(NewCellDist);
-  end;
-  CellsDistance.Sort(CompareDistance);
-
-  // Keep shortest non-intersected cell pairs
-  SelectedCells := TFPGObjectList<TCellsDistance>.Create;
-  SelectedCells.FreeObjects := False;
-  I := 0;
-  while I < CellsDistance.Count do begin
-    Intersected := False;
-    for J := 0 to SelectedCells.Count - 1 do
-    if (TCellsDistance(SelectedCells[J]).Cell1 <> TCellsDistance(CellsDistance[I]).Cell1)
-    and (TCellsDistance(SelectedCells[J]).Cell2 <> TCellsDistance(CellsDistance[I]).Cell2)
-    and (TCellsDistance(SelectedCells[J]).Cell1 <> TCellsDistance(CellsDistance[I]).Cell2)
-    and (TCellsDistance(SelectedCells[J]).Cell2 <> TCellsDistance(CellsDistance[I]).Cell1) then begin
-      L1 := TLine.Create(TCellsDistance(CellsDistance[I]).Cell1.PosPx,
-        TCellsDistance(CellsDistance[I]).Cell2.PosPx);
-      L2 := TLine.Create(TCellsDistance(SelectedCells[J]).Cell1.PosPx,
-        TCellsDistance(SelectedCells[J]).Cell2.PosPx);
-      if TLine.LineIntersect(L1, L2, Intersection) then begin
-        if L1.ToRect.IsPointInside(Intersection) and
-        L2.ToRect.IsPointInside(Intersection) then begin
-          Intersected := True;
-          Break;
-        end;
-      end;
-    end;
-    if not Intersected then SelectedCells.Add(CellsDistance[I]);
-    Inc(I);
-  end;
-
-  // Add cell neighbors
-  for I := 0 to SelectedCells.Count - 1 do begin
-    CellDistance := TCellsDistance(SelectedCells[I]);
-    CellDistance.Cell1.Neighbors.Add(CellDistance.Cell2);
-    CellDistance.Cell2.Neighbors.Add(CellDistance.Cell1);
-  end;
-
-  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];
-      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
-    // Use whole map first for cell polygon
-    if Cell.Neighbors.Count > 0 then begin
-      Polygon := TPolygon.Create(TRect.Create(TPoint.Create(0, 0),
-        TPoint.Create(Size.X * DefaultCellSize.X, Size.Y * DefaultCellSize.Y)));
-      for NeighborCell in Cell.Neighbors do begin
-        LinkLine := TLine.Create(Cell.PosPx, NeighborCell.PosPx);
-        LinkLine.Distance := LinkLine.Distance - CellGapWidth;
-        MP := LinkLine.GetMiddle;
-        // Create half plane vector
-        L1 := TLine.Create(MP, TPoint.Create(MP.X + LinkLine.GetSize.X,
-          MP.Y + LinkLine.GetSize.Y));
-
-        Polygon.CutLine(L1, Cell.PosPx);
-      end;
-      Cell.Polygon := Polygon;
-    end else Cell.Polygon.Clear;
-  end;}
-
-  // Additional polygon by all other cells
+  // Compute polygon cat out by all other cells
   for Cell in Cells do begin
     Cell.Polygon := TPolygon.Create(TRect.Create(TPoint.Create(0, 0),
@@ -426 +282 @@
     for Cell2 in Cells do
     if Cell2 <> Cell then begin
-          LinkLine := TLine.Create(Cell.PosPx, Cell2.PosPx);
-          LinkLine.Distance := LinkLine.Distance - CellGapWidth;
-          MP := LinkLine.GetMiddle;
-          // Create half plane vector
-          L1 := TLine.Create(MP, TPoint.Create(MP.X + LinkLine.GetSize.X,
-            MP.Y + LinkLine.GetSize.Y));
-
-          Cell.Polygon.CutLine(L1, Cell.PosPx);
+      LinkLine := TLine.Create(Cell.PosPx, Cell2.PosPx);
+      LinkLine.Distance := LinkLine.Distance - CellGapWidth;
+      MP := LinkLine.GetMiddle;
+      // Create half plane vector
+      L1 := TLine.Create(MP, TPoint.Create(MP.X + LinkLine.GetSize.X,
+        MP.Y + LinkLine.GetSize.Y));
+
+      Cell.Polygon.CutLine(L1, Cell.PosPx);
     end;
   end;
 
-  // Remove all neighbor links for cell pairs with non-overlaping polygons
-  for Cell in Cells do begin
-    for I := Cell.Neighbors.Count - 1 downto 0 do begin
-      if Cell.Polygon.EdgeDistance(Cell.Neighbors[I].Polygon) > 2 * CellGapWidth then
-        Cell.Neighbors.Delete(I);
+  // Link all cells with neighboring polygon edges
+  for I := 0 to Cells.Count - 1 do begin
+    for J := I + 1 to Cells.Count - 1 do begin
+      if Cells[I].Polygon.EdgeDistance(Cells[J].Polygon) < 2 * CellGapWidth then
+        Cells[I].ConnectTo(Cells[J]);
     end;
   end;