HaDes XP - PacMan

Überblick

Das Ziel von PacMan: Überleben Sie lange genug, um das komplette Feld abgrasen zu können, ohne dabei von den gefährlichen Spinnenmonstern gefressen zu werden. Damit's nicht gar zu schwer wird, nehmen Sie unterwegs Kraftfutter auf, um die Monster besiegen zu können. Aber Vorsicht: die verschwinden nicht auf ewig...

Im Gegensatz zu Tetris ist unsere Version von PacMan kein einfacher Klon des klassischen Arcade-Spiels. Der wesentliche Unterschied ist, dass die Karte für jedes Spiel zufällig generiert wird, außerdem unterstützt unser PacMan einen kooperativen Zwei-Spieler-Modus.

Bedienung

Folgen Sie den Anweisungen, um das Spiel zu starten. Zur Steuerung der PacMan(s) verwenden Sie folgende Tasten: 

Im Einzelspieler-Modus wird nur Spieler 1 verwendet. 

Gehen Sie die Gänge ab und sammeln Sie alle Punkte auf. Berühren Sie dabei nicht die Spinnen, dies führt zum sofortigen Verlust eines Lebens und Rücktransport zum Startpunkt. Wenn Sie allerdings eine der gelbroten Pillen aufgesammelt haben (oder gerade getötet wurden), sind Sie rot und unbesiegbar und können selbst die Spinnen fressen (gibt viele Punkte). Sobald der rote Balken in der Statusanzeige abgelaufen ist, sind Sie wieder bedroht. 

Tip: Soundausgabe ist für den ultimativen Spielgenuß von PacMan unverzichtbar.

Implementierung

Alle Informationen über sowohl die menschlichen Spieler als auch die Computergegner werden in der Datenstruktur record Player gespeichert. Diese ist in pdecl.hl deklariert, und es existiert ein globales, statisches Spieler-Array var players[MAX_PLAYERS]; das alle diese Daten enthält.

Das Level wird zur Laufzeit in einem dynamisch alloziierten Array background gehalten. Es ist als Folge von Tilenummern von links oben nach rechts unten abgelegt. Jedes Tile ist 8x8 Pixel groß und kann leer sein (FIELD_EMPTY), einen Punkt (FIELD_POINT), eine Pille (FIELD_PILL) oder eine Mauer (>= FIELD_WALL) enthalten. (Es existieren mehrere verschiedene Mauertiles, um die Anzeige zu verschönern.) Zu beachten ist, dass die Spieler damit stets mindestens 9 Tiles belegen. Entsprechend müssen vor einer Richtungsänderung stets sichergestellt werden, dass drei Felder in der neuen Richtung frei sind (is_legal_action).

Zur Laufzeit des Spiels werden beim Auftreten von Timer-Ereignissen, also alle speed Millisekunden (on_move_timer), alle Spieler bewegt und gegebenenfalls ihre Richtung geändert, wenn sie bereits einen Richtungsänderungswunsch durch Tastendruck angekündigt hatten (player.nextAction). Wie für PacMan typisch, kann damit die Richtungstaste bereits weit vor einer Abzweigung gedrückt werden. 

Computerspieler erhalten immer, bevor sie eine mögliche Abzweigung erreichen, die Möglichkeit, sich eine neue Wunschrichtung auszudenken. Dies wird in der Funktion ad_next_action und deren Subfunktionen ausgeführt (pad.hl). AD steht dafür für Artificial Dumbness, denn gegen vier Spieler mit  Artificial Intelligence hätte ja der einzelne menschliche Spieler keinerlei Chancen... Demenstsprechend ist die Computerstrategie sehr simpel. Aus allen möglichen Strategien (Teilmenge von "gehe nach oben/links/rechts/unten") wird eine zufällig ausgewählt. Dabei haben die Strategien eine höhere Auswahlwahrscheinlichkeit, die in die Richtung des besiegbaren Spielers zielen bzw. vom unbesiegbaren Spieler weg. Dabei werden nur die X- und Y-Koordinaten des Computer- bzw. menschlichen Spielers verglichen; es wird keine Untersuchung vorgenommen, ob überhaupt in dieser Richtung ein Weg zum Spieler hinführt. 

Der aufwändigste Algorithmus in PacMan ist der zur Generierung eines Levels. Er ist in pmaze.hl implementiert. Es wird wie folgt vorgegangen: 

• Zunächst wird ein Maze-Objekt erzeugt (maze_alloc), das zu jedem Feld des Labyrinths (entspricht später 4x4 Tiles!) die Information enthält, ob eine Wand rechts bzw. unterhalb des Feldes vorhanden ist. 
• Das Labyrinth wird zufällig mit Wänden gefüllt (maze_gen_rand). 
• Nun wird sichergestellt, dass alle Felder von überall erreichbar sind. Dies geschieht in maze_fill durch die wiederholte Anwendung eines Flood-Fill-Algorithmus: 
  • in einer Schleife werden jeweils alle Felder, die an erreichbare Felder anschließen, mit "erreichbar (STAT_REACH)" oder "unerreichbar (STAT_BLOCKED)" markiert.  
  • Sobald in einem Durchlauf keine neuen Felder mehr markiert werden können, aber unerreichbare Felder vorhanden sind, wird ein zufällig ausgewähltes unerreichbares Feld zugänglich gemacht. Da es an ein erreichbares Feld anschließt, gelingt dies stets durch das Entfernen einer geeignet gewählten Wand (unblock). 
  • Sollten irgendwann einmal keine neuen Felder mehr markiert werden können und keine unerreichbaren Felder vorhanden sein, so ist das komplette Feld als erreichbar markiert und die Konstruktion ist abgeschlossen. 

Eine Debug-Ausgabe des Feldes auf dem Textschirm während des Algorithmus ist möglich (durch Kompilieren mit #define DEBUG).