Comment calculer rapidement la zone de vue dans un jeu en mosaïque 2D?

24

J'ai une matrice de tuiles, sur certaines de ces tuiles il y a des objets. Je veux calculer quelles tuiles sont visibles pour le joueur, et lesquelles ne le sont pas, et je dois le faire assez efficacement (pour que cela calcule assez rapidement même si j'ai de grandes matrices (100x100) et beaucoup d'objets).

J'ai essayé de le faire avec l' algorithme de ligne de Bresenham , mais c'était lent. De plus, cela m'a donné quelques erreurs:

----XXX-        ----X**-     ----XXX-
-@------        -@------     -@------
----XXX-        ----X**-     ----XXX-
(raw version)   (Besenham)   (correct, since tunnel walls are 
                              still visible at distance)

(@ is the player, X is obstacle, * is invisible, - is visible)

Je suis sûr que cela peut être fait - après tout, nous avons NetHack, Zangband, et ils ont tous réglé ce problème d'une manière ou d'une autre :)

Quel algorithme pouvez-vous recommander pour cela?

Pour mes besoins, je définirai visible comme ceci: la tuile est visible quand au moins une partie (par exemple un coin) de la tuile peut être connectée au centre de la tuile du joueur avec une ligne droite qui ne coupe aucun obstacle.

2d mathematics algorithm Rogach
la source
1
Oups, mon erreur, NetHack ne jouait pas avec la ligne de vue :)
Rogach
Certaines idées plus anciennes peuvent être trouvées sur fadden.com/tech/fast-los.html , bien que cela remonte à l'époque où les processeurs étaient assez lents et où les calculs en virgule flottante étaient à éviter.
fadden

Réponses:

10

Votre définition du visible est la suivante:

la tuile est visible lorsqu'au moins une partie (par exemple un coin) de la tuile peut être connectée au centre de la tuile du joueur avec une ligne droite qui ne coupe aucun obstacle

Vous pouvez implémenter ce concept littéralement en traçant les rayons de votre tuile de joueur et en les croisant avec votre scène. Vous rompez à chaque itération une fois que le rayon frappe un obstacle (ou dépasse un certain seuil de distance) car vous n'êtes intéressé que par les tuiles que le joueur peut voir directement. Je vais interrompre le processus pour vous:

  1. Spécifiez le niveau de précision que vous souhaitez donner à l'algorithme. Ce sera le nombre de rayons que vous allez tracer.
  2. Divisez le cercle complet de 360 ​​degrés par la précision choisie pour savoir combien de degrés tourner entre chaque rayon.
  3. En commençant à 0 degré et en augmentant la quantité déterminée à l'étape 2, créez un rayon avec l'origine au centre de la tuile du joueur et la direction déterminée par l'angle actuel.
  4. Pour chaque rayon, en partant de la tuile joueur, marchez le long de la direction du rayon jusqu'à atteindre une tuile obstacle. Ajoutez cette tuile à la liste des tuiles visibles et passez au rayon suivant. Vous pouvez également ajouter une distance maximale pour "abandonner" au cas où aucune collision n'est trouvée.

Voici une photo montrant 3 exemples de rayons. Les carreaux de couleur plus foncée sont le "résultat" de chaque rayon, c'est-à-dire où la collision s'est produite. Vous devrez cependant répéter tout autour du cercle:

entrez la description de l'image ici

Ajustez la distance maximale et le nombre de rayons pour les performances. Trop peu et vous manquerez de tuiles, trop et vos performances en souffriront. De plus, plus les rayons doivent parcourir le plus loin, plus «l'erreur» sera grande et plus vous aurez besoin de précision.

modifier

Consultez le didacticiel suivant sur la diffusion de rayons, en particulier les étapes 3 et 4, pour vous aider à implémenter le bit d'intersection de l'algorithme:

http://www.permadi.com/tutorial/raycast/rayc7.html

David Gouveia
la source
Dois-je simplement "marcher" le long de chaque rayon d'une distance fixe (par exemple, 0,3 point) ou dois-je exécuter quelque chose comme l'algorithme de Besenham sur chaque rayon?
Rogach
Si vous avancez juste d'une distance fixe, vous aurez des problèmes avec les tuiles manquées. Consultez ce tutoriel sur le raycasting . Je vais également modifier cette ressource dans ma réponse. Vous vérifiez essentiellement les collisions horizontales et verticales séparément.
David Gouveia
1
L'algorithme est bon, mais il nécessitera une énorme quantité de rayons pour fonctionner correctement avec de longs tunnels de 1 carreau.
HolyBlackCat
@HolyBlackCat - ce ne sera le cas que si vous envoyez des rayons à angles réguliers dans toutes les directions. Mais vous pouvez éviter d'envoyer la plupart de ces rayons et ne les lancer qu'aux extrémités de votre scène. Voici une bonne explication: redblobgames.com/articles/visibility
Rogach
8

Je préfère projeter des rayons d'ombre au lieu de rayons de ligne de vue.

Disons que c'est votre zone de vue (la zone potentiellement visible)

######################
#####.............####
###................###
##..................##
#....................#
#....................#
#..........@.........#
#....................#
#....................#
##..................##
###................###
#####.............####
######################

Les # blocs ne sont pas visibles lorsque le. sont visibles

Mettons un obstacle X:

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXXX...........#
##..................##
###....X...........###
#####.............####
######################

Vous avez une liste des X qui se trouvent dans la zone de vue, puis vous marquez comme cachée chaque tuile qui se trouve derrière chacun de ces obstacles: lorsqu'un obstacle est marqué comme caché, vous le supprimez de la liste.

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXX*...........#
##......##..........##
###....*#..........###
#####.###.........####
######################

Dans l'exemple ci-dessus, vous pouvez voir l'ombre projetée par le plus à droite du mur inférieur et comment cette ombre supprime l'obstacle caché de la liste des obstacles que vous devez vérifier (X doit vérifier; * vérifié).

Si vous obtenez un tri de la liste à l'aide d'une partition binaire afin que le X le plus cosest soit vérifié en premier, vous pouvez accélérer légèrement votre vérification.

Vous pouvez utiliser une sorte d'algorithme de "batailles navales" pour vérifier le bloc de X à la fois (essentiellement à la recherche d'un X adiaque dans une direction qui peut élargir le cône d'ombre)

[MODIFIER]

Deux rayons sont nécessaires pour projeter correctement une ombre et, comme une tuile est rectangulaire, beaucoup d'hypothèses peuvent être faites en utilisant les symétries disponibles.

Les coordonnées des rayons peuvent être calculées à l'aide d'une simple partition d'espace autour de la tuile obstacle:

Exemple de partitionnement d'espace

Chaque zone rectangulaire constitue un choix quant au coin du carreau qui doit être pris comme bord du cône d'ombre.

Ce raisonnement peut être poussé plus loin pour connecter plusieurs tuiles adjacentes et les laisser jeter un seul cône plus large comme suit.

La première étape consiste à s'assurer qu'aucun obstacle ne se trouve dans la direction de l'observateur, dans ce cas, l'obstacle le plus proche est considéré à la place:

choisissez l'obstacle le plus proche

Si la tuile jaune est un obstacle, cette tuile devient la nouvelle tuile rouge.

Considérons maintenant le bord supérieur du cône:

tuiles candidates

Les carreaux bleus sont tous des candidats possibles pour élargir le cône d'ombre: si au moins l'un d'entre eux est un obstacle, le rayon peut être déplacé en utilisant le partage d'espace autour de ce carreau comme vu précédemment.

La tuile verte n'est candidate que si l'observateur est au-dessus de la ligne orange qui suit:

vérification prolongée

Il en va de même pour l'autre rayon et pour les autres positions de l'observateur autour de l'obstacle rouge.

L'idée sous-jacente est de couvrir autant de surface que possible pour chaque coulée de cône et de raccourcir le plus rapidement possible la liste des obstacles à vérifier.

FxIII
la source
Approche intéressante et probablement une meilleure idée en raison de sa nature soustractive. Après avoir lu ceci, je l'implémenterais probablement de cette façon aussi.
David Gouveia
Je peux prévoir des problèmes dans des situations comme celle-ci . Joueur en jaune, obstacles en bleu et violet. Le joueur doit pouvoir voir l'obstacle violet (comme le montre le rayon vert). Mais le rayon d'ombre rouge passant à travers l'obstacle bleu rejette la tuile violette. Mais je suppose que la version en ligne de visée peut avoir de plus gros problèmes que cela.
David Gouveia
Ce problème vient de la définition de "caché": quand un rayon coupe une tuile, il ne la couvrira (presque) jamais complètement. Le même problème est résolu avec l'alias lors du rendu des segments de ligne. Personnellement, je pense qu'une tuile est cachée lorsque la majeure partie de celle-ci est couverte, on peut la définir comme cachée est entièrement couverte, vous pouvez trouver si elle expose un côté qui peut potentiellement élargir le cône d'ombre ... Quoi qu'il en soit, vous pouvez ne supprimez que les blocs entièrement couverts.
FxIII
@DavidGouveia - quels problèmes plus importants?
Rogach
@DavidGouveia - J'ai déjà essayé l'approche avec des "cônes" d'ombre, et c'était très inefficace. En ce qui concerne la précision des rayons de visibilité - ~ 5500 rayons suffisent pour voir le mur 20 tuiles dans chaque direction si vous vous tenez directement près de lui, et comme la distance dans laquelle une seule tuile est visible est beaucoup plus. Et quant à manquer des tuiles à une plus grande distance - eh bien, tout le monde n'a pas la vue parfaite, hein?
Rogach
8

Le problème que vous essayez de résoudre est parfois appelé Field of View, FOV pour faire court. Comme vous avez mentionné les roguelikes comme exemples, vous devriez jeter un œil à ce que le wiki de RogueBasin a à dire sur le sujet (il y a même des liens vers des implémentations): http://www.roguebasin.com/index.php?title=Field_of_Vision

Il existe plusieurs algorithmes différents avec des avantages et des inconvénients différents - une comparaison très pratique est également disponible sur RogueBasin: http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

Tapio
la source
Résumé vraiment bon et complet!
Rogach
Ce site Web est une excellente ressource, merci de partager ce lien. Il contient également une description étonnamment compréhensible du fonctionnement de la recherche de
chemin
Le lien dans la réponse va maintenant à la page d'accueil du site - roguebasin.com/index.php?title=Category:FOV semble être une correspondance raisonnable.
fadden