Die Berechnung, die Fliesen sind lit in a tile-based game ("raytracing")

Question

Ich Schreibe eine kleine Kachel-basiertes Spiel, für die ich unterstützen möchten Licht Quellen.Aber mein Algorithmus-fu ist zu schwach, damit ich zu Ihnen kommen, um Hilfe.

Die situation ist wie folgt:Es ist eine Kachel-basierte Karten (statt, als ein 2D-array) mit einer einzelnen Lichtquelle und mehrere Gegenstände herum stehen.Ich möchte berechnen, die Fliesen sind beleuchtet von der Lichtquelle, und das im Schatten.

Eine visuelle Hilfe, wie es Aussehen würde, etwa.L ist die Lichtquelle, die Xs sind Gegenstände blockieren das Licht, die 0EN lit Fliesen, und -s sind Fliesen in den Schatten.

0 0 0 0 0 0 - - 0
0 0 0 0 0 0 - 0 0
0 0 0 0 0 X 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 L 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 X X X X 0 0
0 0 0 - - - - - 0
0 0 - - - - - - -

Ein Bruch-system wäre noch besser, natürlich, wo eine Fliese kann im halb-Schatten wegen wird teilweise verdeckt.Der Algorithmus wäre nicht perfekt sein - nur nicht offensichtlich falsch und einigermaßen schnell.

(Natürlich würde es mehrere lichtquellen, aber das ist nur eine Schleife.)

Irgendwelche Abnehmer?

Answer 1

Die roguelike Entwicklungsgemeinschaft hat ein bisschen von einer Obsession mit Line-of-sight, Field-of-View-Algorithmen.

Hier ist ein Link zu einem roguelike Wiki-Artikel zu diesem Thema: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Für meine roguelike Spiel implementierte ich einen Schattenwurf-Algorithmus ( http: // roguebasin. roguelikedevelopment.org/index.php?title=Shadow_casting ) in Python. Es war ein bisschen zusammen stellen komplizierte, aber lief einigermaßen effizient (sogar in reinem Python) und erzeugte schöne Ergebnisse.

Die „Permissive Field of View“ scheint Popularität als auch zu gewinnen: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View

Answer 2

Sie können in alle möglichen Komplexität zu bekommen mit Okklusion usw. berechnet wird, oder Sie können für den einfachen Brute-Force-Methode gehen: Für jede Zelle, verwenden Sie eine Strichzeichnung Algorithmus wie der 2004 IOCCC Sieger verwendet . Offensichtlich, dass nicht gutes Beispiel Code machen, though. ;)

Edit: Wie loren weist darauf hin, mit diesen Optimierungen, müssen Sie nur die Pixel am Rand der Karte zur Auswahl zu verfolgen

.

Answer 3

Die Algorithmen hier werden scheinen präsentiert mir mehr zu tun Berechnungen zu sein, als ich nötig sind, um zu denken. Ich habe nicht getestet, aber ich denke, dass es funktionieren würde:

Am Anfang markieren alle Pixel als leuchtet.

Für jedes Pixel auf dem Rand der Karte: Wie Arachnidus vorgeschlagen, Bresenham verwenden, um eine Linie von dem Pixel auf das Licht zu verfolgen. Wenn diese Zeile auf ein Hindernis trifft markieren dann alle Pixel vom Rand bis kurz hinter das Hindernis wie im Schatten zu sein.

Answer 4

Schnell und schmutzig:

(Je nachdem, wie groß das Array)

• Schleife durch jede Fliese
• eine Linie zum Licht zeichnen
• Wenn eine Pary der Linie ein X trifft, dann ist es im Schatten
• (Optional): Berechnung der Menge von X die Linie durchläuft und tun Phantasie Mathematik, den Anteil der Fliese im Schatten determint. NB: Diese durch Anti-Aliasing die Linie zwischen den Fliesen getan werden könnte, und das Licht (also bei anderen Fliesen entlang der Strecke im Rückblick auf die Lichtquelle) während der Schwellenprozedur diese wird als kleine Anomalien erscheinen. In Abhängigkeit von der Logik verwendet man könnte möglicherweise bestimmen, wie viel (wenn überhaupt) die Fliese im Schatten ist.

Sie können auch eine Spur von dem Pixel getestet wurden halten könnte daher die Lösung ein wenig optimieren und nicht erneut Testpixel zweimal.

Dies könnte Kuppel sein ziemlich gut durch die Bildbearbeitung mit und geraden Linien zwischen pixles (Fliesen) zeichnen Wenn die Linien halbtransparent sind und die X-Blöcke sind semi-transparent wieder. Sie können das Bild Schwelle, um zu bestimmen, ob die Linie ein ‚X‘ geschnitten hat

Wenn Sie eine Option haben ein 3rd-Party-Tool zu verwenden, dann Id wahrscheinlich es nehmen. Auf lange Sicht schneller sein, es könnte sich herausstellen, aber Sie würden verstehen, weniger über das Spiel.

Answer 5

Dies ist nur zum Spaß:

Können Sie replizieren die Doom-3-Ansatz in 2D, wenn Sie zuerst eine Schritt konvertieren Sie Ihre Kacheln in Linien.Für Beispiel,

- - - - -
- X X X -
- X X - -
- X - - -
- - - - L

...reduziert werden würde, die in drei Linien verbinden die Ecken des festes Objekt in ein Dreieck.

Und dann tun, was der Doom-3-engine gilt:Aus der Sicht der Lichtquelle, sollten Sie jede "Wand", die Gesichter, das Licht.(In dieser Szene, nur die Diagonale betrachtet werden.) Für jede solche Zeile, das Projekt in ein Trapez, dessen vordere Kante ist die original-Linie, deren Seiten liegen auf Linien, die aus dem Licht der Quelle durch jeden Endpunkt, und deren Rückseite ist weit Weg, vorbei an der ganzen Szene.Es ist also ein Trapez, dass "Punkte" die Licht.Es enthält alle für den Raum, die Wand wirft seine Schatten auf.Füllen Sie jede Fliese in diesem Trapez mit der Dunkelheit.

Gehen Sie durch alle diese Linien, und Sie werden am Ende mit einer "Schablone", die enthält alle die Kacheln sichtbar von der Lichtquelle.Füllen Sie die Fliesen mit der hellen Farbe.Möchten Sie vielleicht, um Licht in die Fliese ein wenig weniger, als Sie bekommen, Weg von der Quelle ("attenuation") oder andere ausgefallene Sachen.

Wiederholen Sie den Vorgang für jede Lichtquelle in Ihrer Szene.

Answer 6

Um zu überprüfen, ob eine Fliese im Schatten ist, müssen Sie eine gerade Linie zurück auf die Lichtquelle ziehen. Wenn die Zeile eine andere Kachel schneidet, die besetzt ist, dann ist die Platte, die Sie testeten im Schatten. Raytracing-Algorithmen tun dies für jedes Objekt (in Ihrem Fall Kachel) in der Ansicht.

Der Raytracing Artikel auf Wikipedia hat Pseudo-Code.

Answer 7

Hier ist eine sehr einfache, aber ziemlich effektive Methode, die verwendet die lineare Zeit, in der die Anzahl der Kacheln auf dem Bildschirm.Jede Fliese ist entweder undurchsichtig oder transparent (, dass ist, die uns gegeben), und jeder kann sichtbar oder schattiert (das ist, was wir versuchen zu berechnen).

Wir beginnen mit der Markierung der avatar selbst als "sichtbar".

Dann wenden wir diese rekursive Regel, um zu bestimmen, die Sichtbarkeit der übrigen Fliesen.

1. Wenn die Kachel ist auf der gleichen Zeile oder Spalte wie der avatar, dann ist es nur sichtbar, wenn der benachbarten Fliese näher der avatar ist sichtbar und transparent.
2. Wenn die Kachel ist auf einem 45-Grad-diagonalen von dem avatar, dann ist es nur sichtbar, wenn der benachbarten diagonalen Fliesen (in Richtung der avatar) ist sichtbar und transparent.
3. In allen anderen Fällen betrachten die drei benachbarten Fliesen, die sind näher an den avatar als die Fliese in Frage.Zum Beispiel, wenn diese Fliese ist bei (x,y) und ist oben und rechts neben dem avatar, dann die drei Steine, die zu berücksichtigen sind (x-1, y), (x, y-1) (x-1, y-1).Die Fliese im Frage ist sichtbar, wenn alle diese drei Kacheln sind sichtbar und transparent.

Um diese Arbeit zu machen, die Fliesen, die geprüft werden muss in einer bestimmten Reihenfolge, um sicherzustellen, dass die rekursive Fälle sind bereits berechnet.Hier ist ein Beispiel von einer Arbeitsgruppe der Bestellung, beginnend von 0 (das ist der avatar selbst) und zählen auf:

9876789
8543458
7421247
6310136
7421247
8543458
9876789

Kacheln mit der gleichen Nummer können überprüft werden in beliebiger Reihenfolge untereinander.

Das Ergebnis ist nicht schön, schattenwurf, sondern berechnet glaubwürdig tile Sichtbarkeit.

Answer 8

TK-Lösung ist die, die Sie in der Regel für diese Art der Sache verwenden würden.

Für das Teilbeleuchtungsszenario könnte Sie es so, dass, wenn eine Kachel ergibt im Schatten zu sein, wird diese Fliese dann in 4 Kacheln aufgeteilt und jeder von denen getestet wird. Sie könnten dann aufgeteilt, dass so viel wie Sie wollen?

Edit:

Sie können es auch ein bisschen von nicht Testen jeder der Kacheln neben einem Licht optimieren heraus - dies wichtiger wäre zu tun, wenn Sie mehrere Lichtquellen haben, ich denke ...

Answer 9

Ich habe eigentlich erst vor kurzem schrieb diese Funktionalität in einem meiner Projekte.

void Battle::CheckSensorRange(Unit* unit,bool fog){
    int sensorRange = 0;
    for(int i=0; i < unit->GetSensorSlots(); i++){
        if(unit->GetSensorSlot(i)->GetSlotEmpty() == false){
            sensorRange += unit->GetSensorSlot(i)->GetSensor()->GetRange()+1;
        }
    }
    int originX = unit->GetUnitX();
    int originY = unit->GetUnitY();

    float lineLength;
    vector <Place> maxCircle;

    //get a circle around the unit
    for(int i = originX - sensorRange; i < originX + sensorRange; i++){
        if(i < 0){
            continue;
        }
        for(int j = originY - sensorRange; j < originY + sensorRange; j++){
            if(j < 0){
                continue;
            }
            lineLength = sqrt( (float)((originX - i)*(originX - i)) + (float)((originY - j)*(originY - j)));
            if(lineLength < (float)sensorRange){
                Place tmp;
                tmp.x = i;
                tmp.y = j;
                maxCircle.push_back(tmp);
            }
        }
    }

    //if we're supposed to fog everything we don't have to do any fancy calculations
    if(fog){
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
        }
    }else{

        bool LOSCheck = true;
        vector <bool> placeCheck;

        //have to check all of the tiles to begin with 
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            placeCheck.push_back(true);
        }

        //for all tiles in the circle, check LOS
        for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
            vector<Place> lineTiles;
            lineTiles = line(originX, originY, maxCircle[circleI].x, maxCircle[circleI].y);

            //check each tile in the line for LOS
            for(int lineI = 0; lineI < (int) lineTiles.size(); lineI++){
                if(false == CheckPlaceLOS(lineTiles[lineI], unit)){
                    LOSCheck = false;

                    //mark this tile not to be checked again
                    placeCheck[circleI] = false;
                }
                if(false == LOSCheck){
                    break;
                }
            }

            if(LOSCheck){
                Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
            }else{
                LOSCheck = true;
            }
        }
    }

}

Es gibt einige zusätzliche Sachen drin, dass du nicht brauchen, wenn Sie es für den eigenen Gebrauch sind anzupassen. Der Typ Ort ist einfach definiert als x und y-Position für Komfort zuliebe.

Die Linienfunktion wird von Wikipedia mit sehr kleinen Änderungen gemacht. Statt x y-Koordinaten von Ausdrucken habe ich es einen Platz Vektor mit allen Punkten in der Zeile zurückzukehren. Die CheckPlaceLOS Funktion gibt nur wahr oder falsch ist, basierend auf, wenn die Fliese ein Objekt auf sich hat. Es gibt einige weitere Optimierungen, die damit fertig werden könnte, aber das ist in Ordnung für meine Bedürfnisse.

Answer 10

Ich weiß, das ist Jahre alte Frage, aber für alle, für diese Art von Sachen suchen würde Ich mag eine Lösung anbieten ich für eine roguelike meiner eigenen einmal verwendet; manuell „vorberechnet“ FOV. Wenn Sie Blickfeld der Lichtquelle einen maximalen Außen Abstand hat es wirklich nicht sehr viel Mühe Hand der Schatten durch Blockieren Objekte erstellt zeichnen. Sie müssen nur 1/8 des Kreises (plus die geraden und diagonalen Richtungen) ziehen; Sie können symmerty für die anderen eigths verwenden. Sie werden so viele Shadowmaps haben, wie Sie Quadrate haben in diesem 1 / 8th eines Kreises. Dann einfach oder sie nach Objekten zusammen.

Die drei wichtigsten Profis hierfür sind: 1. Es ist sehr schnell umgesetzt, wenn es richtig 2. Sie erhalten zu entscheiden, wie der Schatten geworfen werden soll, nicht zu vergleichen, welche algorith Griffe der Situation der besten 3. Keine seltsame algorith induzierte Grenzfälle, die Sie müssen irgendwie beheben

Die con ist, dass Sie nicht wirklich ein Spaß-Algorithmus zu implementieren bekommen.

Answer 11

Ich habe tilebased Sichtfeld in einer einzigen C-Funktion implementiert. hier ist es: https://gist.github.com/zloedi/9551625

Answer 12

Wenn Sie nicht die Zeit verbringen möchten, neu zu erfinden / neu implementieren diese, es gibt viele Spiele-Engines gibt. Ogre3D ist ein Open-Source-Spiel-Engine, sowie Klang und Spielsteuerungen voll Beleuchtung unterstützt.