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

7

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.

Syed
quelle
Sind Ihre Pfade immer gleich breit (dh zwei Kacheln breit)?
Richard Marskell - Drackir

Antworten:

23

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.

SimonW
quelle
Können Sie mir einen Hinweis auf solche Algen geben, die normalerweise in Tower Defense-Spielen verwendet werden?
Syed
Nicht spezifisch für die Turmverteidigung, aber hier ist eine gute Einführung für Anfänger in A * und eine eingehendere Behandlung . Wenn Sie eine Engine verwenden, wird wahrscheinlich eine A * -Implementierung dafür verfügbar sein, und es gibt einige Pfadfindungsbibliotheken, die Sie verwenden könnten. Speziell für die Turmverteidigung wird in der Antwort auf diese Frage behauptet, dass es einen besseren Algorithmus als A * gibt, aber ich bin damit nicht vertraut
SimonW
Ich habe das Algo noch nicht codiert, um den Feind von Anfang bis Ende zu führen, da ich denke, dass die Platzierung des Gitters zuerst erfolgen sollte. Ich habe es satt, den Wand-Wand-Check wie oben beschrieben zu versuchen, da er den Turm verfolgen sollte, bis er über / unter / rechts / links Wand findet. Ich möchte das Spiel genau wie "Feldläufer" machen. Was denkst du, sollte ich weiterhin Wand-Wand-Checks versuchen oder zu einem anderen Algo wechseln? Ich bin wirklich festgefahren bei meiner Arbeit: | em mit Unity3D Game Engine
Syed
1
Mein normaler Plan beim Erstellen eines Spiels ist es, jeden Teil auf den minimal spielbaren Zustand zu bringen und dann von dort fortzufahren. Das bedeutet, schwierige Dinge zu ignorieren, wie dem Spieler zu verbieten, den Weg zu blockieren, und stattdessen sicherzustellen, dass Sie Feinde von Anfang bis Ende schicken können und der Spieler auf sie schießen kann. Sobald Sie ein Spiel haben, können Sie gewinnen oder verlieren, tun Sie, was immer es Spaß macht / nicht kaputt. Wiederholen, bis es großartig ist.
SimonW
1
Um eine Wegfindung in Unity zu erhalten, sollten Sie sich dieses kostenlose Projekt ansehen . Wenn Sie nicht viel Erfahrung haben, sind Bibliotheken eine großartige Möglichkeit, die Zeit zu reduzieren, die Sie damit verbringen, durch langweilige Dinge demotiviert zu werden. Holen Sie sich Code von überall und überall, um Ihr Spiel spielbar zu machen, und sorgen Sie sich später um die Behebung.
SimonW
3

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.

Ilmari Karonen
quelle
1

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.

BlueRaja - Danny Pflughoeft
quelle
0

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.

Ahmed Belal Hashmi
quelle
0

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.

Erwacht
quelle