Problème Super Mario Galaxy

Supposons que Mario marche sur la surface d'une planète. S'il commence à marcher depuis un endroit connu, dans une direction fixe, sur une distance prédéterminée, à quelle vitesse pouvons-nous déterminer où il s'arrêtera?

Plus formellement, supposons que nous recevions un polytope convexe dans un espace, un point de départ à la surface de , un vecteur de direction (dans le plan d’une facette contenant ) et une distance . Combien de temps pouvons-nous déterminer quelle facette de Mario s’arrêtera à l’intérieur? (Comme point technique, supposons que si Mario entre dans un sommet de , il explose immédiatement; heureusement, cela ne se produit presque jamais .)s p v p ℓ P $P$$s$$P$$v$$p$$\ell$$P$$P$

Ou si vous préférez: supposons que le polytope , le point source et le vecteur de direction soient donnés à l’avance. Après pré - traitement, la rapidité avec laquelle nous pouvons répondre à la question pour une distance donnée ?s v $P$$s$$v$$\ell$

Il est facile de simplement suivre les traces de Mario, surtout si n’a que des facettes triangulaires. Chaque fois que Mario entre une facette par l’un de ses bords, nous pouvons déterminer en temps qu’il doit laisser au travers des deux autres bords. Bien que le temps d' exécution de cet algorithme est uniquement linéaire du nombre de passages à bord, il est sans limite en fonction de la taille d'entrée, car la distance peut être arbitrairement plus grand que le diamètre de . Pouvons-nous faire mieux?O ( 1 ) ℓ $P$$O(1)$$\ell$$P$

(En pratique, la longueur du chemin n’est pas réellement illimitée; il existe une limite supérieure globale en termes de nombre de bits nécessaires pour représenter l’entrée. Mais insister sur les entrées entières soulève quelques problèmes numériques plutôt désagréables - Comment calculer exactement où pour arrêter? - nous allons donc nous en tenir à des entrées réelles et arithmétique exacte exacte.)

Est-ce qu'on sait quelque chose de non trivial sur la complexité de ce problème?

Mise à jour: à la lumière du commentaire de julkiewicz, il semble clair qu'un temps d'exécution en RAM réelle limité uniquement en termes de (complexité du polytope) est impossible. Prenons le cas particulier d'une unité carrée à deux côtés , Mario commençant à et marchant dans la direction . Mario s’arrêtera à l’avant ou à l’arrière du carré en fonction de la parité du nombre entier . On ne peut pas calculer la fonction de sol en temps constant sur la RAM réelle, à moins que nous sommes heureux assimilant PSPACE et P . Mais nous pouvons calculer en[ 0 , 1 ] 2 ( 0 , 1 / 2 ) ( 1 , 0 ) ⌊ ℓ ⌋ ⌊ ℓ ⌋ O ( log ℓ ) n log ℓ$n$$[0,1]^2$$(0,1/2)$$(1,0)$$\lfloor \ell \rfloor$$\lfloor \ell \rfloor$$O(\log \ell)$temps par recherche exponentielle, ce qui représente une amélioration exponentielle par rapport à l’algorithme naïf. Le polynôme temporel en et toujours réalisable?$n$$\log \ell$

Ce problème est très très difficile. Nous pourrions le simplifier pour le rendre plus facile, comme suit.

1. Nous pouvons ajouter l’hypothèse que la somme des angles autour de chaque sommet du polytope est un multiple rationnel de . Cela élimine la plupart des "polytopes", mais il reste encore de nombreuses possibilités intéressantes: par exemple, les solides platoniques.$P$$\pi$

2. Nous pouvons supposer que le polytope n’est pas vraiment tridimensionnel, mais plutôt le "double" d’un polygone; cela ressemble un peu à une taie d'oreiller. On peut encore simplifier et supposer que le polygone a des côtés égaux et parallèles; par exemple un carré, comme dans le jeu Astroids.

Si nous formulons ces deux hypothèses, la théorie est vaste. (Trouver un algorithme pour le carré est un exercice difficile impliquant le développement continu de la fraction de l'angle de la trajectoire de Mario. Obtenir un résultat similaire pour l'octogone régulier est possible mais plus difficile. Les solutions pour le square et l'octogone impliquent de réfléchir à la manière de coder efficacement une "séquence de découpage pour une géodésique sur une surface de translation". La plupart des autres polygones rationnels conduiront rapidement à des problèmes ouverts.) Une référence initiale, qui inclut une référence supplémentaire à la le tore carré, sont ces diapositives de conversation par Diana Davis.$O(\log(\ell))$

Si nous n'assumons pas la rationalité, mais supposons que le polytope est le double d'un polygone, nous discutons alors de la théorie des "découpages de séquences dans des billards irrationnels". Il semble que pratiquement rien ne soit connu ici; par exemple, voir la dernière phrase de cette présentation de Corinna Ulcigrai.

Si nous ne faisons aucune hypothèse, eh bien, je ne peux penser à rien dans la littérature.

Enfin, je suppose qu’il existe une solution problème de Super Mario Galaxy pour les solides platoniques. C'est un bon problème pour un étudiant diplômé qui commence à jouer au billard rationnel. Par exemple, le cas du dodécaèdre "devrait" découler de la thèse de Diana Davis. (Mais commençons par le tétraèdre - qui découlera d'une analyse des séquences de coupe pour le tore hexagonal.)$O(\log(\ell))$

Je pense que vous pouvez faire mieux que linéaire. Je suis novice en informatique théorique, alors pardonnez-moi si c'est de la foutaise.

Quelques idées générales (de valeur variable):

• Si nous donnons un symbole à chaque facette, son orbite peut être décrite comme une chaîne, le dernier symbole de la chaîne étant la réponse.
• Nous pouvons supposer sans perte de généralité que Mario commence sur un bord (marchez en arrière et prolongez-le jusqu'au bord)
• L'espace 2D des positions de départ et des angles peut être partitionné par l'arête suivante. Donc, à partir du bord a, x unités à partir du bas, avec un angle de a, nous aboutissons au bord V après avoir traversé une facette.
• À ce stade, nous nous trouvons à un autre bord avec une autre orientation. Nous pouvons donc appeler la fonction de manière récursive pour subdiviser l'espace en partitions de chaînes de 2 symboles, etc.
• À ce stade, nous avons terminé si nous disons que l'espace doit être discrétisé pour que le problème soit implémenté sur une MT. Cela signifie que chaque orbite doit être périodique car il n’ya que de nombreux points sur la planète discrétisée. Nous pouvons calculer la fonction décrite ci-dessus jusqu'à ce que nous ayons des orbites pour tous les points de départ et stocker cette information. Alors le problème devient O (1).
• Peut-être que c'est un peu un flic. Certaines recherches sur Google me disent que presque toutes les orbites de billard à l'intérieur de polygones convexes rationnels sont périodiques (c'est-à-dire que les orbites périodiques sont denses). Donc, pour une (disons) planètes carrées, la même approche pourrait fonctionner.
• Une autre approche consisterait à considérer le système en tant que générateur / identificateur de chaînes (en attribuant à chaque facette son propre symbole). Si le langage a une classe de complexité connue, c'est votre réponse. Si vous élargissez la famille des polytopes à une dimension non convexe et à une dimension quelconque, vous pouvez capturer une très grande classe de langues.

Cela ne constitue pas vraiment une réponse, mais je dois retourner au travail. :)