lehrkraefte:blc:informatik:ffprg1-2019:arrays-anwendung2 [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Wer hat gewonnen? ======
**Ausgangslage**: Der Zustand des Spielfeldes ist in einer Variable ''feld'' als 2-dimensionales Array gespeichert. Die Einträge sind Strings der Länge 1, entweder " ", "x" oder "o".

Zu schreiben ist eine Funktion, die überprüft ob 3 (oder allgemeiner $n$) gleiche Einträge "x" oder "o" auf einer Linie sind, horizontal, vertikal oder diagonal.

Die Grösse vom Spielfeld ist ''w=len(feld)'' in $x$-Richtung und ''h=len(feld[0])'' in $y$-Richtung (für width und height).

===== Variante "viele if" =====
Für ein 3x3-Feld könnte man mit einem Haufen if-Abfragen das Feld überprüfen, z.B. wie folgt:
  if feld[0][0]!=" " and feld[0][0]==feld[1][0] and feld[1][0]==feld[2][0]:
    return feld[0][0]  # Gewinner melden
  ...
  ...
  return " "   # Niemand hat gewonnen

Sobald das Feld grösser als 3x3 ist (z.B. 7x6 für Vier gewinnt), ist das natürlich völlig unpraktikabel.

===== Variante Vektorgeometrie =====
Die Grundidee ist die gleiche wie bei der Parameterdarstellung der Geraden in der Vektorgeometrie. Man definiert einen Startpunkt und einen Richtungsvektor, der die Verschiebung angibt.

D.h. Man startet z.B. im Punkt (0,2) und verschiebt dann schrittweise um den Vektor $\binom{1}{-1}$, um die Punkte (1,1) und (2,0) zu erhalten. Auf diesem Weg zählt man, wie viele Male man hintereinander den gleichen Eintrag findet. **Achtung**, der folgende Code ist ein **Pseudo-Code**, der aber an Python angelehnt ist:

  punkt = startpunkt
  anzahl = 0
  was = " "
  while (punkt noch im feld):
     inhalt = feld[punktx][punkty]  # Aktuellen Feldinhalt auslesen
       if inhalt==" ":  # Leeres Feld
          anzahl = 0
          was = " "
       else:
          if inhalt==was:  # Gleiches Feld!
             anzahl+=1     # Zähler erhöhen
             if anzahl==3  # Linie voll? Könnte auch eine grössere Zahl sein.
                return was  # Plus eventuell melden, wo 
          else:
             anzahl = 1
             was = inhalt
     punkt = punkt + richtung
     
     
Was jetzt noch fehlt, sind die Startpunkte für die Überprüfung und die Richtungsvektoren. Die Idee ist, die Startpunktskoordinaten in einer for-Schleife zu erzeugen.

==== Variante "noch ein bisschen effizienter" ====
Es muss nicht jedes Mal das ganze Feld überprüft werden. Es reicht, von der Position aus zu zählen, wo das Feld verändert wurde. Dazu muss in die vier Richtungen (d.h. horizontal, vertikal und 2 diagonal) vorwärts **und** rückwärts gezählt werden.

Dazu schreibt man am einfachsten eine for-Schleife über die möglichen Richtungen:

  for dir in [[1,0],[1,1], [0,1], [-1,1]]:
    anzahl = In Richtung ''dir'' zählen
    anzahl += In Richtung ''-dir'' zählen
    anzahl +=1  # Die Position selbst zählen
    if anzahl==3:  # Oder was auch immer
       return True  # Sieg melden
  return False  # Kein Sieg