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

Question

Je suis en train d'écrire un peu de tile-based jeu, pour lequel je tiens à l'appui de sources de lumière. Mais mon algorithme-fu est trop faible, donc je viens à vous pour vous aider.

La situation est comme cela: Il y a une carte (tenue comme un tableau 2D), contenant une seule source de lumière et de plusieurs éléments debout autour de lui. Je veux calculer dont les tuiles sont illuminés par la lumière de la source, et qui sont dans l'ombre.

Une aide visuelle de ce qu'il pourrait ressembler, environ. Le L est la source de lumière, les x sont des éléments de blocage de la lumière, les 0 sont allumés tuiles, et le-s sont des tuiles 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 - - - - - - -

Une fraction de système serait encore mieux, bien sûr, où une tuile peut être dans la demi-ombre en raison d'être partiellement obscurcie. L'algorithme ne doit pas être parfait, mais qui ne sont pas manifestement mal et assez rapide.

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

Les élèves?

Answer 1

Le roguelike de la communauté de développement a un peu une obsession avec ligne de vue, le champ de vue des algorithmes.

Voici un lien vers un roguelike l'article wiki sur le sujet: http://roguebasin.roguelikedevelopment.org/index.php?title=Field%5Fof%5FVision

Pour ma roguelike jeu, j'ai mis en place une ombre portée de l'algorithme dehttp://roguebasin.roguelikedevelopment.org/index.php?title=Shadow%5Fcasting) en Python. C'était un peu compliqué à mettre en place, mais a fonctionné raisonnablement efficace (même en pur Python) et a généré de bons résultats.

Le "Permissif Champ de vision" semble gagner en popularité ainsi: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive%5FField%5Fof%5FView

Answer 2

Vous pouvez lancer dans toutes sortes de difficultés avec le calcul de l'occlusion etc, ou vous pouvez aller pour la simple force brute de la méthode: Pour chaque cellule, utiliser une ligne de dessin algorithme tel que le Bresenham Ligne de l'Algorithme d'examiner chaque cellule, entre l'actuel et la source de lumière. Si tous sont remplies de cellules ou (si vous n'avez qu'une seule source de lumière), les cellules qui ont déjà été testé et trouvé dans l'ombre, ta cellule est dans l'ombre. Si vous rencontrez une cellule connu pour être éclairés, vos cellules seront de même allumé. Facile d'optimisation consiste à définir l'état de toutes les cellules que vous rencontrez le long de la ligne quelque soit le résultat final est.

C'est plus ou moins ce que j'ai utilisé dans mon 2004 IOCCC gagnante. Évidemment, ce n'est pas un exemple de code, si. ;)

Edit: Comme loren, avec ces optimisations, vous avez seulement besoin de sélectionner les pixels sur le bord de la carte à la trace.

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:

(Selon la taille de la matrice)

• Boucle sur chaque vignette
• tracez une ligne à la Lumière
• Si tout pary de la ligne de touche un X, alors elle est dans l'ombre
• (Facultatif): calcul de la quantité de X de la ligne passe à travers et faire de fantaisie en mathématiques à determint la proportion de la tuile dans l'ombre. NB: Ceci pourrait être fait par l'anti-aliasing de la ligne entre la tuile et de la Lumière (donc à la recherche à d'autres tuiles le long de la route de retour vers la source de lumière) au cours de la procédure de seuillage ils apparaissent comme de petites anomalies. Selon la logique que vous pourriez potentiellement déterminer combien (si), le carreau est dans l'ombre.

Vous pouvez également garder une trace de pixels qui ont été testés, par conséquent, d'optimiser la solution un peu et ne pas re-test de pixels deux fois.

Cela pourrait être dôme assez bien par l'aide de la manipulation d'image et de dessin de lignes droites entre pixles (tuiles) Si les lignes sont semi-transparentes et le X blocs sont semi-transparente. Vous pouvez le seuil de l'image pour déterminer si la ligne a recoupé un "X"

Si vous avez l'option d'utiliser un outil 3ème partie, puis Id probablement le prendre. Dans le long terme, il pourrait être plus rapide, mais vous devez comprendre de moins en moins sur votre jeu.

Answer 5

C'est juste pour le fun:

Vous pouvez reproduire le Doom 3 approche 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éduite en trois lignes reliant les coins de l'objet solide dans un triangle.

Ensuite, faire ce que le moteur de Doom 3 n': du point De vue de la source de lumière, de considérer chaque "mur" qui fait face à la lumière. (Dans cette scène, seule la ligne diagonale serait pris en considération.) Pour chaque ligne de ce type de projet dans un trapèze dont le bord avant est la ligne d'origine, dont les côtés se trouvent sur les lignes de la source de lumière à travers chaque point de fin, et dont la partie arrière est de loin, le passé de l'ensemble de la scène. Donc, c'est un trapèze qui "points" de la lumière. Il contient tout l'espace que le mur jette son ombre sur. Remplissez tous les carreaux de cette trapèze avec les ténèbres.

Passer par toutes ces lignes et vous allez vous retrouver avec un "pochoir", qui comprend toutes les tuiles visibles à partir de la source de lumière. Remplir ces cases avec la couleur de la lumière. Vous souhaitez peut-être à la lumière de la tuile un peu moins que vous vous éloignez de la source ("atténuation") ou de faire d'autres trucs de fantaisie.

Répétez l'opération pour chaque source de lumière dans votre scène.