Die Türme von Hanoi

1. Aufgabe

Das Spiel der Türme von Hanoi wird auf den französischen Mathematiker Edouard Lucas zurückgeführt, der 1883 folgende kleine Geschichte erfand: Im Großen Tempel von Benares, der die Mitte der Welt markiert, ruht eine Messingplatte, in der drei Diamantnadeln befestigt sind. Bei der Erschaffung der Welt hat Gott vierundsechzig Scheiben aus purem Gold auf eine der Nadeln gesteckt, wobei die größte Scheibe auf der Messingplatte ruht, und die übrigen, immer kleiner werdend, eine auf der anderen.

Die Hindupriester sind nun unablässig damit beschäftigt, die Scheiben dieses Turms von Brahma zu versetzen. Dabei darf immer nur, den Gesetzen von Brahma folgend, eine Scheibe auf einmal umgesetzt werden, und zwar so, dass eine kleinere Scheibe auf eine größere gelegt wird. Wenn alle vierundsechzig Scheiben von dem Stapel, auf die Gott sie bei der Erschaffung der Welt gesetzt hat, auf einen der anderen Plätze gebracht sind, werden der Turm samt dem Tempel und allen Brahmanen zu Staub zerfallen, und die Welt wird untergehen.

Nachdem Sie und ich noch am Leben sind, betrachten wir in dieser Aufgabe eine Simulation dieses Puzzles, die wir in mehreren Teilschritten entwerfen. Die Standardvariante dieses Puzzles verwendet drei Pfähle. Prinzipiell müssen für jeden Lösungsalgorithmus die folgenden zwei Randbedingungen erfüllt sein:

  • Es darf zu einem Zeitpunkt nur eine Scheibe bewegt werden.

  • Es darf nie eine größere Scheibe auf einer kleineren Scheibe abgelegt werden.

Zu Beginn unserer Simulation dürfen sich auf einem der Pfähle eine bis sieben Scheiben in Pyramidenform auftürmen: Die kleineren Scheiben liegen auf den größeren Scheiben (Abbildung 1). Ein zweiter und ein dritter Pfahl sind in der Ausgangssituation leer. Der zweite Pfahl dient als Hilfspfahl für temporäre Ablagen, um die zweite Randbedingung zu erfüllen. Der dritte Pfahl ist das Ziel der Verschiebungsoperationen.

Die Türme von Hanoi: Ausgangs- und Endzustand.

Abbildung 1. Die Türme von Hanoi: Ausgangs- und Endzustand.


Die nachfolgenden Hinweise zur Gestaltung der Realisierung legen das MVC-Paradigma (Model-View-Controller) zu Grunde.

1.1. Die Ansicht: Komponente HanoiTowerView

In dieser Teilaufgabe beschreiben wir die Entwicklung eines einzelnen Turms der Simulation, sprich einer Komponente HanoiTowerView. Ein HanoiTowerView-Steuerelement visualisiert sowohl den Pfahl als auch eine Reihe von Scheiben mit einem Loch in der Mitte, die auf dem Pfahl abgelegt werden können, siehe dazu ein Beispiel in Abbildung 2:

Graphisches Steuerelement HanoiTowerView: Pfahl mit mehreren Scheiben.

Abbildung 2. Graphisches Steuerelement HanoiTowerView: Pfahl mit mehreren Scheiben.


Fügen Sie in Ihrer Projektmappe ein Unterprojekt vom Typ WPF Custom Control hinzu. Entwickeln Sie in diesem Projekt eine Komponente HanoiTowerView, die sich von der Basisklasse Canvas ableitet. In Tabelle 1 finden Sie eine Beschreibung der zentralen Eigenschaften und Methoden des Steuerelements vor:

Element

Beschreibung

Eigenschaft DiscSpeed

public int DiscSpeed { set; get; }

Legt die Anzahl Millisekunden fest, die bei einer Simulation im Steuerelement (Ablegen oder Entfernen einer Scheibe) die Pause zwischen zwei Simulationsschritten einnimmt.

Methode Create

public void Create (int levels);

Legt auf dem Turm eine bestimmte Anzahl von Scheiben ab, spezifiziert durch den Parameter levels.

Methode Push

public void Push (int size);

Legt eine Scheibe auf dem Pfahl ab. size legt die Größe der Scheibe fest. Zulässig sind Werte im Bereich von 1 (sehr kleine Scheibe) bis 7 (sehr große Scheibe).

Beachte: Mit Push können Scheiben in beliebiger Reihenfolge auf dem Pfahl abgelegt werden. Für die Einhaltung der speziellen Regeln der Türme von Hanoi-Simulation ist ein Container des HanoiTowerView-Steuerelements zuständig.

Methode Pop

public int Pop ();

Mit Pop wird die oberste Scheibe auf dem Pfahl entfernt. Der Rückgabewert spezifiziert ihre Scheibengröße. Für das Entfernen spielt dieser Wert zwar keine Rolle. Wenn dieselbe Scheibe aber auf einem anderen Turm wieder abgelegt werden soll, benötigt man ihn!

Methode PushAnimated

public void PushAnimated (int size);

Legt wie Methode Push eine Scheibe auf dem Pfahl ab, jedoch grafisch animiert. Aus diesem Grund arbeitet diese Methode asynchron, sie kehrt nach ihrem Aufruf sofort zurück (non-blocking). Für die Simulation des Ablegens einer Scheibe sind die Hilfsmittel des .NET-Multithreadings zu verwenden.

Methode PopAnimated

public int PopAnimated ();

Die PopAnimated-Methode arbeitet prinzipiell wie die Methode Pop, nur erfolgt das Entfernen der Scheibe grafisch animiert.

Tabelle 1. Elemente der Klasse HanoiTowerView.


Erstellen Sie zum Testen ihres Steuerelements einen WPF-Testcontainer (WPF-Anwendung), der ein HanoiTowerView-Steuerelement sowie vier Schaltflächen besitzt (siehe Abbildung 3). Die Schaltflächen mit der Beschriftung „Test Push“ bzw. „Test Push Animated“ testen das Ablegen einer Scheibe auf dem Turm (ohne oder mit Animation), die zwei Schaltflächen „Test Pop“ bzw. „Test Pop Animated“ testen das Entfernen einer Scheibe.

Test-Container für das HanoiTowerView-Steuerelement.

Abbildung 3. Test-Container für das HanoiTowerView-Steuerelement.

1.2. Das Modell: Klasse HanoiTowerModelImpl

Wir beschreiben das Modell des Problems zunächst – ganz im Sinne der MVC-Paradigmas – mit einer abstrahierenden Schnittstelle:

01: public interface ITowersOfHanoi
02: {
03:     int Discs { get; set; }
04: 
05:     void DoSimulation();
06: 
07:     event DiscMovedHandler DiscMoved;
08: }

Beispiel 1. Die Schnittstelle ITowersOfHanoi


Auf die drei Elemente Discs, DoSimulation und DiscMoved gehen wir im Folgenden näher ein. Zur Lösung des Puzzles gibt es eine Strategie, die auf folgender rekursiven Überlegung basiert:

  • Falls der Turm die Höhe n hat, bewege den Turm der Höhe n-1 zunächst (rekursiv) vom Startpfahl auf den Hilfspfahl.

  • Bewege die untere, größte Scheibe auf den Zielpfahl.

  • Bewege den Turm der Höhe n-1 (rekursiv) auf den Zielpfahl.

Das Problem hat sich nun darauf reduziert, das Puzzle für n-1 Scheiben zu lösen. Das lässt sich wiederum auf das Puzzle für n-2 Scheiben reduzieren usw., bis schließlich das Problem nur noch für eine einzelne Scheibe zu lösen ist und damit trivial geworden ist. Beachten Sie: Durch diese (rekursive) Strategie werden die zwei eingangs erwähnten Randbedingungen nicht verletzt! Wir skizzieren die rekursive Idee des Algorithmus visuell in Abbildung 4. Dort steht im Mittelpunkt eine Methode MoveTower:

Türme von Hanoi: Grundprinzip der rekursiven Strategie.

Abbildung 4. Türme von Hanoi: Grundprinzip der rekursiven Strategie.


Durch den Parameter n der Methode MoveTower aus Abbildung 4 ist die Anzahl der zu verschiebenden Scheiben bezeichnet, mit from der Pfahl, von dem die Scheiben entfernt werden, mit tmp der Pfahl, der als Zwischenziel dient und mit to der Pfahl, der als Ziel dient. Wenn wir den drei Pfählen die Namen A, B und C zuordnen, gehen wir zu Beginn der Simulation davon aus, das sich alle Scheiben auf Pfahl A befinden. Ziel der Simulation ist es, den kompletten Scheibenstapel von A nach C – unter Beachtung der Regeln – zu versetzen. Zur Lösung des Problems wird MoveTower mit from = A, tmp = B und to = C aufgerufen.

In einer programmiersprachlichen Notation kann man den Algorithmus mit diesen Überlegungen so formulieren (Abbildung 5):

Pseudocode-Darstellung des Algorithmus.

Abbildung 5. Pseudocode-Darstellung des Algorithmus.


Wenn es Ihnen hilft, können Sie diesen Algorithmus zunächst in einer Konsolen-Anwendung zum Laufen bringen, bevor Sie mit der Entwicklung des Modells fortfahren. In der Methode MoveDisc platzieren Sie ausschließlich einen Console.WriteLine-Aufruf, etwa der Gestalt

public void MoveDisc (int from, int to)
{
    Console.WriteLine("Moving disk from {0} to {1}", from, to);
}

Die Ausgabe des Programms sieht an einem konkreten Stapel mit 3 Scheiben so aus:

Moving disk from 1 to 3
Moving disk from 1 to 2
Moving disk from 3 to 2
Moving disk from 1 to 3
Moving disk from 2 to 1
Moving disk from 2 to 3
Moving disk from 1 to 3

Für diese Programmausführung ist ein MoveTower-Aufruf mit den aktuellen Parametern

MoveTower (3, 1, 2, 3);

verantwortlich. Aus der rekursiven Darstellung des Algorithmus ist nicht unmittelbar erkennbar, wie die einzelnen Scheiben nun tatsächlich in der Praxis verschoben werden. Dies können Sie nur eruieren, indem Sie für eine konkrete Anzahl von Scheiben die Arbeitsweise der MoveTower-Methode Aufruf für Aufruf nachvollziehen. In Abbildung 6 erkennen Sie die Arbeitsweise des Algorithmus an einem Turm der Größe 3:

Fallstudie am Beispiel eines Turms der Größe 3.

Abbildung 6. Fallstudie am Beispiel eines Turms der Größe 3.


Bemerkung: Für die Anzahl der Bewegungen gibt es eine Formel, bei n Scheiben benötigt man 2n - 1 Züge!

Die Beschreibung der beiden Elemente Discs und DoSimulation der Schnittstelle ITowersOfHanoi sowie die beiden Hilfsmethoden MoveTower und MoveDisc einer Klasse HanoiTowerModelImpl, die das Modell implementiert, finden Sie nun in Tabelle 2 vor:

Element

Beschreibung

Eigenschaft Discs

int Discs { get; set; }

Beschreibt die Anzahl der Scheiben, die zu Beginn der Simulation auf einem Turm liegen.

Methode DoSimulation

public void DoSimulation ();

Hauptmethode zur Durchführung der Simulation. Im Prinzip benutzt sie nur die beiden Hilfsmethoden MoveTower und MoveDisc.

Methode MoveTower

private void MoveTower(int discs, int from, int tmp, int to);

Beschreibung siehe Abbildung 4.

Methode MoveDisc

private void MoveDisc(int from, int to);

Versetze die unterste Scheibe vom Turm from zum Turm to.

Tabelle 2. Elemente der Klasse HanoiTowerModelImpl.

1.3. Das Modell: Ereignis DiscMoved

Der vorgestellte Algorithmus aus dem letzten Abschnitt ist für eine grafische Anwendung, die auf der Verarbeitung von Ereignissen basiert, nicht direkt geeignet. Wir erweitern deshalb die Modellklasse HanoiTowerModelImpl um das Ereignis DiscMoved. Dazu definieren wir zunächst den Delegate-Typ DiscMovedHandler:

public delegate void DiscMovedHandler (int from, int to);

Ergänzen Sie das Modell nun um ein Ereignis DiscMoved. Das Ereignis ergänzt die Methode MoveDisc aus dem letzten Abschnitt: Jedes Mal, wenn der rekursive Algorithmus MoveTower eine Scheibe von einem Turm zu einem anderen versetzt, ist das Ereignis DiscMoved mit zwei Parametern from (Turm, von dem Scheibe entnommen wird) und to (Turm, auf dem Scheibe abgelegt wird) auszulösen:

Element

Beschreibung

Ereignis DiscMoved

public event DiscMovedHandler DiscMoved;

Das Ereignis wird bei einem Scheibenwechsel ausgelöst.

Tabelle 3. Ereignis DiscMoved der Schnittstelle ITowersOfHanoi.

1.4. Hauptanwendung

In diesem Teilabschnitt entwickeln Sie eine WPF-Anwendung, die die bislang entwickelten Komponenten HanoiTowerView (Ansicht), HanoiTowerModelImpl (Modell) und mehrere Schaltflächen (Controller) geeignet instanziiert und initialisiert. Platzieren Sie drei Türme (HanoiTowerView-Komponenten) sowie Schaltflächen und Auswahlfelder wie in Abbildung 7 gezeigt.

Fensterobjekt (Container) mit drei Türmen.

Abbildung 7. Fensterobjekt (Container) mit drei Türmen.


Auf die Simulation (betrifft die Schaltflächen Start, Stop und Clear) gehen wir erst im nächsten Teilabschnitt ein! Das Discs-Auswahlfeld ermöglicht die Auswahl eines Wertes im Bereich von 1 bis 7. Nach der Selektion werden auf dem linken Pfahl entsprechend viele Scheiben abgelegt. Mit der Clear-Schaltfläche werden von allen drei Türmen die Scheiben entfernt. Mit dem Disc Speed-Auswahlfeld können frei wählbare Werte im Bereich von 10 bis 150 ausgewählt werden. Der Wert legt fest, wie groß die Pause beim animierten Bewegen der obersten Scheibe eines Turms ist. Das zweite Auswahlfeld Simulation Speed zeigt Werte im Bereich von 1000 bis 5000 an. Dieser Wert ist für die Geschwindigkeit (Pause in Millisekunden) der Simulation zuständig, auf die wir jetzt zu sprechen kommen.

1.5. Simulation der Anwendung: Ein einfacher Ansatz

Um zu einer Simulation der Anwendung zu gelangen, benötigen Sie im Container (Hauptfenster der WPF-Anwendung) zuerst eine Modellinstanz, also ein Objekt der Klasse HanoiTowerModelImpl. Melden Sie das Hauptfensterobjekt der WPF-Anwendung am Ereignis DiscMoved dieses Modellobjekts an. Beim Klicken der Start-Schaltfläche wird die Simulation durch einen Aufruf der DoSimulation-Methode gestartet. Die einzelnen DiscMoved-Ereignisse laufen nun im Hauptfensterobjekt ein. Pro DiscMoved-Ereignis sind nun an den betroffenen HanoiTowerView-Komponenten die Methoden Pop und Push (bzw. PopAnimated und PushAnimated) aufzurufen. Offensichtlich sieht Ihre Simulation nicht sehr gelungen aus, wenn die beiden Türme zeitgleich mit dem Verschieben der Scheiben beginnen. Überlegen Sie sich eine Strategie, wie Sie die beiden Aufrufe von Pop und Push (bzw. PopAnimated und PushAnimated) sinnvoll zeitlich nacheinander gestalten können!

1.6. Simulation der Anwendung: Der perfekte Ansatz

Beim Eintreffen eines DiscMoved-Ereignisses sind zwei Aktivitäten zu starten. Entfernen einer Scheibe und Ablegen einer Scheibe. Welche kausale Aussage können Sie über diese zwei Aktivitäten formulieren? Welches Hilfsmittel des Multithreadings kennen Sie, wenn zwei Aktivitäten zu koordinieren sind?

Ergänzen Sie eine zweite Simulationsmethode im Fenster-Objekt, die die zuvor angesprochenen Hinweise berücksichtigt!

1.7. Testrahmen: Turm mit vier Scheiben

Für einen Turm mit vier Scheiben finden Sie nachfolgend die Ausgaben der Konsolen-Anwendung wie auch eine Illustration in Abbildung 8 zu Testzwecken vor:

Moving disk from 1 to 2
Moving disk from 1 to 3
Moving disk from 2 to 3
Moving disk from 1 to 2
Moving disk from 3 to 1
Moving disk from 3 to 2
Moving disk from 1 to 2
Moving disk from 1 to 3
Moving disk from 2 to 3
Moving disk from 2 to 1
Moving disk from 3 to 1
Moving disk from 2 to 3
Moving disk from 1 to 2
Moving disk from 1 to 3
Moving disk from 2 to 3
Fallstudie am Beispiel eines Turms der Größe 4.

Abbildung 8. Fallstudie am Beispiel eines Turms der Größe 4.

2. Lösung

Quellcode: Siehe auch https://github.com/peterloos/Wpf_TowersOfHanoi.

Die Implementierung des Modells steht am Anfang unserer Betrachtungen. Mit den Hinweisen in der Aufgabenbeschreibung sollte dies nicht sonderlich schwierig gewesen sein (Listing 2):

01: public class HanoiTowerModelImpl : ITowersOfHanoi
02: {
03:     public event DiscMovedHandler DiscMoved;
04: 
05:     private int discs;
06: 
07:     // c'tor
08:     public HanoiTowerModelImpl()
09:     {
10:         this.discs = 3;
11:     }
12: 
13:     // properties
14:     public int Discs
15:     {
16:         get { return this.discs; }
17:         set { this.discs = value; }
18:     }
19: 
20:     // public interface
21:     public void DoSimulation()
22:     {
23:         this.MoveTower(this.discs, 1, 2, 3);
24:     }
25: 
26:     // private helper methods
27:     private void MoveTower(int discs, int from, int tmp, int to)
28:     {
29:         if (discs > 0)
30:         {
31:             this.MoveTower(discs - 1, from, to, tmp);  // move tower of height n-1
32:             this.MoveDisc (from, to);                  // move lowest disc
33:             this.MoveTower(discs - 1, tmp, from, to);  // move remaining tower
34:         }
35:     }
36: 
37:     private void MoveDisc(int from, int to)
38:     {
39:         if (this.DiscMoved != null)
40:             this.DiscMoved(from, to);
41:     }
42: }

Beispiel 2. Klasse HanoiTowerModelImpl.


Weiter geht es mit der Ansicht eines Turms, wir kommen auf die Klasse HanoiTowerView zu sprechen (Listing 3). Um die beiden Modi „Scheibe bewegen“ und „Scheibe animiert bewegen“ in der Ansicht zu unterstützen, ist ein gewisser Aufwand von Nöten. Zusätzlich kommt hinzu, dass die Methoden der Klasse HanoiTowerView darauf gewappnet sein müssen, nicht im UI-Thread der Anwendung aufgerufen zu werden. Damit müssen alle Methoden mit Zugriff auf das User Interface in den Kontext des Dispatcher-Threads verlagert werden:

001: namespace WpfTowerControl
002: {
003:     public class HanoiTowerView : Canvas
004:     {
005:         private const int TopPosition = 12;
006:         private const int WidthScaleFactor = 25;
007:         private const int DefaultAnimationSpeed = 70;
008: 
009:         // disc sizes of tower (valid elements: 1, 2, ..., 7)
010:         private List<int> discs;
011: 
012:         // floating disc, if any
013:         private int floatingDiscPosition;
014:         private Rectangle floatingDiscRectangle;
015: 
016:         // threading utils
017:         private Task t;
018:         private int speed;
019:         private bool isActive;
020: 
021:         // c'tor
022:         public HanoiTowerView()
023:         {
024:             this.Background = Brushes.LightGray;
025:             this.Height = 300;
026:             this.Width = 200;
027: 
028:             // setup empty stack
029:             Point p1 = new Point(10, this.Height - 10);
030:             Point p2 = new Point(this.Width - 10, this.Height - 10);
031:             Point p3 = new Point(this.Width - 10, this.Height - 30);
032:             Point p4 = new Point(this.Width / 2 + 10, this.Height - 30);
033:             Point p5 = new Point(this.Width / 2 + 10, 100);
034:             Point p6 = new Point(this.Width / 2 - 10, 100);
035:             Point p7 = new Point(this.Width / 2 - 10, this.Height - 30);
036:             Point p8 = new Point(10, this.Height - 30);
037: 
038:             PointCollection pointCollection = new PointCollection();
039:             pointCollection.Add(p1);
040:             pointCollection.Add(p2);
041:             pointCollection.Add(p3);
042:             pointCollection.Add(p4);
043:             pointCollection.Add(p5);
044:             pointCollection.Add(p6);
045:             pointCollection.Add(p7);
046:             pointCollection.Add(p8);
047: 
048:             Polygon poly = new Polygon();
049:             poly.Fill = SystemColors.ControlDarkBrush;
050:             poly.Points = pointCollection;
051:             this.Children.Add(poly);
052: 
053:             // no discs, yet ...
054:             this.discs = new List<int>();
055: 
056:             // threading utils
057:             this.t = null;
058:             this.isActive = false;
059:             this.speed = DefaultAnimationSpeed;
060:         }
061: 
062:         // properties
063:         public int DiscSpeed
064:         {
065:             get
066:             {
067:                 return this.speed;
068:             }
069: 
070:             set
071:             {
072:                 this.speed = value;
073:             }
074:         }
075: 
076:         // public interface
077:         public void Create(int levels)
078:         {
079:             // add disc sizes according to number of levels
080:             this.discs.Clear();
081:             for (int i = 0; i < levels; i++)
082:                 this.discs.Add(levels - i);
083: 
084:             if (this.Children.Count > 1)
085:                 this.Children.RemoveRange(1, this.Children.Count - 1);
086:             for (int i = 0; i < levels; i++)
087:                 this.AddRectangle(this.discs[i], i + 1, Colors.Yellow);
088:         }
089: 
090:         public void Push(int size)
091:         {
092:             // is tower full
093:             if (this.discs.Count >= 7)
094:                 return;
095: 
096:             // add disc size
097:             this.discs.Add(size);
098: 
099:             // create and add a new rectangle
100:             this.AddRectangle(size, this.discs.Count, Colors.Yellow);
101:         }
102: 
103:         public void PushAnimated(int size)
104:         {
105:             // any animation active
106:             if (this.t != null)
107:                 return;
108: 
109:             // is tower full
110:             if (this.discs.Count >= 7)
111:                 return;
112: 
113:             // add disc size
114:             this.discs.Add(size);
115: 
116:             // create and add a new rectangle
117:             Rectangle rect = this.AddRectangle(size, this.discs.Count, Colors.Red);
118: 
119:             // set floating recangle's position for animation
120:             this.floatingDiscPosition = TopPosition;
121:             this.floatingDiscRectangle = rect;
122: 
123:             // .. and animate this disc
124:             this.isActive = true;
125:             this.t = Task.Factory.StartNew(() => { this.PushSimulation(); });
126:         }
127: 
128:         // task procedure
129:         private void PushSimulation()
130:         {
131:             // position of top most disc in internal stack
132:             int top = this.discs.Count - 1;
133: 
134:             while (this.floatingDiscPosition != top)
135:             {
136:                 if (!this.isActive)
137:                     break;
138: 
139:                 this.UpdateDiscLocation(this.floatingDiscRectangle, this.floatingDiscPosition);
140:                 Thread.Sleep(this.speed);
141:                 this.floatingDiscPosition--;
142:             }
143: 
144:             // change color of disc
145:             this.ChangeDiscColor(this.floatingDiscRectangle, Colors.Yellow); 
146: 
147:             // task is no more longer needed
148:             this.t = null;
149:         }
150: 
151:         public int Pop()
152:         {
153:             // empty tower
154:             if (this.discs.Count == 0)
155:                 return -1;
156: 
157:             // retrieve size of last rectangle
158:             int size = this.discs[this.discs.Count - 1];
159: 
160:             // remove topmost disc from stack
161:             this.discs.RemoveAt(this.discs.Count - 1);
162: 
163:             // remove rectangle
164:             this.Children.RemoveAt(this.Children.Count - 1);
165: 
166:             return size;
167:         }
168: 
169:         public int PopAnimated()
170:         {
171:             // any animation active
172:             if (this.t != null)
173:                 return -1;
174: 
175:             // empty tower
176:             if (this.discs.Count == 0)
177:                 return -1;
178: 
179:             // retrieve infos about topmost (floating) rectangle
180:             this.floatingDiscPosition = this.discs.Count;
181:             this.floatingDiscRectangle = this.AttachTopMostRectangle();
182: 
183:             // retrieve size of last rectangle
184:             int size = this.discs[this.discs.Count - 1];
185: 
186:             // remove topmost disc from internal stack
187:             this.discs.RemoveAt(this.discs.Count - 1);
188: 
189:             // create new task
190:             this.isActive = true;
191:             this.t = Task.Factory.StartNew(() => { this.PopSimulation(); });
192: 
193:             return size;
194:         }
195: 
196:         private void PopSimulation()
197:         {
198:             // change color of disc
199:             this.ChangeDiscColor(this.floatingDiscRectangle, Colors.Red);
200:             Thread.Sleep(this.speed);
201: 
202:             while (this.floatingDiscPosition != TopPosition)
203:             {
204:                 if (!this.isActive)
205:                     break;
206: 
207:                 this.UpdateDiscLocation(this.floatingDiscRectangle, this.floatingDiscPosition);
208:                 Thread.Sleep(this.speed);
209:                 this.floatingDiscPosition++;
210:             }
211: 
212:             // remove disc from tower
213:             this.RemoveRectangle(this.floatingDiscRectangle);
214: 
215:             // task is no more longer needed
216:             this.t = null;
217:         }
218: 
219:         public void WaitForEndOfSimulation()
220:         {
221:             if (this.t != null)
222:                 this.t.Wait();
223:         }
224: 
225:         public void Stop()
226:         {
227:             if (this.t != null)
228:             {
229:                 this.isActive = false;
230:                 this.t.Wait();
231:             }
232:         }
233: 
234:         // helper methods
235:         private void UpdateDiscLocation(Rectangle rect, int offset)
236:         {
237:             if (this.Dispatcher.CheckAccess())
238:             {
239:                 // set dependency property 'Canvas.Top'
240:                 double y = this.Height - 30 - offset * 20;
241:                 rect.SetCurrentValue(Canvas.TopProperty, y);
242:             }
243:             else
244:             {
245:                 this.Dispatcher.Invoke(
246:                     (Action)(() => { this.UpdateDiscLocation(rect, offset); })
247:                 );
248:             }
249:         }
250: 
251:         private void ChangeDiscColor(Rectangle rect, Color color)
252:         {
253:             if (this.Dispatcher.CheckAccess())
254:             {
255:                 rect.Fill = new SolidColorBrush(color);
256:             }
257:             else
258:             {
259:                 this.Dispatcher.Invoke(
260:                     (Action)(() => { this.ChangeDiscColor(rect, color); })
261:                 );
262:             }
263:         }
264: 
265:         private Rectangle AttachTopMostRectangle()
266:         {
267:             if (this.Dispatcher.CheckAccess())
268:             {
269:                 return (Rectangle) this.Children[this.Children.Count - 1];
270:             }
271:             else
272:             {
273:                 Rectangle tmp = null;
274:                 this.Dispatcher.Invoke(
275:                     (Action)(() => { tmp = this.AttachTopMostRectangle(); })
276:                 );
277:                 return tmp;
278:             }
279:         }
280: 
281:         private void RemoveRectangle (Rectangle r)
282:         {
283:             if (this.Dispatcher.CheckAccess())
284:             {
285:                 this.Children.Remove(r);
286:             }
287:             else
288:             {
289:                 // this.Dispatcher.BeginInvoke(
290:                 this.Dispatcher.Invoke(
291:                    (Action)(() => { this.RemoveRectangle(r); })
292:                 );
293:             }
294:         }
295: 
296:         private Rectangle AddRectangle(int size, int position, Color color)
297:         {
298:             if (this.Dispatcher.CheckAccess())
299:             {
300:                 int width = WidthScaleFactor * size;
301:                 double x = (this.Width - width) / 2;
302:                 double y = this.Height - 30 - position * 20;
303:                 Rectangle rect = this.CreateRectangle(x, y, width, 20, color);
304:                 this.Children.Add(rect);
305:                 return rect;
306:             }
307:             else
308:             {
309:                 Rectangle rect = null;
310:                 this.Dispatcher.Invoke(
311:                     (Action)(() => { rect = this.AddRectangle(size, position, color); })
312:                 );
313:                 return rect;
314:             }
315:         }
316: 
317:         private Rectangle CreateRectangle(double x, double y, int width, int height, Color color)
318:         {
319:             Rectangle rect = new Rectangle();
320:             rect.Height = 20;
321:             rect.Width = width;
322:             rect.Fill = new SolidColorBrush(color);
323:             rect.Stroke = Brushes.Black;
324:             rect.StrokeThickness = 1;
325: 
326:             // set dependency properties 'Canvas.Left' and 'Canvas.Top'
327:             rect.SetCurrentValue(Canvas.LeftProperty, x);
328:             rect.SetCurrentValue(Canvas.TopProperty, y);
329:             return rect;
330:         }
331:     }
332: }

Beispiel 3. Klasse HanoiTowerView.


Die HanoiTowerView-Klasse wurde als WPF-Custom Control realisiert, sie besteht daher nur aus einem (imperativen) C#-Codeanteil, ein XAML-Frontend ist nicht vorhanden. Das Hauptfenster der Anwendung realisieren wir dafür auf klassische Weise, also mit einem XAML- und Codebehind-Anteil. In Listing 4 finden Sie die XAML-Direktiven zur visuellen Gestaltung des Hauptfensters vor:

01: <Window x:Class="TowersOfHanoi.MainWindow"
02:         xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:         xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:         xmlns:local="clr-namespace:WpfTowerControl;assembly=WpfTowerControl"
05:         Title="WPF Towers of Hanoi Simulator" Height="450" Width="700">
06:     <Canvas>
07:         <Button Name="ButtonStart" Canvas.Left="10" Canvas.Top="340" Width="90"
08:                 Click="ButtonTest_Click">Start</Button>
09:         <Button Name="ButtonStop" Canvas.Left="120" Canvas.Top="340" Width="90" 
10:                 Click="ButtonTest_Click">Stop</Button>
11:         <Button Name="ButtonClear" Canvas.Left="230" Canvas.Top="340" Width="90"
12:                 Click="ButtonTest_Click">Clear</Button>
13: 
14:         <local:HanoiTowerView Name="TowerLeft"  Canvas.Top="10" Canvas.Left="10"/>
15:         <local:HanoiTowerView Name="TowerMiddle" Canvas.Top="10" Canvas.Left="230"/>
16:         <local:HanoiTowerView Name="TowerRight" Canvas.Top="10" Canvas.Left="450"/>
17: 
18:         <Label Canvas.Left="450" Canvas.Top="340" Width="90">Discs:</Label>
19:         <ComboBox
20:             Name="ComboBox_Discs" Width="80" HorizontalContentAlignment="Right"
21:             SelectionChanged="ComboBox_SelectionChanged"  Canvas.Left="570" Canvas.Top="340">
22:         </ComboBox>
23: 
24:         <Label Canvas.Left="450" Canvas.Top="370" Width="90">Disc Speed:</Label>
25:         <ComboBox
26:             Name="ComboBox_DiscSpeed" Width="80" HorizontalContentAlignment="Right"
27:             SelectionChanged="ComboBox_SelectionChanged"  Canvas.Left="570" Canvas.Top="370">
28:         </ComboBox>
29:     </Canvas>
30: </Window>

Beispiel 4. Hauptfenster der „Türme von Hanoi“-Anwendung: XAML.


Im Codebehind-Anteil des Hauptfensters finden auch die Aktivitäten der Controller der Anwendung statt. Im Prinzip sind dies die Schaltflächen aus Listing 4, ihre Click-Ereignisse sind auf entsprechende Aktionen am Modell umzulenken. Meldungen des Modells (Ereignisse) sind vom Hauptfenster ebenfalls entgegenzunehmen. In der Regel betreffen die Meldungen den Wechsel einer Scheibe von einem Turm zu einem anderen. Es sind entsprechende Methodenaufrufe an den einzelnen HanoiTowerView-Komponenten zu veranlassen (Listing 5):

001: namespace TowersOfHanoi
002: {
003:     public partial class MainWindow : Window
004:     {
005:         // number of discs
006:         public const int MaxDiscs = 4;
007: 
008:         // model
009:         private ITowersOfHanoi model;
010:         private int discSpeed;
011: 
012:         // threading utils
013:         private Task t;
014:         private bool isActive;
015: 
016:         public MainWindow()
017:         {
018:             this.InitializeComponent();
019: 
020:             // create model
021:             this.model = new HanoiTowerModelImpl();
022:             this.model.Discs = MaxDiscs;
023:             this.model.DiscMoved += new DiscMovedHandler(this.Model_DiscMoved);
024: 
025:             // adjust views
026:             this.TowerLeft.Create(this.model.Discs);
027:             this.TowerMiddle.Create(0);
028:             this.TowerRight.Create(0);
029: 
030:             // setup controller
031:             for (int i = 0; i < 7; i++)
032:                 this.ComboBox_Discs.Items.Add(i + 1);
033: 
034:             this.ComboBox_DiscSpeed.Items.Add(10);
035:             this.ComboBox_DiscSpeed.Items.Add(50);
036:             this.ComboBox_DiscSpeed.Items.Add(75);
037:             this.ComboBox_DiscSpeed.Items.Add(100);
038:             this.ComboBox_DiscSpeed.Items.Add(150);
039: 
040:             this.ComboBox_Discs.SelectedItem = this.model.Discs;
041:             this.ComboBox_DiscSpeed.SelectedItem = 50;
042:         }
043: 
044:         // event handlers
045:         private void ButtonTest_Click(Object sender, RoutedEventArgs e)
046:         {
047:             if (sender == this.ButtonStart)
048:             {
049:                 // any animation active
050:                 if (this.t != null)
051:                     return;
052: 
053:                 this.isActive = true;
054:                 this.t = Task.Factory.StartNew(() => {
055:                     this.model.DoSimulation();
056:                     this.t = null;
057:                 });
058:             }
059:             else if (sender == this.ButtonStop)
060:             {
061:                 this.isActive = false;
062:             }
063:             else if (sender == this.ButtonClear)
064:             {
065:                 this.TowerLeft.Create(0);
066:                 this.TowerMiddle.Create(0);
067:                 this.TowerRight.Create(0);
068:             }
069:         }
070: 
071:         private void ComboBox_SelectionChanged(Object sender, SelectionChangedEventArgs e)
072:         {
073:             ComboBox comboBox = (ComboBox)sender;
074:             int value = (int) comboBox.SelectedItem;
075: 
076:             if (sender == this.ComboBox_Discs)
077:             {
078:                 this.TowerLeft.Create(value);
079:                 this.TowerMiddle.Create(0);
080:                 this.TowerRight.Create(0);
081: 
082:                 this.model.Discs = value;
083: 
084:             }
085:             else if (sender == this.ComboBox_DiscSpeed)
086:             {
087:                 this.discSpeed = value;
088:                 this.TowerLeft.DiscSpeed = this.discSpeed;
089:                 this.TowerMiddle.DiscSpeed = this.discSpeed;
090:                 this.TowerRight.DiscSpeed = this.discSpeed;
091:             }
092:         }
093: 
094:         private void Model_DiscMoved(int from, int to)
095:         {
096:             // premature end of simulation
097:             if (!this.isActive)
098:                 return;
099: 
100:             // pop disc
101:             int size = -1;
102:             switch (from)
103:             {
104:                 case 1:  // Left
105:                     size = this.TowerLeft.PopAnimated();
106:                     break;
107: 
108:                 case 2:  // Middle
109:                     size = this.TowerMiddle.PopAnimated();
110:                     break;
111: 
112:                 case 3:  // Right
113:                     size = this.TowerRight.PopAnimated();
114:                     break;
115:             }
116: 
117:             Thread.Sleep(10 * this.discSpeed);
118: 
119:             // push disc
120:             switch (to)
121:             {
122:                 case 1:  // Left
123:                     this.TowerLeft.PushAnimated(size);
124:                     break;
125: 
126:                 case 2:  // Middle
127:                     this.TowerMiddle.PushAnimated(size);
128:                     break;
129: 
130:                 case 3:  // Right
131:                     this.TowerRight.PushAnimated(size);
132:                     break;
133:             }
134: 
135:             Thread.Sleep(10 * this.discSpeed);
136:         }
137:     }
138: }

Beispiel 5. Hauptfenster der „Türme von Hanoi“-Anwendung: Codebehind.


Die zeitliche Koordination zweier asynchron ablaufender PopAnimated- und PushAnimated-Aufrufe in Listing 5 wurde zunächst einmal sehr einfach – und damit auch nicht ganz optimal – gelöst. Wenn eine Simulation eines PopAnimated- bzw. PushAnimated-Aufrufs maximal 10 Sleep-Verzögerungsaufrufe enthält, so sollte eine entsprechende Wartezeit zwischen einem PopAnimated- und einem PushAnimated-Aufruf genügen, um die Simulation zeitlich sequentiell darzustellen.

Eleganter – und vor allem software-technisch korrekt – können wir den zeitlichen Ablauf gestalten, wenn wir Task-Objekte (Thread-Objekte) zur Umsetzung einer Animation mit einbeziehen. Diese stellen eine Wait-Methode (Klasse Thread: Join-Methode) zur Verfügung. Ein Wait-Methodenaufruf blockiert solange, bis die beteiligte Task abgearbeitet wurde. Eine zeitlich sich anschließende Aktivität kann folglich ganz unkompliziert nach der Rückkehr von Wait in die Wege geleitet werden. Diesen Zweck erfüllt die Methode WaitForEndOfSimulation an einem HanoiTowerView-Steuerelement, siehe dazu auch die Zeilen 219 bis 223 von Listing 3:

public void WaitForEndOfSimulation()
{
    if (this.t != null)
        this.t.Wait();
}

Mit Hilfe dieser Methode implementieren wir die Model_DiscMoved-Methode aus Listing 5 nun verbessert wie folgt:

01: private void Model_DiscMoved(int from, int to)
02: {
03:     // premature end of simulation
04:     if (!this.isActive)
05:         return;
06: 
07:     // pop disc
08:     int size = -1;
09:     switch (from)
10:     {
11:         case 1:  // Left
12:             size = this.TowerLeft.PopAnimated();
13:             this.TowerLeft.WaitForEndOfSimulation();
14:             break;
15: 
16:         case 2:  // Middle
17:             size = this.TowerMiddle.PopAnimated();
18:             this.TowerMiddle.WaitForEndOfSimulation();
19:             break;
20: 
21:         case 3:  // Right
22:             size = this.TowerRight.PopAnimated();
23:             this.TowerRight.WaitForEndOfSimulation();
24:             break;
25:     }
26: 
27:     // push disc
28:     switch (to)
29:     {
30:         case 1:  // Left
31:             this.TowerLeft.PushAnimated(size);
32:             this.TowerLeft.WaitForEndOfSimulation();
33:             break;
34: 
35:         case 2:  // Middle
36:             this.TowerMiddle.PushAnimated(size);
37:             this.TowerMiddle.WaitForEndOfSimulation();
38:             break;
39: 
40:         case 3:  // Right
41:             this.TowerRight.PushAnimated(size);
42:             this.TowerRight.WaitForEndOfSimulation();
43:             break;
44:     }
45: }