Die Karte und das Sichtfeld
Kurz gesagt: Das Sichtfeld ist die Menge der Zellen, die der Held sieht: Zu jeder Zelle in Reichweite wird eine Bresenham-Linie gezogen, eine Wand hält sie auf, und was einmal gesehen wurde, bleibt als Nebel auf der Karte.
Problem
Der Boss ist vom Eingang aus zu sehen
Die erste Ebene der Mine ist 50 × 20 Zellen groß, und die Karte auf dem Bildschirm ist 40 × 13. Die ganze Ebene passt nicht hinein. Selbst wenn sie hineinpassen würde, solltest du nicht alles sehen: Wenn du den Wächter der Tiefe und jede Truhe schon vom Eingang aus siehst, gibt es nichts mehr zu entdecken.
Deshalb zeigt das Spiel nur, was der Held sieht, und es merkt sich, was der Held gesehen hat. Hier ist das erste Bild, nachdem der Held in die Mine hinabgestiegen ist (aus dem Durchlauf, mit dem das Spiel geprüft wird):
### Obere Galerie#@.....# Ebene 1 von 3#......+ ......# Ringsum: ...... niemand ######
Iva, Barbar St.1 EP 0/20 Gold 5L [############] 48/48 M [########] 4/4Neue Quest: Die Blutspur.Neue Quest: Silber für die Schmiedin.Ebene 1: Obere Galerie.Du siehst den Raum und die Tür. Der Gang und die Halle hinter der Tür fehlen, obwohl sie nur fünf oder sechs Zellen entfernt sind. Dieses Bild braucht fünf Dinge: eine Karte aus Text, Bewegung mit Kollision, eine Kamera, ein Sichtfeld und Nebel. Die Lektion baut sie nacheinander auf einer kleinen Ebene von 16 × 7 auf und zeigt dann dieselbe Stelle im Spiel.
Die Idee
Die Ebene ist Text
Die Ebene dieser Lektion ist 16 × 7:
#################......#.......##......+.......##...~~@#....>..##...~~.#.......##......#.......#################Jedes Zeichen ist eine Zelle: # Wand, . Boden, + geschlossene Tür, ~ Wasser, > Treppe nach unten, @ der Held. Der Code kennt die Form der Ebene nicht. Er liest den Text. Eine neue Ebene ist neuer Text, ohne eine einzige neue Codezeile.
Für Bewegung und Sicht muss eine Zelle zwei Fragen beantworten: Kann man darauf gehen und versperrt sie die Sicht. Die beiden Antworten gehören nicht immer zusammen. Über Wasser kann man sehen, aber nicht hindurchgehen. Eine geschlossene Tür versperrt die Sicht und lässt dich nicht hinein. Eine Kachel ist also ein Datensatz aus einem Zeichen, einem Namen und den beiden Antworten, und die Tabelle der Kacheln sind Daten:
from dataclasses import dataclass
@dataclass(frozen=True)class Tile: glyph: str name: str walkable: bool opaque: bool
TILES = [ Tile("#", "Wand", False, True), Tile(".", "Boden", True, False), Tile("+", "Tür", False, True), Tile("'", "offene Tür", True, False), Tile("~", "Wasser", False, False), Tile(">", "Treppe", True, False),]
def tile_of(glyph): for tile in TILES: if tile.glyph == glyph: return tile raise ValueError("Unbekannte Zelle: " + glyph)
class Level: def __init__(self, text): rows = text.split("\n") self.height = len(rows) self.width = len(rows[0]) self.hero_x = 0 self.hero_y = 0 self.cells = [] for y in range(self.height): row = [] for x in range(self.width): glyph = rows[y][x] if glyph == "@": self.hero_x = x self.hero_y = y glyph = "." row.append(tile_of(glyph)) self.cells.append(row)
def in_bounds(self, x, y): return 0 <= x < self.width and 0 <= y < self.height
# Außerhalb der Karte ist Wand: Niemand geht hinaus und niemand schaut hinaus. def at(self, x, y): return self.cells[y][x] if self.in_bounds(x, y) else TILES[0]MAP = """#################......#.......##......+.......##...~~@#....>..##...~~.#.......##......#.......#################""".strip()
level = Level(MAP)print(f"Die Ebene ist {level.width} × {level.height}, der Held steht auf ({level.hero_x}, {level.hero_y}).")for tile in TILES: count = 0 for row in level.cells: for cell in row: if cell is tile: count += 1 if count == 0: continue walk = "ja" if tile.walkable else "nein" sight = "ja" if tile.opaque else "nein" print(f"{tile.glyph} {tile.name}: {count}, begehbar: {walk}, versperrt die Sicht: {sight}")Die Ebene ist 16 × 7, der Held steht auf (6, 3).# Wand: 46, begehbar: nein, versperrt die Sicht: ja. Boden: 60, begehbar: ja, versperrt die Sicht: nein+ Tür: 1, begehbar: nein, versperrt die Sicht: ja~ Wasser: 4, begehbar: nein, versperrt die Sicht: nein> Treppe: 1, begehbar: ja, versperrt die Sicht: neinat(x, y) gibt für alles außerhalb der Karte eine Wand zurück. So müssen weder die Bewegung noch die Sicht die Grenzen prüfen: Niemand verlässt die Karte, denn draußen ist Wand.
@dataclass(frozen=True) erzeugt den Datensatz: Die Felder werden dem Konstruktor übergeben und ändern sich nicht.Genauer, für Neugierige
Das Gitter hat 112 Zellen, aber es gibt nur sechs Kachelobjekte. Jede Zelle hält einen Verweis auf eines davon, deshalb vergleicht das Zählen oben mit is. Wenn die Tür aufgeht, zeigt die Zelle einfach auf eine andere Kachel. Das ist das Flyweight-Muster: Was geteilt wird (der Name, die Eigenschaften), liegt an einer Stelle, und die Position auf der Karte steht im Gitter.
Im Kanon sind die Zellen Zeichen, und die Eigenschaften sind zwei kleine Methoden: isWalkable und isOpaque. Die Idee ist dieselbe und die Form einfacher, denn es gibt acht Arten und zwei Eigenschaften. Kommen weitere dazu (Bewegungskosten, Lärm, Licht), gewinnt wieder die Tabelle.
Die Idee
Die Ebenen im Spiel
Die drei Ebenen der Mine stehen in einem Stück Text im Code des Spiels. Jede beginnt mit einer Zeile level|1|… (die Tiefe und der Name in allen vier Sprachen), dann folgen die Zeilen der Karte, die Legende und end. Hier ist die erste Ebene ohne ihre Kopfzeile:
###################################################<.....#............#........1.#..~~~~~.......2..##......+....r.......+......g...#..~~~~~..........##......#............#..........+..~~~~~..........##......#............#..........#.........,.......#########.........r..############........,........#########............############........,........###############.#########################,#######################.#########################.#######################.#########################,############....#.3............#########.........,...#########.4..?.........s....+..................,..#########....#...g..........#########..........,..##############..............###################+######################.###############........5555555....###......................######............,......###..................r...######..............,L...###.>....................######......w............###......7...............######.................6.###################################################legend|1|item|potion_heal|1legend|2|gold|25|0legend|3|item|antidote|1legend|4|item|ring_life|1legend|5|marker|lair|0legend|6|gold|30|0legend|7|item|potion_heal|1endEs gibt mehr Zeichen als Kacheln. Die Buchstaben (r, g, s, L) sind Feinde aus der Tabelle der Feinde. Die Ziffern kommen aus der Legende unter der Karte: ein Gegenstand, Gold, eine Questmarke. < ist die Stelle, an der der Held herabkommt. ? ist eine Geheimtür, die wie eine Wand aussieht. , ist Blut auf dem Boden.
# Die Karte ist Text: Die Zeilen zwischen „level|…“ und „legend|…“ sind die Karte selbst, die Legende sagt, was# jede Ziffer bedeutet. Hier werden nur die Definitionen gelesen; die lebende Ebene entsteht in build_level.def load_maps(): current = None for raw_line in MAPS_DATA.split('\n'): line = trim_spaces(raw_line) if len(line) == 0: continue if line.startswith('level|'): cells = line.split('|') current = SimpleNamespace(depth=to_int(cells[1]), bg=cells[2], en=cells[3], de=cells[4], es=cells[5], rows=[], legend={}) elif line.startswith('legend|'): cells = line.split('|') current.legend[cells[1]] = SimpleNamespace(kind=cells[2], value=cells[3], amount=to_int(cells[4])) elif line == 'end': MAP_DEFS.append(current) current = None else: current.rows.append(line)Das Lesen geschieht in zwei Schritten. loadMaps teilt den Text nur in Definitionen auf. Die lebendige Ebene wird bei einem neuen Spiel (und beim Laden) mit buildLevel gebaut: Buchstaben werden zu Feinden, Ziffern zu Gegenständen, und der Boden bleibt darunter. Deshalb steht im Gitter der Ebene kein Goblin. Die Wesen sind eine eigene Liste, die sich über die Karte bewegt, und die Karte bleibt ruhig.
Die Idee
Ein Zug ist eine Bitte
Der einfachste Zug ist heroX += dx. Damit geht der Held durch Wände und von der Karte herunter. Ein Zug muss eine Bitte sein: „Ich will dorthin.“ Die Zelle, in die der Held will, entscheidet:
# Ein Zug ist eine Bitte: Die Zelle, in die du willst, entscheidet.def step(level, dx, dy): x = level.hero_x + dx y = level.hero_y + dy target = level.at(x, y) if target.glyph == "+": level.cells[y][x] = tile_of("'") return "Die Tür knarrt auf." if not target.walkable: return "Kein Durchkommen: " + target.name + "." level.hero_x = x level.hero_y = y return ""- eine Wand oder Wasser: nein, und es sagt warum;
- eine geschlossene Tür: Sie öffnet sich (wird zu
'), aber der Held bleibt stehen. Das Öffnen ist der Zug; - alles andere: Der Held geht hinein.
Das Programm liest die Befehle w a s d (hoch, links, runter, rechts), einen pro Zeile, und zeichnet nach jedem die Ebene. Die Eingabe ist d a w d d d:
level = Level(MAP)for line in sys.stdin: command = line.strip() if len(command) != 1: continue direction = MOVES.find(command) if direction < 0: continue message = step(level, DX[direction], DY[direction]) print("> " + command + (" " + message if message else "")) print_level(level)> d Kein Durchkommen: Wand.#################......#.......##......+.......##...~~@#....>..##...~~.#.......##......#.......#################> a Kein Durchkommen: Wasser.#################......#.......##......+.......##...~~@#....>..##...~~.#.......##......#.......#################> w#################......#.......##.....@+.......##...~~.#....>..##...~~.#.......##......#.......#################> d Die Tür knarrt auf.#################......#.......##.....@'.......##...~~.#....>..##...~~.#.......##......#.......#################> d#################......#.......##......@.......##...~~.#....>..##...~~.#.......##......#.......#################> d#################......#.......##......'@......##...~~.#....>..##...~~.#.......##......#.......#################Die ersten beiden Züge gehen gegen eine Wand und in Wasser: Der Held bleibt stehen. Dann geht der Held nach oben, öffnet die Tür und geht hindurch.
Im Spiel tut der Schritt mehr, und die Reihenfolge zählt:
# Ein Schritt des Helden: Kampf, Gespräch, Tür, verstecktes Versteck, Wand oder Bewegung.def step_hero(self, dx, dy): level = self.level() hero = self.hero x = hero.x + dx y = hero.y + dy enemy = level.enemy_at(x, y) if enemy is not None: self.start_battle(enemy) return 'stop' npc = level.npc_at(x, y) if npc is not None: self.stack.push(DialogScreen(self, npc.id)) return 'stop' tile = level.tile(x, y) if tile == '+': level.tiles[y][x] = "'" self.say(t('map.door')) self.world_turn() return 'stop' if len(self.stack.changes) > 0 else 'acted' if tile == '?': level.tiles[y][x] = '+' self.say(t('map.secret')) self.world_turn() return 'stop' if len(self.stack.changes) > 0 else 'acted' if not level.is_walkable(x, y): self.say(t('map.water' if tile == '~' else 'map.wall')) return 'blocked' if hero.has_effect('bleed'): level.add_blood(hero.x, hero.y) hero.x = x hero.y = y self.bus.publish(SimpleNamespace(type='TileEntered', depth=self.depth, x=x, y=y, decor=level.decor[y][x], marker=level.markers[y][x])) here = level.items_at(x, y) if len(here) > 0: names = [] for item in here: names.append(item_label(item.id, item.count)) self.say(t('map.itemsHere', {'items': ', '.join(names)})) self.world_turn() return 'stop' if len(self.stack.changes) > 0 else 'moved'Zuerst fragt er nach einem Feind: Der Feind steht auf Boden, und würde die Kachel zuerst entscheiden, ginge der Held in den Feind hinein. Dann kommt eine Person (ein Gespräch), eine Tür, eine Geheimtür und erst dann die Kachel. Wenn sich der Held wirklich bewegt, hinterlässt ein blutender Held Blut auf dem Boden, das Ereignis TileEntered sagt den Quests, wo der Held ist, und am Ende ist die Welt am Zug.
Das Anstoßen an eine Wand gibt blocked zurück und ruft worldTurn nicht auf: Ein Spielerfehler kostet keinen Zug, und die Feinde kommen nicht näher. Die Tür kostet einen Zug.
Genauer, für Neugierige
Hier lässt Wasser einfach nicht durch. In vielen Spielen geht man durch flaches Wasser, aber langsam: Jede Kachel hat Bewegungskosten (Boden 1, flaches Wasser 2, Sumpf 3), und der Held sammelt Energie, bis sie die Kosten erreicht, wie die Energie im Kampf (die Lektion über das Kampfsystem). Dann wird walkable eine Zahl statt ja oder nein. Auch die Wegsuche muss die Kosten kennen: BFS reicht nicht mehr, du brauchst Dijkstra.
Die Idee
Die Kamera
Die Ebene des Spiels ist 50 × 20, und die Ansicht ist 40 × 13. Die Kamera ist die Welt, gesehen durch ein Fenster: cameraX und cameraY sind die Weltzelle in der linken oberen Ecke des Bildschirms. Beide Richtungen sind nur eine Addition entfernt:
- von der Welt zum Bildschirm:
screenX = x − cameraX; - vom Bildschirm zur Welt:
x = cameraX + screenX.
Die Kamera folgt dem Helden: Der Held ist in der Mitte, also cameraX = heroX − VIEW_W / 2. Nahe am Rand der Karte ergibt das eine negative Zahl oder eine Ansicht, die über die Karte hinausläuft. Deshalb wird die Kamera zwischen 0 und width − VIEW_W begrenzt (clamp). Dort bleibt die Ansicht stehen, und der Held wandert zum Bildschirmrand.
VIEW_W = 9VIEW_H = 5
def clamp(value, low, high): if value < low: return low if value > high: return high return value
def print_view(level): camera_x = clamp(level.hero_x - VIEW_W // 2, 0, level.width - VIEW_W) camera_y = clamp(level.hero_y - VIEW_H // 2, 0, level.height - VIEW_H) print(f"Held ({level.hero_x}, {level.hero_y}), Kamera ({camera_x}, {camera_y}" f"), auf dem Bildschirm ({level.hero_x - camera_x}, {level.hero_y - camera_y})") for view_y in range(VIEW_H): row = "" for view_x in range(VIEW_W): x = camera_x + view_x y = camera_y + view_y row += "@" if x == level.hero_x and y == level.hero_y else level.at(x, y).glyph print(row)Das Programm benutzt eine Ansicht von 9 × 5 auf der Ebene von 16 × 7 und gibt die Ansicht nach jedem Abschnitt des Weges des Helden aus:
level = Level(MAP)for leg in ["", "wdddd", "ddddd", "sss"]: for command in leg: direction = MOVES.find(command) step(level, DX[direction], DY[direction]) print_view(level)Held (6, 3), Kamera (2, 1), auf dem Bildschirm (4, 2).....#........+.....~~@#.....~~.#........#...Held (9, 2), Kamera (5, 0), auf dem Bildschirm (4, 2)#########..#........'.@....~.#....>.~.#......Held (14, 2), Kamera (7, 0), auf dem Bildschirm (7, 2)##########.......#'......@##....>..##.......#Held (14, 5), Kamera (7, 2), auf dem Bildschirm (7, 3)'.......##....>..##.......##......@##########Die ersten beiden Ansichten sind zentriert: Der Held steht auf dem Bildschirm bei (4, 2). In der dritten hat die Kamera die rechte Grenze 16 − 9 = 7 erreicht und bleibt stehen, während der Held weiter zum Rand geht. In der vierten ist die Kamera auch unten stehen geblieben.
VIEW_W // 2 ist die Ganzzahldivision: 9 // 2 = 4.camera_x = clamp(level.hero_x - VIEW_W // 2, 0, )Die am weitesten rechts stehende Kamera ist die, bei der der rechte Rand der Ansicht am rechten Rand der Karte liegt: width − VIEW_W. Für 16 × 7 und eine Ansicht von 9 sind das 7: Die Ansicht zeigt die Spalten 7 bis 15.
Genauer, für Neugierige
Wenn die Ebene schmaler ist als die Ansicht, ist width − VIEW_W negativ, und je nachdem, wo der Held steht, gibt clamp 0 oder eine negative Zahl zurück: Die Kamera springt oder verlässt links die Karte. Im Kanon passiert das nicht, weil alle drei Ebenen 50 × 20 sind, aber in einem Spiel mit kleinen Räumen wird die Ebene in der Ansicht zentriert: cameraX = (width − VIEW_W) / 2.
Eine Kamera, die sich bei jedem Schritt bewegt, lässt den ganzen Bildschirm springen. Viele Spiele halten eine Totzone: Die Kamera bewegt sich erst, wenn der Held ein Rechteck in der Mitte verlässt. In einem rundenbasierten Konsolenspiel braucht man sie selten; in einem Spiel mit fließender Bewegung schon.
Das Spiel macht dasselbe mit 40 × 13. Hier ist ein Bild weiter unten auf der ersten Ebene: Die Kamera ist nach unten gewandert, deshalb liegen die obersten Zeilen der Ebene außerhalb der Ansicht:
########............############........ Obere Galerie #............# #........ Ebene 1 von 3 #######.##### ######### # Ringsum: ###### ########## niemand ........#########......... ...%.%@.'................. ........#########......... ........# ########## ######## . ... .... ....Iva, Barbar St.2 EP 40/55 Gold 30L [############] 57/57 M [########] 5/5Speergoblin bemerkt dich!Sieg! Erfahrung aus dem Kampf: 21.Iva erreicht Stufe 2: neue Fähigkeit: Wirbelwind (Raserei).Die Idee
Erster Versuch: ein Radius
Der Held soll die Umgebung sehen. Die erste Idee ist ein Radius: Du siehst jede Zelle, die näher als 6 ist.
RADIUS = 6
def radius_only(level, visible, seen): origin_x = level.hero_x origin_y = level.hero_y for y in range(level.height): for x in range(level.width): visible[y][x] = False for y in range(origin_y - RADIUS, origin_y + RADIUS + 1): for x in range(origin_x - RADIUS, origin_x + RADIUS + 1): if not level.in_bounds(x, y): continue dx = x - origin_x dy = y - origin_y if dx * dx + dy * dy > RADIUS * RADIUS + RADIUS: continue visible[y][x] = True seen[y][x] = Truevisible heißt „ich sehe es jetzt“. seen heißt „ich habe es irgendwann gesehen“, und es wird später für den Nebel gebraucht. Das sieht der Held vom Start aus:
level = Level(MAP)visible = [[False] * level.width for _ in range(level.height)]seen = [[False] * level.width for _ in range(level.height)]radius_only(level, visible, seen)report(level, visible, seen)Held (6, 3): du siehst 87, du erinnerst dich an 87| ########### ||#......#..... ||#......+..... ||#...~~@#....> ||#...~~.#..... ||#......#..... || ########### |87 Zellen sind sichtbar, und darunter die Treppe (>) hinter der Wand. Die geschlossene Tür spielt keine Rolle. Der Radius weiß, wie weit eine Zelle entfernt ist, aber nicht, was zwischen ihr und dem Helden liegt. Das ist der Boss, den du vom Eingang aus siehst.
Genauer, für Neugierige
Warum lautet die Bedingung dx² + dy² ≤ R² + R und nicht ≤ R²? Mit ≤ R² ragen vier einzelne Zellen aus dem Kreis heraus: (R, 0), (0, R) und ihre Spiegelbilder. Das zusätzliche + R rundet ihn ab: Für ganze Zahlen ist dx² + dy² ≤ R² + R dasselbe wie ein Abstand zur Zellenmitte unter R + ½, denn (R + ½)² = R² + R + ¼. Keine Wurzel und keine Brüche.
Die Idee
Eine gerade Linie: Bresenham
Eine Zelle ist sichtbar, wenn die gerade Linie vom Helden zu ihr nicht durch eine Wand geht. Auf einem Gitter ist eine gerade Linie eine Folge von Zellen, und man muss entscheiden, welche. Der Algorithmus von Bresenham macht das nur mit ganzen Zahlen: Addieren, Subtrahieren und Multiplizieren mit 2.
Die Idee: Du startest an einem Ende, und bei jedem Schritt gehst du entlang von x, entlang von y oder beides. Was davon gilt, entscheidet error: wie weit die Linie von der wahren Geraden abgewichen ist. Wenn die Abweichung entlang einer Achse zu groß wird, machst du einen Schritt entlang dieser Achse und verringerst die Abweichung.
def line(x0, y0, x1, y1): cells = [] dx = abs(x1 - x0) dy = -abs(y1 - y0) step_x = 1 if x0 < x1 else -1 step_y = 1 if y0 < y1 else -1 error = dx + dy x = x0 y = y0 while True: cells.append((x, y)) if x == x1 and y == y1: return cells doubled = 2 * error if doubled >= dy: error += dy x += step_x if doubled <= dx: error += dx y += step_yDas Programm zeichnet die Linie von A = (0, 0) nach B = (8, 3) und dann zurück, von B nach A:
there = line(0, 0, 8, 3)back = line(8, 3, 0, 0)print("A → B: " + format_cells(there))print("B → A: " + format_cells(back))picture = [["."] * 9 for _ in range(4)]for x, y in there: picture[y][x] = "*"picture[0][0] = "A"picture[3][8] = "B"for row in picture: print("".join(row))A → B: 0,0 1,0 2,1 3,1 4,2 5,2 6,2 7,3 8,3B → A: 8,3 7,3 6,2 5,2 4,1 3,1 2,1 1,0 0,0A*.........**.........***.........*BDie beiden Richtungen gehen durch fast dieselben Zellen, aber nicht ganz: Der Hinweg geht durch 4,2, der Rückweg durch 4,1. In der Mitte ist der Fehler genau gleich, und der Algorithmus wählt eine Seite. Auf dem Rückweg wählt er die andere. Merk dir das: Du brauchst es für die Schwächen der Methode.
Genauer, für Neugierige
Woher kommt error = dx + dy (mit negativem dy)? Die Gerade durch die beiden Enden ist f(x, y) = 0, wobei f linear ist, und das Vorzeichen von f sagt dir, auf welcher Seite du bist. error ist f, auf eine ganze Zahl skaliert, an dem Punkt, der als Nächstes käme. Die Prüfungen 2 · error ≥ dy und 2 · error ≤ dx fragen, ob ein Schritt entlang von x oder von y dich näher an die Gerade bringt. Deshalb funktioniert der Algorithmus in allen acht Richtungen und teilt nie.
Jack Bresenham hat ihn 1962 bei IBM für einen Plotter erfunden: Die Maschine bewegt den Stift einen Schritt nach dem anderen, und Division ist teuer. Heute ist Division nicht teuer, aber ganze Zahlen geben auf jedem Computer und in jeder Sprache dasselbe Ergebnis, und für unser Spiel ist das ein Muss.
Sieh es dir an
Sichtfeld und Nebel
Jetzt kommt beides zusammen. Eine Bresenham-Linie geht zu jeder Zelle im Radius. Bei jedem Schritt prüft die Linie zwei Dinge: sind wir angekommen und ist hier eine Wand. Die Reihenfolge zählt. Hat die Linie das Ziel erreicht, ist die Zelle sichtbar, auch wenn sie eine Wand ist. Steht vor dem Ziel eine Wand auf dem Weg, hält die Linie an: Die Zelle ist nicht sichtbar.
RADIUS = 6
def line_of_sight(level, x0, y0, x1, y1): dx = abs(x1 - x0) dy = -abs(y1 - y0) step_x = 1 if x0 < x1 else -1 step_y = 1 if y0 < y1 else -1 error = dx + dy x = x0 y = y0 while True: if x == x1 and y == y1: return True if (x != x0 or y != y0) and level.at(x, y).opaque: return False doubled = 2 * error if doubled >= dy: error += dy x += step_x if doubled <= dx: error += dx y += step_y
def compute_fov(level, visible, seen): origin_x = level.hero_x origin_y = level.hero_y for y in range(level.height): for x in range(level.width): visible[y][x] = False for y in range(origin_y - RADIUS, origin_y + RADIUS + 1): for x in range(origin_x - RADIUS, origin_x + RADIUS + 1): if not level.in_bounds(x, y): continue dx = x - origin_x dy = y - origin_y if dx * dx + dy * dy > RADIUS * RADIUS + RADIUS: continue if line_of_sight(level, origin_x, origin_y, x, y): visible[y][x] = True seen[y][x] = Truedef line_of_sight(level, x0, y0, x1, y1): dx = abs(x1 - x0) dy = -abs(y1 - y0) step_x = 1 if x0 < x1 else -1 step_y = 1 if y0 < y1 else -1 error = dx + dy x = x0 y = y0 while True: if x == x1 and y == y1: return True if (x != x0 or y != y0) and level.at(x, y).opaque: return False doubled = 2 * error if doubled >= dy: error += dy x += step_x if doubled <= dx: error += dx y += step_y
def compute_fov(level, visible, seen): origin_x = level.hero_x origin_y = level.hero_y for y in range(level.height): for x in range(level.width): visible[y][x] = False for y in range(origin_y - RADIUS, origin_y + RADIUS + 1): for x in range(origin_x - RADIUS, origin_x + RADIUS + 1): if not level.in_bounds(x, y): continue dx = x - origin_x dy = y - origin_y if dx * dx + dy * dy > RADIUS * RADIUS + RADIUS: continue if line_of_sight(level, origin_x, origin_y, x, y): visible[y][x] = True seen[y][x] = TrueSchritt für Schritt, in Worten
- Der Held steht auf (6, 3). Das Sichtfeld wird jeden Zug neu berechnet, und zuerst wird jede Zelle unsichtbar. Noch nichts wurde gesehen: Die ganze Ebene ist unbekannt.
- Die Kandidaten sind die Zellen im Radius 6: dx² + dy² ≤ 6² + 6. Es sind 87, auch der Raum hinter der Wand. Der Radius weiß nichts von Wänden.
- Zu jedem Kandidaten geht eine gerade Linie (Bresenham). Sie hält an der ersten Wand auf dem Weg, erreicht diese aber, deshalb ist die Wand selbst sichtbar. 37 Linien enden früher (die grauen).
- Von (6, 3) aus siehst du 50 Zellen, und alle kommen in seen. Der Raum rechts liegt im Radius, aber die geschlossene Tür und die Wand verbergen ihn: Die Treppe bleibt unbekannt.
- Der Held öffnet die Tür und geht hindurch (wdddddd). Jeden Zug wird visible geleert und seen bleibt: Was du gesehen hast, aber nicht mehr siehst, wird zu Nebel.
- Von (11, 2) aus gehen die Linien durch die offene Tür. Im linken Raum ist nur ein schmaler Keil sichtbar: Die Wand verbirgt den Rest.
- Du siehst 63, du erinnerst dich an 109 von 112 Zellen. Der Nebel bewahrt die Form des linken Raums, aber nicht, was jetzt darin passiert.
In jedem Zug wird visible geleert und neu berechnet, während sich seen nur füllt. Das Programm zeichnet sichtbare Zellen mit ihrem Zeichen, gesehene, aber nicht mehr sichtbare mit : und unbekannte als Leerzeichen. Zuerst vom Start aus, dann nach 7 Zügen (hoch, die Tür, fünfmal rechts):
level = Level(MAP)visible = [[False] * level.width for _ in range(level.height)]seen = [[False] * level.width for _ in range(level.height)]compute_fov(level, visible, seen)report(level, visible, seen)for command in "wdddddd": direction = MOVES.find(command) step(level, DX[direction], DY[direction]) compute_fov(level, visible, seen)report(level, visible, seen)Held (6, 3): du siehst 50, du erinnerst dich an 50| ###### ||#...... ||#......+ ||#...~~@# ||#...~~.# ||#...... || ###### |Held (11, 2): du siehst 63, du erinnerst dich an 109| :::::::####### ||:::::::#.......#||:::::..'...@...#||:::::::#....>..#||:::::::#.......#||:::::::#.......#|| ::::::#########|Am Anfang ist die Treppe nicht sichtbar: Die Wand und die geschlossene Tür verbergen sie. Nachdem der Held hindurchgegangen ist, ist der linke Raum Nebel. Der Held weiß, wie er aussieht, aber er sieht nicht, was darin vorgeht: Ein Feind, der dort hineingeht, erscheint nicht auf dem Bildschirm.
Im Spiel ist das Sichtfeld derselbe Code, an derselben Stelle im Zug:
# Sichtfeld: Ein Feld ist sichtbar, wenn es im Radius liegt und die Linie dorthin (Bresenham) nicht# durch eine Wand oder geschlossene Tür geht. Das Gesehene wird gemerkt: das ist der Nebel.FOV_RADIUS = 6
def line_of_sight(level, x0, y0, x1, y1): dx = abs(x1 - x0) dy = -abs(y1 - y0) step_x = 1 if x0 < x1 else -1 step_y = 1 if y0 < y1 else -1 error = dx + dy x = x0 y = y0 while True: if x == x1 and y == y1: return True if (x != x0 or y != y0) and level.is_opaque(x, y): return False doubled = 2 * error if doubled >= dy: error += dy x += step_x if doubled <= dx: error += dx y += step_y
def compute_fov(level, origin_x, origin_y): for y in range(level.height): for x in range(level.width): level.visible[y][x] = False for y in range(origin_y - FOV_RADIUS, origin_y + FOV_RADIUS + 1): for x in range(origin_x - FOV_RADIUS, origin_x + FOV_RADIUS + 1): if not level.in_bounds(x, y): continue dx = x - origin_x dy = y - origin_y if dx * dx + dy * dy > FOV_RADIUS * FOV_RADIUS + FOV_RADIUS: continue if line_of_sight(level, origin_x, origin_y, x, y): level.visible[y][x] = True level.seen[y][x] = TrueMapScreen ruft ihn in update auf, nach jedem Befehl. Das Zeichnen der Karte zeigt Kamera und Nebel zusammen: Eine Zelle, die nie gesehen wurde, wird übersprungen (continue), eine sichtbare hat ihre eigene Farbe, und eine gesehene ist grau:
def draw(self, buffer): game = self.game level = game.level() hero = game.hero camera_x = clamp(hero.x - VIEW_WIDTH // 2, 0, level.width - VIEW_WIDTH) camera_y = clamp(hero.y - VIEW_HEIGHT // 2, 0, level.height - VIEW_HEIGHT) for view_y in range(VIEW_HEIGHT): for view_x in range(VIEW_WIDTH): x = camera_x + view_x y = camera_y + view_y if not level.seen[y][x]: continue cell = cell_look(level, x, y) buffer.put(view_x, view_y, cell.ch, cell.color if level.visible[y][x] else 'gray') buffer.put(hero.x - camera_x, hero.y - camera_y, '@', 'white') self.draw_side_panel(buffer, level) draw_hud(buffer, game, VIEW_HEIGHT) draw_messages(buffer, game, VIEW_HEIGHT + 2, 3)Hier ist das Bild, in dem der Held die Tür zur großen Halle auf der ersten Ebene öffnet. Durch die offene Tür siehst du einen Keil der Halle und eine Riesenratte darin:
######## Obere Galerie#<.....# .... Ebene 1 von 3#.....@'....r#......# .... Ringsum:#......# .. r Riesenratte########
Iva, Barbar St.1 EP 0/20 Gold 5L [############] 48/48 M [########] 4/4Die Tür knarrt auf.Riesenratte bemerkt dich!Du siehst: Riesenratte.Genauer, für Neugierige
In einem einfachen Terminal (--plain) sehen gesehene und sichtbare Zellen gleich aus: Das Zeichen ist dasselbe, und es gibt keine Farbe. In einem Terminal mit ANSI-Farben sind gesehene Zellen grau. Deshalb benutzt das Programm in dieser Lektion : für den Nebel: damit du den Unterschied auch ohne Farben siehst.
Was kostet das? Der Kreis mit Radius 6 hat 137 Zellen, und die Linie zu jeder ist höchstens 6 Schritte lang: unter 1.000 Prüfungen pro Zug. Das ist O(r³) pro Zug: r² Zellen mal r Schritte.
Probier es aus
Sage die Ausgabe voraus
Ein kleiner Raum mit einem Pfeiler in der Mitte. Der Held steht links vom Pfeiler, und der Radius reicht bis zu jeder Zelle. Was gibt das Programm aus?
room = """########.....##@.#..##.....########""".strip()level = Level(room)visible = [[False] * level.width for _ in range(level.height)]seen = [[False] * level.width for _ in range(level.height)]compute_fov(level, visible, seen)print_sight(level, visible, seen)Der Pfeiler wirft einen Schatten: Die Zellen dahinter rechts sind nicht sichtbar, und der Schatten breitet sich zu den Ecken hin aus. Die Wände sind sichtbar, außer dort, wo die Linie durch den Pfeiler oder durch eine andere Wand geht. Die Ausgabe, in der alles sichtbar ist, ist der Radius allein; die Ausgabe ohne Wände hat die vertauschten Prüfungen aus der nächsten Aufgabe.
Probier es aus
Finde den Fehler
Ein Kollege hat die Linienfunktion angefasst, und jetzt gibt das Programm gleich vom Start aus Folgendes aus:
def line_of_sight(level, x0, y0, x1, y1): dx = abs(x1 - x0) dy = -abs(y1 - y0) step_x = 1 if x0 < x1 else -1 step_y = 1 if y0 < y1 else -1 error = dx + dy x = x0 y = y0 while True: if (x != x0 or y != y0) and level.at(x, y).opaque: return False if x == x1 and y == y1: return True doubled = 2 * error if doubled >= dy: error += dy x += step_x if doubled <= dx: error += dx y += step_yHeld (6, 3): du siehst 30, du erinnerst dich an 30| || ...... || ...... || ...~~@ || ...~~. || ...... || |Der Boden ist sichtbar, die Tür und die Wände sind weg, und das Wasser ist wie vorher. Welche Zeile prüft zu früh?
Wähle die Zeile mit dem Fehler.
Die Wandprüfung steht vor der Prüfung „sind wir angekommen“. Wenn die Linie eine Wand erreicht, die selbst das Ziel ist, fragt sie zuerst „ist hier eine Wand“ und gibt „nicht sichtbar“ zurück. Deshalb verschwinden genau die Wände und die geschlossene Tür. Die richtige Reihenfolge ist: zuerst „sind wir angekommen“, dann „ist auf dem Weg eine Wand“. Dann erreicht die Linie die Wand und hält danach an.
Genauer
Die Schwächen der einfachen Methode
Eine Linie zu jeder Zelle ist das einfachste Sichtfeld. Es hat drei bekannte Schwächen, und alle zeigen sich in unserem Spiel.
Löcher neben Wänden. Sieh dir das erste Bild vom Start noch einmal an: Der Held steht neben der Tür, und die Wand bei (7, 1) und (7, 5) ist nicht sichtbar, obwohl der Boden daneben es ist. Die Linie zu (7, 1) macht ihren ersten Schritt diagonal und landet auf der Tür bei (7, 2): Sie hält an. Dasselbe zeigt das Bild aus der Mine am Anfang der Lektion: Der Held steht neben der linken Wand, und sie hat ein Loch. Wenn du fast der Länge nach auf eine Wand schaust, läuft die Linie in die Nachbarzelle derselben Wand.
Asymmetrie. Von A aus siehst du B, aber von B aus siehst du A nicht, weil die Rücklinie durch andere Zellen geht (du hast es mit 4,2 und 4,1 gesehen). Auf der ersten Ebene der Mine gibt es 89 solche Zellenpaare von 17248: Von (12, 4) siehst du (14, 8), aber nicht umgekehrt. Im Kanon hat das Folgen. Ein Feind schaut mit seiner eigenen Linie, von sich zum Helden (enemySeesHero, bis zu 8 Zellen), und du siehst mit dem Sichtfeld vom Helden aus. Ein Goblin kann dich also bemerken, bevor du ihn siehst. Immerhin verrät das Spiel nicht mehr, als du siehst: Die Meldung, dass ein Feind aufgewacht ist, erscheint nur, wenn der Feind sichtbar ist.
Die billigere Variante lässt Löcher in Hallen. Statt einer Linie zu jeder Zelle kannst du Linien nur zum Rand des Kreises schicken und alles auf dem Weg markieren. Das ist O(r²) statt O(r³). Aber die Strahlen laufen mit der Entfernung auseinander, und Zellen dazwischen bleiben unbedeckt: Bei Radius 6 sind es 8 von 137, bei Radius 20 sind es 80 von 1313. In einer großen Halle sind das Löcher im Boden und in den fernen Wänden.
Bessere Algorithmen. Shadowcasting geht die acht Sektoren um den Helden Zeile für Zeile durch und hält die „Schatten“ als Bereiche von Steigungen. Jede Zelle wird einmal angeschaut, es gibt keine Löcher, und es gibt auch symmetrisches Shadowcasting, bei dem A genau dann B sieht, wenn B A sieht. Permissive FOV sagt, eine Zelle ist sichtbar, wenn irgendeine gerade Linie von irgendeinem Punkt der Zelle des Helden zu irgendeinem Punkt des Ziels frei ist. Es ist per Definition symmetrisch und sieht mehr um Ecken.
Warum der Kanon die einfache behält. Die Ebenen sind 50 × 20 und der Radius ist 6: unter 1.000 Prüfungen pro Zug, nichts für irgendeinen Computer. Ganze Zahlen geben in allen vier Sprachen dasselbe Ergebnis, und so werden die Portierungen geprüft. Und es passt auf eine Karte. Bekommt das Spiel je große offene Flächen und lange Sichtlinien, wird computeFov an einer Stelle ersetzt.
Übung
Die Geheimtür
Löse das in deinem Editor.
Eine Geheimtür. Füge eine Kachel ? hinzu: Sie sieht aus wie eine Wand (sie wird als # gezeichnet), man kann nicht darauf gehen, und sie versperrt die Sicht. Stößt der Held dagegen, wird sie zu einer geschlossenen Tür +, und das Programm gibt „Die Wand klingt hohl... Eine Geheimtür!“ aus. Der nächste Stoß öffnet sie wie jede Tür. Die Ebene ist:
#################......#.......##......+.......##...~~@#....>..##...~~.?.......##......#.......#################Mit der Eingabe s d d d d (je eine pro Zeile) lautet die Ausgabe:
> s#################......#.......##......+.......##...~~.#....>..##...~~@#.......##......#.......#################> d Die Wand klingt hohl... Eine Geheimtür!#################......#.......##......+.......##...~~.#....>..##...~~@+.......##......#.......#################> d Die Tür knarrt auf.#################......#.......##......+.......##...~~.#....>..##...~~@'.......##......#.......#################> d#################......#.......##......+.......##...~~.#....>..##...~~.@.......##......#.......#################> d#################......#.......##......+.......##...~~.#....>..##...~~.'@......##......#.......#################Weitere Übungen
- Eine Fackel. Mach den Radius zu einem Parameter. Mit Fackel sieht der Held 6 Zellen, ohne 2. Wie viel vom linken Raum sieht der Held vom Start aus ohne Fackel?
- Ansicht und Nebel zusammen. Verbinde die Kamera und das Sichtfeld: eine Ansicht von 9 × 5 auf der Ebene, die sichtbare, gesehene (
:) und unbekannte Zellen zeigt, wiedrawim Spiel. - Wer sieht wen. Schreibe ein Programm, das auf der Ebene dieser Lektion die Paare von Bodenzellen zählt, bei denen die eine die andere sieht, aber nicht umgekehrt.
Test