- Implement AI land marks which only used to tracks visited areas on the map for now. Significantly reduces wasting of cpu time by AI checking same place several times (10x or even more in rare cases)
authorunc0rr
Wed, 25 Jul 2012 16:24:30 +0400
changeset 7433 c7fff3e61d49
parent 7430 9c132b368ddb
child 7435 bf80e66d6131
- Implement AI land marks which only used to tracks visited areas on the map for now. Significantly reduces wasting of cpu time by AI checking same place several times (10x or even more in rare cases) - More branching in walk algorythm which allows for better coverage of reachable places. Sometimes makes AI perform ridiculous jumping just to make a tiny step. - Small fixes/adjustments
hedgewars/hwengine.pas
hedgewars/uAI.pas
hedgewars/uAIActions.pas
hedgewars/uAIAmmoTests.pas
hedgewars/uAILandMarks.pas
hedgewars/uAIMisc.pas
--- a/hedgewars/hwengine.pas	Wed Jul 25 12:29:53 2012 +0400
+++ b/hedgewars/hwengine.pas	Wed Jul 25 16:24:30 2012 +0400
@@ -32,7 +32,7 @@
 uses SDLh, uMisc, uConsole, uGame, uConsts, uLand, uAmmos, uVisualGears, uGears, uStore, uWorld, uInputHandler, uSound,
      uScript, uTeams, uStats, uIO, uLocale, uChat, uAI, uAIMisc, uRandom, uLandTexture, uCollisions,
      SysUtils, uTypes, uVariables, uCommands, uUtils, uCaptions, uDebug, uCommandHandlers, uLandPainted
-     {$IFDEF SDL13}, uTouch{$ENDIF}{$IFDEF ANDROID}, GLUnit{$ENDIF};
+     {$IFDEF SDL13}, uTouch{$ENDIF}{$IFDEF ANDROID}, GLUnit{$ENDIF}, uAILandMarks;
 
 {$IFDEF HWLIBRARY}
 procedure initEverything(complete:boolean);
@@ -401,6 +401,7 @@
         uAI.initModule;
         //uAIActions does not need initialization
         //uAIAmmoTests does not need initialization
+        uAILandMarks.initModule;
         uAIMisc.initModule;
         uAmmos.initModule;
         uChat.initModule;
@@ -432,6 +433,7 @@
     begin
         WriteLnToConsole('Freeing resources...');
         uAI.freeModule;
+        uAILandMarks.freeModule;
         uAIMisc.freeModule;         //stub
         uCaptions.freeModule;
         uWorld.freeModule;
--- a/hedgewars/uAI.pas	Wed Jul 25 12:29:53 2012 +0400
+++ b/hedgewars/uAI.pas	Wed Jul 25 16:24:30 2012 +0400
@@ -31,7 +31,7 @@
 implementation
 uses uConsts, SDLh, uAIMisc, uAIAmmoTests, uAIActions,
     uAmmos, SysUtils{$IFNDEF USE_SDLTHREADS} {$IFDEF UNIX}, cthreads{$ENDIF} {$ENDIF}, uTypes,
-    uVariables, uCommands, uUtils, uDebug;
+    uVariables, uCommands, uUtils, uDebug, uAILandMarks;
 
 var BestActions: TActions;
     CanUseAmmo: array [TAmmoType] of boolean;
@@ -212,7 +212,7 @@
 end;
 
 procedure Walk(Me: PGear; var Actions: TActions);
-const FallPixForBranching = cHHRadius * 2 + 8;
+const FallPixForBranching = cHHRadius;
 var
     ticks, maxticks, steps, tmp: Longword;
     BaseRate, BestRate, Rate: integer;
@@ -275,6 +275,7 @@
 
             if (BotLevel < 5) and (GoInfo.JumpType = jmpHJump) then // hjump support
                 if Push(ticks, Actions, AltMe, Me^.Message) then
+                    begin
                     with Stack.States[Pred(Stack.Count)] do
                         begin
                         if Me^.dX.isNegative then
@@ -290,11 +291,21 @@
                         else
                             AddAction(MadeActions, aia_LookRight, 0, 200, 0, 0);
                         end;
+                    
+                    // check if we could go backwards and maybe ljump over a gap after this hjump
+                    Push(ticks, Stack.States[Pred(Stack.Count)].MadeActions, AltMe, Me^.Message xor 3)
+                    end;
             if (BotLevel < 3) and (GoInfo.JumpType = jmpLJump) then // ljump support
                 begin
-                // push current position so we proceed from it after checking jump opportunities
+                // at final check where we go after jump walking backward
+                if Push(ticks, Actions, AltMe, Me^.Message xor 3) then
+                    with Stack.States[Pred(Stack.Count)] do
+                        AddAction(MadeActions, aia_LJump, 0, 305 + random(50), 0, 0);
+
+                // push current position so we proceed from it after checking jump+forward walk opportunities
                 if CanGo then Push(ticks, Actions, Me^, Me^.Message);
-                // first check where we go after jump
+                
+                // first check where we go after jump walking forward
                 if Push(ticks, Actions, AltMe, Me^.Message) then
                     with Stack.States[Pred(Stack.Count)] do
                         AddAction(MadeActions, aia_LJump, 0, 305 + random(50), 0, 0);
@@ -317,8 +328,16 @@
                 end
             else if Rate < BestRate then
                 break;
+                
             if ((Me^.State and gstAttacked) = 0) and ((steps mod 4) = 0) then
+                begin
+                if (steps > 4) and checkMark(hwRound(Me^.X), hwRound(Me^.Y), markWasHere) then
+                    break;                    
+                addMark(hwRound(Me^.X), hwRound(Me^.Y), markWasHere);
+                
                 TestAmmos(Actions, Me, true);
+                end;
+                
             if GoInfo.FallPix >= FallPixForBranching then
                 Push(ticks, Actions, Me^, Me^.Message xor 3); // aia_Left xor 3 = aia_Right
             end {while};
@@ -426,7 +445,9 @@
 or isInMultiShoot then
     exit;
 
-//DeleteCI(Me); // this might break demo
+//DeleteCI(Me); // this will break demo/netplay
+clearAllMarks;
+
 Me^.State:= Me^.State or gstHHThinking;
 Me^.Message:= 0;
 
--- a/hedgewars/uAIActions.pas	Wed Jul 25 12:29:53 2012 +0400
+++ b/hedgewars/uAIActions.pas	Wed Jul 25 16:24:30 2012 +0400
@@ -116,19 +116,19 @@
 
 procedure AddAction(var Actions: TActions; Action: Longword; Param: LongInt; TimeDelta: Longword; X, Y: LongInt);
 begin
-with Actions do
-    begin
-    actions[Count].Action:= Action;
-    actions[Count].Param:= Param;
-    actions[Count].X:= X;
-    actions[Count].Y:= Y;
-    if Count > 0 then
-        actions[Count].Time:= TimeDelta
-    else
-        actions[Count].Time:= GameTicks + TimeDelta;
-    inc(Count);
-    TryDo(Count < MAXACTIONS, 'AI: actions overflow', true);
-    end
+if Actions.Count < MAXACTIONS then
+    with Actions do
+        begin
+        actions[Count].Action:= Action;
+        actions[Count].Param:= Param;
+        actions[Count].X:= X;
+        actions[Count].Y:= Y;
+        if Count > 0 then
+            actions[Count].Time:= TimeDelta
+        else
+            actions[Count].Time:= GameTicks + TimeDelta;
+        inc(Count);
+        end
 end;
 
 procedure CheckHang(Me: PGear);
--- a/hedgewars/uAIAmmoTests.pas	Wed Jul 25 12:29:53 2012 +0400
+++ b/hedgewars/uAIAmmoTests.pas	Wed Jul 25 16:24:30 2012 +0400
@@ -818,7 +818,7 @@
     {first RateShove checks farthermost of two whip's AmmoShove attacks 
     to encourage distant attacks (damaged hog is excluded from view of second 
     RateShove call)}
-    v1:= RateShove(Me, x - 15, y
+    v1:= RateShove(Me, x - 13, y
             , 30, 30, 25
             , -1, -0.8, trackFall or afSetSkip);
     v1:= v1 +
@@ -826,7 +826,7 @@
             , 30, 30, 25
             , -1, -0.8, trackFall);
     // now try opposite direction
-    v2:= RateShove(Me, x + 15, y
+    v2:= RateShove(Me, x + 13, y
             , 30, 30, 25
             , 1, -0.8, trackFall or afSetSkip);
     v2:= v2 +
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hedgewars/uAILandMarks.pas	Wed Jul 25 16:24:30 2012 +0400
@@ -0,0 +1,71 @@
+unit uAILandMarks;
+
+interface
+const markWasHere = $01;
+
+procedure addMark(X, Y: LongInt; mark: byte);
+function  checkMark(X, Y: LongInt; mark: byte) : boolean;
+procedure clearAllMarks;
+procedure clearMarks(mark: byte);
+
+procedure initModule;
+procedure freeModule;
+
+implementation
+uses uVariables;
+
+const gr = 2;
+
+var marks: array of array of byte;
+    WIDTH, HEIGHT: Longword;
+
+procedure addMark(X, Y: LongInt; mark: byte);
+begin
+    if((X and LAND_WIDTH_MASK) = 0) and ((Y and LAND_HEIGHT_MASK) = 0) then
+        begin
+        X:= X shr gr;
+        Y:= Y shr gr;
+        marks[Y, X]:= marks[Y, X] or mark
+        end
+end;
+
+function  checkMark(X, Y: LongInt; mark: byte) : boolean;
+begin
+    checkMark:= ((X and LAND_WIDTH_MASK) = 0) 
+        and ((Y and LAND_HEIGHT_MASK) = 0) 
+        and ((marks[Y shr gr, X shr gr] and mark) <> 0)
+end;
+
+procedure clearAllMarks;
+var 
+    Y, X: Longword;
+begin
+    for Y:= 0 to Pred(HEIGHT) do
+        for X:= 0 to Pred(WIDTH) do
+            marks[Y, X]:= 0
+end;
+
+procedure clearMarks(mark: byte);
+var 
+    Y, X: Longword;
+begin
+    for Y:= 0 to Pred(HEIGHT) do
+        for X:= 0 to Pred(WIDTH) do
+            marks[Y, X]:= marks[Y, X] and (not mark)
+end;
+
+
+procedure initModule;
+begin
+    WIDTH:= LAND_WIDTH shr gr;
+    HEIGHT:= LAND_HEIGHT shr gr;
+    
+    SetLength(marks, HEIGHT, WIDTH);
+end;
+
+procedure freeModule;
+begin
+    SetLength(marks, 0, 0);
+end;
+
+end.
--- a/hedgewars/uAIMisc.pas	Wed Jul 25 12:29:53 2012 +0400
+++ b/hedgewars/uAIMisc.pas	Wed Jul 25 16:24:30 2012 +0400
@@ -170,7 +170,7 @@
     begin
         case Gear^.Kind of
             gtCase:
-                AddBonus(hwRound(Gear^.X), hwRound(Gear^.Y) + 3, 33, 28);
+                AddBonus(hwRound(Gear^.X), hwRound(Gear^.Y) + 3, 37, 25);
             gtFlame:
                 if (Gear^.State and gsttmpFlag) <> 0 then
                     AddBonus(hwRound(Gear^.X), hwRound(Gear^.Y), 20, -50);
@@ -697,7 +697,7 @@
         Gear^.dY:= Gear^.dY + cGravity;
         if Gear^.dY > _0_4 then
             begin
-            Goinfo.FallPix:= 0;
+            GoInfo.FallPix:= 0;
             // try ljump instead of fall with damage
             HHJump(AltGear, jmpLJump, GoInfo); 
             if AltGear^.Hedgehog^.BotLevel < 4 then