"Sichtlinie" mit Hindernissen im 2D-Raster simulieren?

10

Stieß auf ein interessantes Problem. Ich muss herausfinden, wie man die Sichtlinie simuliert - einfach genug, nur auf einem 2D-Gitter mit Hindernissen. Entweder ist eine Gitterzelle sichtbar oder nicht.

Ich kann etwas wirklich rudimentäres in Gang bringen - wie das Verteilen von n Feldern vom Spieler oder das Blockieren der horizontalen Ausbreitung, wenn ein benachbartes Hindernis erkannt wird, aber ich kann mich nicht damit leben lassen. Viele andere Apps verwenden ausgefeiltere Methoden, die die Sichtlinie um Ecken usw. neigen, und ich möchte auf dem neuesten Stand sein.

Bisher war DCSS meine Inspirationsquelle, wenn ich ratlos bin. Ich hoffe, dass ich etwas in die Nähe dessen bekomme, was sie haben: http://crawl.sz.org/ .

Jeder Einblick wäre dankbar - danke für die Hilfe!

(Verzeihen Sie, wenn dies peinlich noobisch ist - erst vor ein paar Wochen mit dem Spielentwickler begonnen und versucht, aufzuholen.)

CodeMoose
quelle
2
Was genau meinen Sie mit "Neigung der Sichtlinie um Ecken"?
Djentleman
Das Beste, was ich sagen kann, ist, sich ein Spiel auf crawl.sz.org anzusehen. Wenn der Spieler beispielsweise unter einer 5 Kacheln breiten horizontalen Wand steht, bricht die Sichtlinie über der horizontalen Ebene dieser Wand - jedoch nicht unrealistisch darüber hinaus. Das Beste, was ich annähern konnte, ist, die Sichtlinie in der horizontalen Ebene der Wand zu halten.
CodeMoose

Antworten:

7

Ray Casting ist eine sehr schnelle und effiziente Methode, um die Sichtlinie zu bestimmen. Im Grunde geht es darum, einen Strahl (denken Sie an einen unendlichen Laser, der nicht umgeleitet werden kann) von einer bestimmten Position in eine bestimmte Richtung zu senden. Mit diesem Strahl können Sie beispielsweise bestimmen, welche Punkte er schneidet und wie weit er vom Ursprung entfernt ist, als er einen bestimmten Punkt überquert hat.

So könnte beispielsweise in einem Spieler / Feind-Szenario der Strahl vom Feind ausgehen, wobei die Richtung der Standort des Spielers ist. Wenn der Strahl mit einem festen Plättchen kollidiert, kann der Feind den Spieler nicht sehen. Wenn nicht, kann der Feind den Spieler sehen.

Hier ist ein ausgezeichnetes Tutorial, das helfen sollte.

Sie können auch den Linienalgorithmus von Bresenham berücksichtigen (aufsummiert, es schafft Linien) für etwas, das Fliesen leichter skaliert werden könnten.

Djentleman
quelle
1
Scheint der richtige Weg zu sein - besonders der von Bresenham. Danke für die Hilfe djent!
CodeMoose
3

Ich habe Code gebloggt , um die Sichtlinie aus einer Höhenkarte zu berechnen. Eine einfache flache Karte mit Hindernissen ist nur eine sehr flache Höhenkarte, und diese Implementierung ist immer noch vollständig anwendbar.

Geben Sie hier die Bildbeschreibung ein

Hier ist es in C ++ und seine O(n); Wenn Sie die maximale Höhe in der Karte kennen, können Sie eine Scanlinie verfolgen, bei der keine Strahlen mehr unter dieser Höhe verbleiben, und zwar frühzeitig:

typedef std::vector<float> visbuf_t;

inline void map::_visibility_scan(const visbuf_t& in,visbuf_t& out,const vec_t& eye,int start_x,int stop_x,int y,int prev_y) {
    const int xdir = (start_x < stop_x)? 1: -1;
    for(int x=start_x; x!=stop_x; x+=xdir) {
        const int x_diff = abs(eye.x-x), y_diff = abs(eye.z-y);
        const bool horiz = (x_diff >= y_diff);
        const int x_step = horiz? 1: x_diff/y_diff;
        const int in_x = x-x_step*xdir; // where in the in buffer would we get the inner value?
        const float outer_d = vec2_t(x,y).distance(vec2_t(eye.x,eye.z));
        const float inner_d = vec2_t(in_x,horiz? y: prev_y).distance(vec2_t(eye.x,eye.z));
        const float inner = (horiz? out: in).at(in_x)*(outer_d/inner_d); // get the inner value, scaling by distance
        const float outer = height_at(x,y)-eye.y; // height we are at right now in the map, eye-relative
        if(inner <= outer) {
            out.at(x) = outer;
            vis.at(y*width+x) = VISIBLE;
        } else {
            out.at(x) = inner;
            vis.at(y*width+x) = NOT_VISIBLE;
        }
    }
}

void map::visibility_add(const vec_t& eye) {
    const float BASE = -10000; // represents a downward vector that would always be visible
    visbuf_t scan_0, scan_out, scan_in;
    scan_0.resize(width);
    vis[eye.z*width+eye.x-1] = vis[eye.z*width+eye.x] = vis[eye.z*width+eye.x+1] = VISIBLE;
    scan_0.at(eye.x) = BASE;
    scan_0.at(eye.x-1) = BASE;
    scan_0.at(eye.x+1) = BASE;
    _visibility_scan(scan_0,scan_0,eye,eye.x+2,width,eye.z,eye.z);
    _visibility_scan(scan_0,scan_0,eye,eye.x-2,-1,eye.z,eye.z);
    scan_out = scan_0;
    for(int y=eye.z+1; y<height; y++) {
        scan_in = scan_out;
        _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y-1);
        _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y-1);
    }
    scan_out = scan_0;
    for(int y=eye.z-1; y>=0; y--) {
        scan_in = scan_out;
        _visibility_scan(scan_in,scan_out,eye,eye.x,-1,y,y+1);
        _visibility_scan(scan_in,scan_out,eye,eye.x,width,y,y+1);
    }
}
Wille
quelle
Das ist gut, aber ich denke weit mehr als er danach sucht, wenn er etwas wie den Link will, den er gepostet hat.
Djentleman
Sehr ausführlich und beeindruckend, aber djent hat recht - weit außerhalb meines Anwendungsbereichs. Danke für den Beitrag!
CodeMoose
@CodeMoose eh seinen Arbeitscode; Einfach ausschneiden und einfügen, wörtlich in die Sprache übersetzen, auf die Sie abzielen. Es ist eine Implementierung von Bresenham, die schrittweise durchgeführt wird, sodass jedes Quadrat nur einmal besucht wird. Wenn Sie für jedes Gitterfeld eine Bresenham-Linie mit dem Spieler machen, werden Sie feststellen, dass diese massiv langsamer ist.
Will
Guter Punkt wird
CodeMoose