Refactoring die Erste

Wenn man nach einiger Zeit mal wieder in alten Code reinschaut fällt einem immer wieder auf, dass mal wieder ein Refactoring nötig ist. Generell ist es das Ziel, dass Programm-Code auch nach langer Zeit immer noch lesbar ist und man versteht, was dort passieren soll. Als Beispiel will ich die IsInRow() Methode aus meinem letzten Post verwenden. Wenn ich mir diese for-Schleife anschaue gruselt es mich.

Hier noch einmal die Methode vom letzten mal:

public bool IsInRow(List<Ball> balls) {
  if (balls.Count <= 1) {
    return true;
  }

  int minX = balls.Min(ball => ball.PosX);
  int minY = balls.Min(ball => ball.PosY);

  int dx = balls.Max(ball => ball.PosX) - minX;
  int dy = balls.Max(ball => ball.PosY) - minY;

  int xinc = Convert.ToInt32(dx > 0);
  int yinc = Convert.ToInt32(dy > 0);

  for (int i = 0, x = 0, y = 0; (x <= dx && y <= dy) ||
       i < balls.Count; x += xinc, y += yinc, i++) {
    if (balls.Find(ball => ball.PosX == (x + minX) &&
        ball.PosY == (y + minY)) == null) {
      return false;
    }
  }
  return true;
}

Sofort ist mir aufgefallen, dass die erste Bedingung der for-Schleife überflüssig ist. Generell kann ich ruhig jede Kugel prüfen und damit reicht die zweite Bedingung aus.

...
for (int i = 0, x = 0, y = 0; i < balls.Count;
     x += xinc, y += yinc, i++) {
...
}

Als nächstes kann ich die Suche nach einer Kugel an der jeweiligen Position durch eine Methode austauschen.

...
for (int i = 0, x = 0, y = 0; i < balls.Count;
     x += xinc, y += yinc, i++) {
  if (ThereIsNoBall(balls, minX + x, minY + y)) {
    return false;
  }
}
...

private bool ThereIsNoBall(List<Ball> balls) {
  return balls.Find(ball => ball.PosX == x && ball.PosY == y) == null;
}

Da ich den Test so oft durchführen muss, wie Kugeln in der Liste sind kann ich die Iteration auch über eine foreach-Schleife machen. So brauche ich selbst nicht mehr auf das Ende der Liste prüfen.

...
int x = 0;
int y = 0;
foreach (Ball ball in balls) {
  if (ThereIsNoBall(balls, x + minX, y + minY)) {
    return false;
  }
  x += xinc;
  y += yinc;
}
...

Im nächsten Schritt werde ich zwei Dinge verändern. Zum einen werden die Variablen dx und dy nur an einer stelle verwendet. Also kann ich mir diese Variable auch komplett sparen. Als nächtes werde ich noch die index-Variablen x und y entfernen, da ich auch direkt minX und minY hochzählen kann. Sinnvollerweise benenne ich minX und minY gleich in posX und posY um.

...
int posX = balls.Min(ball => ball.PosX);
int posY = balls.Min(ball => ball.PosY);

int xinc = Convert.ToInt32((balls.Max(ball => ball.PosX) - posX) > 0);
int yinc = Convert.ToInt32((balls.Max(ball => ball.PosY) - posY) > 0);

foreach (Ball ball in balls) {
  if (ThereIsNoBall(balls, posX, posY)) {
    return false;
  }
  posX += xinc;
  posY += yinc;
}
...

Da jetzt die Zeile um x-/y-inc zu ermitteln etwas zu kryptisch aussieht, werde ich das noch in eine Methode auslagern. Ausserdem passiert im wesentlichen in beiden Zeilen das Gleiche, was ebenfalls für eine neue Methode sprechen würde.

...
int xinc = GetStepSize(balls, posX, ball => ball.PosX);
int yinc = GetStepSize(balls, posY, ball => ball.PosY);
...

private int GetStepSize(IEnumerable<Ball> balls, int pos,
                        Func<Ball, bool> positionProjection) {
  return Convert.ToInt32((balls.Max(positionProjection) - pos) > 0);
}

Als letztes werde ich noch überall das List gegen IEnumerable austauschen. Das hat den Grund, dass ich an keiner Stelle der Methode meine List verändern will. Mit einer Liste könnte ich das machen. Mit einem IEnumerable nicht. Dafür ist es nötig balls.Count gegen die Extension balls.Count() und balls.Find() gegen balls.FirstOrDefault() auszutauschen. Die fertige Methode sieht dann so aus.

public bool IsInRow(IEnumerable<Ball> balls) {
  if (balls.Count() <= 1) {
    return true;
  }

  int posX = balls.Min(ball => ball.PosX);
  int posY = balls.Min(ball => ball.PosY);

  int xinc = GetStepSize(balls, posX, ball => ball.PosX);
  int yinc = GetStepSize(balls, posY, ball => ball.PosY);

  foreach (Ball ball in balls) {
    if (ThereIsNoBall(balls, posX, posY)) {
      return false;
    }
    posX += xinc;
    posY += yinc;
  }
  return true;
}

private int GetStepSize(IEnumerable<ball> balls, int pos, 
                        Func<Ball, bool> positionProjection) {
  return Convert.ToInt32((balls.Max(positionProjection) - pos) > 0);
}

private bool ThereIsNoBall(IEnumerable<Ball> balls, int x, int y) {
  return balls.FirstOrDefault(ball => ball.PosX == x && ball.PosY == y) == null;
}

Ansich finde ich, dass der Code so wensentlich besser zu lesen ist als vorher. Was man vielleicht noch machen könnte wäre, die x/y Werte zu einem Point zusammen zu fassen. Ich denke aber, dass es fürs Erste reichen sollte.

Wie gut, dass ich vorher Tests geschrieben habe und nun überprüfen kann, ob mein Refactoring irgend welche Auswirkungen auf das Verhalten hat :-)

Das Spiel Abalone und die Algorithmen dahinter

In meinem Projekt will ich ja das Spiel Abalone als Onlineversion implementieren. Falls jemand das Spiel oder die Regeln nicht kennt, so findet er hier alle notwendigen Erklärungen.

Als ich mir Abalone als Spiel aussuchte dachte ich mir "Hmm die Regeln sind ja recht einfach. Das sollte nicht sonderlich schwer sein umzusetzen". Als ich mit der Implementierung der Spielmechanik begonnen hatte, hat sich meine Annahme als Irrtum herausgestellt. Es fängt mit so einfachen Dingen an wie "Liegen die gewählten Kugeln in einer Reihe?" und hört bei "Wo liegen die Kugeln nach dem Verschieben?" auf.

Als Beispiel erläutere ich, wie ich erkenne, ob Kugeln in einer Reihe liegen. Generell benötige ich diese Funktionalität beim Selektieren der einzelnen Kugeln und beim Verschieben einer Reihe.
Ich betrachte in der Methode immer eine Menge von Kugeln. Da ich mein Spielfeld als zweidimensionales Array darstelle haben meine Kugeln eine X und eine Y Koordinate.

Als erste Variante habe ich einfach versucht über die Kugeln zu iterieren um zu schauen, ob die nachfolgende Kugel in Reihe zu der vorherigen Kugel liegt. Der Versuch schlug schon nach erstem Probieren Fehl. Erstens weiß ich nicht in welcher Richtung die Kugeln liegen und zweitens können die Kugeln völlig unsortiert sein. Es könnte also passieren, dass ich drei Kugeln in Reihe habe die durchnummeriert sind aber in der Iteration die Reihenfolge 1:3:2 haben. Somit würde diese Variante spätestens bei der zweiten Kugel in der Liste davon ausgehen, dass es keine Reihe ist.

Ich benötige also eine Möglichkeit die wahrscheinliche Richtung meiner Kugeln zu bestimmen, so dass ich später nur noch die Position in die Richtung verschieben und schauen muss, ob dort eine Kugel gibt.

Hier also der Algorithmus:

1. Bilde die Differenz zwischen der Maximalen und der Minimalen X und Y Koordinate die die zu Prüfenden Kugeln haben.
2. Ist die Differenz größer 0 so muss später bei der Iteration die X / Y Koordinate hochgezählt werden.
3. Iteriere so über das Spielfeld, dass bei der Kugel mit geringstem X, Y Wert begonnen wird
4. Suche in der Liste nach Kugeln die diese Koordinate haben
5. Inkrementiere die X / Y Koordinate je nach Ergebnis in Schritt 2.
6. Wiederhole den Vorgang bis entweder eine Kugel nicht gefunden wird (bedeutet dass die Kugeln nicht in Reihe liegen) oder alle Kugeln eine der erwarteten Koordinaten haben

Hier mal die Methode:

public bool IsInRow(List<Ball> balls) {
 if (balls.Count <= 1) {
   return true;
 } 
 
 //finde kugel mit kleinstem x und kleinstem y
 int minX = balls.Min(ball => ball.PosX);
 int minY = balls.Min(ball => ball.PosY);

 int dx = balls.Max(ball => ball.PosX) - minX;
 int dy = balls.Max(ball => ball.PosY) - minY;

 int xinc = Convert.ToInt32(dx > 0);
 int yinc = Convert.ToInt32(dy > 0);

 for (int i = 0, x = 0, y = 0; (x <= dx && y <= dy) ||
   i < balls.Count; x += xinc, y += yinc, i++) {
   if (balls.Find(ball => ball.PosX == (x + minX) &&
               ball.PosY == (y + minY)) == null) {
     return false;
   }
 }
 return true;
}

Irgend wie müsste ich das Ganze nochmal Refactorn. Die for-Schleife ist mir noch eine Nummer zu kryptisch. Als ich nach etwa einem 3/4 Jahr nochmal draufgeschaut habe dachte ich mir "Huch was hast du denn da verbrochen" :-)

PS: Hat jemand eine Ahnung, wie man hier Quelltexte vernünftig darstellen kann?