Spielewelten mit Raycasting: Spielfeld

Das Spielfeld ist der zentrale Bereich unserer Spielewelt. Es besteht aus einer rechteckigen Anordnung von Feldern, etwa wie beim Schachbrett. Die Spielfigur ist vollständig umgeben von einer Mauer. Wir lernen, wie man einen einen einzelnen Strahl verfolgt, bis er auf eine Wand trifft um dann die Entfernung zur Wand zu bestimmen. Ebenfalls wird sich unsere Spielfigur am Ende des Kapitels im Spielfeld bewegen können, ohne mit dem Kopf an eine Mauer zu stoßen.

Wenn wir das Spielfeld geschaffen haben, ist es nur noch ein kurzer Weg zu einem Raum.

GrundbegriffeBearbeiten

  • Mauer, Wand: Das Spielfeld umgebender Bereich, auf den die Spielfigur nicht gehen kann. Wände können auch innerhalb des Spielfeldes den Raum unterteilen. Wände werden später im Raum besonders dargestellt.
  • Sehstrahl: Ein Strahl, der von der Spielfigur ausgeht und irgendwo im Raum eine Wand trifft.
  • Blickrichtung: Der Sehstrahl verläuft in Richtung der Blickrichtung, einem Winkel, in dem die Spielfigur blickt. 90° bedeutet hier nach oben zu schauen, bei 0° blickt sie nach rechts.

Datenstruktur SpielfeldBearbeiten

Als Datenstruktur für ein Spielfeld können wir eine Textdatei benutzen, die aus Zeilen der Spielewelt besteht. Das folgende Beispiel zeigt ein Spielfeld, das 10 Zeilen und 10 Spalten hat. Großbuchstaben stehen dabei für verschiedenen Wände, Punkte für freie Fläche und das Doppelkreuz für die Spielfigur. So haben wir noch Ziffern für feindliche Monster frei und können mit Kleinbuchstaben besondere Dinge wie Munitions- oder Verbandpäckchen im Spiel kennzeichnen.

Textdatei Spielfeld
NNNNNNNNNN
W........O
W........O
W..#.....O
W........O
W........O
W........O
W........O
W........O
SSSSSSSSSS
 
Ein 10*10 Kästchen großes Spielfeld

Das folgende Programm zeigt, wie man ein Spielfeld laden kann und eine grafische wie auch textuelle Ausgabe des Spielfeldes angezeigt bekommt. Sie können das Programm nutzen, um eigene Spielfelder zu testen. Bitte beachten Sie, dass alle Spielfeld-Zeilen die gleiche Länge haben müssen. Es darf nur eine Spielfigur vorkommen. Die Ausgabe dieses Programms entspricht dem in diesem Abschnitt gezeigten Bild, deswegen verzichten wir auf eine Ausgabe.

#!/usr/bin/python
# -*- coding: utf-8 -*-

import math
import pygame
import sys


class Spielfeld(object):

    def __init__(self, dateiname):
        self.felder = []
        datei = open(dateiname, 'r')
        # Datei zeilenweise einlesen
        for zeile in datei:
            if len(zeile) > 5:
                # Eine Zeile hinzufügen
                self.felder.append(zeile[:-1])
        datei.close()
        # Anzahl der Spalten einer Zeile
        self.breite = len(self.felder[0])
        # Anzahl der Zeilen
        self.hoehe = len(self.felder)
        # Spielfigur plazieren
        for num, zeile in enumerate(self.felder):
            idx = zeile.find('#')
            if idx >= 0:
                # x-, y- Koordinaten: Spalte, Zeile
                self.position = (idx, num)
                # Feld ist ein normaler Untergrund
                self.felder[num] = self.felder[num].replace('#', '.')
                break


    def zeichen(self, x, y):
        """Liefert das Zeichen an der Position x, y """
        assert(0 <= x < self.breite)
        assert(0 <= y < self.hoehe)
        return self.felder[y][x]


    def __str__(self):
        """Druckt das Spielfeld aus"""
        s = "Spielfeld, Breite=%2d Höhe=%2d  Position=%2d ; %2d\n" % \
            (self.breite, self.hoehe, self.position[0], self.position[1])
        for num, zeile in enumerate(self.felder):
            if num == self.position[1]:
                zeile = zeile[:self.position[0]] + 'P' + zeile[self.position[0]+1:]
            s+= zeile + '\n'
        return s



def init(breite, hoehe):
    screen = pygame.display.set_mode((breite, hoehe))
    screen.fill((200, 200, 200))
    pygame.display.update()
    return screen


def zeichneSpielfeld(screen, breite, hoehe, spielfeld):
    feldbreite = breite // spielfeld.breite
    feldhoehe = hoehe // spielfeld.hoehe
    for y in xrange(spielfeld.hoehe):
        for x in xrange(spielfeld.breite):
            zeichen = spielfeld.zeichen(x, y)
            rechteck = (x * feldbreite, y * feldhoehe, feldbreite, feldhoehe)
            if zeichen == '.':
                pygame.draw.rect(screen, (0, 0, 0), rechteck)
            elif zeichen == 'N':
                pygame.draw.rect(screen, (128, 0, 0), rechteck)
            elif zeichen == 'W':
                pygame.draw.rect(screen, (160, 43, 43), rechteck)
            elif zeichen == 'S':
                pygame.draw.rect(screen, (128, 128, 0), rechteck)
            elif zeichen == 'O':
                pygame.draw.rect(screen, (213, 85, 0), rechteck)
    # Spielfigur zeichnen
    pos = (spielfeld.position[0] * feldbreite + feldbreite // 2, spielfeld.position[1] * feldhoehe + feldhoehe // 2)
    pygame.draw.circle(screen, (255, 255, 255), pos, min(feldhoehe, feldbreite) // 3)
    # grid zeichnen
    for x in xrange(1, spielfeld.breite):
        start = (x * feldbreite, 0)
        ende = (start[0], hoehe - 1)
        pygame.draw.line(screen, (128, 128, 128), start, ende)
    for y in xrange(1, spielfeld.hoehe):
        start = (0, y * feldhoehe)
        ende = (breite - 1, start[1])
        pygame.draw.line(screen, (128, 128, 128), start, ende)
    pygame.display.update()


def hauptschleife():
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT or event.type == pygame.KEYDOWN:
                sys.exit()


if __name__ == '__main__':
    spielfeld = Spielfeld('spielfeld.txt')
    print spielfeld
    screen = init(500, 500)
    zeichneSpielfeld(screen, 500, 500, spielfeld)
    hauptschleife()

In diese Programm wurde die Spielfeld-Klasse vorbereitet. In der Methode __init__() wird das Spielfeld aus einer Textdatei geladen und die Position der Spielfigur bestimmt. Die Textdatei wird zeilenweise eingelesen, wobei das Newline-Zeichen nicht übernommen werden soll. Die Zeilen werden in einer Liste gespeichert, so können wir auf jede Zeile per Index zugreifen. Haben wir später die Position der Spielfigur bestimmt, ersetzen wir den das Zeichen durch ein einfaches Hintergrundzeichen. Wir können dann später die Spielfigur auf dem Spielfeld bewegen, ohne jedes Mal die Markierung in der Liste anpassen zu müssen.

Die Methode zeichen() liefert ein Zeichen an der angegebenen Position für Spalte und Zeile. Wir achten in dieser Methode darauf, dass der Index zur Zeilenzahl/Spaltenzahl passt.

In __str__() geben wir eine Textbeschreibung des Spielfeldes aus.

Die übrigen Funktionen befassen sich mit Details der Grafikumgebung. zeichneSpielfeld() stellt das Spielfeld grafisch dar. Es werden kleine Rechtecke an die passenden Stellen gemalt, je nach Zeichen an der Stelle im Spielfeld wird ein farbiges Rechteck in das Fenster gemalt. Die Spielfigur wird durch einen Kreis angedeutet. Hinterher zeichnen wir noch die Kästchenumrisse. Beachten Sie, dass zwei benachbarte Kästchen in horizontaler Richtung den Abstand feldbreite, und in vertikaler Richtung den Abstand feldhoehe haben.

Gehen auf dem SpielfeldBearbeiten

Wollen wir auf dem Spielfeld ein Stück entlang der Blickrichtung (u) gehen, bedeutet das, ein Stück waagerecht und ein Stück senkrecht zu gehen. Diese jeweiligen Stücke bezeichnen wir mit dx und dy, analog zu dem Ihnen schon bekannten Steigungsdreieck.

Hier gilt:

  •  
  •  

Wir müssen hier das Vorzeichen von dy umkehren, da unser Nullpunkt ja in der oberen linken Ecke liegt, nicht in der unteren wie sonst auf dem Papier.

Um das nächste Kästchen (qx;qy) ausgehend von unserer momentanen Position (px;py) zu erreichen zählen wir einfach (dx;dy) hinzu:

  •  
  •  

In Python sieht das so aus:

def geheVor(self):
    """gehe in Richtung der Blickrichtung """
    px, py = self.position
    qx = int(round(px + math.cos(math.radians(self.blickrichtung))))
    qy = int(round(py - math.sin(math.radians(self.blickrichtung))))
    zeichen = self.zeichen(qx, qy)
    if not self.istWand(zeichen):
        self.position = (qx, qy)

wobei die Methode istWand() herausfindet, ob die neue Position eine Wand ist. Wir müssen hier runden und anschließend die Zahl nach Integer umwandeln, damit wir gerade auf einem neuen Kästchen landen.

Wollen wir in die andere Richtung laufen, brauchen wir nur unsere Blickrichtung um 180° zu vergrößern, nach vorne gehen und die Blickrichtung wieder zu verkleinern:

def geheZurueck(self):
    """gehe entgegen der Blickrichtung """
    self.blickrichtung += 180
    self.geheVor()
    self.blickrichtung -= 180


Drehen kann man sich auf de Spielfeld, in dem man zur Blickrichtung einen Wert hinzuzählt oder abzieht:

def dreheLinks(self):
    self.blickrichtung = (self.blickrichtung + 5) % 360


Wo ist die Wand?Bearbeiten

In diesem Abschnitt geht es darum, von einer Spielfigur aus die Wand zu finden, und zwar entlang des Sehstrahls.


IrrwegBearbeiten

 
Wo ist die Wand?

Da wir ja nun schon wissen, wie man sich auf dem Spielfeld bewegt, liegt es nahe, das gleiche Verfahren zu nutzen, um die Mauer zu finden, die der Sehstrahl kreuzt. In der nebenstehenden Zeichnung sind die horizontalen und vertikalen Abschnitte eingezeichnet, die uns entlang des Sehstrahls zur Mauer führen. Auch hier gilt wieder:

  •   und
  •  

Wir brauchen also nichts weiter zu tun, als immer dem Sehstrahl zu folgen und bei jedem Schritt zur aktuellen Position einige Male dx und dy hinzuzufügen:

def findeWand(self):
    """findet eine Wand, ausgehend von der aktuellen Spielerposition unter dem winkel blickrichtung """
    dx = math.cos(math.radians(self.blickrichtung))
    dy = math.sin(math.radians(self.blickrichtung))
    px, py = self.position
    qx = px + dx
    qy = py - dy
    wand = ()
    while not wand:
        zeichen = self.zeichen(int(round(qx)), int(round(qy)))
        if self.istWand(zeichen):
            wand = (int(round(qx)), int(round(qy)))
        else:
            qx = qx + dx
            qy = qy - dy
    return wand


Leider ist das Verfahren nicht besonders gut. In vielen Fällen findet es die Wand an der richtigen Stelle, in vielen aber eben auch nicht. Das Verfahren ist zu grob, wie wir an den folgenden Bildern zeigen. Die Anwendung, der wir diese Ausschnittsbilder entnommen haben, stellen wir Ihnen gleich vor.

Auf den Bildern sehen sie im oberen Bereich die Wand. In weiß sehen Sie die Spielfigur, den Sehstrahl haben wir grün eingefärbt. Die mit dem Verfahren herausgefundene Wandposition haben wir mit einem blauen Kreis gekennzeichnet. Die jeweiligen Mitten zwischen der Spielfigur und der gefundenen Mauer haben wir gleich noch mit einer blauen Linie gekennzeichnet:

 
Ganz falsch, der Sehstrahl kreuzt ein Feld früher
 
Schon besser, aber leider nur Zufall


 
Anwendung: Mauer finden

Wir stellen Ihnen hier auch noch die Anwendung vor. Sie lädt ein Spielfeld, zeichnet konstant die gefundene Mauer ein und stellt den Sehstrahl in grün dar. Sie können mit den Cursortasten entlang des Sehstrahls wandern. Um das Programm zu beenden, klicken Sie bitte auf den Schließen-Knopf in der Titelleiste. Dieses Programm werden wir in den folgenden Abschnitten wiederverwenden.

#!/usr/bin/python
# -*- coding: utf-8 -*-

import math
import pygame
import sys


class Spielfeld(object):

    def __init__(self, dateiname):
        self.felder = []
        # Blickrichtung als Winkel in Grad
        self.blickrichtung = 90
        # Datei einlesen
        datei = open(dateiname, 'r')
        for zeile in datei:
            self.felder.append(zeile[:-1])
        datei.close()
        self.breite = len(self.felder[0])
        self.hoehe = len(self.felder)
        for num, zeile in enumerate(self.felder):
            idx = zeile.find('#')
            if idx >= 0:
                self.position = (idx, num)
                self.felder[num] = self.felder[num].replace('#', '.')
                break


    def zeichen(self, x, y):
        """Liefert das Zeichen an der Position x, y """
        assert(0 <= x < self.breite)
        assert(0 <= y < self.hoehe)
        return self.felder[y][x]


    def istWand(self, zeichen):
        """True, wenn das Zeichen ein Wandzeichen ist """
        return zeichen in ('N', 'W', 'S', 'O')


    def geheVor(self):
        """gehe in Richtung der Blickrichtung """
        px, py = self.position
        qx = int(round(px + math.cos(math.radians(self.blickrichtung))))
        qy = int(round(py - math.sin(math.radians(self.blickrichtung))))
        zeichen = self.zeichen(qx, qy)
        if not self.istWand(zeichen): 
            self.position = (qx, qy)  


    def geheZurueck(self):
        """gehe entgegen der Blickrichtung """
        self.blickrichtung += 180
        self.geheVor()
        self.blickrichtung -= 180


    def dreheLinks(self):
        self.blickrichtung = (self.blickrichtung + 5) % 360


    def dreheRechts(self):
        self.blickrichtung = (self.blickrichtung - 5) % 360
                                                            

    def findeWand(self):
        """findet eine Wand, ausgehend von der aktuellen
          Spielerposition unter dem winkel blickrichtung """
        dx = math.cos(math.radians(self.blickrichtung))
        dy = math.sin(math.radians(self.blickrichtung))
        px, py = self.position
        qx = px + dx
        qy = py - dy
        wand = ()
        while not wand:
            zeichen = self.zeichen(int(round(qx)), int(round(qy)))
            if self.istWand(zeichen):
                wand = (int(round(qx)), int(round(qy)))
            else:
                qx = qx + dx
                qy = qy - dy
        return wand
        



def init(breite, hoehe):
    screen = pygame.display.set_mode((breite, hoehe))
    screen.fill((200, 200, 200))
    pygame.display.update()
    return screen


def zeichneSpielfeld(screen, breite, hoehe, spielfeld, wandpos):
    feldbreite = breite // spielfeld.breite
    feldhoehe = hoehe // spielfeld.hoehe
    for y in xrange(spielfeld.hoehe):
        for x in xrange(spielfeld.breite):
            zeichen = spielfeld.zeichen(x, y)
            rechteck = (x * feldbreite, y * feldhoehe, feldbreite, feldhoehe)
            if zeichen == '.':
                pygame.draw.rect(screen, (0, 0, 0), rechteck)
            elif zeichen == 'N':
                pygame.draw.rect(screen, (128, 0, 0), rechteck)
            elif zeichen == 'W':
                pygame.draw.rect(screen, (160, 43, 43), rechteck)
            elif zeichen == 'S':
                pygame.draw.rect(screen, (128, 128, 0), rechteck)
            elif zeichen == 'O':
                pygame.draw.rect(screen, (213, 85, 0), rechteck)
    # Spielfigur zeichnen
    pos = (spielfeld.position[0] * feldbreite + feldbreite // 2, spielfeld.position[1] * feldhoehe + feldhoehe // 2)
    pygame.draw.circle(screen, (255, 255, 255), pos, min(feldhoehe, feldbreite) // 3)
    # grid zeichnen
    for x in xrange(1, spielfeld.breite):
        start = (x * feldbreite, 0)
        ende = (start[0], hoehe - 1)
        pygame.draw.line(screen, (128, 128, 128), start, ende)
    for y in xrange(1, spielfeld.hoehe):
        start = (0, y * feldhoehe)
        ende = (breite - 1, start[1])
        pygame.draw.line(screen, (128, 128, 128), start, ende)
    # Blickrichtung zeichnen
    qx = int(pos[0] + 2 * feldbreite * math.cos(math.radians(spielfeld.blickrichtung)))
    qy = int(pos[1] - 2 * feldbreite * math.sin(math.radians(spielfeld.blickrichtung)))
    pygame.draw.line(screen, (0, 255, 0), pos, (qx, qy))
    # gefundene Wand zeichnen
    wx, wy = wandpos
    wx = wx * feldbreite + feldbreite // 2
    wy = wy * feldhoehe + feldhoehe // 2
    pygame.draw.line(screen, (0, 0, 255), pos, (wx, wy))
    pygame.draw.circle(screen, (0, 0, 255), (wx, wy), min(feldhoehe, feldbreite) // 3)
    pygame.display.update()


def hauptschleife(spielfeld, screen, breite, hoehe):
    wand = spielfeld.findeWand()
    zeichneSpielfeld(screen, breite, hoehe, spielfeld, wand)
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                sys.exit()
            elif event.type == pygame.KEYDOWN:
                if event.key == pygame.K_UP:
                    spielfeld.geheVor()
                elif event.key == pygame.K_DOWN:
                    spielfeld.geheZurueck()
                elif event.key == pygame.K_LEFT:
                    spielfeld.dreheLinks()
                elif event.key == pygame.K_RIGHT:
                    spielfeld.dreheRechts()
                wand = spielfeld.findeWand()
                zeichneSpielfeld(screen, breite, hoehe, spielfeld, wand)


if __name__ == '__main__':
    spielfeld = Spielfeld('spielfeld.txt')
    screen = init(500, 500)
    hauptschleife(spielfeld, screen, 500, 500)


In diesem Programm habe wir die Methoden eingefügt, die es unserer Spielfigur ermöglichen, sich über das Spielfeld zu bewegen sowie die Methode findeWand(), die wir weiter oben besprochen haben.

Die Funktion zeichneSpielfeld() hat einen weiteren Parameter bekommen. Wir können mit dieser Funktion also nun das gefundenen Wandelement mit einem blauen Kreis versehen, die Blickrichtung und auch eine gedachte Linie zwischen der Spielfigur und der Wandmitte einzeichnen.

Unsere Hauptschleife (hauptschleife()) kennt nun ebenfalls das Spielfeld wie auch die Breite und Höhe des Spielfeldes. Das brauchen wir, da wir innerhalb der Hauptschleife die Spielfigur bewegen wollen und zu passenden Gelegenheiten das Spielfeld neu zeichnen, nämlich immer dann, wenn eine Taste gedrückt wurde und dadurch die Spielfigur möglicherweise bewegt wurde. Natürlich müssen wir das nur, wenn die Spielfigur wirklich bewegt wurde.

Verbesserte WandsucheBearbeiten

Die verbesserte Variante, um die Mauer in Blickrichtung zu suchen besteht darin, horizontale und vertikale Schnittpunkte mit den Mauern zu finden. Diese werden aber getrennt behandelt. Wir unterscheiden, weil es die Sache einfacher macht, ob die Blickrichtung horizontal/vertikal oder diagonal ist.

Fall 1: Horizontal/VertikalBearbeiten

 
Für Winkel von 0°, 90°, 180° und 270° ist alles ganz einfach

Für Winkel von 0°, 90°, 180° und 270° sind hier in grün die entsprechenden Blickrichtungen eingezeichnet. Die grünen Punkte sind horizontale, die pinkfarbenen vertikale Schnittpunkte, weil die Mauern mit denen geschnitten wird, senkrecht laufen.

Um vom Punkt P unter dem Blickwinkel 0° den ersten pinkfarbenen Schnittpunkt zu finden, geht man ein halbes Kästchen nach rechts. Die Y-Position bleibt erhalten. Der nächste Schnittpunkt ist genau ein Kästchen rechts entfernt.

Unter dem Blickwinkel 90° findet man den ersten grünen Schnittpunkt, in dem man ein halbes Kästchen nach oben geht. Jeden weiteren Schnittpunkt findet man, in dem man ein Kästchen nach oben geht. Hierbei bleibt die X-Position erhalten.

Wo auch immer sich hier eine Mauer befindet, wir finden sie in gerader Linie vom Punkt P aus.

In der Praxis kann man es sich bei diesen Sonderfällen einfach machen. Man sucht im Fall 0° einfach in den rechts daneben liegenden Kästchen nach einer Wand und im Fall 90° in den darüber liegenden. Das folgende Beispiel demonstriert die Suche nach Mauern in horizontaler und vertikaler Richtung. Wir haben die Variable wand mit wand = (0, 0) initialisiert, damit Sie mit diesem Spezialfall direkt die oben geschriebene gleichlautende Methode ersetzen können.

def findeWand(self):
    wand = (0, 0)
    px, py = self.position
    # vertikal
    if self.blickrichtung == 0:
        xpos = px + 1
        zeichen = self.zeichen(xpos, py)
        while not self.istWand(zeichen):
            xpos = xpos + 1
            zeichen = self.zeichen(xpos, py)
        wand = (xpos, py)
    elif self.blickrichtung == 180:
        xpos = px - 1
        zeichen = self.zeichen(xpos, py)
        while not self.istWand(zeichen):
            xpos = xpos - 1
            zeichen = self.zeichen(xpos, py)
        wand = (xpos, py)
    # horizontal
    elif self.blickrichtung == 90:
        ypos = py - 1
        zeichen = self.zeichen(px, ypos)
        while not self.istWand(zeichen):
            ypos = ypos - 1
            zeichen = self.zeichen(px, ypos)
        wand = (px, ypos)
    elif self.blickrichtung == 270:
        ypos = py + 1
        zeichen = self.zeichen(px, ypos)
        while not self.istWand(zeichen):
            ypos = ypos + 1
            zeichen = self.zeichen(px, ypos)
        wand = (px, ypos)
    return wand


Fall 2: DiagonalBearbeiten

 
Beispiel: Winkel von 50°

Die beiden Fälle haben wir in dieser Tabelle zusammengestellt. Dies soll es erleichtern, Unterscheide bei der Behandlung von horizontalen und vertikalen Wänden bei diagonalen Blickrichtungen aufzuspüren. Letztlich ist es unser Ziel, beide Fälle gemeinsam zu untersuchen.

findeWandDiagH() deckt hierbei die grünen Punkte in der Zeichnung ab, findeWandDiagV() die pinkfarbenen. In beiden Fällen laufen wir ein halbes Kästchen in eine Richtung und berechnen uns die Entfernung der anderen Richtung mit Hilfe vom Tangens des Blickwinkels.

Je nachdem, in welche Richtung unser Spieler blickt, müssen wir die Vorzeichen korrigieren. Außerdem haben wir immer darauf zu achten, ob nicht das nächste zu testende Kästchen außerhalb vom Spielfeld liegt. Der Tangens kann nämlich in der Gegend von 90° und 270° sehr groß oder sehr klein und in der Gegend von 0° und 180° nahezu 0 sein.

Wenn Sie diese Methoden in findeWand() aufrufen, kann es wegen dieser Eigenschaften vom Tangens bei Vielfachen von 90° zum Absturz des Programmes kommen. Achten Sie also darauf, genau diese Winkel nicht zu wählen.


Horizontal (grün) Vertikal (pinkfarben)
def findeWandDiagH(self):
    wand = (0, 0)
    px, py = self.position
    px += 0.5
    py += 0.5
    tangens = math.tan(math.radians(self.blickrichtung))
    dy = 0.5
    dx = dy / tangens
    # Vorzeichen
    if self.blickrichtung > 0 and self.blickrichtung < 90:
        dy = -dy
    elif self.blickrichtung > 90 and self.blickrichtung < 180:
        dy = -dy
    elif self.blickrichtung > 180 and self.blickrichtung < 270:
        dx = -dx
    elif self.blickrichtung > 270 and self.blickrichtung < 360:
        dx = -dx
    xpos = px + dx
    ypos = py + dy
    if xpos < 0 or ypos < 0 or xpos >= self.breite or ypos >= self.hoehe:
        return wand
    zeichen = self.zeichen(int(xpos), int(ypos))
    if self.istWand(zeichen):
        wand = (int(xpos), int(ypos))
    else:
        dx = 2.0 * dx
        dy = 2.0 * dy
        xpos = xpos + dx
        ypos = ypos + dy
        if xpos < 0 or ypos < 0 or xpos >= self.breite or ypos >= self.hoehe:
            return wand
        zeichen = self.zeichen(int(xpos), int(ypos))
        while not self.istWand(zeichen):
            xpos = xpos + dx
            ypos = ypos + dy
            if xpos < 0 or ypos < 0 or xpos >= self.breite or ypos >= self.hoehe:
                return wand
            zeichen = self.zeichen(int(xpos), int(ypos))
        wand = (int(xpos), int(ypos))
    return wand
def findeWandDiagV(self):
    wand = (0, 0)
    px, py = self.position
    px += 0.5
    py += 0.5
    tangens = math.tan(math.radians(self.blickrichtung))
    dx = 0.5
    dy = tangens * dx
    # Vorzeichen
    if self.blickrichtung > 0 and self.blickrichtung < 90:
        dy = -dy
    elif self.blickrichtung > 90 and self.blickrichtung < 180:
        dx = -dx
    elif self.blickrichtung > 180 and self.blickrichtung < 270:
        dx = -dx
    elif self.blickrichtung > 270 and self.blickrichtung < 360:
        dy = -dy
    xpos = px + dx
    ypos = py + dy
    if xpos < 0 or ypos < 0 or xpos >= self.breite or ypos >= self.hoehe:
        return wand
    zeichen = self.zeichen(int(xpos), int(ypos))
    if self.istWand(zeichen):
        wand = (int(xpos), int(ypos))
    else:
        dx = 2.0 * dx
        dy = 2.0 * dy
        xpos = xpos + dx
        ypos = ypos + dy
        if xpos < 0 or ypos < 0 or xpos >= self.breite or ypos >= self.hoehe:
            return wand
        zeichen = self.zeichen(int(xpos), int(ypos))
        while not self.istWand(zeichen):
            xpos = xpos + dx
            ypos = ypos + dy
            if xpos < 0 or ypos < 0 or xpos >= self.breite or ypos >= self.hoehe:
                return wand
            zeichen = self.zeichen(int(xpos), int(ypos))
        wand = (int(xpos), int(ypos))
    return wand

Wie erläutern kurz die Funktionsweise von findeWandDiagV(): Das Paar dx, dy entspricht Abständen in horizontaler/vertikaler Richtung, bildet also mit dem Sehstrahl Steigungsdreiecke. Zuerst wird die horizontale Richtung mit einem halben Kästchen vorgegeben. Anschließend wird die vertikale Richtung bestimmt. Abhängig von der Blickrichtung werden Vorzeichenkorrekturen vorgenommen. Nun wird zur Ausgangsposition der Spielfigur das Steigungsdreieck hinzuaddiert (xpos = px + dx, selbiges für y) und wir testen, ob wir auf eine Wand treffen. Wenn nicht, können wir das Steigungsdreieck einmal vergrößern (dx = 2.0 * dx, selbiges für y), so dass wir nun ein ganzes Kästchen in horizontaler Richtung abdecken. Nun addieren wir so lange zur aktuellen Suchposition das Steigungsdreieck hinzu, bis wir auf eine Wand treffen. Diese Wandposition wird dann übergeben. In einigen Fällen findet die Methode keine Wand. In diesem Fall wird (0, 0) als Wand übergeben.

Gute WandsucheBearbeiten

Von einer guten Wandsuche erwarten wir, dass sie uns zuverlässig die Wand findet und die Entfernung zur Wand berechnen kann. Da wir in den obigen Methoden Bereiche gefunden haben, die sich sehr ähneln, können wir Teile in eigene Methoden auslagern.

Die Logik, wann welche Wandsuche -horizontal/vertikal oder diagonal- benutzt wird, ist ein eigener Bereich. Hier wird abhängig vom Winkel die passende Wandsuche aufgerufen, wobei Parameter vorbereitet werden. Für alle Winkel, die Vielfache von 90° sind, wird findeWandHV() aufgerufen, wobei diese Methode Position und Suchrichtung als Parameter mitbekommt. Für alle Bereiche, in denen diagonal gesucht werden muss, wird findeWandDiagonal() zweifach aufgerufen und das Minimum der Entfernung zur Wand berücksichtig. einmal geht es um die horizontalen und einmal um die vertikalen Schnittpunkte.

Beachten Sie bitte, dass die Wand nun aus drei Teilen besteht, nämlich zwei Ortsangaben (x- und y-Koordinate) und einer Entfernungsangabe.

def findeWand(self):
    px, py = self.position
    wand = (0, 0, 0.0)
    tangens = math.tan(math.radians(self.blickrichtung))
    if self.blickrichtung == 0:
        wand = self.findeWandHV(px, py, 1, 0)
    elif self.blickrichtung > 0 and self.blickrichtung < 90:
        dx = 0.501
        dy = -tangens * dx
        wand1 = self.findeWandDiagonal(px, py, dx, dy)
        dy = -0.501
        dx = -dy / tangens
        wand2 = self.findeWandDiagonal(px, py, dx, dy)
        if wand1[2] < wand2[2]:
            wand = wand1
        else:
            wand = wand2
    elif self.blickrichtung == 90:
        wand = self.findeWandHV(px, py, 0, -1)
    elif self.blickrichtung > 90 and self.blickrichtung < 180:
        dx = -0.501
        dy = -tangens * dx
        wand1 = self.findeWandDiagonal(px, py, dx, dy)
        dy = -0.501
        dx = -dy / tangens
        wand2 = self.findeWandDiagonal(px, py, dx, dy)
        if wand1[2] < wand2[2]:
            wand = wand1
        else:
            wand = wand2
    elif self.blickrichtung == 180:
        wand = self.findeWandHV(px, py, -1, 0)
    elif self.blickrichtung > 180 and self.blickrichtung < 270:
        dx = -0.501
        dy = -tangens * dx
        wand1 = self.findeWandDiagonal(px, py, dx, dy)
        dy = 0.501
        dx = -dy / tangens
        wand2 = self.findeWandDiagonal(px, py, dx, dy)
        if wand1[2] < wand2[2]:
            wand = wand1
        else:
            wand = wand2
    elif self.blickrichtung == 270:
        wand = self.findeWandHV(px, py, 0, 1)
    elif self.blickrichtung > 270 and self.blickrichtung < 360:
        dx = 0.501
        dy = -tangens * dx
        wand1 = self.findeWandDiagonal(px, py, dx, dy)
        dy = 0.501
        dx = -dy / tangens
        wand2 = self.findeWandDiagonal(px, py, dx, dy)
        if wand1[2] < wand2[2]:
            wand = wand1
        else:
            wand = wand2
    return wand

Es lassen sich in dieser Methode noch Bereiche zur Quellcodeoptimierung finden, das überlassen wir Ihnen als Übung. Wichtig ist uns, dass Sie den Quelltext verstehen.

Wir stellen Ihnen hier die Methode findeWandHV() vor. Als Richtungsargumente kommen bei der horizontalen/vertikalen Suche nur 1 oder 0 vor, wir brauchen uns hier also nur darum zu kümmern, dass wir in die richtige Richtung laufen bis wir auf eine Wand treffen. Da entweder dx oder dy Null ist, können wir bei der Berechnung der Entfernung die Summe in beide Richtungen berechnen. Ein Teil ist 0 und fällt damit weg. Wir ziehen von der Entfernung 0,5 ab, da wir ja auf der Mitte des Feldes stehen:

def findeWandHV(self, px, py, dx, dy):
    """Findet eine Wand in ausschließlich horizontaler und vertikaler Richtung.
    (px, py) ist die Feldkoordinate des Spielers,
    (dx, dy) ist die Schrittweite, die wir bei jeder Iteration gehen"""
    FeldXpos = px + dx
    FeldYpos = py + dy
    zeichen = self.zeichen(FeldXpos, FeldYpos)
    while not self.istWand(zeichen):
        # untersuche nächstes Feld
        FeldXpos = FeldXpos + dx
        FeldYpos = FeldYpos + dy
        zeichen = self.zeichen(FeldXpos, FeldYpos)
    entfernung = (dx * (FeldXpos - px) + dy * (FeldYpos - py)) - 0.5
    wand = (FeldXpos, FeldYpos, entfernung)
    return wand

Die Methode findeWandDiagonal() ist ganz ähnlich aufgebaut und enthält lediglich andere Variablen. Die Entfernungsbestimmung passiert mit dem Satz des Pythagoras, nachdem der Schnittpunkt mit der Wand bestimmt wurde.

def findeWandDiagonal(self, px, py, dx, dy):
    """Findet eine Wand in diagonaler Richtung.
    (px, py) ist die Feldkoordinate des Spielers,
    (dx, dy) ist die Schrittweite, die wir bei jeder Iteration gehen"""
    mitteX = px + 0.5
    mitteY = py + 0.5
    schnittpunktX = mitteX + dx
    schnittpunktY = mitteY + dy
    # nächste Schrittweite
    dx = dx * 2.0
    dy = dy * 2.0
    FeldXpos = int(schnittpunktX)
    FeldYpos = int(schnittpunktY)
    if 0 < FeldXpos < self.breite and 0 < FeldYpos < self.hoehe:
        zeichen = self.zeichen(int(FeldXpos), int(FeldYpos))
        while not self.istWand(zeichen):
            schnittpunktX = schnittpunktX + dx
            schnittpunktY = schnittpunktY + dy
            FeldXpos = int(schnittpunktX)
            FeldYpos = int(schnittpunktY)
            if not (0 < FeldXpos < self.breite and 0 < FeldYpos < self.hoehe): break
            zeichen = self.zeichen(FeldXpos, FeldYpos)
    entfernung = math.sqrt((schnittpunktX - mitteX) ** 2 + (schnittpunktY - mitteY) ** 2)
    wand = (FeldXpos, FeldYpos, entfernung)
    return wand

Spielfeld-KlasseBearbeiten

Da wir nun an einigen Stellen Änderungen vorgenommen haben, wollen wir hier nochmal ein gesamtes Programm vorstellen, welches die Wandsuche benutzt:

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
import math
import pygame
import sys
 
 
class Spielfeld(object):
 
    def __init__(self, dateiname):
        self.felder = []
        # Blickrichtung als Winkel in Grad
        self.blickrichtung = 90
        # Datei einlesen
        datei = open(dateiname, 'r')
        for zeile in datei:
            self.felder.append(zeile[:-1])
        datei.close()
        self.breite = len(self.felder[0])
        self.hoehe = len(self.felder)
        for num, zeile in enumerate(self.felder):
            idx = zeile.find('#')
            if idx >= 0:
                self.position = (idx, num)
                self.felder[num] = self.felder[num].replace('#', '.')
                break
 
 
    def zeichen(self, x, y):
        """Liefert das Zeichen an der Position x, y """
        assert(0 <= x < self.breite)
        assert(0 <= y < self.hoehe)
        return self.felder[y][x]
 
 
    def istWand(self, zeichen):
        """True, wenn das Zeichen ein Wandzeichen ist """
        return zeichen in ('N', 'W', 'S', 'O')
 
 
    def geheVor(self):
        """gehe in Richtung der Blickrichtung """
        px, py = self.position
        qx = int(round(px + math.cos(math.radians(self.blickrichtung))))
        qy = int(round(py - math.sin(math.radians(self.blickrichtung))))
        zeichen = self.zeichen(qx, qy)
        if not self.istWand(zeichen): 
            self.position = (qx, qy)  
 
 
    def geheZurueck(self):
        """gehe entgegen der Blickrichtung """
        self.blickrichtung += 180
        self.geheVor()
        self.blickrichtung -= 180
 
 
    def dreheLinks(self):
        self.blickrichtung = (self.blickrichtung + 1) % 360
 
 
    def dreheRechts(self):
        self.blickrichtung = (self.blickrichtung - 5) % 360
 
 
    def findeWandHV(self, px, py, dx, dy):
        """Findet eine Wand in auschließlich horizontaler und vertikaler Richtung.
        (px, py) ist die Feldkoordinate des Spielers,
        (dx, dy) ist die Schrittweite, die wir bei jeder Iteration gehen"""
        FeldXpos = px + dx
        FeldYpos = py + dy
        zeichen = self.zeichen(FeldXpos, FeldYpos)
        while not self.istWand(zeichen):
            # untersuche nächstes Feld
            FeldXpos = FeldXpos + dx
            FeldYpos = FeldYpos + dy
            zeichen = self.zeichen(FeldXpos, FeldYpos)
        entfernung = (dx * (FeldXpos - px) + dy * (FeldYpos - py)) - 0.5
        wand = (FeldXpos, FeldYpos, entfernung)
        return wand


    def findeWandDiagonal(self, px, py, dx, dy):
        """Findet eine Wand in diagonaler Richtung.
        (px, py) ist die Feldkoordinate des Spielers,
        (dx, dy) ist die Schrittweite, die wir bei jeder Iteration gehen"""
        mitteX = px + 0.5
        mitteY = py + 0.5
        schnittpunktX = mitteX + dx
        schnittpunktY = mitteY + dy
        # nächste Schrittweite 
        dx = dx * 2.0
        dy = dy * 2.0
        FeldXpos = int(schnittpunktX)
        FeldYpos = int(schnittpunktY)
        if 0 < FeldXpos < self.breite and 0 < FeldYpos < self.hoehe:
            zeichen = self.zeichen(int(FeldXpos), int(FeldYpos))
            while not self.istWand(zeichen):
                schnittpunktX = schnittpunktX + dx
                schnittpunktY = schnittpunktY + dy
                FeldXpos = int(schnittpunktX)
                FeldYpos = int(schnittpunktY)
                if not (0 < FeldXpos < self.breite and 0 < FeldYpos < self.hoehe): break
                zeichen = self.zeichen(FeldXpos, FeldYpos)
        entfernung = math.sqrt((schnittpunktX - mitteX) ** 2 + (schnittpunktY - mitteY) ** 2)
        wand = (FeldXpos, FeldYpos, entfernung)
        return wand


    def findeWand(self):
        px, py = self.position
        wand = (0, 0, 0)
        tangens = math.tan(math.radians(self.blickrichtung))
        if self.blickrichtung == 0:
            wand = self.findeWandHV(px, py, 1, 0)
        elif self.blickrichtung > 0 and self.blickrichtung < 90:
            dx = 0.501
            dy = -tangens * dx
            wand1 = self.findeWandDiagonal(px, py, dx, dy)
            dy = -0.501
            dx = -dy / tangens
            wand2 = self.findeWandDiagonal(px, py, dx, dy)
            if wand1[2] < wand2[2]:
                wand = wand1
            else:
                wand = wand2
        elif self.blickrichtung == 90:
            wand = self.findeWandHV(px, py, 0, -1)
        elif self.blickrichtung > 90 and self.blickrichtung < 180:
            dx = -0.501
            dy = -tangens * dx
            wand1 = self.findeWandDiagonal(px, py, dx, dy)
            dy = -0.501
            dx = -dy / tangens
            wand2 = self.findeWandDiagonal(px, py, dx, dy)
            if wand1[2] < wand2[2]:
                wand = wand1
            else:
                wand = wand2
        elif self.blickrichtung == 180:
            wand = self.findeWandHV(px, py, -1, 0)
        elif self.blickrichtung > 180 and self.blickrichtung < 270:
            dx = -0.501
            dy = -tangens * dx
            wand1 = self.findeWandDiagonal(px, py, dx, dy)
            dy = 0.501
            dx = -dy / tangens
            wand2 = self.findeWandDiagonal(px, py, dx, dy)
            if wand1[2] < wand2[2]:
                wand = wand1
            else:
                wand = wand2
        elif self.blickrichtung == 270:
            wand = self.findeWandHV(px, py, 0, 1)
        elif self.blickrichtung > 270 and self.blickrichtung < 360:
            dx = 0.501
            dy = -tangens * dx
            wand1 = self.findeWandDiagonal(px, py, dx, dy)
            dy = 0.501
            dx = -dy / tangens
            wand2 = self.findeWandDiagonal(px, py, dx, dy)
            if wand1[2] < wand2[2]:
                wand = wand1
            else:
                wand = wand2
        return wand

 
def init(breite, hoehe):
    screen = pygame.display.set_mode((breite, hoehe))
    screen.fill((200, 200, 200))
    pygame.display.update()
    return screen
 
 
def zeichneSpielfeld(screen, breite, hoehe, spielfeld, wandpos):
    feldbreite = breite // spielfeld.breite
    feldhoehe = hoehe // spielfeld.hoehe
    for y in xrange(spielfeld.hoehe):
        for x in xrange(spielfeld.breite):
            zeichen = spielfeld.zeichen(x, y)
            rechteck = (x * feldbreite, y * feldhoehe, feldbreite, feldhoehe)
            if zeichen == '.':
                pygame.draw.rect(screen, (0, 0, 0), rechteck)
            elif zeichen == 'N':
                pygame.draw.rect(screen, (128, 0, 0), rechteck)
            elif zeichen == 'W':
                pygame.draw.rect(screen, (160, 43, 43), rechteck)
            elif zeichen == 'S':
                pygame.draw.rect(screen, (128, 128, 0), rechteck)
            elif zeichen == 'O':
                pygame.draw.rect(screen, (213, 85, 0), rechteck)
    # Spielfigur zeichnen
    pos = (spielfeld.position[0] * feldbreite + feldbreite // 2, spielfeld.position[1] * feldhoehe + feldhoehe // 2)
    pygame.draw.circle(screen, (255, 255, 255), pos, min(feldhoehe, feldbreite) // 3)
    # grid zeichnen
    for x in xrange(1, spielfeld.breite):
        start = (x * feldbreite, 0)
        ende = (start[0], hoehe - 1)
        pygame.draw.line(screen, (128, 128, 128), start, ende)
    for y in xrange(1, spielfeld.hoehe):
        start = (0, y * feldhoehe)
        ende = (breite - 1, start[1])
        pygame.draw.line(screen, (128, 128, 128), start, ende)
    # gefundene Wand zeichnen
    wx, wy, entfernung = wandpos
    wx = wx * feldbreite + feldbreite // 2
    wy = wy * feldhoehe + feldhoehe // 2
    pygame.draw.circle(screen, (0, 0, 255), (wx, wy), min(feldhoehe, feldbreite) // 3)
    # Entfernungslinie zeichnen
    qx = int(pos[0] + entfernung * feldbreite * math.cos(math.radians(spielfeld.blickrichtung)))
    qy = int(pos[1] - entfernung * feldhoehe * math.sin(math.radians(spielfeld.blickrichtung)))
    pygame.draw.line(screen, (255, 255, 0), pos, (qx, qy))
    pygame.display.update()
 
 
def hauptschleife(spielfeld, screen, breite, hoehe):
    wand = spielfeld.findeWand()
    zeichneSpielfeld(screen, breite, hoehe, spielfeld, wand)
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                sys.exit()
            elif event.type == pygame.KEYDOWN:
                if event.key == pygame.K_UP:
                    spielfeld.geheVor()
                elif event.key == pygame.K_DOWN:
                    spielfeld.geheZurueck()
                elif event.key == pygame.K_LEFT:
                    spielfeld.dreheLinks()
                elif event.key == pygame.K_RIGHT:
                    spielfeld.dreheRechts()
                wand = spielfeld.findeWand()
                zeichneSpielfeld(screen, breite, hoehe, spielfeld, wand)
 
 
if __name__ == '__main__':
    spielfeld = Spielfeld('spielfeld.txt')
    screen = init(500, 500)
    hauptschleife(spielfeld, screen, 500, 500)

AnmerkungenBearbeiten