Ligne de visée diagonale à deux coins

En ce moment, j'utilise l'algorithme de ligne de Bresenham pour la ligne de vue. Le problème est que j'ai trouvé un boîtier de bord où les joueurs peuvent regarder à travers les murs. Se produit lorsque le joueur regarde entre les deux coins d'un mur avec un espace de l'autre côté à des angles spécifiques.

Le résultat que je veux, c'est que la tuile entre deux murs soit marquée comme non valide.

Quel est le moyen le plus rapide de modifier l'algorithme de ligne de Bresenham pour résoudre ce problème? S'il n'y a pas de bonne solution, existe-t-il un algorithme mieux adapté? Toutes les idées sont les bienvenues. Veuillez noter que la solution devrait également être capable de prendre en charge la 3D.

Edit: Ma solution simple était de vérifier si les deux coins sont fermés lorsque les coordonnées x et y d'une ligne changent. Pour le code source de travail et une démonstration interactive du produit terminé, veuillez consulter http://ashblue.github.io/javascript-pathfinding/

Eric Lippert a écrit une excellente série sur la génération de lignes de visée en C # avec Shadow Casting sur une grille plane rectangulaire.

Entre autres questions, Eric a traité diverses questions auxquelles il faut répondre au sujet des exigences en matière de visibilité directe, qui donnent des résultats différents et donne des exemples de quelques résultats différents. Un des articles traite en profondeur d'une circonstance de "regarder au coin de la rue" qui s'est produite dans une première version de son algorithme.

J'ai adapté l'algorithme d'Eric à une grille hexagonale ici , et je l'ai utilisé avec succès sur de grandes grilles hexagonales (> 400 x 700) avec un rayon de visibilité étendu (> 60 hexs). Cette implémentation calcule et affiche un champ de vision complet aussi vite que je peux cligner des yeux, en utilisant un seul processeur i7. C'est certainement assez rapide pour toutes les utilisations auxquelles je m'attends.

Mise à jour - Ligne de visée avec élévation:
L'implémentation de la grille hexadécimale liée à ci-dessus calcule la ligne de visée avec élévation, pas seulement les obstacles. Les notes de documentation discutent également d'une décision supplémentaire qui doit être prise en ce qui concerne les calculs d'élévation: la hauteur cible et la hauteur de l'observateur. La sélection par défaut consiste à rendre les deux égaux, ce qui crée un champ de vision symétrique, mais le sol au sol et les observateurs au sol peuvent également être sélectionnés. (Le code est Open Source sous licence MIT)

Que se passe-t-il si pour le calcul de la LOS, vous avez une grille distincte de «résolution plus élevée» qui remplit les espaces vides Je pensais à quelque chose comme ça:

La gauche est la section de bloc d'origine de 4 carrés.

La droite est la version "haute résolution", comme vous pouvez le voir, chaque carré d'origine a été subdivisé en quatres et l'un des coins a été rempli. Je ne suis pas sûr de l'algorithme pour le générer, mais il peut être pré-calculé de la carte actuelle.

Cela signifie que l'espace de coordonnées est quadruplé, mais je n'envisage pas que ce soit un problème de performance important.