AntMe! 2.0 Blog

Statische Generische Klassen und Bastis Tutorial

2007-11-17T11:56:00Z

Vor ein paar Tagen hat Basti mir eine Ameisenklasse geschickt, die er von jemandem bekommen hat, die einen Bug in AntMe! demonstriert. Für solche Einsendungen sind wir immer dankbar, denn genau wie bei der Rechtschreibung gilt bei der Programmierung auch, dass man seine eigenen Fehler meistens nicht selbst findet. Nach Bastis E-Mail habe ich noch eine E-Mail von jemand anderem bekommen, der den selben Bug demonstriert hat. Es handelt sich hierbei um eine neue Version des Bug-Bugs durch die man einen Käfer mehrfach töten und damit sehr viele Punkte sammeln konnte. Das ist jetzt natürlich behoben. Wenn Käfer tot, dann Käfer tot. Nochmal draufhauen bringt nichts.

Die zweiten Person hat mir dann noch eine andere Ameisenklasse geschickt, durch die ich einen anderen lange gesuchten Bug gefunden habe. Vielen Dank Philipp! Dank dir bewegen sich Äpfel nun nicht mehr von alleine und in die falsche Richtung.

Wie auch immer. Mir war an Philipps Ameisenvolk eine Hilfklasse aufgefallen, die mir ein wenig seltsam erschien und in dem anderen Volk fand ich selbige Klasse auch wieder. Ich kam dann darauf: beide haben den KoordinatenSpeicher aus Bastis Globales Gedächtnis Tutorial verwendet. Das habe ich, weil ich was Ameisen angeht ein Fan von überhaupt-kein-Gedächtnis-und-schon-gar-nicht-global bin, zugegebenermaßen nie gelesen. Inzwischen habe ich das nachgeholt und das Tutorial ist (wie erwartet) richtig gut, aber eine kleine Sache darin ist sicher nicht im Sinne des Autors und damit kommen wir endlich zum Titel dieses Blog Eintrags.

Basti schreibt

Kommen wir also schon zu unserem ersten Schritt. Wir erstellen uns eine neue Klasse mit dem Namen „KoordinatenSpeicher“. Diese Klasse machen wir statisch und erstellen uns dort drin 3 Collections.

public static class KoordinatenSpeicher<K,V> {
    private static Dictionary<K, V> zuckerKoordinaten = new Dictionary<K, V>();
    private static Dictionary<K, V> obstKoordinaten = new Dictionary<K, V>();
    private static Collection<int> geloeschteObjekte = new Collection<int>();
    // Properties...
}

Jetzt Fragt ihr euch bestimmt was hat der Typ da gemacht. Ich erkläre es euch. Also wir ihr seht haben wir jetzt 3 Collections erstellt. Die erste Collection „zuckerKoordinaten“ ist dafür bestimmt alle Zucker Koordinaten abzuspeichern. Die 2te Collection „obstKoordinaten“ ist für die Obst Koordinaten zuständig. Dann seht ihr hier noch, dass ich hier generische Typen benutzt habe und zwar K und V. K steht in diesem Falle für den Typen des Keys und V für den Typen des Values. Als Key nehmen wir im weiteren Tutorial immer die ID des Obstes oder Zuckers und also Value immer das Obst oder den Zucker selbst, aber dazu später mehr. Als drittes haben wir noch die „geloeschteObjekte“, hier werden alle IDs der Obst oder Zuckerobjekte gespeichert, die schon gelöscht wurden, auch dazu später mehr. Das war dann schon erst einmal alles was wir für unseren Speicher benötigen um ihn zu benutzen.

Gestört hat mich daran der generische Typparameter <K,V> an der statischen Klasse KoordinatenSpeicher. Der Typparameter K für die Dictionary Instanzen ist im Tutorial immer int, bei der Collection Instanz steht aber nicht K sondern direkt int. Das ist meiner Meinung nach ein wenig inkonsequent. Der Zugriff auf den Speicher erfolgt unterschiedlich, je nachdem auf welche der internen Listen zugegriffen wird.

KoordinatenSpeicher<int, Zucker>.zuckerKoordinaten.Add(zucker.Id, zucker);
KoordinatenSpeicher<int, Obst>.obstKoordinaten.Add(obst.Id, obst);

Was nun passiert ist nämlich folgendes: der Compiler merkt sich, mit welchen Typparametern auf den KoordinatenSpeicher zugegriffen wird und erzeugt für jede Parameterkombination eine neue "Instanz" der statischen Klasse. Am Ende gibt es also nicht nur einen, sondern viele KoordinatenSpeicher, jeder mit eigenen Versionen der internen Listen. Freilich wird im Tutorial in jedem Speicher nur auf die Liste zugegriffen, die den passenden Namen hat. Aber folgendes ist trotzdem möglich:

KoordinatenSpeicher<int, Zucker>.obstKoordinaten.Add(zucker.Id, zucker);
KoordinatenSpeicher<int, Obst>.zuckerKoordinaten.Add(obst.Id, obst);

Das ganze ist nicht schlimm. Es werden einfach nur ein paar Listen erzeugt, die nie verwendet werden. Und es hat mich einmal zum Nachdenken angeregt und das kann nie schaden. Damit auch Anders Hejlsberg (der Erfinder von C#) wieder gut schlafen kann, schlage ich vor, die Klasse auf eine der folgenden Arten abzuändern. Ich favorisiere stark die zweite Methode, da dort einfach ersichtlicher ist was passiert:

public static class KoordinatenSpeicher<K,V> {
    private static Dictionary<K, V> koordinaten = new Dictionary<K, V>();
    private static Collection<K> geloeschteObjekte = new Collection<K>();
    // Properties...
}

public static class KoordinatenSpeicher {
    private static Dictionary<int, Zucker> zuckerKoordinaten = new Dictionary<int, Zucker>();
    private static Dictionary<int, Obst> obstKoordinaten = new Dictionary<int, Obst>();
    private static Collection<int> geloeschteObjekte = new Collection<int>();
    // Properties...
}

Was haben wir nun von der ganzen Sache? Zwei Bugs weniger und etwas dabei gelernt :-) Im Anhang zu diesem Blog Eintrag findet ihr ein kleines Demo Projekt, das die Sache anschaulich demonstriert.

There is no theory of evolution. Just a list of creatures Chuck Norris has allowed to live.

XNA und Windows Forms

2007-11-16T12:06:00Z

Im XNA Team Blog stand heute die lang erwartete Meldung, dass die Beta von XNA Game Studio 2.0 bald verfügbar sein wird. Leider stand da auch folgendes:

Unfortunately, there were a few things that didn't make it into this release. The most prominent being that you cannot host XNA applications in Windows Forms.

Den kompletten Beitrag gibt es hier: http://blogs.msdn.com/xna/archive/2007/11/15/xna-game-studio-2-0-beta-available-soon.aspx

Gerade auf dieses Feature habe ich gewartet. Das hätte die Entwicklung von XNA Visualisierungen um so vieles eleganter gemacht. Eine rudimentäre 3D Visualisierung gibt es schon länger. Die zeigt bisher nur das Spielfeld und Ameisen an, dafür ist die Kamera voll beweglich. In Vorbereitung auf einen XNA Workshop den ich nächste Woche halte habe ich gestern abend eine 2D Visualisierung gebaut und die 3D Version baue ich dafür eventuell auch noch ein wenig aus. Dabei legt XNA mir folgende Steine in den Weg:

Ein Microsoft.Framework.Xna.Game hat eine eigene Ereigniswarteschleife, die über die Run() Methode synchron ausgeführt wird. Für reine XNA Spiele, die als Hauptfenster laufen, macht das Sinn. Für AntMe! wäre es aber besser ich könnte eine eigene Schleife bauen und die XNA Ereignisbehandlung (Grafik-Hardware!) darin selbst anstoßen.
Sämtliche Zugriffe auf die Game Instanz dürfen nur aus dem Thread heraus erfolgen, der die Instanz erzeugt hat. Eine Invoke() Methode wie bei Windows Forms gibt es nicht.
Die Game Instanz verweist auf eine GameWindow Instanz. Der fehlen sogar auf dem PC so wichtige Methoden wie Show() und Hide(). Außerdem wird der Mauscursor ausgeblendet.

Aber man ist ja nicht auf den Kopf gefallen und weiss sich weiterzuhelfen. Inzwischen bin ich so weit, dass ich XNA zwar nicht als Control in eine bestehende Windows Forms Anwendung einbinden kann, aber beide Techniken in einem Fenster, das nicht das Hauptfenster ist, nebeneinander laufen lasse.

Das Erzeugen der Game Instanz und der Aufruf der Run() Methode passieren in einer statischen Methode die von einer anderen statischen Methode in einem neuen Thread gestartet und selbst wiederrum von IPlugin.Start() aufgerufen wird.
Über Mouse.GetState() können die Mauskoordinaten ausgelesen werden. Den Cursor zeichne ich einfach selbst als Sprite.
Die GameWindow Instanz namens Window liefert ein Handle, das benutzt werden kann um eine Windows Forms Form Instanz für das Spielfenster zu ergeugen.
Auf dieser Instanz kann dann endlich auch Show() und Hide() aufgerufen werden. So kann das XNA Spiel über mehrere AntMe! Spiele hinweg verwendet und dazwischen nur versteckt werden.
Außerdem können der Form Instanz wie gewohnt weitere Kontrollelemente hinzugefügt werden. Diese werden über den XNA Hintergrund gezeichnet. Der Bereich in den XNA zeichnet kann über graphics.GraphicsDevice.Viewport festgelegt werden Auf diese Weise kann dann auch eine XNA Visualisierung die aus der alten 2D-Visualisierung gewohnte Seitenleiste bekommen.

Hier der Code um an das Fenster zu kommen:

Form form = (Form)Form.FromHandle(game.Window.Handle);

Und hier der Code um das Fenster aus einem anderen Thread heraus zu verstecken:

if (form != null && form.IsHandleCreated)
form.Invoke(new ThreadStart(form.Hide));

So, dann werde ich mal meinen Workshop weiter vorbereiten. Viel Spaß mit XNA!

The chief export of Chuck Norris is pain.

Schon wieder Listen in .NET und Profiling

2007-11-15T14:48:00Z

Ich habe in der MSDN Library eine sehr schöne englische Artikelreihe über Listen in .NET gefunden. Dort wird unter anderem auch bestätigt, was ich mir über die Funktionsweise der Klassen ArrayList und List<T> schon gedacht habe. Die Artikel finden sich hier:

http://msdn2.microsoft.com/en-us/library/aa287104(VS.71).aspx

Außerdem habe ich mich ein wenig mit Profiling beschäftigt. Jeder Profi wird mir wahrscheinlich gleich auf den Hinterkopf hauen wollen, wenn ich das sage (Denkvermögen anregen und so), aber wir haben AntMe! bisher nie durch einen Profiler gejagt. Ein Profiler ist ein Programm, das kurz gesagt misst, wie oft jede Methode in einem Programm aufgerufen wird, wie lange das dauert und wie viel Speicher dabei verbraucht wird. Ich werde demnächst einen ausführlichen Blog Eintrag über das Profiling schreiben. Jetzt möchte ich aber bei den Listen bleiben und gebe lediglich folgendes bekannt:

In einem Spiel mit den Demo-A-Meisen wird der Befehl List<T>.Clear() knapp 200 Millionen mal aufgerufen und dessen Ausführung verschlingt über 38% der gesamten Laufzeit des Spiels. Wird zeit die Listen zu optimieren. Schnell.

Beim Leeren der Listen wird durch die komplette Liste iteriert und alle Elemente werden auf null gesetzt. Das dauert seite Zeit. ich denke darüber nach meine Group<T> Klasse so zu ändern, dass das unterlassen wird. Damit bleiben die Elemente in der Liste bis sie überschrieben werden. Das wirkt sich dann positiv auf die Geschwindigkeit aber negativ auf den Speicherverbrauch aus. Ich werde damit ein wenig herumspielen und die Ergebnisse dann hier bekannt geben.

Chuck Norris counted to infinity - twice.

Codename "Chuck"

2007-11-11T17:51:00Z

Der Codename für AntMe! 2.0 ist ab sofort "Chuck", benannt nach den Chuck Norris Facts.

Outer space only exists because it's afraid to be on the same planet with Chuck Norris.

Nocheinmal Listen in .NET

2007-11-05T10:35:00Z

Ich habe den Test aus dem letzten Blogbeitrag gestern einmal mit Visual C# 2008 und LINQ durchgeführt. Der verwendete Code sieht für die vorgeschlagene Group<T>-Klasse etwa folgendermaßen aus:

var query = from item in list where item != null select item;
foreach (Item item in query)
item.Value--;

Für die generische Liste und die verkettete Liste fällt natürlich die where-Klausel weg, aber hier ist der Zwischenschritt über LINQ auch sinnlos. Die ArrayList unterstützt LINQ nicht. Auf jeden Fall war die foreach-Iteration über die LINQ-Abfrage in jedem Fall um den Faktor drei bis fünf langsamer als die foreach-Iteration direkt über die Liste. Das bedeutet nun nicht, daß LINQ keine Daseinsberechtigung hätte, es bedeutet nur, daß ich mir ein anderes Projekt ausdenken muß, um einmal damit herumspielen zu können ;-)

Listen in .NET

2007-10-28T19:33:00Z

Ich habe mich die letzten beiden Tage ein wenig mit Listen in .NET beschäftigt. In AntMe! 1 habe ich bisher hauptsächlich die generische List Klasse verwendet und die Listen mit dem foreach Konstrukt durchlaufen. Foreach soll ja bekanntlich langsamer sein als for und da AntMe! sehr viele Listen verwaltet wollte ich einmal sehen wie viel langsamer es ist.

Die einfachste Liste in .NET ist das Array. Da ein Array eine feste Größe hat, in AntMe! aber laufend neue Elemente zu einer Liste hinzugefügt werden können, braucht es ein wenig mehr Logik um eine Liste zu verwalten. Zunächst habe ich mir dazu die ArrayList und List<T> Klassen angeschaut. Der Quelltext des .NET Frameworks wurde zwar noch nicht veröffentlicht, aber wenn man das Verhalten dieser beiden Listen-Typen betrachtet, bekommt man eine gute Vorstellung davon wie sie funktionieren. Prinzipiell funktionieren beide Listen-Typen gleich und unterscheiden sich nur im Typ der enthaltenen Elemente. Elemente können am Ende und an beliebiger Position hinzugefügt und über ihren Index oder ihre Referenz gelöscht werden. Beiden Listen können über einen Indexer wie ein Array angesprochen werden und benutzen intern ein Array zum Speichern der Elemente. Wenn nun ein Element aus der Mitte des internen Arrays gelöscht wird, dann werden die nachfolgenden Elemente nach links aufgerückt. Wenn ein Element in die Mitte eingefügt wird, werden die Elemente ab der Einfügeposition zunächst nach rechts verschoben und dann das neue Element an der Einfügeposition gespeichert. So ist das Array immer lückenlos gefüllt. Bei Bedarf wird das Array vergrößert oder verkleinert wenn es zu wenig Elemente enthält. Das sind wie gesagt alles Vermutungen, bestätigt durch das beobachtete Verhalten.

Ein Benchmark sollte mir nun zeigen welcher Listen-Typ mit welcher Art des Durchlaufens wie schnell ist. Die Messwerte unterliegen dabei sehr starken Schwankungen. Man weiß nie, wann der Garbage Collector einspringt und was der Computer sonst noch so treibt. Qualitative Aussagen kann ich dennoch machen. Ein Unterschied zwischen einer ArrayList und einer generischen List<T> lässt sich nicht feststellen. Nehmen wir zunächst eine Liste in der Größenordnung von 10.000 Elementen. Wenn wir diese Liste nun 10.000mal durchlaufen, dann braucht ein foreach etwa 150% mehr Zeit als ein for. Bei einer Liste mit etwa 1.000.000 Elementen die 100mal durchlaufen wird, ist foreach nur noch etwa 10% langsamer, obwohl nominell die selbe Anzahl an Elementen durchlaufen wurde. Wenn der Compiler auf ein foreach stößt erzeugt er MSIL-Code der ein Iterator-Objekt erzeugt und über Methodenaufrufe auf dem Iterator die Liste durchläuft. Das Erzeugen dieses Iterators kostet offensichtlich Zeit, während die Methodenaufrufe dank Optimierung durch den Compiler (Inlining) recht billig sind. Auch wenn der Code damit nicht mehr ganz so schön aussieht, ist für AntMe! 2 das for-Konstrukt auf jeden Fall empfehlenswert.

Das Befüllen der Listen wird sehr schnell abgearbeitet und die benötigte Zeit ist vernachlässigbar. Was nicht vernachlässigt werden darf ist das Auffinden von Elementen in der Liste. Wenn zum Beispiel ein Element gelöscht werden soll, dann muß vorher der Array-Index des Elements gefunden werden. Das Löschen unter Angabe eines Index ist damit schneller als das Löschen eines Elements dessen Index nicht bekannt ist. Die Mehrkosten liegen in der Größenordnung um 100% bis 1000%. Daraus ergibt sich, daß es für ein Element immer gut ist, seinen Array-Index zu kennen. Durch das wiederholte Verschieben von Teilen des Arrays verändern sich aber die Indizes seiner Elemente.

Bei genauer Betrachtung haben die beiden Listen-Typen eine Eigenschaft, die ich nicht einfordere und das ist die Reihenfolge-Treue der Elemente. Mir reicht es so gut wie immer, daß ein Element in einer Liste enthalten ist. Seine Position relativ zu den anderen Elemente ist mir aber egal. Nehmen wir wieder ein Array her um die Elemente zu speichern. Genaugenommen haben wir in verwaltetem Code auch gar keine andere Möglichkeit um eine unbekannte Anzahl von Elementen typsicher zu verwalten. Beim Entfernen eines Elements sollen die nachfolgenden Elemente aber nicht aufrücken, sondern eine leere Stelle zurücklassen. Neue Elemente sollen an einer beliebigen freien Position eingefügt werden. Damit das Array nicht bei jedem Einfügen komplett durchlaufen werden muß, um einen freien Index zu finden, soll eine Liste freier Indizes gespeichert werden. Hier darf man natürlich nicht in die Falle treten, dafür einen der betrachteten Listen-Typen zu verwenden. Sämtliche Vorteile der neuen Liste wären dadurch wieder dahin. Am Anfang soll das Array von vorne beginnend aufgefüllt werden und sobald einzelnen Elemente entfernt werden, sollen die frei gewordenen Indizes gespeichert und wiederverwendet werden. Hierfür bietet sich ein Ringpuffer oder ein Stapel (Stack) an. Ich habe eine entsprechende Listen-Klasse implementiert und mit den anderen Listen-Typen verglichen. Für das Speichern der Indizes habe ich einen eigenen Ringpuffer fester Größe benutzt. Das .NET Framework bietet zwar eine Stack-Klasse an, aber ich wollte eine leichtgewichtige Lösung von der ich weiß, was sie tut. Ich werde den Ringpuffer wohl noch durch einen (eigenen) Stapel ersetzen. Der ist einfacher zu verwalten als der Ringpuffer, aber ich habe auf die Schnelle einfach nicht daran gedacht. Beim Iterieren über das Array muß man natürlich dafür sorgen, daß leere Indizes nicht beachtet werden.

Aussagen über die Geschwindigkeit lassen sich aber auch so treffen. Das Einfügen von neuen Elementen dauert je nach Füllungsgrad des Arrays und Größe des Ringpuffers länger, ist aber weiter vernachlässigbar. Das Iterieren mit for und foreach dauert etwa genau so lange wie bei den vorhandenen Listen-Typen. Das Löschen von Elementen über ihren Index geht unabhängig von der Listen-Größe beinahe in Null-Zeit. Und das Löschen über eine Referenz benötigt grob 85% weniger Zeit als vorher! In AntMe! 2 werde ich diese Klasse auf jeden Fall verwenden. Die Elemente der Liste werden dabei auch ihren Array-Index speichern. Da sich die Indizes nicht verändern müssen in der Beziehung auch keine weiteren Vorkehrungen getroffen werden (wie ein Subject-Observer-Beziehung die den Elementen ihren neuen Index mitteilt). Natürlich kann ein Element in mehreren Listen enthalten sein, so daß man hier aufpassen muß, den gespeicherten Index nur in der richtigen Liste zu verwenden.

Ich habe auch eine verkettete Liste implementiert um zu sehen wie dieses Konzept sich schlägt. Die Liste ist doppelt verkettet, aber es wird nur die Vorwärts-Referenz verwendet. Das Löschen von Elementen verhält sich verständlicherweise genau umgekehrt wie bei dem eben vorgestellten Listen-Typ. Das Löschen über eine Referenz ist billig und das Löschen über einen Index ist teuer. Das Hinzufügen eines Elements dauert unabhängig von der Listengröße immer gleich lang da es nur aus dem Verbiegen einiger Referenzen besteht. Das Iterieren durch die Liste dauert im Rahmen der Meßungenauigkeit so lange wie bisher. Lohnenswerte Vorteile ergeben sich keine und wenn ein Element in mehreren Listen erhalten sein soll, muß man noch wesentlich mehr Aufwand treiben. Mit verketteten Listen werde ich mich daher zunächst nicht weiter beschäftigen.

Der verwendete Quelltext findet sich im Anhang dieses Posts. Wenn ihr den Quelltext geladen habt, dann erzeugt einen Release Build und startet ihn mit Strg+F5. Nur so werden alle Compiler-Optimierungen angewandt und das Programm ohne Debug-Code gestartet. Mehr über AntMe! 2 bald in diesem Blog