JAVA - Go-Spiel-Algorithmus

Question

Ich versuche, einen Algorithmus zu implementieren, um tote Steine ​​in meinem Go-Spiel zu löschen.

Ich höre, dass Floodfill das Beste ist, um dies zu erreichen, da die rekursive Verwendung am effizientesten und einfacher zu implementieren wäre.

Ich habe Probleme mit der Verwendung in meinem Code und fragte mich, wie ich es implementieren sollte.

Dies ist einer meiner Klassen, es ist ziemlich selbsterklärend.

import java.io.*; 

public class GoGame implements Serializable { 

    int size; 
    char[][] pos; // This is the array that stores whether a Black (B) or White (W) piece is stored, otherwise its an empty character. 

    public GoGame(int s){ 
     size = s; 
    } 

    public void init() { 
     pos = new char[size][size]; 
     for (int i=0;i<size;i++) { 
      for (int j=0;j<size;j++) { 
       pos[i][j] = ' '; 
      } 
     } 
    } 

    public void ClearAll() { 
     for (int i=0;i<size;i++) { 
      for (int j=0;j<size;j++) { 
       pos[i][j] = ' '; 
      } 
     } 
    } 

    public void clear(int x, int y) { 
     pos[x][y]=' '; 
    } 

    public void putB(int x, int y) { //places a black stone on the board+array 
     pos[x][y]='B'; 
     floodfill(x,y,'B','W'); 

    } 

    public void putW(int x, int y) { //places a white stone on the board+array 
     pos[x][y]='W'; 
     floodfill(x,y,'W','B'); 

    } 

    public char get(int x, int y) { 
     return pos[x][y]; 
    } 

    public void floodfill(int x, int y, char placed, char liberty){ 


     floodfill(x-1, y, placed, liberty); 
     floodfill(x+1, y, placed, liberty); 
     floodfill(x, y-1, placed, liberty); 
     floodfill(x, y+1, placed, liberty); 

    } 

} 

x und y die Koordinaten des Platzes sind, placed ist der Charakter des Steins nach unten setzen, ist liberty der andere Charakter

Jede mögliche Hilfe würde erstaunlich sein!

Answer 1

während die anderen Antworten technisch korrekt sind, vermissen Sie auch viel mehr Logik zu gehen. was Sie tun müssen, ist, glaube ich (auf B move):

for each W neighbour of the move: 
    check that W group to see if it has any liberties (spaces) 
     remove it if not 

Flußfüllen für die Suche nach dem Ausmaß einer Gruppe von Steinen nützlich sind, aber Ihre Routine viel mehr als das braucht (ich bin Vereinfachung hier, und auch versuchen zu erraten, wofür diese Routine verwendet wird - siehe Kommentare unter dieser Antwort).

Angesichts der oben genannten würde eine Flut füllen, die alle Steine ​​in einer Gruppe identifiziert, so etwas (beachten Sie, dass es ein zweites Array für die Füllung verwendet, weil Sie nicht pos ändern möchten, nur um eine zu finden Gruppe):

public void findGroup(int x, int y, char colour, char[][] mask) { 
    // if this square is the colour expected and has not been visited before 
    if (pos[x][y] == colour && mask[x][y] == ' ') { 
     // save this group member 
     mask[x][y] = pos[x][y]; 
     // look at the neighbours 
     findGroup(x+1, y, colour, mask); 
     findGroup(x-1, y, colour, mask); 
     findGroup(x, y+1, colour, mask); 
     findGroup(x, y-1, colour, mask); 
    } 
} 

Sie können das nennen eine einzelne Gruppe (und kopieren Sie sie in Maske) zu identifizieren, so dass es hilft Ihnen, die Mitglieder einer W-Gruppe, die Nachbarn ein B bewegen (zum Beispiel) zu identifizieren, aber es ist nur ein kleiner Teil der gesamten Logik, die Sie brauchen.

Schließlich, wenn Sie etwas mit jedem Stein in einer Gruppe tun möchten, haben Sie zwei Möglichkeiten. Sie können eine Routine wie die obige aufrufen und dann über mask umkehren, um die Gruppe zu finden, oder Sie können die gewünschte Aktion direkt in die Routine einfügen (in diesem Fall verwenden Sie weiterhin mask, um das Ausmaß der Flutfüllung zu steuern) im Test && mask[x][y] == ' ' aber Sie verwenden es nicht als Ergebnis - die ganze Arbeit ist bis zum Zeitpunkt der Rückkehr der Routine erledigt.

(Programmierung etwas zu behandeln geht richtig, nach allen Regeln, ist eigentlich recht komplex - Sie haben eine Menge Arbeit vor haben ...: o)

Answer 2

Ich würde für die falschen Beweis verwenden. Hier ist, wie ich gefangen Steine ​​finden:

private static final int SIZE = 8; 
private static final int VACANT = 0;  //empty point 
private static final int MY_COLOR = 1;  //Black 
private static final int ENEMY_COLOR = 2; //White 
private static final int CHECKED = 50;  //Mark for processed points 
private static final int OUT = 100;  //points out of the board 

private static boolean isCaptured(int col, int row, int[][] board) { 
    boolean result = !isNotCaptured(col, row, board); 
    cleanBoard(board); 
    return result; 
} 

private static boolean isNotCaptured(int col, int row, int[][] board) { 
    int value = board[col][row]; 
    if (!(value == MY_COLOR || value == CHECKED)) 
     return true; 

    int top = row < SIZE - 1 ? board[col][row + 1] : OUT; 
    int bottom = row > 0 - 1 ? board[col][row - 1] : OUT; 
    int left = col > 0 ? board[col - 1][row] : OUT; 
    int right = col < SIZE - 1 ? board[col + 1][row] : OUT; 

    if (top == VACANT || right == VACANT || left == VACANT || bottom == VACANT) 
     return true; 

    board[col][row] = CHECKED; 

    return (top == MY_COLOR && isNotCaptured(col, row + 1, board)) 
      || (bottom == MY_COLOR && isNotCaptured(col, row - 1, board)) 
      || (left == MY_COLOR && isNotCaptured(col - 1, row, board)) 
      || (right == MY_COLOR && isNotCaptured(col + 1, row, board)); 
} 

private static void cleanBoard(int[][] board) { 
    for (int i = 0; i < SIZE; i++) { 
     for (int j = 0; j < SIZE; j++) { 
      if (board[i][j] == CHECKED) 
       board[i][j] = MY_COLOR; 
     } 
    } 
} 

Dann können Sie die Methode wie folgt aufrufen:

isCaptured(5, 4, board) 

Answer 3

Ich denke, dass BFS für diesen Fall besser sein wird, weil man die Nachbarn zuerst erforschen müssen, so Wenn einer von ihnen erfasst wird, wird der Punkt erfasst.