Es gäbe noch eine effizientere Lösung:
Delphi-Quellcode:
type
TPlayer = -1..+1;
PGamePos = ^TGamePos;
TGamePos = packed record
Stone: Integer;
Link: array[0..7] of PGamePos;
end;
function Move(X: Integer; Player: TPlayer): Boolean;
var
Pos,Next: PGamePos;
I,Count: Integer;
begin
Pos := @Game[0, X]; // Y,X Koordinaten, Y = 0 = oberste Zeile im Game
while (Pos.Stone = 0) and (Pos.Link[1] <> nil) and (Pos.Link[1].Stone = 0) do Pos := Pos.Link[1];
Pos.Stone := Player;
Count := 1;
for I := 1 to 7 do
begin
Next := Pos.Link[I];
if Next <> nil then
if Next.Stone = -Player then
begin // A)
Pos.Link[I] := nil;
if Odd(I) then Next.Link[I -1] := nil
else Next.Link[I +1] := nil;
end else
if Next.Stone = Player then
begin
if not Odd(I) then Count := 1;
repeat
Inc(Count);
if Count >= StoneInRow then
begin
Result := True;
Exit;
end;
Next := Next.Link[I];
until (Next = nil) or (Next.Stone <> Player);
end;
end;
Result := False;
end;
(* Link-Positionen sind nun:
x x x
6 1 3
7 0 2
x 4 5 x 4 5 x
3 1 6
2 0 7
x x x
*)
Obige Methode hat mehrere Neuerungen:
1.) nachdem ein Spielerstein eingefügt wurde werden in allen Richtungen die Verlinkungen auf NIL gesetzt deren Game-Positionen durch Steine des Gegners belegt sind. Dies geschiet im Source bei A). Somit werden nach jedem setzen eines Steines immer mehr Zellen im Game immer weniger Verlinkungen zu ihren Nachbarzellen besitzen. Dies beschleunigt dann die Suche in diese Richtungen. Somit sucht obiger Algo. nur in Richtungen in denen entweder ein Stein des aktuelle Spielers sitzt oder aber noch kein Stein gesetzt wurde.
2.) die Richtungen = Linkpositionen wurden geändert so daß immer zu einer Geradzahligen Richtung die +1 Richtung die Gegenrichtung der Verlinkung darstellt.
Also TGamePos.Link[0] nach Oben, TGamePos.Link[1] nach Unten, TGamePos.Link[4] nach Rechts, TGamePos.Link[5] nach Links.
Somit ist:
P.Link[0].Link[0 +1] = P
P.Link[1].Link[1 -1] = P
P.Link[2].Link[2 +1] = P
P.Link[3].Link[3 -1] = P
P.Link[4].Link[4 +1] = P
P.Link[5].Link[5 -1] = P
P.Link[6].Link[6 +1] = P
P.Link[7].Link[7 -1] = P
3.) wir beginnen unsere Suche erst mit dem Link[1] nach Unten. Den Link[0] nach oben können wir komplett aussparen da ja dort alle LEER sein muß. Auch dies beschleunigt die Suche.
Gruß Hagen