Changeset 88 for trunk


Ignore:
Timestamp:
Nov 16, 2014, 2:31:27 PM (10 years ago)
Author:
chronos
Message:
  • Modified: Change attack probability calculation to use cache of precalculated values to speed up calculation dramatically.
  • Added: Fallback as computer strategy element to withdraw border cells where enemy is stronger.
  • Modified: Test of polygon canvas method modification.
Location:
trunk
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/Forms/UFormMove.lfm

    r75 r88  
    1414  object SpinEditOnce: TSpinEdit
    1515    Left = 208
    16     Height = 35
     16    Height = 32
    1717    Top = 40
    1818    Width = 98
     
    2323  object Label1: TLabel
    2424    Left = 16
    25     Height = 25
     25    Height = 22
    2626    Top = 40
    27     Width = 54
     27    Width = 46
    2828    Caption = 'Once:'
    2929    ParentColor = False
     
    5050  object Label2: TLabel
    5151    Left = 24
    52     Height = 25
     52    Height = 22
    5353    Top = 136
    54     Width = 100
     54    Width = 87
    5555    Caption = 'Every turn:'
    5656    ParentColor = False
     
    5858  object SpinEditRepeat: TSpinEdit
    5959    Left = 208
    60     Height = 35
     60    Height = 32
    6161    Top = 128
    6262    Width = 98
     
    131131  object Label3: TLabel
    132132    Left = 16
    133     Height = 25
     133    Height = 22
    134134    Top = 8
    135     Width = 145
     135    Width = 127
    136136    Caption = 'Win probability:'
    137137    ParentColor = False
     
    139139  object LabelWinProbability: TLabel
    140140    Left = 264
    141     Height = 25
     141    Height = 22
    142142    Top = 8
    143143    Width = 15
  • trunk/Forms/UFormMove.pas

    r72 r88  
    7878  LabelWinProbability.Caption :=
    7979    IntToStr(Round(Core.Game.AttackProbability(AttackCount + SpinEditOnce.Value,
    80     DefendCount, 1) * 100)) + ' %';
     80    DefendCount) * 100)) + ' %';
    8181end;
    8282
  • trunk/UGame.pas

    r86 r88  
    111111  TCanvasEx = class(TCanvas)
    112112    procedure TextOutEx(X,Y: Integer; const Text: string; MovePen: Boolean = True);
     113    procedure PolygonEx(const Points: array of TPoint; Winding: Boolean);
    113114  end;
    114115
     
    278279    procedure IncreaseMoves;
    279280    procedure Process;
     281    procedure FallBack;
     282    function AttackersCount(Cell: TCell): Integer;
    280283  end;
    281284
     
    343346    FRunning: Boolean;
    344347    LoadedImageFileName: string;
     348    ProbabilityMatrix: array of array of Single;
    345349    procedure Attack(var AttackPower, DefendPower: Integer);
    346350    procedure MoveAll(Player: TPlayer);
     
    371375    FileName: string;
    372376    FogOfWar: Boolean;
    373     function AttackProbability(AttackCount, DefendCount, Depth: Integer): Double;
     377    function AttackProbability(AttackCount, DefendCount: Integer): Double;
    374378    procedure LoadConfig(Config: TXmlConfig; Path: string);
    375379    procedure SaveConfig(Config: TXmlConfig; Path: string);
     
    703707end;
    704708
     709procedure TCanvasEx.PolygonEx(const Points: array of TPoint; Winding: Boolean);
     710begin
     711  //Changing;
     712  //RequiredState([csHandleValid, csBrushValid, csPenValid]);
     713  LCLIntf.Polygon(Handle, @Points[0], Length(Points), Winding);
     714  //Changed;
     715end;
     716
     717
    705718{ TCells }
    706719
     
    12321245      Points[I] := View.CellToCanvasPos(Cell.Polygon[I]);
    12331246    Brush.Style := bsSolid;
    1234     Polygon(Points, False, 0, Length(Points));
     1247    //Polygon(Points, False, 0, Length(Points));
     1248    TCanvasEx(Canvas).PolygonEx(Points, False);
     1249    //MoveTo(Points[0].X, Points[0].Y);
     1250    //LineTo(Points[1].X, Points[1].Y);
    12351251
    12361252    // Show cell text
     
    17891805
    17901806  // Sort descending to attack cells with higher power first
    1791   // Higher power enemy cells grow faster and is more dangerous
     1807  // Higher power enemy cells can grow faster and is more dangerous
    17921808  TargetCells.Sort(CellCompareDescending);
    17931809
     
    18281844  NewTargetCells: TCells;
    18291845  Cells2: TCells;
     1846  MovedPower: Integer;
    18301847begin
    18311848  // We need to move available power to borders to be available for attacks
     
    18821899              Inc(CanAttack);
    18831900            end;
    1884             if CanAttack = 0 then
    1885               Game.SetMove(TCell(Neighbors[I]), TCell(TargetCells[C]), TCell(Neighbors[I]).GetAvialPower, False);
     1901            if CanAttack = 0 then begin
     1902              MovedPower := TCell(Neighbors[I]).GetAvialPower;
     1903              if (TCell(TargetCells[C]).GetAvialPower + TCell(TargetCells[C]).GetAttackPower + MovedPower) > Game.Map.MaxPower then
     1904                MovedPower := Game.Map.MaxPower - TCell(TargetCells[C]).GetAvialPower - TCell(TargetCells[C]).GetAttackPower;
     1905              Game.SetMove(TCell(Neighbors[I]), TCell(TargetCells[C]), MovedPower, False);
     1906            end;
    18861907          end;
    18871908          TCell(Neighbors[I]).Mark := True;
     
    19201941  InnerMoves;
    19211942  IncreaseMoves;
     1943  //FallBack;
    19221944  CellProcessDirection := not CellProcessDirection;
     1945end;
     1946
     1947procedure TComputer.FallBack;
     1948var
     1949  C: Integer;
     1950  I: Integer;
     1951  AllCells: TCells;
     1952  BorderCells: TCells;
     1953  EnemyPower: Integer;
     1954begin
     1955  BorderCells := TCells.Create;
     1956  BorderCells.OwnsObjects := False;
     1957  AllCells := Game.Map.Cells;
     1958
     1959  // Get list of border cells
     1960  for C := 0 to AllCells.Count - 1 do
     1961  with TCell(AllCells[C]) do begin
     1962    if (Terrain <> ttVoid) and (Player = Game.CurrentPlayer)  then begin
     1963      if AttackersCount(TCell(AllCells[C])) > 0 then
     1964        BorderCells.Add(AllCells[C]);
     1965    end;
     1966  end;
     1967
     1968  // Move all units back to inner area from weak border cells
     1969  for C := 0 to BorderCells.Count - 1 do
     1970  with TCell(BorderCells[C]) do begin
     1971    // Calculate enemy power
     1972    // TODO: Do not sum different enemy power to one value
     1973    EnemyPower := 0;
     1974    for I := 0 to Neighbors.Count - 1 do
     1975    if (TCell(Neighbors[I]).Player <> Game.CurrentPlayer) and (TCell(Neighbors[I]).Player <> nil) then begin
     1976      Inc(EnemyPower, TCell(Neighbors[I]).Power);
     1977    end;
     1978    if EnemyPower > (GetAvialPower + GetAttackPower) then begin
     1979      // Fallback
     1980      for I := MovesTo.Count - 1 downto 0 do
     1981        TUnitMove(MovesTo[I]).Free;
     1982      for I := 0 to Neighbors.Count - 1 do
     1983      if (TCell(Neighbors[I]).Player = Game.CurrentPlayer) and (AttackersCount(TCell(Neighbors[I])) = 0) then begin
     1984
     1985        Game.SetMove(TCell(BorderCells[C]), TCell(Neighbors[I]), GetAvialPower, False);
     1986        Break;
     1987      end;
     1988    end;
     1989  end;
     1990
     1991  BorderCells.Free;
     1992end;
     1993
     1994function TComputer.AttackersCount(Cell: TCell): Integer;
     1995var
     1996  I: Integer;
     1997begin
     1998  Result := 0;
     1999  for I := 0 to Cell.Neighbors.Count - 1 do
     2000  if (TCell(Cell.Neighbors[I]).Player <> Game.CurrentPlayer) and
     2001    (TCell(Cell.Neighbors[I]).Player <> nil) then begin
     2002      Inc(Result);
     2003  end;
    19232004end;
    19242005
     
    20552136end;
    20562137
    2057 function TGame.AttackProbability(AttackCount, DefendCount, Depth: Integer): Double;
     2138function TGame.AttackProbability(AttackCount, DefendCount: Integer): Double;
    20582139var
    20592140  OA, OD: Integer;
     2141  Len: Integer;
     2142  I: Integer;
    20602143begin
    20612144  if AttackCount = 0 then begin
    20622145    Result := 0;
    20632146    Exit;
     2147  end;
     2148  if DefendCount = 0 then begin
     2149    Result := 1;
     2150    Exit;
     2151  end;
     2152
     2153  // Enlarge probability cache table on demand
     2154  if Length(ProbabilityMatrix) < AttackCount then begin
     2155    SetLength(ProbabilityMatrix, AttackCount);
     2156  end;
     2157  if Length(ProbabilityMatrix[AttackCount - 1]) < DefendCount then begin
     2158    Len := Length(ProbabilityMatrix[AttackCount - 1]);
     2159    SetLength(ProbabilityMatrix[AttackCount - 1], DefendCount);
     2160    for I := Len to Length(ProbabilityMatrix[AttackCount - 1]) - 1 do
     2161      ProbabilityMatrix[AttackCount - 1][I] := -1;
     2162  end;
     2163
     2164  if ProbabilityMatrix[AttackCount - 1, DefendCount - 1] <> -1 then begin
     2165    // Use cached value
     2166    Result := ProbabilityMatrix[AttackCount - 1, DefendCount - 1];
     2167    Exit;
    20642168  end else Result := 1;
    2065   if DefendCount = 0 then Exit;
    2066   // TODO: Limiting depth is not solving problem with probability of high near
    2067   // numbers like 96 vs. 92. Complexity of calculation should be simplified
    2068   // in different way
    2069   if Depth > 10 then Exit;
    20702169
    20712170  OA := Min(AttackCount, 3);
     
    20732172
    20742173  if (OA = 1) and (OD = 1) then
    2075     Result := 0.4167 * AttackProbability(AttackCount, DefendCount - 1, Depth + 1) +
    2076       0.5833 * AttackProbability(AttackCount - 1, DefendCount, Depth + 1)
     2174    Result := 0.4167 * AttackProbability(AttackCount, DefendCount - 1) +
     2175      0.5833 * AttackProbability(AttackCount - 1, DefendCount)
    20772176  else if (OA = 2) and (OD = 1) then
    2078     Result := 0.5787 * AttackProbability(AttackCount, DefendCount - 1, Depth + 1) +
    2079       0.4213 * AttackProbability(AttackCount - 1, DefendCount, Depth + 1)
     2177    Result := 0.5787 * AttackProbability(AttackCount, DefendCount - 1) +
     2178      0.4213 * AttackProbability(AttackCount - 1, DefendCount)
    20802179  else if (OA = 3) and (OD = 1) then
    2081     Result := 0.6597 * AttackProbability(AttackCount, DefendCount - 1, Depth + 1) +
    2082       0.3403 * AttackProbability(AttackCount - 1, DefendCount, Depth + 1)
     2180    Result := 0.6597 * AttackProbability(AttackCount, DefendCount - 1) +
     2181      0.3403 * AttackProbability(AttackCount - 1, DefendCount)
    20832182  else if (OA = 1) and (OD = 2) then
    2084     Result := 0.2546 * AttackProbability(AttackCount, DefendCount - 1, Depth + 1) +
    2085       0.7454 * AttackProbability(AttackCount - 1, DefendCount, Depth + 1)
     2183    Result := 0.2546 * AttackProbability(AttackCount, DefendCount - 1) +
     2184      0.7454 * AttackProbability(AttackCount - 1, DefendCount)
    20862185  else if (OA = 2) and (OD = 2) then
    2087     Result := 0.2276 * AttackProbability(AttackCount, DefendCount - 2, Depth + 1) +
    2088       0.4483 * AttackProbability(AttackCount - 2, DefendCount, Depth + 1) +
    2089       0.3241 * AttackProbability(AttackCount - 1, DefendCount - 1, Depth + 1)
     2186    Result := 0.2276 * AttackProbability(AttackCount, DefendCount - 2) +
     2187      0.4483 * AttackProbability(AttackCount - 2, DefendCount) +
     2188      0.3241 * AttackProbability(AttackCount - 1, DefendCount - 1)
    20902189  else if (OA = 3) and (OD = 2) then
    2091     Result := 0.3717 * AttackProbability(AttackCount, DefendCount - 2, Depth + 1) +
    2092       0.2926 * AttackProbability(AttackCount - 2, DefendCount, Depth + 1) +
    2093       0.3358 * AttackProbability(AttackCount - 1, DefendCount - 1, Depth + 1);
     2190    Result := 0.3717 * AttackProbability(AttackCount, DefendCount - 2) +
     2191      0.2926 * AttackProbability(AttackCount - 2, DefendCount) +
     2192      0.3358 * AttackProbability(AttackCount - 1, DefendCount - 1);
     2193  ProbabilityMatrix[AttackCount - 1, DefendCount - 1] := Result;
    20942194end;
    20952195
Note: See TracChangeset for help on using the changeset viewer.