Algorithme pour calculer un chemin de balle vers une cible avec max. 2 ricochets

Désolé pour le pauvre titre mais je n'avais pas de meilleure façon de le dire ...

Il y a donc ce jeu incroyable de Nintendo (oui!) Sur Wii appelé WiiPlay . Il y a 9 mini-jeux, et mon préféré s'appelle Tanks! . Il s'agit de détruire les chars ennemis COM sans vous faire détruire. Voici une capture d'écran d'un niveau:

Une façon de détruire des chars est de tirer des balles. Il y a ce char ennemi vert lime qui tire des balles à grande vitesse qui ricochent (contre les murs et les blocs) deux fois. Vous pouvez voir comment le réservoir du joueur peut être instantanément détruit s'il reste à l'endroit où il se trouve maintenant, car ce réservoir de chaux au centre peut tirer une balle qui suit le chemin vert que j'ai tracé sur l'image.

En tant que programmeur amateur, je me suis demandé comment le réservoir de chaux peut déterminer dans quelle direction il doit tirer pour frapper le réservoir du joueur.

J'y ai pensé moi-même mais je n'ai trouvé aucun algorithme possible. Je vais expliquer mes conclusions au cas où elles inspireraient quelqu'un. Pour plus de simplicité lors de mon explication, je suppose qu'un mur est n'importe quelle surface contre laquelle une balle peut ricocher . Un rectangle isolé de blocs forme ainsi quatre murs.

J'ai conclu que les 2 points auxquels les ricochets de balle se situent toujours d'un côté d'un parallélogramme ou deviennent des sommets opposés d'un parallélogramme. Le char ennemi tirant et le char joueur qu'il vise ne sont pas nécessairement les 2 autres sommets mais se trouvent définitivement sur les lignes colinéaires à l'un ou l'autre des quatre côtés du parallélogramme. Voici une illustration des 4 façons possibles de former un parallélogramme:

HOR-VER signifie que la balle frappe d'abord un mur horizontal, puis elle frappe un mur vertical.

Et puis je suis coincé. J'ai pensé à contourner une ligne qui relie le tank ennemi et le tank joueur autour de la carte pour voir si elle forme un parallélogramme avec deux coups sûrs avec n'importe quel mur, mais cela ne fonctionne pas toujours parce que le tank ennemi et le tank joueur ne sont pas nécessairement coïncidente avec les sommets du parallélogramme.

De plus, je ne suis pas sûr du flux général de l'algorithme. L'algorithme prend-il l'une des 2 structures suivantes, ou peut-être que je me trompe avec les deux?

• Continuez à trouver des chemins possibles et marquez-en toujours un comme le meilleur (peut être le plus court, le plus obscur, le plus incontournable ou une évaluation combinée et pondérée basée sur plusieurs critères) et oubliez le reste. Celui qui reste après tout le calcul est le meilleur à prendre.
• Déterminez d'abord tous les murs accessibles en premier avec la balle (la balle n'a pas besoin de ricocher contre un autre mur pour atteindre chacun de ces murs), puis déterminez toutes les plages accessibles sur chacun de ces murs (il est parfois impossible d'atteindre un point éloigné sur un mur sans ricochet si un autre mur se trouve près de chez vous), puis déterminez à nouveau tous les murs accessibles avec un ricochet, et toutes les plages accessibles sur ces murs. Ces 4 processus peuvent être effectués d'une manière similaire au lancer de rayons. Au cours de chaque processus, si le tank du joueur est touché par un rayon, déterminez le chemin de la balle en fonction de ce rayon.

À mon avis, cet algorithme est difficile à comprendre car:

• une balle peut être tirée dans n'importe quelle direction; et
• il y a infiniment de points sur n'importe quel mur, comme en mathématiques, où il y a infiniment de points sur une ligne.

Mais les gens de Nintendo ont quand même réussi, alors ... quelqu'un avec une idée?

Étant donné une ligne de vue directe, le problème est évidemment trivial. Cependant, nous avons affaire à la réflexion. Il est difficile de déterminer correctement quelles parties de la scène peuvent être vues lors de la mise en œuvre de la réflexion dans le cadre d'un traceur de rayons, car cela pourrait manquer certaines ouvertures. Une «recherche binaire» entre deux angles prometteurs n'est pas non plus viable: à cause des réflexions, l'espace réellement visible n'est pas continu, donc l'heuristique «si c'est à droite de A et à gauche de B, il doit y avoir une cible solution entre A et B »n'est pas autorisée et il manquera des solutions« créatives ». Je recommanderais plutôt de mettre en œuvre la réflexion en réexécutant le traceur à partir d'une position virtuelle - la position où notre réservoir de tir semble être lorsqu'il est vu dans le miroir:

target |obstacle
   X   |
    \  |  X real position
     \   /
      \ /
   ----------- mirror surface
        \
         \
          X virtual position

L'avantage est que le rayon miroir est maintenant une ligne droite provenant de la position virtuelle. J'ai essayé d'illustrer la technique dans le croquis suivant:

X marque la position de tir, (X) la cible. Les zones colorées sont visibles.

1. Ligne de vue directe: la cible n'est pas visible. Cependant, nous pouvons frapper les surfaces (1) et (2).

2. Une réflexion. Il y a deux positions de tir virtuelles dans les obstacles. La position inférieure a un LOS direct vers la cible, nous avons donc notre première solution de tir: la trajectoire de la balle est la partie du rayon entre la cible et la surface inférieure du miroir, et entre le point de collision rayon-miroir et la position de tir réelle.

3. Deux réflexions: La position virtuelle supérieure de la première réflexion peut voir une partie de l'obstacle inférieur à travers sa surface miroir. Puisque deux réflexions sont autorisées, nous pouvons refléter cette position dans l'obstacle inférieur. Les positions sont marquées comme (I) la position réelle, (II) la position virtuelle de la première réflexion et (III) la position virtuelle de la deuxième réflexion.

   À partir de (III), nous avons une LOS directe vers la cible (X), nous avons donc trouvé une autre solution de tir. La trajectoire de la balle est le long de la ligne X – III jusqu'au deuxième point de collision du miroir, puis le long de la ligne III – II entre les points de collision du miroir, et enfin le long de la ligne II – I du premier point de collision du miroir à la position réelle I.

   En fait, la position virtuelle inférieure de la première réflexion pourrait également se refléter dans l'obstacle supérieur, mais cela ne conduira à aucune solution directe.

Une fois que vous pouvez déterminer quelles parties des obstacles sont visibles (et peuvent donc être utilisées pour refléter la balle), la mise en miroir via une recherche en profondeur semble simple. Pour trouver des surfaces de miroirs appropriées, les techniques décrites dans Nicky Case's Sight & Light pourraient être utilisées: plutôt que d'essayer 360 vecteurs - qui pourraient manquer des ouvertures, et qui sont également inutiles - nous lançons des rayons uniquement sur les bords des obstacles.

Extension de l'idée de Karl Bielefeldt pour une réflexion sur 2 murs:

A et B sont donnés (les réservoirs). Vous devez d'abord répertorier tous les murs que A peut voir et une liste de tous les murs que B peut voir. Ensuite, vous faites des paires où le premier mur est dans la première liste et le deuxième mur est différent du premier mur et se trouve dans la deuxième liste. Vous devez effectuer ce test pour toutes les paires de murs possibles (sauf si vous trouvez un moyen d'éliminer les candidats). Une fois que vous avez trouvé R et S pour une paire de murs donnée, vous vérifiez

1) si A a une vision directe de R

2) si R appartient au mur1 (le mur n'est qu'un segment, pas toute la ligne)

3) si R a un accès direct à S

4) si S appartient à wall2 (le mur n'est qu'un segment, pas toute la ligne)

5) si S a un accès direct à B.

Pour trouver R et S : Puisque vous connaissez wall1, vous pouvez déterminer l'équation de la ligne tangente à wall1, puisque R appartient à la ligne tangente au mur 1, vous avez une relation entre les 2 coordonnées de R (se terminant par un degré de liberté pour R) Similairement à S (vous avez une relation entre les coordonnées S puisque ce point appartient à la ligne tanget à wall2). Alors maintenant, vous avez 2 degrés de liberté et vous devez avoir 2 équations indépendantes supplémentaires pour déterminer une solution. Une équation est:

(AA')/(RA')=(SS')/(RS')

l'autre équation est:

(BB')/(SB')=(RR')/(SR')

notez que dans les équations ci-dessus A, A ', B, B' sont connues ou peuvent être calculées directement. R 'et S' sont fonction des coordonnées de R et S et des équations du mur. Je n'ai pas terminé le calcul, donc je ne sais pas à quoi ressembleront les équations.

Vous pouvez profiter du fait que l'angle sortant du ricochet doit être le même que l'angle entrant. Pour un mur horizontal donné avec les coordonnées y cet deux réservoirs fixes avec les coordonnées (a,b)et (d,e), il n'y a qu'un seul angle qui satisfait l'équation ci-dessous.

Il suffit de résoudre pour xobtenir la distance le long du mur vers laquelle vous devez viser. Deux murs fonctionnent de la même façon. Vous avez juste deux équations et deux inconnues.

Vous avez des diagrammes nets montrant comment diriger les rayons, donc je vais laisser les détails sur la façon de déterminer une paire de surfaces réfléchissantes.

Appelons la surface qui doit être frappé première surface A , et le second, B .

Essayez de frapper les (visibles) bords de B en tirant sur A . En d'autres termes, déterminez les points où l'on verrait les reflets des extrémités de B si l'on regarde le A fini miroir . Cela doit être facile à faire, vous n'avez qu'un seul point de réflexion à gérer.

Maintenant , vous savez deux rayons qui ont frappé les bords de (visibles) B . Appelons-les rayons de bord Calculez leurs réflexions sur B; ils doivent aller quelque part au-delà de votre cible. Vous pouvez déterminer si la cible se situe entre eux, c'est-à-dire à gauche d'un rayon mais à droite de l'autre, ou vice versa. C'est trivial à faire en utilisant l' équation générale de la droite .

Si la cible n'est pas entre les rayons du bord, vous ne pouvez évidemment pas la frapper avec un rayon intermédiaire; choisissez une autre paire de surfaces.

Si la cible se trouve entre les rayons, recherchez le rayon de frappe intermédiaire à l'aide de la recherche binaire. Vous avez deux angles de tir correspondant aux rayons de bord, votre angle de frappe se situe entre eux. À condition que le diamètre angulaire de votre cible, vu depuis le point de tir, ne soit pas excessivement petit, vous aurez besoin de quelques itérations jusqu'à ce que vous trouviez la direction d'un rayon de frappe.

Voici une photo:

Ici, les deux rayons latéraux sont représentés en rouge et bleu. Apparemment, vous pouvez trouver un rayon émis à un angle plus petit que le rouge mais plus grand que le rouge de sorte que ce rayon atteigne la cible verte.

Tout d'abord, rappelez-vous en cours de physique lorsque vous avez parlé de réfraction de la lumière? Eh bien, votre problème peut être résolu en utilisant ces principes. L'angle d'incidence est égal à l'angle de réflexion. le char ennemi doit donc parcourir tous les angles possibles pour le premier rebond afin que le deuxième rebond puisse toucher le joueur. Continuez aussi avec l'idée de lancer de rayons. Maintenant, cela se complique lorsque le joueur bouge, mais ce devrait être une assez bonne idée pour vous de commencer sur un algorithme