Calculer les tuiles allumées dans un jeu basé sur des tuiles ("lancer de rayons" & # 8221;)

Question

J'écris un petit jeu basé sur des tuiles, pour lequel je voudrais soutenir les sources de lumière. Mais mon algorithme-fu est trop faible, je viens donc à votre secours.

La situation est la suivante: Il existe une carte basée sur des mosaïques (conservée sous forme de tableau 2D), contenant une seule source de lumière et plusieurs éléments placés à proximité. Je veux calculer quelles tuiles sont éclairées par la source de lumière et lesquelles sont dans l'ombre.

Une aide visuelle de ce à quoi cela ressemblerait, environ. Le L est la source de lumière, les X sont des éléments bloquant la lumière, les 0 sont des mosaïques allumées et les -s sont des mosaïques dans l’ombre.

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 - - - - - - -

Un système fractionnaire serait encore mieux, bien sûr, dans lequel une tuile peut être à moitié ombragée du fait qu’elle est partiellement masquée. L’algorithme n’aurait pas à être parfait, mais il ne serait pas faux et très rapide.

(Bien sûr, il y aurait plusieurs sources de lumière, mais ce n'est qu'une boucle.)

Des preneurs?

Answer 1

La communauté de développement de roguelike est un peu obsédée par les algorithmes de champ de vision en visibilité directe.

Voici un lien vers un article wiki roguelike sur le sujet: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Pour mon jeu réaliste, j’ai mis en œuvre un algorithme de diffusion d’ombres ( http: // roguebasin. roguelikedevelopment.org/index.php?title=Shadow_casting ) en Python. C'était un peu compliqué à mettre en place, mais cela fonctionnait raisonnablement efficacement (même en pur Python) et donnait de bons résultats.

Le " champ de vision permissif " semble gagner aussi en popularité: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of__view

Answer 2

Vous pouvez entrer dans toutes sortes de complexités en calculant l'occlusion, etc., ou vous pouvez opter pour la méthode de la force brute simple: Pour chaque cellule, utilisez un algorithme de dessin au trait tel que le Algorithme de ligne de Bresenham pour examiner chaque cellule entre la cellule actuelle et la source de lumière. Si certaines cellules sont remplies ou (si vous n’avez qu’une seule source de lumière) des cellules qui ont déjà été testées et qui se trouvent dans l’ombre, votre cellule est dans l’ombre. Si vous rencontrez une cellule connue pour être allumée, votre cellule sera également allumée. Une optimisation simple consiste à définir l’état de toutes les cellules rencontrées le long de la ligne, quel que soit le résultat final.

C’est plus ou moins ce que j’ai utilisé dans mon contribution primée à l'IOCCC de 2004 . Évidemment, cela ne fait pas un bon exemple de code, cependant. ;)

Modifier: comme le souligne loren, avec ces optimisations, il vous suffit de sélectionner les pixels situés le long du bord de la carte pour en faire le suivi.

Answer 3

Les algorithmes présentés ici me semblent faire plus de calculs que nécessaire. Je n'ai pas testé cela, mais je pense que cela fonctionnerait:

Initialement, marquez tous les pixels comme allumés.

Pour chaque pixel situé sur le bord de la carte: comme l’a suggéré Arachnid, utilisez Bresenham pour tracer une ligne allant du pixel à la lumière. Si cette ligne rencontre un obstacle, marquez tous les pixels du bord au-delà de l’obstruction comme étant dans l’ombre.

Answer 4

Rapide et sale:

(En fonction de la taille du tableau)

• Boucle dans chaque tuile
• tracez une ligne vers la lumière
• Si une partie de la ligne rencontre un X, elle est dans l'ombre
• (Facultatif): calcule la quantité de X traversée par la ligne et effectue des calculs compliqués pour déterminer la proportion de la mosaïque dans l’ombre. NB: Ceci pourrait être fait en anti-aliasing de la ligne entre la tuile et la Lumière (en regardant donc les autres tuiles le long du trajet jusqu'à la source de lumière) au cours de la procédure de seuillage, elles apparaîtront sous forme de petites anomalies. En fonction de la logique utilisée, vous pouvez éventuellement déterminer le degré d'ombre de la tuile.

Vous pouvez également garder une trace des pixels testés. Optimisez donc un peu la solution et ne testez pas deux fois les pixels.

Cela pourrait être assez pratique en utilisant une manipulation d’image et en traçant des lignes droites entre pixels (tuiles). Si les lignes sont semi-transparentes et les blocs X à nouveau semi-transparents. Vous pouvez seuiller l’image pour déterminer si la ligne a croisé un 'X'

Si vous avez la possibilité d'utiliser un outil tiers, alors Id l'utilisera probablement. À long terme, cela pourrait s'avérer plus rapide, mais vous en comprendriez moins sur votre jeu.

Answer 5

Ceci est juste pour le plaisir:

Vous pouvez reproduire l’approche Doom 3 en 2D si vous faites d’abord une étape pour convertir vos tuiles en lignes. Par exemple,

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

... serait réduit à trois lignes reliant les coins de l'objet solide en triangle.

Ensuite, faites ce que fait le moteur Doom 3: Du point de vue de la source de lumière, considérez chaque "paroi". qui fait face à la lumière. (Dans cette scène, seule la diagonale serait prise en compte.) Pour chacune de ces lignes, projetez-la dans un trapézoïde dont le bord avant est la ligne d'origine, dont les côtés sont alignés sur les lignes allant de la source de lumière à chaque point final et dont le dos est au loin, passé toute la scène. Donc, c’est un trapèze qui pointe vers " la lumière. Il contient tout l'espace sur lequel le mur projette son ombre. Remplissez chaque carreau de ce trapèze de noirceur.

Parcourez toutes ces lignes et vous obtiendrez un "pochoir". cela inclut toutes les tuiles visibles depuis la source de lumière. Remplissez ces carreaux avec la couleur claire. Vous voudrez peut-être éclairer un peu moins le carreau à mesure que vous vous écartez de la source ("atténuation") ou faire d'autres choses fantaisistes.

Répétez cette procédure pour chaque source de lumière de votre scène.

Answer 6

Pour vérifier si une tuile est dans l'ombre, vous devez tracer une ligne droite jusqu'à la source de lumière. Si la ligne coupe une autre tuile occupée, la tuile que vous testiez est dans l'ombre. Les algorithmes de lancer de rayons font cela pour chaque objet (dans votre vignette de cas) dans la vue.

Le article sur le traçage sur Wikipedia a un pseudocode.

Answer 7

Voici une approche très simple mais assez efficace qui utilise le temps linéaire en nombre de carreaux à l’écran. Chaque mosaïque est soit opaque soit transparente (ce qui nous a été donné), et chacune d’elles peut être visible ou ombrée (c’est ce que nous essayons de calculer).

Nous commençons par marquer l'avatar lui-même comme "visible".

Nous appliquons ensuite cette règle récursive pour déterminer la visibilité des mosaïques restantes.

1. Si la vignette se trouve sur la même ligne ou la même colonne que l'avatar, elle n'est visible que si la vignette adjacente la plus proche de l'avatar est visible et transparente.
2. Si la tuile est sur une diagonale de 45 degrés par rapport à l'avatar, elle ne sera visible que si la tuile diagonale voisine (vers l'avatar) est visible et transparente.
3. Dans tous les autres cas, considérez les trois tuiles voisines plus proches de l'avatar que de la tuile en question. Par exemple, si cette tuile est en (x, y) et se situe au-dessus et à droite de l'avatar, les trois tuiles à prendre en compte sont (x-1, y), (x, y-1) et (x- 1, y-1). La vignette en question est visible si une de ces trois vignettes est visible et transparente.

Pour que cela fonctionne, les carreaux doivent être inspectés dans un ordre spécifique pour s'assurer que les cas récursifs sont déjà calculés. Voici un exemple de commande en marche, commençant à 0 (qui est l’avatar lui-même) et en comptant:

9876789
8543458
7421247
6310136
7421247
8543458
9876789

Les tuiles portant le même numéro peuvent être inspectées dans n'importe quel ordre.

Le résultat n'est pas beau, mais calcule une visibilité crédible des tuiles.

Answer 8

La solution de TK est celle que vous utiliseriez généralement pour ce genre de chose.

Pour le scénario d’éclairage partiel, vous pouvez l’avoir de sorte que si une tuile reste dans l’ombre, elle est ensuite divisée en 4 tuiles et chacune d’elles est testée. Vous pouvez ensuite le partager autant que vous le souhaitez?

Modifier:

Vous pouvez également l'optimiser un peu en ne testant aucune des tuiles adjacentes à une lumière. Ce serait plus important à faire lorsque vous avez plusieurs sources de lumière, je suppose ...

Answer 9

En fait, j'ai récemment écrit cette fonctionnalité dans l'un de mes projets.

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;
            }
        }
    }

}

Vous y trouverez des éléments supplémentaires dont vous n’auriez pas besoin si vous les adaptiez pour votre propre usage. Le type de lieu est simplement défini comme une position x et y pour des raisons de commodité.

La fonction de ligne est tirée de Wikipedia avec de très petites modifications. Au lieu d'imprimer les coordonnées x y, je l'ai modifié pour renvoyer un vecteur de lieu avec tous les points de la ligne. La fonction CheckPlaceLOS renvoie simplement true ou false selon que la tuile contient un objet. Il y a encore d'autres optimisations à faire, mais cela convient à mes besoins.

Answer 10

Je sais que cette question remonte à des années, mais pour tous ceux qui recherchent ce style de contenu, j'aimerais proposer une solution que j’avais utilisée une fois pour un roguelike; manuellement " précalculé " FOV. Si votre champ de vision de la source de lumière a une distance extérieure maximale, il n’est vraiment pas très difficile de dessiner à la main les ombres créées par le blocage d’objets. Vous n'avez qu'à dessiner 1/8 du cercle (plus les directions droite et diagonale); vous pouvez utiliser symmerty pour les autres aspects. Vous aurez autant de shadowmaps que de carrés dans ce 1/8 de cercle. Ensuite, il suffit de les combiner OU ensemble en fonction des objets.

Les trois principaux avantages à cet égard sont les suivants: 1. C'est très rapide si bien implémenté 2. Vous décidez comment l’ombre doit être projeté, sans comparer l’algorithme qui gère quelle situation 3. Pas de cas particuliers induits par un algorithme étrange que vous devez en quelque sorte résoudre

Le problème, c’est que vous n’avez pas vraiment à implémenter un algorithme amusant.

Answer 11

J'ai implémenté le champ de vision basé sur les carreaux dans une seule fonction C. C'est ici: https://gist.github.com/zloedi/9551625

Answer 12

Si vous ne voulez pas prendre le temps de réinventer / ré-implémenter cela, il existe de nombreux moteurs de jeu. Ogre3D est un moteur de jeu open source prenant totalement en charge l'éclairage, ainsi que les commandes de jeu et de son.