Wie kann man sicherstellen, dass es in einem Tower-Defense-Spiel immer einen begehbaren Weg für Feinde gibt?

Ich mache ein 2D Tower Defense Spiel. Bisher habe ich ein 2D-Array, das als Raster für mein Spiel dient. Ich kann Türme darauf platzieren, Feinde und einige schleppende und turmschießende Sachen laufen lassen.

Jetzt stehe ich vor einem Problem in der Turmplatzierungslogik. Ich möchte, dass es für Feinde immer einen begehbaren Weg gibt, was bedeutet, dass der Benutzer den Weg nicht vollständig blockieren kann, indem er Türme platziert. Z.B. Wenn der Benutzer Türme vertikal auf einer Karte platziert, muss der Algorithmus die Platzierung eines Turms verhindern, der die vertikale Linie vervollständigt. Oder auf andere Weise muss mindestens ein freier (begehbarer) Platz vorhanden sein, damit der Feind entkommen kann.

Meine aktuelle Logik prüft in alle Richtungen, wann immer der Turm platziert wurde. Wenn sich ein Turm nach oben befindet, wird dieselbe Funktion an diesem oberen Turm erneut aufgerufen, bis er gegen eine Wand stößt. Es gibt 1 für die Aufwärtswand und 5 für die Abwärtswand zurück und gibt die Funktion (Auf- / Ab-Turm) zurück, wenn es einen Turm gibt. Hier ist der Code:

int checkCollision(tower)
{                           
    if( there is a  tower up) 
    return checkCollision(up tower);

    if(there is a tower down) 
    return checkCollision(down tower);                                      

            ......all directions.....       

    if( there is a wall on UP )     
        return 1;

    if( there is a wall DOWN ) 
        return 5;

        ....all walls......

    return 0;   
}   

Was ich jetzt möchte, ist, gleichzeitig zu prüfen, ob es eine Nordwand und eine Südwand gibt, oder andere Richtungen mit einer anderen Möglichkeit (wie Auf-Ab, Auf-Diagonale, Ab-Diagonale usw.) zu prüfen, um den Benutzer nicht zuzulassen Platziere einen Turm, da noch ein Platz für den Feind übrig sein sollte.

Ich bin im Moment mit meinem Code unzufrieden. Ich meine, mein Code sagt mir, dass eine Wand gefunden wurde, aber wie kann ich überprüfen, ob eine Wand in einer Richtung und eine Wand auch in einer anderen Richtung gefunden wird? Ich möchte nicht auf Möglichkeiten eingehen wie:

if(checkCollision(tower) == 1 && checkCollision(tower) == 5) 
  "You cannot place"

Ich möchte so etwas wie:

    if( any combination of more than 2 wall found and there is entry/exit point in between)  //so it is wall to wall
    "You cant place"

Ich habe auch versucht, Flaggen vorab zu berechnen, wenn es Wände auf zwei Seiten gibt (wie oben-unten, oben-diagonal usw.), dann lasse ich den Benutzer den Turm nicht platzieren, aber das funktioniert immer noch nicht.

Wäre es nicht einfacher, einen Pfadfindungsalgorithmus zu verwenden, um zu überprüfen, ob die KI noch eine klare Route hat? Vermutlich verwenden Sie bereits eine, um die Feinde vom Eingang zum Ausgang navigieren zu lassen. Führen Sie sie also einfach mit hinzugefügtem Turm aus. Wenn dies fehlschlägt, ist der Turm nicht zulässig.

Ich gehe davon aus, dass Sie bereits einen Code (mit dem A * -Algorithmus ) haben, mit dem die Feinde einen Pfad zu ihrem Ziel finden können. Jedes Mal, wenn der Spieler versucht, einen Turm zu platzieren, können Sie einfach ein temporäres Hindernis an der Stelle platzieren, an der sich der Turm befinden würde, und den Pfadfindungscode ausführen, um zu überprüfen, ob noch ein Pfad für die Feinde vorhanden ist.

Sie können dies auf verschiedene Arten optimieren. Wenn der neu platzierte Turm beispielsweise höchstens ein vorhandenes Hindernis berührt, kann er den Pfad nicht blockieren. Sie können auch die Ergebnisse früherer Überprüfungen speichern (zumindest bis sich etwas ändert), sodass Sie nicht jedes Mal, wenn der Spieler denselben Ort mehrmals versucht, diese erneut überprüfen müssen.

Es gibt auch einige Techniken, die nur in einigen Fällen funktionieren. Zum Beispiel:

• Wenn sich die möglichen Positionen der Türme nicht überschneiden, können Sie mithilfe eines Brückenfindungsalgorithmus genau ermitteln, welche Positionen den Weg der Feinde blockieren.

• Wenn das Spielfeld zweidimensional ist, gibt es einen cleveren Trick, der darauf beruht, dass es nur dann einen freien Weg von links nach rechts gibt, wenn keine durchgehende Wand von oben nach unten vorhanden ist. So können Sie jeden Turm (oder jedes andere Hindernis) beschriften, je nachdem, mit welcher Seite des Spielfelds er gegebenenfalls durch eine Wand verbunden ist.

  Die Pflege dieser Etiketten beim Hinzufügen neuer Türme ist einfach und schnell. Wenn ein neuer Turm zwei Seiten miteinander verbinden würde, würde er den Weg der Feinde blockieren. Wenn ein Turm entfernt wird, müssen Sie die Beschriftungen natürlich immer noch neu berechnen, aber Sie müssen dies nur tun, wenn ein Turm tatsächlich zerstört wird, und nicht jedes Mal , wenn der Spieler den Mauszeiger lediglich über einen möglichen Ort für einen neuen Turm bewegt.

Ich stimme SimonW zu, dass Sie nur Ihren Pfadalgorithmus ausführen sollten. Der Vollständigkeit halber ist hier ein Trick, der von Starcraft / Warcraft TD-Karten verwendet wird, mit denen nicht überprüft werden kann, ob der Pfadalgorithmus erfolgreich ist oder nicht.

Nehmen wir an, Feinde können überall von der Oberseite des bebaubaren Bereichs kommen und müssen sich irgendwo unterhalb des bebaubaren Bereichs bewegen. und es gibt Wände links / rechts. Führen Sie eine Flutfüllung aller Türme der linken Wand zu berühren. Wenn gefundene Türme die rechte Wand berühren, ist der Weg blockiert.

es sollte eher so sein

bool checkCollision(tower)
{
if(there is tower above)
  return checkCollision(tower above);
if(there is tower below)
  return checkCollision(tower below);
...
...
...
if(wall above)
  return 1;
if(wall below)
  return 5;
...
...
...
return 0;
}

dann später in Ihrem Code, wo Sie überprüfen möchten, ob das Platzieren des Turms zulässig ist oder nicht:

if(!checkCollision(tower above) && !checkCollision(tower below) && !checkCollision(tower left)...[check all sides]...)
  //You can place the tower
else
  //You cannot place the tower

Ändern Sie außerdem Ihren Algorithmus, um die Möglichkeit hinzuzufügen, die Koordinaten zurückzugeben, deren Wandkachel neben der Turmkette gefunden wurde. Überprüfen Sie, ob dieselbe Wandfliese zurückgegeben wurde, und verwerfen Sie sie, damit Sie auch durch Türschleifen gehen können.

Mit Turmschleife meine ich (stört meine ASCII-Kunst nicht):

--------------------------
|                        |
|   TT                   |
|TTTTTTTTT               |
|       X T              |
|       T                |
|                        |
En                       Ex
|                        |
|                        |
|                        |
|________________________|

Sie können keinen Turm bei X platzieren. Der Turm oben, der Turm auf Diagonalen, der Turm rechts und der Turm unten melden Wandkollisionen, die Koordinate der Wandkachel ist jedoch dieselbe. Dies ist, was Sie auch herausfiltern müssen.

Ganz einfach, ich habe heute gerade mein erstes Pfadfindungsprogramm erstellt. Es hat etwas mehr als 2 Stunden gedauert und abgesehen von der Deklaration von Variablen sind es nur 27 Codezeilen, einschließlich schließender Klammern.

Programmieren Sie in Ihrem Pfadfinder ein Array für alle Ihre realen Wände und ein Array für alle Ihre hipothetischen Wände. Wenn ein Spieler einen Turm auf einem Feld errichten möchte, ist das ausgewählte Feld eine hypothetische Wand. Führen Sie Ihren Pfadfinder so aus, dass er hypothetische Wände enthält. Wenn das Programm einen gefundenen Pfad enthält, kann der Turm gebaut werden. Wenn nicht, darf der Turm nicht gebaut werden.

Prost

Hier ist mein Code,

function PathFind(){

var keepgoing:Number=1;
var count:Number=1;
var smallcount:Number=0;
var keepgoing2:Boolean=false;
var startX:Array=[];
var startY:Array=[];
startX[0]=new Array();
startX[1]=new Array();
startY[0]=new Array();
startY[1]=new Array();
startX[0][1] = disc.loca;
startY[0][1] = disc.locb;
startX[1][1] = String(disc.loca)+"$";
startY[1][1] = String(disc.locb)+"$";


for(var c:Number=1; c<=keepgoing; c++){
    smallcount=0;
    for (var a:Number=1; a<=3; a++){
        for (var b:Number=1; b<=3; b++){
            if (a==2 || b==2){
                if(Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].valid==true && SpaceII[startX[0][c]+(a-2)][startY[0][c]+(b-2)]==true){
                    count++;
                    smallcount++;
                    SpaceII[startX[0][c]+(a-2)][startY[0][c]+(b-2)]=false;
                    startX[0][count]=Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].IDx;
                    startY[0][count]=Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].IDy;
                    startX[1][count]=startX[1][c]+String(Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].IDx)+"$";
                    startY[1][count]=startY[1][c]+String(Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].IDy)+"$";
                    if(Space[startX[0][c]+(a-2)][startY[0][c]+(b-2)].goal==true){
                        keepgoing2=true;
                        disc.stringA = startX[1][count].toString();
                        disc.stringB = startY[1][count].toString();
                        //thisText.text=startX[1][count] + "%" + startY[1][count] + "*";
                        success=true;
                    }                       
                }
            }
        }
    }
    if(keepgoing2==true){
        c = keepgoing;
    } else {
        keepgoing = keepgoing + smallcount;
    }
}

}}

Grundsätzlich erstellt mein Code ein Array von Paring-X- und Y-Zeichenfolgen. Dann erben meine sich bewegenden Einheiten die ersten erfolgreichen Paarungszeichenfolgen, und dann zerlegen sie die Zeichenfolgen jeweils segmentweise. Jede Koordinate wird mit einem "$" unterbrochen.

Und das Schöne an dem obigen Code ist, dass "Keepgoing" immer nur so groß wie die Rastergröße wird und mit mehr platzierten Türmen effizienter wird. Die Effizienz wird maximiert, wenn nur ein Pfad festgelegt ist.

Wenn Sie Hilfe bei dem benötigen, was ich oben für Sie habe, lassen Sie es mich einfach wissen.