spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Wie wäre es denn mit diesem Ansatz:
Du berechnest einmal den schnellsten Weg von Core zu Core mit dem A*. Alle Felder, die nicht auf dem Weg liegen, dürfen bebaut werden, da der schnellste Weg erhalten bleibt. Für alle Felder auf dem Weg, kannst du entweder nochmal den A* vom Vorgänger bis zum Ziel anwenden, nur diesmal mit entsprechenden Feld blockiert. Gibt es trotzdem einen Weg, darf das Feld ebenfalls bebaut werden.
Man könnte sogar abfragen, ob die 8 Felder um das Feld auf dem Weg leer sind. In dem Fall gibt es immer einen alternativen Weg, da man komplett um das Feld herumbauen kann. Oder wenn man das vorherige und nächste Feld betrachtet, könnte man sogar noch genauer sagen, wann um das Feld herumgebaut werden kann. Beispielsweise so (X = blockiert, O = frei, B = betrachtetes Feld, W = Weg):

Auf jeden Fall möglich:


Alternativer Weg nötig (A* verwenden):


Ob sich das Berechnen mit den ganzen Fallunterscheidungen dann noch lohnt, oder ob man direkt den A* nimmt, muss man vermutlich einfach ausprobieren.

Das habe ich mir zumindest jetzt so überlegt, dass das so funktioniert, kann ich nicht garantieren

Ich schätze mal, dass der Sinn des Spiels (wie so oft) darin liegt den Weg so lang wie möglich zu machen und daher ist die Forderung den kürzesten Weg erhalten zu müssen eher nicht so prall.
Die Idee mit der Anzeige des Bebauungsplans stelle ich mir kompliziert vor. Ich sehe spontan zumindest keine Echtzeitlösung, um für jedes Feld zu bestimmen, ob es bebaut werden darf. Ich kenne es von anderen Tower-Defence-Games, dass man einfach erlaubt irgendwo zu bauen. Finden die Creeps keinen Pfad, nehmen sie den direkten Weg zum Ziel und zerstören solange Tower, bis wieder ein valider Pfad vorliegt, bzw. laufen sie soweit es möglich ist zum Ziel und zerstören dann Tower, um neue Pfade zu ermöglichen. Wahlweise könnte man nach jedem Tower prüfen, ob es noch einen Pfad gibt und falls nicht, diesen dann von den Creeps zerstören lassen.
Willst Du unbedingt eine Vorschau, bietet sich eventuell noch die Möglichkeit nicht von vornherein für jedes Feld anzuzeigen, ob Bebauung möglich ist, sondern beim Platzieren des Towers eine Vorschau für dieses spezielle Feld zu machen oder das Bauen an diesem Feld erst dann zu prüfen, wenn der Spieler es anordnet.

Andererseits ist 15x7 jetzt keine Killer-Größe. Hast Du mal getestet, wie lange es dauert für jedes Feld einen A* laufen zu lassen, bei einem großen Labyrinth? Du musst ja ohnehin "nur" die freien Felder checken.

Es geht ja nur darum, zu erkennen, ob die Bebauung eines Feldes den Gesamtweg blockiert. Und da sollte sich was machen lassen. Den finalen Test, ob der Spieler soeben die letztmögliche Durchgangsposition zubauen will, kann tatsächlich nur der A* liefern. Aber Du kannst ja drastisch vorselektieren, welche Felder für eine solche Blockade in Frage kommen.

Für die Horizontale gibt es neun minimal blockierende Muster:



Für die vertikale ebenso neun, abzüglich der Eckmuster, die in der Horizontalen auch schon vorkamen. Wobei mir gerade auffällt, dass man das ja nichtmal über Mustererkennung machen muss, sondern ganz banal in den gegenüberliegenden Zeilen (oder halt Spalten) Anwesenheiten zählen muss. Sobald in der Zeile darüber und darunter in der Dreier-Umgebung mindestens ein Block auftaucht, kann das Feld den Pfad blockieren. Das selbe gilt für die Vertikale dann für die Spalte links und rechts. Ob die Bebauung dann auch zu einer totalen Blockade führt, kriegst Du dann aber doch nur mit nem spekulativen A* raus.

Wenn Du das wirklich schnell haben willst, packst Du Deine Begehbar-Karte in ein Bitmuster und benutzt x86-Intrinsics wie das SSE4-popcnt. Das ist allerdings eine recht moderne Instruktion, also wird evtl. nicht jeder Server das unterstützen.

Aber ganz ehrlich: bei dieser Kartengröße und den üblichen Erfolgsquoten von Indie-Spielen ist das verschwendete Lebenszeit. Bau erstmal die direkte Lösung und schau, wie weit sie Dich trägt.

Die Idee von Schrompf ist lediglich als Filter zu verstehen, um die Anzahl Prüfungen zu reduzieren. Hast Du mal einen Benchmark gemacht, ob angesichts des doch sehr kleinen Feldes, denn überhaupt Performance-Probleme zu erwarten sind?

Na dann Thema erledigt