Chemin de «ligne de vue» à travers le maillage de navigation

Je veux calculer la ligne de visée dans un maillage de navigation.

Considérez l'image ci-dessous, la ligne jaune est le résultat de seulement A * et la ligne rouge est le résultat d'un algorithme de ligne de vue "qui utilise la ligne jaune comme entrée. Maintenant, l'unité peut se déplacer directement sans" zigzag ".

Qu'est-ce qu'un algorithme pour calculer cette "ligne de visée"?

Vous recherchez un algorithme en entonnoir.

Ici, vous êtes simple

http://digestingduck.blogspot.com.es/2010/03/simple-stupid-funnel-algorithm.html

Fondamentalement, l'algorithme identifie les bords comme des portails et crée un entonnoir qui est testé par rapport au sommet des bords pour vérifier s'ils sont à l'intérieur de l'entonnoir ou non.

À l'étape A, l'entonnoir est construit avec la position de départ et le portail traversé par une ligne jaune.

À l'étape B, le portail suivant est vérifié, le sommet supérieur est à l'intérieur de l'entonnoir, de sorte que la ligne supérieure de l'entonnoir passe maintenant à travers. Mais le sommet inférieur est hors de l'entonnoir parce que la ligne rouge est sous la ligne verte, donc la ligne inférieure ne passera pas par elle, elle continuera à passer par le sommet inférieur du portail précédent.

Comme vous pouvez vérifier que l'entonnoir sera plus petit et plus petit, jusqu'à l'étape F, où il n'est pas possible de construire l'entonnoir, car la ligne rouge fait un mauvais entonnoir, donc le sommet supérieur est choisi comme nouveau point de départ et un nouvel entonnoir serait être construit si le point final n'est pas dans ce maillage.

Sachez que ce type d'algorithme permet également de résoudre simplement le problème de taille du modèle, car vous pouvez considérer que les portails sont plus petits du 2xradius de votre modèle.

Il existe une technique simple qui peut être utilisée avec les chemins générés en utilisant cette idée de ligne de visée. Fondamentalement, vous voulez parcourir le chemin et, à chaque nœud, "regarder en arrière" le nœud avant le dernier pour voir s'il est visible. Si le nœud avant dernier est visible, vous pouvez supprimer le dernier nœud (puisque vous avez une ligne de vue entre votre nœud actuel et le nœud avant dernier, le dernier nœud, étant un nœud intermédiaire, n'est pas requis).

Un article Gamasutra a l'exemple de pseudo-code suivant:

checkPoint = starting point of path
currentPoint = next point in path
while (currentPoint->next != NULL)
if Walkable(checkPoint, currentPoint->next)
// Make a straight path between those points:
temp = currentPoint
currentPoint = currentPoint->next
delete temp from the path
else
checkPoint = currentPoint
currentPoint = currentPoint->next

Cet algorithme fait ce que vous voulez, où la Walkablefonction est essentiellement une fonction de visibilité directe, mais légèrement améliorée pour inclure également les situations où le chemin est visible, mais pas praticable (c.-à-d. Fosses, pièges, zones restreintes).