In der Serie "Named Problems" stelle ich dir klassische, namentlich bekannte Algorithmus-Probleme vor, die seit Jahrzehnten in Ausbildung, Studium und Interviews verwendet werden. Anhand verständlicher Problemstellungen wie FizzBuzz, Türme von Hanoi oder dem Sieb des Eratosthenes lernst du hier, algorithmisch zu denken, Lösungsstrategien zu entwickeln und diese sauber in Java umzusetzen.

Conways Game of Life ist ein klassisches, bekanntes Problem aus der Informatik: Ein Gitter aus Zellen entwickelt sich Schritt für Schritt weiter, nur nach festen Regeln.

Das Spannende: Es gibt keine Eingaben wie bei vielen Algorithmen. Du startest mit einem Anfangszustand, dann entstehen Muster allein durch die Regeln.

Für Java-Einsteiger ist das perfekt, um 2D-Arrays, Nachbarschafts-Logik und vor allem Zustandsübergänge sauber zu üben.

In diesem Artikel baust du eine kleine Simulation, lernst typische Stolperfallen kennen und siehst zwei Java-Varianten: einmal straightforward, einmal etwas sauberer strukturiert.

 

Problemstellung

Du hast ein 2D-Gitter aus Zellen. Jede Zelle ist entweder lebendig oder tot. In jedem Schritt (Generation) wird für jede Zelle anhand ihrer acht Nachbarn entschieden, ob sie im nächsten Schritt lebt oder stirbt.

  • Nachbarn: maximal 8 Zellen (oben, unten, links, rechts, und die 4 Diagonalen).
  • Regeln (Standard-Game-of-Life):
    • Eine lebendige Zelle mit weniger als 2 lebenden Nachbarn stirbt (Unterbevölkerung).
    • Eine lebendige Zelle mit 2 oder 3 lebenden Nachbarn lebt weiter.
    • Eine lebendige Zelle mit mehr als 3 lebenden Nachbarn stirbt (Überbevölkerung).
    • Eine tote Zelle mit genau 3 lebenden Nachbarn wird lebendig (Geburt).
  • Wichtig: Alle Updates passieren gleichzeitig pro Generation.

Mini-Beispiel (3x3): Wir markieren lebendig mit # und tot mit ..

  1. Start (ein kleines "L"):
    • ...
    • .##
    • .#.
  2. Nächste Generation ergibt sich aus den Regeln für jede Zelle.

 

Die Idee dahinter

Das Kernkonzept ist ein Zustandsübergang: Du hast einen aktuellen Zustand (das Gitter jetzt) und berechnest daraus den nächsten Zustand (das Gitter danach).

Ganz wichtig: Du darfst beim Berechnen nicht sofort in dasselbe Array schreiben, sonst veränderst du die Grundlage für Nachbarzählungen. Darum nutzt man in der Regel ein zweites 2D-Array für die nächste Generation.

  • State: current[row][col] (lebt oder lebt nicht)

  • Transition: zähle Nachbarn, wende Regeln an

  • Next: next[row][col] wird befüllt, dann ersetzt next den aktuellen Zustand

  • Visualisierung als einfache Liste:

    • Generation 0: .#.
    • Generation 1: ###
    • Generation 2: .#.

 

Schritt für Schritt zur Lösung

  1. Lege ein 2D-Array an, z.B. boolean[][] für lebendig/tot.
  2. Schreibe eine Methode, die die lebenden Nachbarn einer Zelle zählt.
  3. Berechne für jede Zelle den nächsten Zustand und schreibe ihn in ein zweites Array.
  4. Tausche nach einer Generation current gegen next aus.
  5. Gib das Gitter aus, damit du sehen kannst, ob es passt.
  6. Wiederhole das Ganze für mehrere Generationen (Iteration über die Zeit).

 

Java-Implementierung (Variante A: straightforward)

public class GameOfLifeStraightforward {

  public static void main(String[] args) {
    boolean[][] grid = new boolean[][]{
        {false, true,  false, false, false},
        {false, false, true,  false, false},
        {true,  true,  true,  false, false},
        {false, false, false, false, false},
        {false, false, false, false, false}
    };

    int generations = 4;

    System.out.println("Start:");
    printGrid(grid);

    for (int i = 1; i <= generations; i++) {
      grid = nextGeneration(grid);
      System.out.println("Generation " + i + ":");
      printGrid(grid);
    }
  }

  private static boolean[][] nextGeneration(boolean[][] current) {
    int rows = current.length;
    int cols = current[0].length;
    boolean[][] next = new boolean[rows][cols];

    for (int r = 0; r < rows; r++) {
      for (int c = 0; c < cols; c++) {
        int aliveNeighbors = countAliveNeighbors(current, r, c);
        boolean alive = current[r][c];

        if (alive) {
          next[r][c] = (aliveNeighbors == 2 || aliveNeighbors == 3);
        } else {
          next[r][c] = (aliveNeighbors == 3);
        }
      }
    }

    return next;
  }

  private static int countAliveNeighbors(boolean[][] grid, int row, int col) {
    int rows = grid.length;
    int cols = grid[0].length;

    int count = 0;

    for (int dr = -1; dr <= 1; dr++) {
      for (int dc = -1; dc <= 1; dc++) {
        if (dr == 0 && dc == 0) {
          continue;
        }

        int rr = row + dr;
        int cc = col + dc;

        if (rr >= 0 && rr < rows && cc >= 0 && cc < cols) {
          if (grid[rr][cc]) {
            count++;
          }
        }
      }
    }

    return count;
  }

  private static void printGrid(boolean[][] grid) {
    for (int r = 0; r < grid.length; r++) {
      StringBuilder line = new StringBuilder();

      for (int c = 0; c < grid[r].length; c++) {
        line.append(grid[r][c] ? '#' : '.');
      }

      System.out.println(line);
    }

    System.out.println();
  }
}

Diese Variante ist bewusst direkt: Ein boolean[][], eine Nachbarzählung und ein neues Array für die nächste Generation. So siehst du klar, wo der Zustandsübergang passiert: current bleibt unverändert, next wird neu aufgebaut. Das ist nicht die schnellste, aber eine sehr gute Einsteiger-Lösung.

 

Java-Implementierung (Variante B: Alternative oder Verbesserung)

public class GameOfLifeImproved {

  private static final char ALIVE = '#';
  private static final char DEAD = '.';

  public static void main(String[] args) {
    String[] input = new String[]{
        ".....",
        "..#..",
        "...#.",
        ".###.",
        "....."
    };

    boolean[][] grid = parseGrid(input);

    System.out.println("Start:");
    printGrid(grid);

    for (int gen = 1; gen <= 4; gen++) {
      grid = evolve(grid);
      System.out.println("Generation " + gen + ":");
      printGrid(grid);
    }
  }

  private static boolean[][] evolve(boolean[][] current) {
    boolean[][] next = new boolean[current.length][current[0].length];

    forEachCell(current, (r, c) -> {
      int aliveNeighbors = countAliveNeighbors(current, r, c);
      next[r][c] = applyRules(current[r][c], aliveNeighbors);
    });

    return next;
  }

  private static boolean applyRules(boolean alive, int aliveNeighbors) {
    if (alive) {
      return aliveNeighbors == 2 || aliveNeighbors == 3;
    }

    return aliveNeighbors == 3;
  }

  private static void forEachCell(boolean[][] grid, CellConsumer consumer) {
    for (int r = 0; r < grid.length; r++) {
      for (int c = 0; c < grid[r].length; c++) {
        consumer.accept(r, c);
      }
    }
  }

  private static int countAliveNeighbors(boolean[][] grid, int row, int col) {
    int count = 0;

    for (int rr = row - 1; rr <= row + 1; rr++) {
      for (int cc = col - 1; cc <= col + 1; cc++) {
        if (rr == row && cc == col) {
          continue;
        }

        if (isInside(grid, rr, cc) && grid[rr][cc]) {
          count++;
        }
      }
    }

    return count;
  }

  private static boolean isInside(boolean[][] grid, int r, int c) {
    return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length;
  }

  private static boolean[][] parseGrid(String[] lines) {
    int rows = lines.length;
    int cols = lines[0].length();
    boolean[][] grid = new boolean[rows][cols];

    for (int r = 0; r < rows; r++) {
      if (lines[r].length() != cols) {
        throw new IllegalArgumentException("All lines must have same length");
      }

      for (int c = 0; c < cols; c++) {
        grid[r][c] = (lines[r].charAt(c) == ALIVE);
      }
    }

    return grid;
  }

  private static void printGrid(boolean[][] grid) {
    for (int r = 0; r < grid.length; r++) {
      StringBuilder line = new StringBuilder();
      for (int c = 0; c < grid[r].length; c++) {
        line.append(grid[r][c] ? ALIVE : DEAD);
      }

      System.out.println(line);
    }

    System.out.println();
  }

  @FunctionalInterface
  private interface CellConsumer {
    void accept(int row, int col);
  }
}

Hier ist die gleiche Logik, aber besser aufgeteilt: applyRules(...) kapselt die Regeln, isInside(...) macht Bounds-Checks lesbar, und parseGrid(...) erlaubt eine einfache Eingabe als Strings. Das macht Tests und kleine Experimente leichter, weil du Startmuster schnell austauschen kannst.

 

Beispiel: Eingabe und Ausgabe

Beispiel 1 (Blinker, 5x5):

  • Eingabe (Generation 0): ..... ..#.. ..#.. ..#.. .....
  • Ausgabe (Generation 1): ..... ..... .###. ..... .....

Beispiel 2 (Blinker, nächster Schritt):

  • Eingabe (Generation 1): ..... ..... .###. ..... .....
  • Ausgabe (Generation 2): ..... ..#.. ..#.. ..#.. .....

Beispiel 3 (Einzelne Zelle stirbt):

  • Eingabe (Generation 0): ... .#. ...
  • Ausgabe (Generation 1): ... ... ...

 

Typische Fehler

  • In-place Update: Du schreibst direkt in current und zählst Nachbarn dann schon mit gemischten Zustanden. Ergebnis: chaotisches Verhalten.
  • Off-by-one bei Grenzen: Schleifen laufen bis <= statt < oder du prüfst rr <= rows statt rr < rows.
  • Die Zelle selbst mitgezählt: In der Nachbarzählung fehlt das continue für dr == 0 && dc == 0.
  • Falsche Regel für tote Zellen: Geburt passiert nur bei == 3, nicht bei >= 3 oder == 2.
  • Unsaubere Eingabe: Zeilen haben unterschiedliche Längen oder du interpretierst falsche Zeichen (z.B. Leerzeichen statt .).
  • Row/Col vertauscht: Du nutzt grid[col][row] oder läufst über grid[0].length als Zeilenanzahl.
  • Vergessener Zeilenumbruch beim Print: Ausgabe wirkt kaputt, obwohl die Logik stimmt, weil du das Gitter nicht klar trennst.

 

Fazit

Conways Game of Life ist ein starkes Übungsproblem, weil du dabei 2D-Arrays sicher handhabst und den Unterschied zwischen aktuellem Zustand und nächstem Zustand wirklich verinnerlichst. Du hast gelernt, Nachbarn zu zählen, Regeln sauber anzuwenden und pro Generation ein neues Grid zu erzeugen. Genau diese Struktur taucht später oft wieder auf, zum Beispiel bei Simulationen, Rasterproblemen oder Bildverarbeitung.