Problème Super Mario Galaxy

140

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?

entrez la description de l'image ici

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 PPsPvpPP

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 Psv

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 ) PPO(1)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)O(log)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?nlog

Jeffε
la source
5
J'ai pensé à un problème plus simple, à savoir: nous avons un polygone simple et un faisceau de lumière partant d'un point donné. Quand il atteint un bord, il devient juste en miroir. Nous voulons savoir où le faisceau finira son voyage après la distance donnée. Il pourrait (presque) être réduit à celui-ci, en prenant un polytope qui est un prisme de très petite hauteur et dont les côtés supérieur et inférieur ont la forme d’un polygone donné. Peut-être que résoudre ceci en premier pourrait aider.
julkiewicz
3
“[T] ime en n et log l” n'a pas de sens pour moi. Si cela dépend de l, il doit également dépendre des coordonnées de P, et si vous ajoutez un journal de tous les nombres de l'entrée, c'est exactement le nombre de bits nécessaires pour représenter l'entrée lorsque les coordonnées de l'entrée sont limitées à des entiers. Je pense que vous regardez la complexité temporelle d'une RAM réelle lorsque l'entrée est donnée sous forme de chaîne de bits.
Tsuyoshi Ito
4
Même décider si jamais Mario frappe un sommet (indépendant de ) semble difficile. Je pense que nous rencontrons ici de nombreuses inconnues dans le domaine de la dynamique du billard.
Joseph O'Rourke,
2
Pas vraiment lié, mais cet article sur le NP-Completeness of Super Mario est vraiment étonnant: arxiv.org/pdf/1203.1895v1.pdf
Lamine
10
"Peut-être que c'est pourquoi il est si bien noté", a déclaré quelqu'un complètement apathique à propos de la théorie de la complexité.
Jeff le

Réponses:

7

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π

  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())

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())

Sam Nead
la source
0

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. :)

Peter
la source
10
"A 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'y a qu'un nombre fini de points sur la planète discrétisée." Vous venez de détruire la partie intéressante du problème. Je ne pas veux prendre l'entrée est discrète; Je veux résoudre le problème permanent actuel, même si cela nécessite un ordinateur idéal capable de faire de l'arithmétique exacte en temps constant. En particulier, le chemin de Mario n'a pas besoin de toucher un sommet.
Jeffε
J'ai pensé que c'était trop facile. Vous pouvez faire la version continue sur une machine finie, à condition que le point de départ et la planète puissent être décrits avec précision. Vous pouvez simplement représenter le chemin symboliquement (style mathematica). Vous devez seulement évaluer certaines limites pour trouver la facette dans laquelle vous vous retrouvez. Si vous pouvez prouver que le chemin est presque certainement périodique (comme pour les billards sur des polygones convexes rationnels), vous pouvez toujours appliquer le même truc, mais le résultat ne serait pas très pratique.
Peter
12
Hélas, les géodésiques génériques sur les polyèdres génériques ne sont pas périodiques. (En particulier, les polygones génériques ne sont pas rationnels.)
Jeffε
Je pense que vous (Peter) faites référence au document "Les orbites périodiques du billard sont denses en polygones rationnels". Cela ne signifie pas que les chemins périodiques sont génériques dans les polygones rationnels. En fait, il n’ya que de nombreux chemins périodiques dénombrables (jusqu’au parallélisme), ils n’ont donc aucune chance d’être génériques.
Sam Nead
En fait, dans un polygone "Veech", les chemins "uniquement ergodiques" sont complets. Donc, si nous envoyons Mario dans une direction aléatoire, il (a) ne touchera jamais un sommet (comme le dit Jeffe dans l’énoncé du problème), (b) son chemin ne se fermera jamais, et (c) à grande échelle, la séquence de les visages visités auront un aspect aléatoire (en raison de la propriété "mélange faible"). Cela ne suggère pas une réponse négative au problème - par exemple, les chiffres de pi ont également une apparence aléatoire ...
Sam Nead