Changeset 175 for trunk/UMap.pas


Ignore:
Timestamp:
Nov 26, 2017, 9:06:01 PM (7 years ago)
Author:
chronos
Message:
  • Modified: Simplified algorithm for generation of random mesh map.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/UMap.pas

    r174 r175  
    66
    77uses
    8   Classes, SysUtils, UGame, XMLRead, XMLWrite, DOM, UGeometryClasses,
     8  Classes, SysUtils, UGame, XMLRead, XMLWrite, DOM,
    99  UGeometry, fgl;
    1010
     
    249249var
    250250  X, Y: Integer;
    251   I1, I2: Integer;
    252251  NewCell: TCell;
    253   CellsDistance: TFPGObjectList<TCellsDistance>;
    254   NewCellDist: TCellsDistance;
    255   SelectedCells: TFPGObjectList<TCellsDistance>;
    256252  I, J: Integer;
    257   Intersected: Boolean;
    258   Intersection: TPoint;
    259   CellDistance: TCellsDistance;
    260253  Cell: TCell;
    261254  Cell2: TCell;
    262   L1, L2: TLine;
     255  L1: TLine;
    263256  MP: TPoint;
    264257  LinkLine: TLine;
    265   LeftClosingLine1: TLine;
    266   LeftClosingLine2: TLine;
    267   RightClosingLine1: TLine;
    268   RightClosingLine2: TLine;
    269   CurrentAngle: Double;
    270   LeftAngle: Double;
    271   RightAngle: Double;
    272   CenterCell: TCell;
    273   LeftCell: TCell;
    274   RightCell: TCell;
    275   LeftIndex: Integer;
    276   RightIndex: Integer;
    277   LeftCenterCell: TCell;
    278   RightCenterCell: TCell;
    279   ChangesCount: Integer;
    280   LeftCellCommon: TCell;
    281   RightCellCommon: TCell;
    282258const
    283259  CellGapWidth = 4;
     
    300276  end;
    301277
    302   // Calculate distance between all cells
    303   CellsDistance := TFPGObjectList<TCellsDistance>.Create;
    304   for I1 := 0 to Cells.Count - 1 do
    305   for I2 := I1 + 1 to Cells.Count - 1 do begin
    306     NewCellDist := TCellsDistance.Create;
    307     NewCellDist.Cell1 := Cells[I1];
    308     NewCellDist.Cell2 := Cells[I2];
    309     NewCellDist.Distance := TLine.Create(NewCellDist.Cell1.PosPx, NewCellDist.Cell2.PosPx).Distance;
    310     CellsDistance.Add(NewCellDist);
    311   end;
    312   CellsDistance.Sort(CompareDistance);
    313 
    314   // Keep shortest non-intersected cell pairs
    315   SelectedCells := TFPGObjectList<TCellsDistance>.Create;
    316   SelectedCells.FreeObjects := False;
    317   I := 0;
    318   while I < CellsDistance.Count do begin
    319     Intersected := False;
    320     for J := 0 to SelectedCells.Count - 1 do
    321     if (TCellsDistance(SelectedCells[J]).Cell1 <> TCellsDistance(CellsDistance[I]).Cell1)
    322     and (TCellsDistance(SelectedCells[J]).Cell2 <> TCellsDistance(CellsDistance[I]).Cell2)
    323     and (TCellsDistance(SelectedCells[J]).Cell1 <> TCellsDistance(CellsDistance[I]).Cell2)
    324     and (TCellsDistance(SelectedCells[J]).Cell2 <> TCellsDistance(CellsDistance[I]).Cell1) then begin
    325       L1 := TLine.Create(TCellsDistance(CellsDistance[I]).Cell1.PosPx,
    326         TCellsDistance(CellsDistance[I]).Cell2.PosPx);
    327       L2 := TLine.Create(TCellsDistance(SelectedCells[J]).Cell1.PosPx,
    328         TCellsDistance(SelectedCells[J]).Cell2.PosPx);
    329       if TLine.LineIntersect(L1, L2, Intersection) then begin
    330         if L1.ToRect.IsPointInside(Intersection) and
    331         L2.ToRect.IsPointInside(Intersection) then begin
    332           Intersected := True;
    333           Break;
    334         end;
    335       end;
    336     end;
    337     if not Intersected then SelectedCells.Add(CellsDistance[I]);
    338     Inc(I);
    339   end;
    340 
    341   // Add cell neighbors
    342   for I := 0 to SelectedCells.Count - 1 do begin
    343     CellDistance := TCellsDistance(SelectedCells[I]);
    344     CellDistance.Cell1.Neighbors.Add(CellDistance.Cell2);
    345     CellDistance.Cell2.Neighbors.Add(CellDistance.Cell1);
    346   end;
    347 
    348   FreeAndNil(SelectedCells);
    349   FreeAndNil(CellsDistance);
    350   SortNeighborsByAngle;
    351 
    352   while True do begin
    353   ChangesCount := 0;
    354   // Optimize link lines for lower angle
    355   for Cell in Cells do begin
    356     // Change link if lower angle can be achieved
    357     for I := 0 to Cell.Neighbors.Count - 1 do begin
    358       LeftCell := Cell.Neighbors[I];
    359       RightCell := Cell.Neighbors[(I + 1) mod Cell.Neighbors.Count];
    360       LeftIndex := LeftCell.Neighbors.IndexOf(Cell);
    361       RightIndex := RightCell.Neighbors.IndexOf(Cell);
    362       LeftCellCommon := LeftCell.Neighbors[(LeftIndex + LeftCell.Neighbors.Count - 1) mod LeftCell.Neighbors.Count];
    363       RightCellCommon := RightCell.Neighbors[(RightIndex + 1) mod RightCell.Neighbors.Count];
    364       if (LeftCellCommon = RightCell) and
    365       (RightCellCommon = LeftCell) then begin
    366         LeftCenterCell := LeftCell.Neighbors[(LeftIndex + LeftCell.Neighbors.Count - 2) mod LeftCell.Neighbors.Count];
    367         RightCenterCell := RightCell.Neighbors[(RightIndex + 2) mod RightCell.Neighbors.Count];
    368 
    369         if LeftCenterCell = RightCenterCell then begin
    370           CenterCell := LeftCenterCell;
    371 
    372           LeftClosingLine1 := TLine.Create(LeftCell.PosPx, Cell.PosPx);
    373           LeftClosingLine2 := TLine.Create(LeftCell.PosPx,
    374             CenterCell.PosPx);
    375           LeftAngle := SubAngle(LeftClosingLine1.GetAngle,
    376             LeftClosingLine2.GetAngle);
    377 
    378           RightClosingLine1 := TLine.Create(RightCell.PosPx, Cell.PosPx);
    379           RightClosingLine2 := TLine.Create(RightCell.PosPx,
    380             CenterCell.PosPx);
    381           RightAngle := SubAngle(RightClosingLine2.GetAngle,
    382             RightClosingLine1.GetAngle);
    383 
    384           LeftClosingLine1 := TLine.Create(Cell.PosPx, LeftCell.PosPx);
    385           RightClosingLine1 := TLine.Create(Cell.PosPx, RightCell.PosPx);
    386           CurrentAngle := SubAngle(RightClosingLine1.GetAngle,
    387             LeftClosingLine1.GetAngle);
    388           if (CurrentAngle > LeftAngle) and (CurrentAngle > RightAngle) then begin
    389             LeftCell.DisconnectFrom(RightCell);
    390             Cell.ConnectTo(CenterCell);
    391             SortNeighborsByAngle;
    392             Inc(ChangesCount);
    393           end;
    394         end;
    395         //end;
    396       end;
    397     end;
    398   end;
    399   if ChangesCount = 0 then Break;
    400   end;
    401 
    402   {// Compute polygon around cells with sequence sorted by link angle
    403   for Cell in Cells do begin
    404     // Use whole map first for cell polygon
    405     if Cell.Neighbors.Count > 0 then begin
    406       Polygon := TPolygon.Create(TRect.Create(TPoint.Create(0, 0),
    407         TPoint.Create(Size.X * DefaultCellSize.X, Size.Y * DefaultCellSize.Y)));
    408       for NeighborCell in Cell.Neighbors do begin
    409         LinkLine := TLine.Create(Cell.PosPx, NeighborCell.PosPx);
    410         LinkLine.Distance := LinkLine.Distance - CellGapWidth;
    411         MP := LinkLine.GetMiddle;
    412         // Create half plane vector
    413         L1 := TLine.Create(MP, TPoint.Create(MP.X + LinkLine.GetSize.X,
    414           MP.Y + LinkLine.GetSize.Y));
    415 
    416         Polygon.CutLine(L1, Cell.PosPx);
    417       end;
    418       Cell.Polygon := Polygon;
    419     end else Cell.Polygon.Clear;
    420   end;}
    421 
    422   // Additional polygon by all other cells
     278  // Compute polygon cat out by all other cells
    423279  for Cell in Cells do begin
    424280    Cell.Polygon := TPolygon.Create(TRect.Create(TPoint.Create(0, 0),
     
    426282    for Cell2 in Cells do
    427283    if Cell2 <> Cell then begin
    428           LinkLine := TLine.Create(Cell.PosPx, Cell2.PosPx);
    429           LinkLine.Distance := LinkLine.Distance - CellGapWidth;
    430           MP := LinkLine.GetMiddle;
    431           // Create half plane vector
    432           L1 := TLine.Create(MP, TPoint.Create(MP.X + LinkLine.GetSize.X,
    433             MP.Y + LinkLine.GetSize.Y));
    434 
    435           Cell.Polygon.CutLine(L1, Cell.PosPx);
     284      LinkLine := TLine.Create(Cell.PosPx, Cell2.PosPx);
     285      LinkLine.Distance := LinkLine.Distance - CellGapWidth;
     286      MP := LinkLine.GetMiddle;
     287      // Create half plane vector
     288      L1 := TLine.Create(MP, TPoint.Create(MP.X + LinkLine.GetSize.X,
     289        MP.Y + LinkLine.GetSize.Y));
     290
     291      Cell.Polygon.CutLine(L1, Cell.PosPx);
    436292    end;
    437293  end;
    438294
    439   // Remove all neighbor links for cell pairs with non-overlaping polygons
    440   for Cell in Cells do begin
    441     for I := Cell.Neighbors.Count - 1 downto 0 do begin
    442       if Cell.Polygon.EdgeDistance(Cell.Neighbors[I].Polygon) > 2 * CellGapWidth then
    443         Cell.Neighbors.Delete(I);
     295  // Link all cells with neighboring polygon edges
     296  for I := 0 to Cells.Count - 1 do begin
     297    for J := I + 1 to Cells.Count - 1 do begin
     298      if Cells[I].Polygon.EdgeDistance(Cells[J].Polygon) < 2 * CellGapWidth then
     299        Cells[I].ConnectTo(Cells[J]);
    444300    end;
    445301  end;
Note: See TracChangeset for help on using the changeset viewer.