RSS
Einstieg ins Programmieren für Anfänger
Diese Seite ist auf Anregung eines Forumsteilnehmers hin entstanden. Wer fühlt sich berufen, Anfängern bei den ersten Schritten zu helfen? Diese Seite ist für jeden änderbar, ich (Harald Bögeholz) bin gespannt, was passiert.
Inhalt
Hintergrundwissen und Theorie:
- Analyse des Beispielprogramms
- Verweise auf C++ Tutorials
- Erklärung des Beispielprogramms (Grundkenntnisse reichen)
- Umsetzung von Ideen in einer Programmiersprache
- Allgemeine Strategien
- Bsp. in C++ oder Java
- die Strategie
- Das fertige Programm
Einleitung
Warum es sinnvoll ist, gerade mit diesem Projekt das Programmieren zu beginnen
Programmieren an sich kann wahrscheinlich jeder lernen. Das Handwerkszeug, das man benötigt um eigene Ideen umsetzen zu können, ist oft innerhalb weniger Tage gelernt und nach einigen Versuchen auch verstanden. Der größere Schritt jedoch erfolgt danach:
Die grundlegenden Konzepte wirklich zu verinnerlichen und sie sinnvoll und effizient einzusetzen.
Leider scheitert der Vorsatz "ich lerne programmieren" oft daran, dass Programmieren ein so weit gefächerter Begriff ist, dass dem Programmieranfänger nicht klar ist, was er darunter zu verstehen hat.
Daher sollte das Programmieren im in Zusammenhang mit einem Problem stehen, das gelöst werden soll. Dabei gibt es jedoch eine Reihe von Hürden, die genommen werden wollen.
Hier kommt nun der c't-Programmierwettbewerb ins Spiel:
In diesem Wiki wird der geneigte Leser an die Hand genommen, indem zunächst die dahinterstehende Theorie (des Spieles Asteroids) analysiert wird. Im Vorbeigehen erlernt man so einige Konzepte der Spieleprogrammierung. Im weiteren Verlauf wird ein Programm geschrieben, das Asteroids selbstständig steuern kann. Um dies zu schaffen, werden einige Programmierkonzepte erarbeitet und umgesetzt. Um den Rahmen nicht zu sprengen, sollte der Leser dennoch nebenbei das eine oder andere Programmiertutorial oder -buch zu Rate zeihen.
Es hat wohl gleich mehrere Vorteile, ausgerechnet hiermit seinen Programmiereinstieg zu versuchen:
- es ist leichter ein einfaches Spiel zu steuern, als es zu erstellen
- die Spielsteuerung und die Lösungsstrategien sind für jeden verständlich
- die grundlegenden Programmiertechniken können durch dieses Projekt praxisnah erlernt werden
- durch das zur Verfügung gestellte Beispielprojekt kann direkt losgelegt werden.
Vorgehen
Das Wichtigste bei der algorithmischen Lösung eines Problems (also beim Schreiben eines Programms, das eine wiederkehrende Aufgabe automatisch bearbeitet) ist, sich klar zu machen, mit welcher Strategie man selbst das gestellte Problem lösen würde. Dazu muss als erstes das gestellte Problem genau untersucht werden. Ist das Problem verstanden, muss die Lösungsstrategie erarbeitet werden. Eine gute Möglichkeit dazu ist, sich vorzustellen, man müsste einem kleinen Kind erklären, was es zur Lösung tun muss. Die einzelnen Schritte, die zur Lösung führen, müssen dabei in möglichst elementare Teilschritte zerlegt werden - eben solche, die ein anderer ohne selbst nachzudenken ausführen kann.
Analyse des Problems
Im konkreten Fall ist die Aufgabe, das Raumschiff so zu steuern, dass es
- nicht mit einem Asteroiden oder einem feindlichen UFO kollidiert,
- nicht von einem feindlichen UFO abgeschossen wird,
- möglichst viele Asteroiden und feindliche UFOs in möglichst kurzer Zeit zerstört.
Dabei sind die folgenden Randbedingungen zu berücksichtigen:
- Das Raumschiff kann aktiv nur nach vorne beschleunigt werden und bewegt sich anschließend mit geringer Verzögerung in eine Richtung weiter.
- Die maximale Beschleunigung ist limitiert.
- Asteroiden bewegen sich gleichförmig.
- Feindliche Schiffe können spontan ihre Bewegungsrichtung ändern.
- Es können nur 4 Schüsse gleichzeitig unterwegs sein.
- Ein Schuss eines feindlichen Raumschiffs kann nicht durch einen eigenen Schuss zerstört werden.
- Unterschiedliche Ziele geben unterschiedlich viele Punkte. Soll ein optimales Ergebnis erziehlt werden, müssen vorrangig lohnende Ziele ausgesucht werden.
- große Asteroiden: 20 Punkte
- mittlere Asteroiden: 50 Punkte
- kleine Asteroiden: 100 Punkte
- große feindliche Schiffe: 200 Punkte
- kleine feindliche Schiffe: 1000 Punkte
Zusammengenommen handelt es sich um ein äußerst komplexes Optimierungsproblem. Ein optimaler Algorithmus müsste diejenige Sequenz von Steuerbefehlen berechnen, die bei jedem Spielablauf den Punktestand am Ende der Spielzeit maximiert. Der Spielablauf ist dabei durch die Sequenz von Zufallszahlen bestimmt, welche die Spielkonsole zum Erzeugen neuer Asteroiden, ihrer Geschwindigkeit, der Steuerung der feindlichen Schiffe usw. benutzt.
Die optimalen Steuerbefehle, welche den Spielstand bei gegebenem Spielablauf maximieren, sind höchstwahrscheinlich überhaupt nicht algorithmisch bestimmbar. Bei dem zu erstellenden Steuerprogramm muss man sich daher mit einer "einigermaßen guten" Lösung zufrieden geben. Aber das macht ja gerade den Reiz eines solchen Programmierwettbewerbes aus: Kein eingesandtes Programm kann die optimale Steuersequenz berechnen, die Programme treten daher wie Spieler an einem echten Automaten als Stellvertreter für ihre Programmierer auf der Jagd nach dem High-Score an.
Aufgabe unseres Programms
[dies bitte noch überarbeiten - bin selbst noch dabei das alles genau zu verstehen]
Wie im Artikel beschrieben soll unser Programm wie folgt aufgebaut sein:
1. Asteroids läuft in einem Emulator auf irgendeinem Computer
2. Asteroids verschickt über das Netzwerk (per UDP) den Inhalt seines Vektorrams (genaueres dazu kommt später)
3. der Client (also unser Programm) empfängt den Inhalt des Vektorrams
4. der Client wertet die empfangenen Daten aus und entscheidet, welche Aktion er ausführen möchte.
5. Der Client sendet seinen Befehl an den Emulator, der in dem Spiel umgesetzt wird.
Besonders wichtig sind hier 3 Dinge:
- Vektor-RAM (Theorie ist zum Verständnis für die Datenauswertung wichtig)
- Datenauswertung
- Treffen der Entscheidung
Vektorram
Die Sprache des Vektorgenerators reloaded
aka - die Sprache des Vektorgenerators verstehen
Der Vektorgenerator (kurz VG) beschreibt den Vektor-Ram, den wir auslesen, bzw. empfangen. Deswegen sind die Befehle des VG die einzigen uns zur Verfügung stehenden Anhaltspunkte um die Spielszene zu analysieren.
Zunächst einmal kennt der VG 16 Opcodes (das sind Steuerungsanweisungen).
- von 0-9
- A-F
0-9 und A sind 16-Bit-Wörter, B-F sind 8-Bit-Wörter. Ein Wort ist normalerweise eine Folge von 8 bit (das sind 8 Zustände die entweder 0 oder 1 sein können). 16-Bit-Wörter setzen sich sozusagen aus 2 8-Bit-Sequenzen zusammen. Um die Verwirrung nicht zu groß werden zu lassen folgt nun eine Veranschaulichung:
[0][0][0][0][0][0][0][0] (eine Sequenz von 8 Bit)
[0][0][0][0][0][0][0][0] [0][0][0][0][0][0][0][0] (eine Seuquenz von 16 Bit)
Das sind die kleinsten Einheiten, mit denen wir uns auseinandersetzen müssen, da einer bestimmten Bit-Folge eine ganz bestimmte Funktion folgt.
sieht der Computer die Bit-Folge:
wird das Programm beendet. Die genaue Auflistung aller Befehle findet sich hier und wird im Folgenden für ein besseres Verständnis genauer beschrieben.
Aus Gründen der besseren Benutzbarkeit spricht man den Computer nun nicht von Hand in dieser binären Schreibweise an, sondern nutzt statt des binären das Hexdezimale Zahlensystem. Kurz gesagt heißt dies, dass als mögliche Ziffern nicht nur 0 und 1 zur Verfügung stehen oder 0-9 wie im dezimalen Zahlensystem, sondern die Symbole 0-9, A,B,C,D,E und F. So lässt sich sehr bequem, platzsparend und dennoch verständlich mit dem Dezimalsystem umgehen. Nähere Erklärungen dazu finden sich hier oder hier.
Im Artikel der c't ist ein Beispiellisting für einen Bildschirmausschnitt angegeben.
| Speicherstelle | Opcode | Opcode | Mnemonic |
| 000 | E001 | JMPL $001 | |
| 001 | A11C | 0311 | LABS (785, 284), s0 |
| 003 | 7000 | 0000 | VCTR (0, 0), s7, z0 ; Ruhezeit |
| 005 | 7000 | F000 | VCTR (0, 0), s7, z15 ; Schuss |
| 007 | A167 | E2BC | LABS (700, 359), s14 |
| 01D | C929 | JRSL $929 ; UFO | |
| 01E | A1AB | E272 | LABS (626, 427), s14 |
| 020 | 9000 | 0000 | VCTR (0, 0), s9, z0 ; Ruhezeit |
| 022 | 4380 | 0500 | VCTR (-256, 896), s4, z0 |
| 024 | 4720 | C680 | VCTR (-640, -800), s4, z12 ; Schiff |
dieser Ausschnitt aus dem Listing wird nun genau analysiert.
Speicherstelle: bezeichnet die Speicherstelle im Vektor-Ram. Dies ist für uns ohne Bedeutung und kann ignoriert werden
Opcode: diese beiden Spalten stellt die eigentliche Sprache des Vektorgenerators dar.
Mnemonic: Dies ist eine für Menschen besser merkbare Darstellung der Opcodes. Siehe Wikipedia und ist nur als Kommentar zu betrachten und wird nicht im Vektor-Ram stehen. Diese Spalte schlüsselt die beiden Opcode-Spalten auf, was wir jedoch etwas genauer betrachten werden.
Der Ausschnitt des obigen Listings würde in unserm Vektor-Ram foglendermaßen aussehen:
E001A11C0311700000007000F000A167E2BCC929A1ABE27290000000438005004720C680
Da dies jedoch schwer lesbar wäre, halten wir uns an die Tabelle und arbeiten diese nun Zeile für Zeile ab:
Zeile 1: Am Beginn des RAM (Speicherstelle 000) finden wir die Zeichenfolge E001 vor. Wie im Artikel beschrieben, bedeutet der Opcode E einen Sprung an die Adresse die in den folgenden Bits angegeben wird. (dies dient Asteroids intern dazu, immer die richtige Hälfte des Vektor-Rams anzusprechen, so wie dies im Artikel beschrieben wurde.) Die letzte Spalte zeigt uns dies nocheinmal in einer für uns besseren Sprache:
E (=JMPL = unbedingter Sprung) zu Adresse 001.
Zeile2: Die folgende Speicherstelle (001) enthält nun die Zeichenfolge A11C0311. Warum berücksichtigen wir hier 8 und nicht 4 Buchstaben? ganz einfach:
Wie zu Beginn des Kapitels erwähnt, können die Opcodes entweder aus einem 16-bit-Wort oder aus 2 16-bit-Worten bestehen.
16 bit = [0][0][0][0][0][0][0][0] [0][0][0][0][0][0][0][0] --> 216 = 65536 mögliche Zustände.
im hexdezimalen System bietet eine Folge von 4 Ziffern 164 = 65536 mögliche Zustände. Somit können die 16-bit-Worte jeweils mit unseren 4 Ziffern beschrieben werden. Die erste Ziffer beschreibt den Opcode. die foglenden 3 Ziffern stehen zur Übergabe von Informationen zur Verfügung (siehe im Artikel "Sprache des Vektorgenerators)
da jedoch einige Opcodes aus 2-Wort-Befehlen bestehen benötigt man dementsprechend 2x4 Ziffern, also unsere 8 Ziffern.
im der erste Zeile sagte uns Opcode E ( JMPL - unbedingter Sprung), dass es sich um einen 1-Wort-Befehl handelt. (E001 reicht). der Befehl A (LABS - Strahl positionieren) ist ein 2-Wort-Befehl. Dementsprechend reicht der Befehl A11C nicht aus und wir müssen die folgenden Ziffern - 0311 - mit in unsere Berechnungen mit einbeziehen.
der Befehl A (LABS) setzt den Elektronenstrahl der Bildröhre auf eine ganz genau definierte Position (angegeben durch x und y).
nach A folgt 11C. Diese ist von hexdizimal in binär umgerechnet: 100011100
100011100 in Dezimalsystem umgerechnet entspricht 284 und somit der y-Koordinate, wie in der Mnemonic-Spalte unschwer zu erkennen.
der zweite Teil des A-Befehls (0311) versteckt die x-Koordinate in den letzten 10 bit (ist im Kasten "Sprache des Vektorgenerators" des Artikels zu sehen). die letzten 10 bit entsprechen den letzten 3 Ziffern (311) und ergeben umgerechnet vom hex- ins Dezimalsystem: 785, also unsere x-Koordinate.
Hier kann man ein wenig mit der Umrechnung der verschiedenen Zahlensystem herumexperimentieren um ein Gefühl dafür zu erlangen.
Die erste Ziffer unseres zweiten Wortes (0331) beinhaltet die letzten 6 bit und damit den GSF - den globalen Skalierungsfaktor. Dieser spielt für die Zeichnung verschiedener Größen der Objekte (Raumschiff, Metereoid,...) eine Rolle und beträgt ins usnerem Fall 0
Damit ist auch die 2. Zeile erklärt.
3. Zeile: Nachdem wir nun einen 2-Wort-Befehl hatten, befinden wir uns an Speicherstelle 003. 002 beinhaltet den Befehl 0311, den wir eben mit betrachet haben.
der Befehl lautet 7000 0000. Und damit wieder einen 2-Wort-Befehl. 7 zeichnet eine Linie auf den Bildschirm. In unserem Fall sind jedoch sämtliche Argumente 0 - und damit ist auch die Sichtbarkeit auf 0 gesetzt, was bedeutet, dass in diesem Fall nichts angezeigt wird.
4. Zeile: Wir befinden uns nun an Speicherstelle 005 (von Speicherstelle 003 wieder 2 Wörter weitergerückt) und erkennen ebenfalls den Befehl 7 - also Zeichnen einer Linie. Diese ist sogar sichtbar, was sich erkennen lässt, wenn man den oft erwähnten Kasten zu Rate zieht. Die Sichtbarkeit befindet sich in den ersten 6 bit des zweiten Wortes und beträgt hier F, also 15. (wir fangen bei 0 an zu zählen). Somit ist ein sichtbarer Punkt zu erkennen, da sich der Elektronenstrahl nicht weiter bewegt hat (der Linie wurde keine Länge und Richtung übergeben), was auf dem Bildschirm als leuchtender Punkt - also als Schuss zu erkennen ist.
Die folgenden Zeilen sollten mit dem Kasten im Artikel erarbeitet werden können.
Herzlichen Glückwunsch - wir haben die "Sprache des Vektorgenerators" verstanden! :)
Interpretation des Vektor-RAM
Nachdem nun die grundsätzliche Funktionsweise des Vektorgenerators analysiert wurde, geht es im folgenden nun endlich mit dem eigentlichen Programm weiter.
Wie bereits erwähnt, empfängt unser Programm von dem Spiel Asteroids (genauer gesagt von dem Emulator in dem es läuft) jeweils den Aufbau genau eines Bildes. Die Informationen werden aus dem Vektor-RAM ausgelesen und enstprechen damit den Befehlen des Vektorgenerators, die wir in unserem Programm auswerten müssen.
Hier müssen wir zuerst ein kleines Problem umschiffen, das hier im Wiki bereits angesprochen wurde. Die Daten des Vektor-RAM, die wir empfangen ist Little-Endian. Wer mit dem Begriff nichts anfangen kann, findert hier die nötigen Hintergrundinformationen. Kurz zusammengefasst bedeutet dies folgendes:
Der Computer hat 2 Möglichkeiten eine Bitfolge auszuwerten. Entweder ist das höchst-wertige Bit rechts oder Links. Auf einem Standard-Intel-PC befindet sich das höchstwertige Bit auf der linken Seite. Bei dem Spiel Asteroids ist die Interpretation jedoch umgekehrt, sodass das höchst-wertige Bit am Rechten Rand liegt. Dies bedeutet für uns, dass wir die empfangenen Daten des Vektorgenerators noch "umschreiben" müssen.
War in unserem Beispiellisting des Vektor-Rams der Bildschirm folgendermaßen beschrieben -
E0 01 A1 1C 03 11 70 00 00 00 70 00 F0 00 A1 67 E2 BC C9 29 - (mit Leerzeichen zur besseren Lesbarkeit)
so ändert sich diese Reihenfolge durch das empfangene Little-Endian-Format folgerndermaßen:
01 E0 1C A1 11 03 00 70 00 00 00 70 00 F0 67 A1 BC E2 29 C9
Für jeden Bildinhalt erhalten wir ein Paket mit 1024 Byte Größe. (da jeder Bildschirminhalt in genau dieser Größe liegen muss - egal, was passiert. Ob nun 1 oder 10 Objekte - es wird immer der komplette (halbe) Vektor-Ram ausgelesen, sodass wir auf 1024 Byte kommen.
Zusätzlich zu diesen 1024 Byte schickt der Emulator jeweils ein Byte mit, das bei jedem neuen Bildschirminhalt um 1 erhöht wird. Dadurch kann unser Programm erkennen, ob Pakete verloren gingen, oder in der richtigen Reihenfolge ankamen.
In einem weiteren Byte schickt der Emulator das letzte von unserem Programm empfangene Byte wieder zurück.
Somit erhält unser Programm jeweils ein 1026 Byte-Paket, das es analysieren muss. So kann der Bildschirminhalt des Spiels rekonstruiert werden, woraufhin das Programm entscheidet, wie das Raumschiff gesteuert werden soll.
Kommunikation mit Asteroids
Unser Progamm kann bisher also den Bildschirminhalt des Spieles rekonstruieren. Nachdem es einen Steuerbefehl errechnet hat kann es folgende Befehle an Asteroids senden:
- Hyperspace
- Schub
- Feuer
- Links
- Rechts
Mit dem Hyperspace kann das Raumschiff (einmalig?) aus einer ausweglosen Situation fliehen, indem es sich "wegbeamt".
Das Raumschiff selbst kann sich nur um seine eigene Achse drehen (links oder rechts) und beschleunigen. Möchte man als anhalten, muss man sich um 180° drehen und beschleunigen. Möchte man eine Kurve fliegen, muss man das Raumschiff zunächst beschleunigen, es (während es sich [ gleichförmig weiterbewegt drehen und in der gedrehten Lage wiederum beschleunigen.
Schließlich kann das Raumschiff Astereoiden und UFOs abschießen. Hierbei können jedoch nur 4 Schüsse gleichzeitig unterwegs sein.
Um diese Befehle zu übermitteln, sendet unser Programm ein Paket mit einer Länge von 8 Byte. Die ersten 6 Byte enhalten die Signator "ctmame". Dadurch erkennt unsere Emulator, dass die folgenden Befehle an ihn gerichtet sind.
Das 7. Byte enthält in den unteren 5 Bit die zu drückenden Tasten:
Bit Befehl 0 Hyperspace 1 Feuer 2 Schub 3 Rechts 4 Links
die restlichen Bits werden ignoriert.
im letzten verbleibenden, 8. Byte kann unser Programm senden, was es will. Hierbei handelt es sich um das oben beschriebene - Ping-Byte, dessen Wert wieder zurückgeschickt wird. (Der Vorschlag der c't lautet, damit Verzögerungen im Netzwerk zu messen.)
Analyse des Beispielprogramms
Verweise auf C++ Tutorials
Um das Beispielprogramm der c't verstehen zu können, sollte man vielleicht das eine oder andere C/ C++ Tutorial oder Buch gelesen oder zumindest überflogen haben. Ohne grundlegende Programmiergrundkenntnisse kommt man ab hier leider nicht mehr weiter.
Jedoch ist es leichter, die etwas trockene und vielleicht komplizierte erste Phase des Lernens einer Programmiersprache zu überstehen, wenn man ein Ziel vor Augen hat. Und dafür ist dieser Artikel gedacht :)
Einige Anlaufstellen:
- Bücher: hier sollte jeder selber nachsehen, was genau er will und mit welchem Buch er gut zurechtkommt.
Erklärung des Beispielprogramms
Zunächst sollte man sich das c't-Beispielprogramm besorgen. Der Übersicht halber wurde die Analyse des Beispielprogramms ausgelagert und ist hier zu finden:
