Das jüngste Gerücht
Inhaltsverzeichnis
Aufgabenstellung
Auf einem Spielfeld von 100*100 Quadraten sind 5000 Personen zufällig verteilt. Dabei können auf einem Feld auch mehrere Leute stehen. Zusätzlich gibt es zwei besondere Personen: Anton Angeber und Berta Blümchen. Im Gegensatz zu den anderen kann ihre Position frei gewählt werden. In jeder Runde kann jede Person entweder stehen bleiben oder in eine zufällige Richtung auf ein angrenzendes Feld gehen. Wenn zwei oder mehr Personen auf einem Feld stehen, erzählen sie sich die neuesten Gerüchte. Anton Angeber streut das Gerücht aus, dass Berta Blümchen ihn heiraten wird. Sobald Berta von dem Gerücht erfährt dementiert sie es heftig. Das Gerücht beziehungsweise das Dementi verbreitet sich nach den folgenden Regeln:
- Solange eine Person noch nichts von dem Gerücht oder dem Dementi gehört hat, hat sie keine Meinung.
- Wenn es unter den Leuten auf einem Feld eine Mehrheit für eine Meinung gibt, übernehmen alle auf diesem Feld diese Meinung.
- Wenn die Meinungen auf einem Feld ausgeglichen sind, sind alle Leute auf diesem Feld verunsichert und haben keine Meinung mehr.
- Anton und Berta bleiben natürlich bei ihrer Meinung, egal was andere sagen.
Erweiterung
Das Spielfeld soll eine frei wählbare Größe haben und auch die Anzahl der Personen soll vom Benutzer festgelegt werden.
Lösung des Problems
Speicherung der Personendaten
Die wahrscheinlich einfachste Lösung bei der Speicherung ist ein Array, dass für jede Person die Meinung und die Position festhält.
Verwendet man hier ein dynamisches Array, so ist auch eine vom Benutzer wählbare Anzahl der Personen möglich.
Um eine solches Array zu erstellen muss man in Delphi einen eigenen Datentyp vereinbaren. Im Pascal-Code ergibt sich also:
type TPerson = record meinung : integer; xpos : integer; ypos : integer; end;
Das entsprechende Array wird mit:
Person: Array of TPerson;
vereinbart und bekommt mit folgender Zeile ihre Länge zugewiesen:
SetLength(Person, AnzahlPersonen);
Bewegung der Personen
Beim "jüngsten Gerücht" sollen die Personen auf dem Spielfeld entweder stehen bleiben oder in eine zufällige Richtung laufen. Es ergeben sich also fünf mögliche Zustände:
- Die Person bleibt stehen.
- Die Person Bewegt sich
- ... nach oben.
- ... nach rechts.
- ... nach unten.
- ... nach links.
Mit Hilfe der in Delphi verfügbaren Zufallsfunktion lässt sich eine Zufallszahl zwischen 0 und 4 generieren, sodass bei einer "case of"-Abfrage für jede der Zufallszahlen eine andere Aktion eintritt. Allerdings haben es Computer im allgemeinen schwieriger eine "zufällige" Zahl auszuwählen, wie wir Menschen. Es empfiehlt sich also, beim Programmstart die Delphi-Funktion "Randomize" aufzurufen, die den Zufallsgenerator etwas "zufälliger" machen soll. Bei meinen Tests mit dem Programm stellte ich jedoch fest, dass bei der Generierung der Zufallszahlen fast nie die "4" auftrat, sodass nach etwa 120 Runden alle Personen am rechten Spielfeldrand angekommen waren. In der aktuellen Fassung meiner Version des "jüngsten Gerüchts" findet sich eine Zufallszahl zwischen 0 und 23, sodass für jede Möglichkeit der Bewegung 3 Zahlenwerte und für nicht Bewegen 12 Werte stehen.
Da jede auf dem Spielfeld befindliche Person bewegt werden soll, muss nun noch eine Zählschleife ergänzt werden.
Ein weiteres Problem, dass bedacht werden muss, ist, das es den Personen möglich ist, dass Spielfeld zu verlassen. Dies lässt sich verhindern, indem man mit vier einfachen if-Abfragen die Koordinaten der Leute überprüft und gegebenenfalls korrigiert.
Für die Prozedur des Bewegens ergibt sich im Pascal-Code beispielsweise:
procedure Bewegen;
var i, richtung : integer;
begin
for i := 0 to AnzahlPersonen-1 do
begin
begin
richtung := Random(24);
case richtung of
0, 4, 8 : Person[i].ypos := Person[i].ypos-1; // 1 nach oben
1, 5, 9 : Person[i].ypos := Person[i].ypos+1; // 1 nach unten
2, 6,10 : Person[i].xpos := Person[i].xpos+1; // 1 nach rechts
3, 7,11 : Person[i].xpos := Person[i].xpos-1; // 1 nach links
end;
end;
if Person[i].ypos < 0 then
inc(Person[i].ypos);
if Person[i].ypos > 99 then
dec(Person[i].ypos);
if Person[i].xpos < 0 then
inc(Person[i].xpos);
if Person[i].xpos > 99 then
dec(Person[i].xpos);
end;
end;
Austausch der Meinungen
In jeder Runde tauschen die Personen, die auf dem selben Feld stehen, die neuesten Gerüchte über Anton und Berta aus. Gibt es mehrere Meinungen über das Gerücht, werden alle Personen auf dem Spielfeld von der Meinung überzeugt, die zahlenmäßig überlegen ist. Beim Programmieren bedeutet dies, dass zuerst die Meinungen gezählt und verglichen werden müssen, bevor die neuen Meinungen zugewiesen werden können. Mithilfe von zwei Zählschleifen, die, verschachtelt, die Koordinaten auf dem Spielfeld darstellen, kann jedes einzelne Feld für sich betrachtet werden. Bei jedem Durchlauf wird nach Personen gesucht, die die selben Koordinaten haben, wie das zur Zeit untersuchte Spielfeld. Wird eine oder mehrere Personen gefunden, werden ihre Meinungen untersucht und in Hilfsvariablen vom Typ Integer gezählt. Hat man alle im Spiel befindlichen Personen überprüft, werden die Hilfsvariablen für die Meinungen verglichen und die Leute auf dem Spielfeld bekommen nach den in der Aufgabenstellung vermerkten Regeln eine neue Meinung zugewiesen.
Beispiel: Auf dem Spielfeld mit den Koordinaten x = 4 und y = 20 befinden sich 3 Personen. Zwei von Ihnen sind davon überzeugt, dass Antons Gerücht die Wahrheit ist, wobei die 3. Person jedoch an Bertas Dementi glaubt.
- 1. Die Zählschleifen kommen bei den Koordinaten 4, 20 an.
- 2. Alle im Spiel befindlichen Personen werden nun überprüft, ob sie auf diesem Feld stehen.
- 3. Die erste Person wird gefunden und durch ihre Meinung Antons Gerücht sei wahr, wird die Hilfsvariable "counterA" um den Wert 1 erhöht.
- 4. Es wird weiter nach den Personen auf dem Spielfeld 4, 20 gesucht. Auch die anderen Beiden werden gefunden und erhöhen entsprechend ihrer Meinung die Variablen counterA und counterB um jeweils 1.
- 5. Nachdem keine weiteren Personen mehr auf dem Feld gefunden wurden, werden die Variablen counterA und counterB verglichen. Da counterA mit dem Wert 2 größer ist als counterB, wird nun allen Personen auf dem Feld 4, 20 die Meinung zugewiesen, dass Antons Gerücht wahr ist.
Die Hilfsvariablen werden nach jedem Schleifendurchlauf wieder auf 0 gesetzt, sodass von neuem gezählt werden kann.
Sofern Berta noch nicht von Antons Gerücht erfahren hat, muss in der Prozedur des Meinungsaustauschs dafür gesorgt werden, dass sie, sobald sie es hört, das Dementi verbreitet.
Hier noch meine Version dieses Prinzips in Delphi mit Anmerkungen:
procedure Schwaetzen;
var i, j, k, counterx, countery : integer;
counterA, counterB : integer;
begin
for counterx := 0 to Breite do
begin
for countery := 0 to Hoehe do
begin
counterA := 0;
counterB := 0;
for i := 0 to AnzahlPersonen-1 do
begin
if (counterx = Person[i].xpos) and (countery = Person[i].ypos) then
begin
case Person[i].meinung of
1 : inc(counterA);
2 : inc(counterB);
end;
end;
end;
for j := 2 to AnzahlPersonen-1 do // Anton und Berta sollen ihre Meinung behalten!
begin
if (counterx = Person[j].xpos) and (countery = Person[j].ypos) then
begin
if counterA>counterB then // Die anderen werden von Antons Gerücht
Person[j].meinung := 1 // überzeugt wenn diese Meinung in der Überzahl ist.
else if counterA<counterB then // Dementi von Berta überzeugt
Person[j].meinung := 2
else if counterA=counterB then // Bei gleich vielen Meinungen Gerücht / Dementi
Person[j].meinung := 0; // entsteht allgemeine Verwirrung und keiner hat eine Meinung.
end;
end;
if (counterA>0) and (counterx = Person[1].xpos) and (countery = Person[1].ypos) then // Berta erfährt von Antons Gerücht
Person[1].meinung := 2; // und dementiert es!
end;
end;
end;
Grafische Ausgabe
Bei der grafischen soll jedes Quadrat auf dem Spielfeld in einer bestimmten Farbe gefärbt werden.
- Ist keine Person, oder sind nur Personen ohne Meinung über das Gerücht auf dem Feld, so wird es weiß gefärbt.
- Sind die Personen auf dem Feld Antons Meinung, wird das Feld blau gefärbt.
- Sind die Personen auf dem Feld Bertas Meinung, wird das Feld rot gefärbt.
- Ist Anton auf dem Feld, wird es hellblau gefärbt.
- Ist Berta auf dem Feld, wird es lila gefärbt.
Ähnlich wie beim Austausch der Meinungen, muss bei der grafischen Ausgabe jedes einzelne Feld, mit Hilfe von zwei Zählschleifen für sich betrachtet werden. Sollte eine Person auf dem betrachteten Feld sein, wird ihre Meinung überprüft. Durch eine "case of"-Entscheidung kann dan bequem eine Farbe festgelegt werden. Gespeichert wird diese Information in einem zweidimensionalen Array, dass genauso groß wie das Spielfeld ist. Nach dem Durchlauf der beiden Zählschleifen wurden alle Felder überprüft, und das Array hat nun für jedes Feld eine Farbe gespeichert.
Erst jetzt kommt es zum eigentlichen Zeichnen. Der einfachste Fall wäre nun, wenn das Spielfeld 100x100 Quadrate groß wäre und das Ausgabefeld ebenfalls 100x100 Pixel. Man müsste nur jeden Pixel in der im Array festgelegten Farbbelegung einfärben, doch Größe des Spielfelds soll variabel sein und auch die Ausgabe ist mit 100x100 Pixeln viel zu klein. Also muss man auch mit mehreren Pixeln ein Feld zeichnen können. Dazu muss man nur für jeden Pixel eine relativ einfache Berechnung durchführen. "Für jeden Pixel" heißt in diesem Fall, dass wiedereinmal zwei Zählschleifen eingeführt werden, die beim Durchlaufen jeden Pixel abarbeiten. Multipliziert man die x-Koordinate des aktuellen Pixels mit der Breite des Spielfelds und teilt das Produkt durch die Breite des Ausgabefelds, so erhält man die zugehörige x-Koordinate im Spielfeld. Diese Berechnung wird noch mit der y-Koordinate und der Höhe durchgeführt, sodass nun ein eindeutiges Spielfeld dem Pixel zugeordnet wird. Durch das oben festgelegte Array kann nun die Farbe für den Pixel ausgelesen werden und schließlich wird der Pixel gefärbt.
Bemerkung: Um bei der Division eine natürliche Zahl zu erhalten, verwende ich die Gaußklammer.
Hier noch der Pascal-Code zum Nachvollziehen der Theorie:
procedure TMainFrm.Zeichnen;
var i, j, counterx, countery : integer;
field : array of array of tcolor;
x, y : integer;
begin
SetLength(field, Breite, Hoehe);
for counterx := 0 to Breite-1 do
begin
for countery := 0 to Hoehe-1 do
begin
field[counterx, countery] := clWhite;
for i := 0 to AnzahlPersonen-1 do
begin
if (counterx = Person[i].xpos) and (countery = Person[i].ypos) then
begin
case Person[i].meinung of
0 : field[counterx, countery] := clWhite;
1 : field[counterx, countery] := clBlue;
2 : field[counterx, countery] := clRed;
end;
end;
if (counterx = Person[0].xpos) and (countery = Person[0].ypos) then
field[counterx, countery] := clSkyBlue;
if (counterx = Person[1].xpos) and (countery = Person[1].ypos) then
field[counterx, countery] := clPurple;
end;
end;
end;
for x := 0 to Zeichenflaeche.Width - 1 do
begin
for y := 0 to Zeichenflaeche.Height - 1 do
begin
Zeichenflaeche.Canvas.Pixels[x, y] := field[floor(x*Breite/Zeichenflaeche.Width),floor(y*Hoehe/Zeichenflaeche.Height)];
end;
end;
end;
Effizienz
Bei einem Programmablauf, bei dem 5000 unabhängige Personen bewegt und verglichen werden müssen, kommen auch moderne Prozessoren, die Milliarden von Taktzyklen pro Sekunde durchlaufen, an ihre Grenzen. Gerade deshalb ist es wichtig, möglichst wenige Rechenintensive Operationen, wie etwa Schleifen zu verwenden. Bei der Umsetzung meines Programms habe ich folglich darauf geachtet effizient Rechenleistung möglichst effizient zu nutzen. Beispielsweise wird das Programm beim Ablauf mehrerer Runden effizienter, da die Zeichenprozedur erst nach dem Ablauf aller Bewegungen und Meinungsaustausche stattfindet. Dies spart bei einer Anzahl von 5000 Personen etwa 500.000 Schleifendurchläufe. Weitere Rechenzeit könnte man durch die Integration der Zeichenprozedur in die Meinungsprozedur einsparen: Hierauf habe ich aber zugunsten der Übersichtlichkeit verzichtet.
Ausbreitung des Gerüchts bei unterschiedlichen Ausgangssituationen
Anton und Berta in entgegengesetzten Ecken
Ausgangssituation: Anton und Berta sind in entgegengesetzten Ecken positioniert.
Die Ausbreitung des Gerüchts nach 250 Runden.
Die Ausbreitung des Gerüchts nach 525 Runden. Berta hat gerade vom Gerücht erfahren.
Die Ausbreitung des Gerüchts nach 600 Runden. Bertas Dementi konnte sich nicht durchsetzen.
Anton und Berta auf gegenüberliegender Position
Ausgangssituation: Anton und Berta sind gegenüberliegend positioniert.
Die Ausbreitung des Gerüchts nach 250 Runden.
Die Ausbreitung des Gerüchts nach 500 Runden. Berta kann sich nicht gegen das Gerücht durchsetzen.
Anton und Berta auf gleicher Startposition
Ausgangssituation: Anton und Berta sind direkt nebeneinander.
Die Ausbreitung des Gerüchts nach 50 Runden. Berta hat gerade vom Gerücht erfahren
Die Ausbreitung des Gerüchts nach 250 Runden. Auch diesmal kann sich Berta nicht durchsetzen.
Fazit
Offensichtlich kann sich Berta, auch bei unterschiedlichen Startpositionen, nicht gegen das Gerücht wehren. Ist es erst einmal gestreut, kann sie nie genügend Leute vom Dementi überzeugen. Dies liegt daran, dass einige Zeit vergeht, bis Berta anfängt das Dementi zu verbreiten. In dieser Zeit sind bereits so viele Leute Antons Meinung, dass von Berta überzeugte Personen kurze Zeit später wieder an das Gerücht glauben.
Download des Programmes
Programm: Datei:Das jüngste Gerücht.zip
Präsentation vom 23.01.2007 Datei:Das juengste geruecht praesentation.zip
