Laicheinheiten in einer Welt, die Perlin-Lärm erzeugt?

16

Es gibt einige Probleme, auf die ich in meinem Perlin-Spiel gestoßen bin. Schauen Sie sich den beigefügten Screenshot unten an.

Bildbeschreibung hier eingeben

Die weißen Bereiche, die Sie sehen, sind Wände und die schwarzen Bereiche sind begehbar. Das Dreieck in der Mitte ist der Spieler.

Ich habe die Physik in dieses Spiel implementiert, indem ich sie auf eine Textur (weiße oder schwarze Pixel) gezeichnet und diese dann von der CPU abgerufen habe.

Jetzt stehe ich jedoch vor einem anderen Problem. Ich möchte, dass Einheiten (oder Creeps, wie auch immer Sie sie nennen) ständig am Rand des Bildschirms erscheinen. Der Punkt hier ist, dass es im letzten Spiel einen "Nebel des Krieges" geben wird, der es dem Spieler sowieso nicht erlaubt, so weit zu sehen.

Ich dachte, ich könnte einfach die Pixel am Rand des Bildschirms scannen und sehen, ob ihre physikalische Textur schwarz ist, und dann willkürlich dort Zeug erzeugen. Wenn Sie sich jedoch den Screenshot noch einmal ansehen, gibt es (in der oberen linken Ecke) ein Beispiel dafür, wo ich nicht möchte, dass die Gänsehaut entsteht (da sie den Spieler von dort aus nicht erreichen können). .

Ist es möglich, dass die GPU diese Spawn-Spots für mich bestimmt oder auf eine andere Art und Weise? Ich überlegte, Vektoren zwischen dem vorgeschlagenen Punkt am Rand des Bildschirms und dem Player zu erstellen und sie dann alle 10 Voxel zu verfolgen und zu prüfen, ob eine Wand kollidiert, bevor ich dort eine Einheit hervorbringe.

Die oben vorgeschlagene Lösung ist jedoch möglicherweise zu CPU-intensiv.

Irgendwelche Vorschläge zu diesem Thema?

Hinweis 1 Für die geborenen Einheiten möchte ich keine Pfadfindung verwenden, um Wandkollisionen zu vermeiden, da diese Einheiten auf den Spieler zu rennen. Daher müssen die Einheiten am Rand des Bildschirms erscheinen, an einem Ort, an dem das Gehen in einer geraden Linie in Richtung des Spielers nicht mit Wänden kollidieren würde.

Mathias Lykkegaard Lorenzen
quelle
1
Bewegt sich die Karte mit dem Spieler oder bewegt sich der Spieler in der Karte? Das heißt, wird sich die Karte ändern? Wenn nicht, würde ich vorschlagen, alle nicht erreichbaren Punkte bei der Generierung auszufüllen, damit Sie sich nicht um sie kümmern müssen.
dlras2
Wenn sich der Spieler bewegt, benötigen die Einheiten eine Wegfindungsmethode. Wenn du konkave Gebiete haben willst, wirst du dieses Problem haben und du musst eine Lösung für die sich bewegende Einheit finden, die versucht, einen sich bewegenden Spieler zu erreichen.
Blau
1
Oder, um Blaus Kommentar anders auszudrücken: Ihre Frage hat nachweislich keine gültige Antwort (abgesehen von dem trivialen Fall einer Karte ohne Wandkacheln / Pixel), wenn sich der Spieler bewegen kann. Es ist weiterhin erforderlich, dass Sie definieren, was Sie mit "Gerade" meinen, um eine Antwort zu erhalten, wenn der Spieler stationär ist.
Martin Sojka

Antworten:

3

Für diesen Job gibt es einen ziemlich nützlichen Algorithmus, der viel effizienter ist als der Flutungsalgorithmus in dieser Situation (seine Komplexität ist die Laufzeit proportional zur Grenzgröße und nicht zum überfluteten Bereich): Es ist der Marschquadrat-Algorithmus. Das Konzept ist einfach: Beginne den Ort des Spielers (Mittelpunkt des Bildschirms), wähle eine Richtung und gehe, bis du eine Wand findest. Wenn Sie mit der Wand kollidieren, starten Sie den Algorithmus: Sie wählen eine Ausrichtung (nach oben oder unten) und beginnen, über die Grenze dieses Bereichs zu marschieren und die Pixel hervorzuheben. Dies gibt Ihnen die innere Grenze für den erlaubten Bereich. Anschließend prüfen Sie einfach, ob die Kandidatenpunkte für Laicheinheiten an dieser Grenze liegen.

Dies ist das Prinzip, dem Sie beim Ausführen der Grenze folgen sollten:

http://en.wikipedia.org/wiki/File:Marchsquares.png (meh ich kann noch keine Bilder posten)

Beschreibung von Wikipedia (obwohl es viel komplexer ist, weil es für andere Anwendungen verwendet wird):

http://en.wikipedia.org/wiki/Marching_squares

allmächtig
quelle
10

Machen Sie eine Flutfüllung von der Position des Spielers; Jeder "überflutete" Bereich ist dann ein gültiger Spielbereich, und alle anderen sind Wände.

EDIT: Was die zusätzliche Anforderung "in einer geraden Linie erreichbar" angeht, denken Sie daran, dass Sie diese in einem diskreten Raum etwas weiter definieren müssen. Zum Beispiel könnten alle oben genannten Pfade in einer solchen Umgebung eine gültige "Gerade" sein, und ich habe gesehen, dass sie alle in einem Spiel irgendwann verwendet wurden:

"Gerade" -Varianten

Insbesondere sind die meisten von ihnen nicht kommutativ. Das bedeutet nicht, dass Sie A auch von B aus erreichen können, nur weil Sie B von A aus in einer "geraden Linie" erreichen können. Weder ist das Gegenteil unbedingt der Fall.

Außerdem stellt sich die Frage, wie Sie mit diagonalen Bewegungen umgehen, wenn einer oder beide "Seiten" -Punkte blockiert sind.

Martin Sojka
quelle
Kann dies vollständig in HLSL implementiert werden?
Mathias Lykkegaard Lorenzen
@ Mathias Lykkegaard Lorenzen: Ja, im Zweifel, indem Sie jeden Schritt des Algorithmus als Pixel-Shader ausführen und zum Beispiel zwischen zwei Textur-Zielen rendern, aber ... warum ? Sie werden wahrscheinlich die Informationen des Algorithmus auf der CPU sowieso benötigen, um zumindest den Pfad zu finden.
Martin Sojka
1
@ Mathias Lykkegaard Lorenzen: Das ist aber etwas anders, als du es dir gewünscht hast. In diesem Fall: Wie definieren Sie eine "gerade Linie" angesichts Ihres Partitionierungsschemas für diskrete Bereiche?
Martin Sojka
2
Auch wenn Sie die Pfadfindung nicht verwenden möchten, ist es möglich, die CPU zur Ausführung des Floodfill-Jobs aufzufordern. Denken Sie jedoch daran, dass Sie Floodfill nur einmal aufrufen müssen, und dann eine dreifarbige Textur haben, die Wand, freie Räume und spawnbare Räume definiert. Für eine 4096x4096-Textur würde es weniger als eine Sekunde dauern, bis die CPU den Floodfill-Job abgeschlossen hat.
Ali1S232
1
Der Punkt ist, dass Sie diese Flutfüllung nur einmal ausführen müssen, und selbst wenn sich Ihr Terrain während des Spiels ändert, müssen Sie nur die betroffenen Abschnitte aktualisieren und Flutfüllung durchlaufen lassen, was höllisch schnell ist.
TravisG
1

Wie wäre es, wenn Sie die Brut einfach passieren lassen? Darin sehe ich kein besonderes Problem.

aaaaaaaaaaa
quelle
Und wenn sie hinter einer Mauer laichen? Wie würden Sie sie dazu bringen, den Spieler zu erreichen?
Mathias Lykkegaard Lorenzen
1
Es könnte ein Problem sein, wenn das Spiel ein Szenario hat, in dem alle Feinde getötet werden, und es 50 Feinde hervorbringt, aber einige wurden hinter der Mauer hervorgebracht. Der Spieler wäre nicht in der Lage, die Feinde zu töten, und das Szenario wäre nicht zu Ende.
Lie Ryan
1
Andere Einheiten können den Spieler möglicherweise immer noch nicht erreichen. Dies hängt davon ab, wie sich der Spieler bewegt, nachdem sie erzeugt wurden. In beiden Fällen müssen Sie einige Einheiten entsperren.
aaaaaaaaaaa
Der Nebel des Krieges wird die beschissenen Laichen bedecken
KRB
1
Das funktioniert sowieso nicht, wenn sich der Spieler bewegt.
aaaaaaaaaaa
1

Wenn es wichtig ist, dass Sie nur Punkte mit einer gültigen geraden Linie für den Player markieren, können Sie einen Algorithmus wie den folgenden verwenden (es ist ein C ++ - Code), der mehr verbraucht als normales Floodfill. Es kann einige kleinere Fehler geben (ich bin froh, wenn jemand sie korrigiert), da ich den Code nicht selbst getestet habe, aber Sie werden auf die Idee kommen.

void straightlineFill(Point startPoint, Texture target)
{
    queue<Point> pointQueue;
    for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(startPoint.x + dx, startPoint.y + dy));
    while (!pointQueue.empty())
    {
        point front = pointQueue.front();
        pointQueue.pop();
        if (target.pixelAt(front) == COLOR_SPAWNABLE||
            target.pixelAt(front) == COLOR_WALL||
            target.pixelAt(front) == COLOR_NOT_SPAWNABLE)
                continue;
        taraget.setPixelAt(front, colorFilled); 
        for (int dx = -1;dx <=1;dx ++)
            for(int dy = -1;dy <=1;dy++)
                if(dx != 0 && dy != 0)
                    pointQueue.push(point(front.x + dx, front.y + dy));
        // up until now was the normal floodfill code
        // and here is the part that will do the real straight line checking

        // lineDX & lineDY will keep how much the line we are checking is skewed
        int lineDX = front.x - startPoint.x;
        int lineDY = front.y - startPoint.y;

        // step will show us how much we have to travel to reach each point of line
        point step;
        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDX < 0)
                step = point(-1,0);
            if (lineDX == 0)
                if (lineDY < 0)
                    step = point(0,-1);
                else
                    step = point(0,1);
            if (lineDX > 0)
                step = point(1,0);
        }

        if (abs(lineDX) < abs(lineDY))
        {
            if (lineDY < 0)
                step = point(0,-1);
            if (lineDY == 0)
                if (lineDX < 0)
                    step = point(-1,0);
                else
                    step = point(1,0);
            if (lineDY > 0)
                step = point(0,1);
        }

        // moved will keep how much we have traveled so far, it's just some value that will speed up calculations and doesn't have any mathematical value
        point moved = 0;

        // spawnable will keep if the current pixel is a valid spawnpaint

        bool spawnable = true;

        // now we will travel on the straight line from player position to the edges of the map and check if whole line is valid spawn points or not.

        while (target.isInside(front))
        {
            front = front + step;
            moved = moved + point(step.x * lineDX, step.y * lineDY);
            if (step.x != 0 && moved.x < moved.y)
            {
                moved.x = moved.x - lineDY * sign(lineDY);
                front.y = front.y + sign(lineDY);
            }
            if (step.y != 0 && moved.y < moved.x)
            {
                moved.y = moved.y - lineDX * sign(lineDX);
                front.x = front.x + sign(lineDX);
            }

            if (target.getPixelAt(front) == COLOR_WALL)
                spawnable = false;

            if (spawnable)
            {
                target.setPixelAt(front,COLOR_SPAWNABLE);
                for (int dx = -1;dx <=1;dx ++)
                    for(int dy = -1;dy <=1;dy++)
                        if(dx != 0 && dy != 0)
                            pointQueue.push(point(front.x + dx, front.y + dy));             
            }
            else
            {
                target.setPixelAt(front,COLOR_NOT_SPAWNABLE);
            }
        }
    }
}
Ali1S232
quelle
1

Sie können die Karte mit Farben füllen, die konvexe Bereiche darstellen. Auf diese Weise können Sie Ihre Einheit erzeugen, wenn sie im selben Bereich liegt. Oder Sie können leichter nach erreichbaren Bereichen suchen.

Dies sind statische Daten, damit Sie sie vorberechnen können.

Sie mussten die Bildfindungspunkte füllen, an denen es zu einem Wechsel von konvav zu konvex kommt. Optisch scheint es einfach zu finden. Sie haben zwei Situationen:

  1. Horizontal: Wo sich Orange zu Blau ändert.
  2. Vertikal: Rot wechselt zwischen Grün und Orange.

Bildbeschreibung hier eingeben

Blau
quelle
Das geht nicht. Sehen Sie sich unten rechts den Fleck im roten Bereich an. Es ist vollständig konvex, sodass keine Änderung vorgenommen werden muss, um die Verwendung einer anderen Farbe zu veranlassen. Es ist jedoch klar, dass keine gerade Linie vom unteren Rand des Rots zum rechten Rand des Rots am unteren Rand vorhanden ist.
Loren Pechtel
@Loren Pechtel das ist handgemacht, du hast recht, da ist ein Fehler, es ist meine Schuld, aber du kannst erkennen, dass es die gleiche Situation ist wie beim Übergang von Orange nach Blau.
Blau
@Loren Pechtel, erinnere daran, dass das Ziel darin besteht, das Laichen in Bereichen wie Gelb zu vermeiden. Diese Methode stellt sicher, dass ein Gegner, der sich in dem Bereich befindet, in dem sich der Spieler befindet, erreichbar ist, wenn Sie ihn freigeben. Die Implementierung mag natürlich schwierig sein, aber die Idee ist gültig.
Blau
Ihre Überarbeitung hilft nicht. Zwei Punkte auf einer konvexen Kurve haben niemals eine legale Gerade zwischen sich, Punkt. Weitere Abteilungen werden nicht helfen.
Loren Pechtel
Bitte überprüfen Sie die Definition von konvex unter Bezugnahme auf Bereiche oder Punktmengen ... en.wikipedia.org/wiki/Convex
Blau
1

Hier ist etwas, das ich tatsächlich in meinem eigenen Spiel verwendet habe (2d simplex Noise Generated World, fast genau wie deins) - Rays. Beginne beim Spieler, bestimme eine Orientierung (zufällig, wenn du willst) und gehe entlang dieser Linie, bis du auf etwas triffst (Bildschirmrand ODER Asteroid). Wenn Sie auf den Bildschirmrand treffen (und nicht auf einen Asteroiden / weißen Fleck), wissen Sie, dass eine gerade, offene Linie vom Bildschirmrand zum Player verläuft. Dann laichen Sie ein Monster an der Stelle, an der Sie getroffen haben. Wenn Sie einen Asteroiden treffen, wiederholen Sie den Test.

khyperia
quelle
0

Eine andere (nicht GPU-) Lösung, die Sie verwenden können, ist die Pfadfindung. Suchen Sie vor dem Zeichnen der Karte von jedem potenziellen Startpunkt an jedem Rand der Karte aus nach Pfaden und prüfen Sie, ob es einen Pfad zur Mitte gibt. Eine * -Pfadfindung ist in Bezug auf Kosten / Leistung in Ordnung, aber Sie können dies tun, bevor das Spiel beginnt, wenn dies ein Problem ist.

Jeder Spawnpunkt, der keinen Pfad hat, kann in eine Ausschlussliste aufgenommen werden. oder umgekehrt (jeder Punkt mit einem Pfad kann auf eine Einschlussliste gesetzt werden).

ashes999
quelle