| ★ AMSTRAD CPC ★ GAMESLIST ★ ARIADNE (c) CPC AMSTRAD INTERNATIONAL ★ |
 |
Der Faden der Ariadne Der CPC kreiert Labyrinthe Spiele, in denen Labyrinthe die Spieloberfläche darstellen, gibt es wie Sand am Meer. Bei den meisten Programmen sind die Labyrinthe fest abgespeichert oder können manuell mittels eines Editors geändert werden. Nicht so bei Ariadne! Als 1-kByte-Programm wurde es uns zugesandt, aber wir hielten es einer Extraveröffentlichung für würdig. Wer war Ariadne? Dazu ein Blick in die Vergangenheit: Schon zu Zeiten der alten Griechen übten Labyrinthe eine Faszination auf die Menschen aus und regten — wie die griechische Sagenwelt belegt — ihre Fantasie an. Wer hat nicht schon vom Labyrinth des Königs Minos von Knossos gehört, in welchem alle neun Jahre sieben Jünglinge und sieben Jungfrauen der Stadt Athen als Tribut dem Zwitterwesen Minotaurus geopfert wurden. Dies jedenfalls, bis sich Theseus, der Sohn des Königs von Athen, unter die Opfer mischte, um den Minotaurus zu bezwingen. Was aber wäre aus dem Helden geworden. hätte sich nicht Ariadne, die Tochter des Minos, in ihn verliebt und ihn mit der Idee, den Weg aus dem Labyrinth mit Hilfe eines Fadens zu finden, gerettet. Wahrscheinlich hätte er. mit heutigen Worten gesagt, als hirnloser Macho dagestanden, der zwar mutig und stark genug war, das Untier zu besiegen, aber zu dumm, um aus dem Labyrinth zu finden. Was liegt also näher, als ein Programm, das sich dieser Idee bedient, nach Ariadne zu benennen. Ohne Faden nur ein hirnloser Macho In unseren Tagen hat die Faszination der Labyrinthe dazu geführt, daß auch Computerprogramme immer wieder auf der Labyrinth-Idee basieren. Wer kennt nicht die Adventures, in denen man selbst der Held ist, der in verschlungenen Labyrinthen siegreich gegen alle Arten von Monstern besteht, aber letzten Endes nicht den Weg herausfindet, weil keine Programmiererin Ariadne da ist. die an ein Fadenknäuel gedacht hätte. Verlassen wir nun diese schillernde Weit der alten Griechen und CPC-Abcnteurer und beginnen ganz von vorn. So stoßen wir früher oder später auf die Erkenntnis, daß (auch wenn es uns manchmal so scheinen mag) die Labyrinthe in den Computern nicht von vornherein vorhanden sind, sondern erst durch Software generiert werden müssen. Wir müssen uns also erst das Problem schaffen, welches wir lösen wollen. Das Ziel soll nun ein Programm sein, das in der Lage ist, selbst solche Labyrinthe zu erzeugen und grafisch auf dem Bildschirm darzustellen. Und zwar so, daß das gesamte Labyrinth überschaubar ist und der Bildschirm voll ausgenutzt wird. Der Rechner soll, in Anlehnung an die Idee Ariadnes, systematisch nach dem Weg suchen. Eine zusätzliche Möglichkeit ist die Joysticksteuerung, mit deren Hilfe der Ausgang ebenfalls zu finden ist. Konkurrenz -Mensch gegen Computer Wie ist es nun möglich, ein solches Labyrinth durch den Computer aufzubauen? Die Grundstruktur eines Labyrinths besteht aus Mauern oder Trennwänden. Geht man davon aus, daß sich die Grundfläche eines realen Labyrinths in gleich große rechteckige Felder zerlegen läßt, so gibt es im wesentlichen zwei unterschiedliche Abbildungsmöglichkeiten. Die erste Möglichkeit besteht darin, in einer Matrix zu speichern, ob auf einem Feld ein Mauerteil steht oder ob es sich bei dem Feld um den Teil eines Wegs handelt. Bei der zweiten Abbildungsart wird von der physischen Raumausdehnung der Mauern abstrahiert. Mauern haben nur noch eine logische Dimension. Es wird gespeichert, ob von einem Feld zum Nachbarfeld gegangen werden kann oder nicht. Statt in zwei Matrizen zu speichern, ist dies auch in einer Matrix möglich. Dann wird für jedes Feld gespeichert, wo sich die Wände befinden. Dazu werden für jedes Feld 4 Bit benötigt: Bit 1 = oben, 2 = unten, 3 = links, 4 = rechts. Das Labyrinth in einer Matrix gespeichert Betrachtet man die grafische Darstellung von Labyrinthen auf dem Computer näher, so ist die kleinste Struktur ein Pixel. Es kann aber auch eine größere Struktur aus mehreren Pixeln, wie das Leerzeichen im Textbildschirm zur Darstellung eines Feldes, gewählt werden. Spätestens bei der grafischen Darstellung des Such Vorgangs wird bedeutsam. ob die Figur größer, kleiner oder gleich groß wie ein Feld ist. Dies entscheidet nämlich darüber, ob alle als zugänglich definierten Felder auch tatsächlich der Figur zugänglich sind oder diese, wie ein Nilpferd in der Tür, stcckenblciben kann. Ein Labyrinth kann zwar auf beide Arten dargestellt werden, für Transformationen zwischen graphischer und logischer Struktur ist jedoch die erste einfacher handhabbar und sollte deshalb verwendet werden. Außerdem soll die Figur die Größe eines Feldes, also die des kleinsten graphischen Elements, haben. Der Labyrinthaufbau erfolgt nun folgendermaßen: Ausgegangen wird von der Grundflächenstruktur, der Art der Wandelemente und der Dimension der Figur. Die Wandelemente liegen allerdings noch auf “Stapel“. Das Problem besteht nun darin, die Wandelemente anzuordnen. Häufig wird bei Programmen ein Labyrinth quasi per Hand konstruiert, die Daten werden abgespeichert, und durch Einlesen in die verwendete Datenstruktur wird das Labyrinth auf dem Rechner erzeugt. Eine weitere Möglichkeit ist die Erzeugung per Zufallsgenerator, um damit bei jedem Programmlauf neue Labyrinthe darzustellen. Das bedeutet, daß Der Computer erzeugt das Labyrinth Aufgrund dieser Beobachtungen lassen sich Idealeigenschaften formulieren, die ein Labyrinth erfüllen sollte. Erstens wird die Passierbarkeit des Labyrinths verlangt, was bedeutet, daß der Ausgang vom Eingang her erreichbar ist, es darf aber Einschlüsse geben. Zweitens soll der Weg überall nur so breit sein, daß er gerade passierbar ist, damit das Labyrinth nicht zu einfach wird. Ein solches Labyrinth wird erzeugt, wenn — solange dies möglich ist - auf einem zufällig ausgewählten Feld ein Wandelement nur aulgestellt wird, wenn es höchstens an einer Stelle eine bereits bestehende Wand berührt. An dieses Element wird nun in einer der vier zulässigen Richtungen zufällig ein Wandelemente angefügt und so weiter, bis die Wand an eine schon bestehende Wand anstößt. Wie ist nun das 1-kByte-Programm aufgebaut? Eine feste Labyrinthstruktur ist nicht geeignet, weil die gesamten Daten gespeichert werden müßten, was zuviel Speicherplatz verbraucht. Unstrukturierte Generierung mit einem Zufallsgenerator liefert nur unbefriedigende Ergebnisse, und der geschilderte ideale Algorithmus ist für die geforderte Zielsetzung zu aufwendig. Welche Möglichkeit bleibt dann noch? Die verwendeten Zeichen müssen genau aufeinander abgestimmt sein. Dies gelingt mit einer Kombinationen aus drei bestimmten Zeichen, wobei Idealeigenschaft zwei erfüllt und Eigenschaft eins ausreichend erfüllt wird. Mit diesen drei Zeichen ist es nun möglich, eine riesige Menge verschiedenster Labyrinthe zu erzeugen. Im Mode 1 ergibt sich eine gute Ausgewogenheit zwischen Gesamtgröße des Labyrinths und der Breite von Mauern und Wegen. Das kleinste grafische Element (Feld) hat hier die Größe von 44 = 16 Pixeln. Da der Gesamtbildschirm aus 640400 = 256000 Pixeln besteht, hat das Labyrinth die Größe 160100 = 16000 = 256000 / 16 Felder. Mit Hilfe des Befehls TEST (x,y) ist es möglich, direkt auf die graphische Struktur zuzugreifen und festzustellen, ob ein Feld belegt ist oder nicht. So kann mit Hilfe des Joysticks eine Figur von der Größe eines Feldes durch das Labyrinth gesteuert werden. Nun mußte aber exakt festgelegt werden, wo Start und Ziel beim Labyrinth liegen sollten. Im Unterschied zum gänzlich konstruierten einerseits und dem algorithmisch generierten, idealen Labyrinth andererseits war die Eigenschaft der Zugänglichkeit und damit Passierbarkeit hier nicht garantiert. Die äußere Umrandung war eine Ursache für unzugängliche Teile. Daher war cs besser, an zwei gegenüberliegenden Seiten auf den Rand zu verzichten und statt der Zielsetzung, vom festgelegten Eingang zum festgelegten Ausgang zu gelangen, einfach das Labyrinth von einer Seite zur anderen zu durchqueren. Vom Eingang zum Ausgang Nun also ist unser Problem eindeutig beschrieben und auf dem Rechner präsent. Auch die manuell gesteuerte Suche nach einem Weg ist bereits mit dem Joystick möglich, und es wurde nicht mehr als ein Kilobyte BASIC-Text benötigt. Was noch fehlt, ist ein Lösungsverfahren, welches den CPC zu einem ernstzunehmenden Gegner werden läßt. Jedesmal, wenn ein Weg nicht weiterführt, müssen alle Schritte bis zu der letzten Verzweigung, an der alle anderen möglichen Abzweigungen noch nicht versucht worden sind, rückgängig gemacht werden. Wie Theseus an Ariadnes Faden sucht sich das Programm den Weg zurück, wenn ein Versuch fehlschlägt. Was ist einfacher, als den Weg durch das Paar der Positionswerte in zwei Arrays zu speichern, und wenn es nicht mehr weitergeht, den Faden entsprechend zurückzugehen. Dabei wird der Faden genau wie bei Theseus soweit wie nötig wieder aufgewickelt und der falsche Weg markiert, um nicht unnötigerweise mehrmals einen falschen Weg zu probieren. Wie wir von Hänsel und Gretel aus Grimms Märchen wissen, sind Steine oder Brotkrumen geeignete, wenn auch unzuverlässige Hilfsmittel, dies zu tun. Bei genauerer Überlegung haben Hänsel und Gretel jedoch das gleiche Problem wie Theseus. Sie wollen lediglich einen einmal gegangenen Weg zurückgehen. Von der Zielsetzung her heißt das, den Eingang auch wieder als Ausgang zu benutzen. Die gestreuten Steine haben also die gleiche Funktion wie der Faden. Wir hingegen stehen vor dem komplizierteren Problem, einen unbekannten Ausgang finden zu müssen. Nur wenn es nicht weitergeht, wollen wir zurückgehen, sonst jedoch auf unbekannten Pfaden wandeln. Wir nutzen die Steine daher zum entgegengesetzten Zweck, nämlich die Wege zu kennzeichnen, die nicht wieder gegangen werden sollen. Es wäre nun möglich, den Computer Steine, symbolisiert durch Punkte, in das Labyrinth, das auf dem Bildschirm dargestellt ist, streuen zu lassen. Dies hätte jedoch den Nachteil, daß sich der Bildschirm in ein Schotterfeld verwandeln würde und die Spielfigur, die wir steuern, dauernd über diese Steine stolperte. Zudem ist da auch noch der Faden, den die Figur des Rechners hinter sich herschleppt und der eine Verwicklungsgefahr in sich birgt. Wir fertigen deshalb eine Kopie des Labyrinths für den Rechner an, in der er nach Herzenslust mit Fäden und Steinen um sich werfen kann. Nachdem das Labyrinth grafisch erzeugt worden ist, muß es deshalb in eine logische Struktur transformiert werden. Wie erläutert, wird dazu eine Matrix benutzt. Die Figur des Rechners sucht daher nicht, wie es scheint, in demselben Labyrinth wie wir, sondern in einer Kopie. Entgegen der möglichen Vermutung hat der Rechner auch nicht von vornherein Überblick über das Gesamtlabyrinth, sondern muß mühsam, wie eine Maus im Laborversuch, den Weg suchen, ohne über die Wände schauen zu können. Wie eine Maus im Labor Obwohl die Daten des Labyrinths (sogar doppelt) vorhanden sind, bedeutet dies nicht, daß sie auch von Beginn an als Information verfügbar sind. Nur zu unserer Information wird die Figur des Rechners im Labyrinth permanent auf dem Bildschirm dargestellt. Aus diesem Grund kann auch nur unsere Figur der Figur des Rechners begegnen und nicht umgekehrt . Während unsere Figur nicht in der Lage ist. über die Figur des Rechners zu klettern, ist unsere Figur in der Kopie des Labyrinths nicht existent und folglich auch kein Hindernis. Da die Figur des Rechners (solange das Ziel nicht erreicht ist) ohnehin ständig in Bewegung ist, versperrt sie uns aber niemals wirklich den Weg. Wir haben somit außerdem Überblick über das Gesamtlabyrinth den weiteren Vorteil, beobachten zu können, was die Figur des Rechners macht. Wir können Begegnungen sozusagen nutzen, um nach dem Weg zu fragen. Zum Beispiel, wenn wir der oft schnelleren Figur des Rechners folgen und diese sich plötzlich auf dem Rückweg befindet, können wir oft erkennen, daß die weitere Suche zwecklos ist und ebenfalls umkehren. Die Figur verrät unbeabsichtigt, daß wir auf dem Holzweg sind. Da das Fogramm mit Absicht so klein gehalten wurde, ist es natürlich stark erweiterungsfähig. Aberdas überlassen wir nun Ihrer Phantasie. Ralf Grafe/jg , CPCAI |
|  |
|
Page créée en 418 millisecondes et consultée 876 fois L'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko. |
