Orientation sur une surface planétaire inégale

16

Ma question est quelle serait la meilleure approche pour trouver un chemin sur une surface planétaire inégale?


Informations d'arrière-plan

J'ai créé une planète à partir d'un déplacement cartographiant 6 plans projetés de sphère. Les plans ont initialement formé un cube avant d'être projetés en forme de sphère.

entrez la description de l'image ici

Je me demande s'il est possible d'utiliser chaque "face de cube de sphère projetée" comme grilles et d'utiliser un simple algorithme A * pour trouver le meilleur itinéraire possible, j'aimerais aussi que la hauteur de déplacement soit prise en compte pour que le chemin évite de grimper montagnes, etc. (je suppose que ce ne serait qu'une heuristique dans l'algorithme A *) Une autre considération est que j'ai réalisé un mouvement planétaire en tirant parti du moteur physique d'Unity3d, en appliquant la gravité vers le centre de la planète. Ma solution proposée exigerait-elle que le mouvement des agents soit contrôlé indépendamment de la physique gravitationnelle.

Pour aider à mieux articuler ma question, voici mon corps planétaire actuel:

entrez la description de l'image ici

Caius Eugene
la source
2
Vous pouvez être intéressé par cette vidéo de l'annihilation planétaire. Ils semblent faire la même chose que vous envelopper le monde d'un cube et trouver un chemin autour de lui. Ce n'est pas vraiment une réponse, mais vous pouvez voir qu'ils utilisent A * avec d'autres stratégies pour optimiser la recherche de chemin autour d'une sphère. Le bit de recherche de chemin commence à 24h30 .
MichaelHouse
@ Byte56 Merci pour ce lien approche vraiment intéressante des coûts, j'ai hâte de voir ce jeu quand il sera terminé!
Caius Eugene

Réponses:

12

Il semble que vous ayez déjà répondu à votre propre question. Un * est probablement la meilleure approche. Oui, bien sûr, il peut être utilisé de la manière que vous décrivez, y compris en utilisant les informations de hauteur pour éviter les montagnes. Tant que vous êtes en mesure d'accéder à des informations sur n'importe quelle grille à la surface de votre monde, il n'y a aucune raison que vous ne puissiez pas l'utiliser dans l'heuristique A *.

Enfin, vous confondez la recherche de chemin avec le suivi de chemin à la fin de votre question. La recherche de chemin ne se soucie pas de la gravité, sauf si vous l'ajoutez comme heuristique et puisque vous êtes à la surface d'une planète, la gravité sera essentiellement la même sur toute la surface. De nombreux jeux ont de la gravité et du mouvement, je ne vois aucune raison pour laquelle vous ne pouvez pas.

Fondamentalement, nous voulons cartographier le passage du rouge au bleu, pour être le même sur une sphère que sur un cube.

entrez la description de l'image ici

Comme A * obtient fréquemment des voisins sur son nœud actuel, vous pouvez facilement créer un ensemble de fonctions pour obtenir des nœuds adjacents. Par exemple, getXPlus(), getXMinus(), getZPlus()et ainsi de suite. Ces fonctions prendront le nœud actuel et retourneront le nœud dans la direction spécifiée par le nom de la fonction.

La plupart du temps, ces fonctions peuvent simplement incrémenter une valeur et être effectuées, cependant, sur les bords, cela changera.

Vous souhaiterez mapper la surface de votre cube sur un système de coordonnées 2D. Quoi que vous fassiez, cela ne dépend que de vous, ils n'ont pas à s'aligner, il suffit de donner à chaque espace de la grille une coordonnée X, Y unique.

Maintenant, sur une arête, et en obtenant l'espace de grille adjacent, cela n'augmentera pas nécessairement les coordonnées. Nous devons trouver la face vers laquelle nous allons et passer aux coordonnées de cette face.

Par exemple, obtenir les coordonnées XPlus ici changera les coordonnées X et Y parce que nous nous déplaçons vers un nouvel espace de grille sur une nouvelle face. La ligne verte représente un bord entre deux faces.

entrez la description de l'image ici

Maintenant, ce ne sont que des coordonnées globales, il peut être plus facile d'utiliser un système de coordonnées local interne, avec une 3ème dimension qui représente la face du cube sur laquelle vous vous trouvez actuellement.

Dans les deux cas, vous devez avoir une coordonnée unique pour chaque espace de grille sur la face du cube. Le déplacement entre eux dépendra de la façon dont vous implémentez le système de coordonnées. Vous devez également savoir où ces coordonnées correspondent à la surface de la sphère.

Tout cela devrait finalement être résumé afin que vous ne le sachiez même pas.

MichaelHouse
la source
Vive la réponse. Je pense que ce avec quoi je me bats, c'est que chaque avion est une grille isolée. Auriez-vous des suggestions (ou des lectures supplémentaires) sur la façon de gérer les coutures, je suppose que je vais déplier mathématiquement mon "cube", combiner toutes les grilles et calculer le chemin à l'aide de cet ensemble de données?
Caius Eugene
Vraiment, ce ne sont que les bords dont vous devez vous soucier. Cela est facilement résolu par une fonction wrapper (envelopper votre cube dans une fonction wrapper, qui enveloppe votre monde ...). Vous pouvez résumer le cube en une surface plane qui s'enroule. Créez des fonctions pour obtenir l'espace de grille adjacent, getXPlus () obtiendra la grille dans la direction XPlus, peu importe si elle se trouve à la frontière entre les faces, la fonction changera simplement de face et retournera les informations de grille appropriées.
MichaelHouse
La seule imprécision avec la recherche de chemin sur le cube plié est que les sommets sont asymétriques et que les bords ont donc des longueurs différentes. Il est possible que cela ne fasse pas de différence notable dans les chemins résultants et sinon vous pourriez simplement prendre en compte les longueurs.
danijar
1
La chose importante à comprendre ici est que A * ne fonctionne pas nécessairement sur un plan; il fonctionne sur un graphique. Bien que dans chaque face de cube, les nœuds soient disposés et connectés dans une grille, il existe également des connexions de nœuds sur les bords du cube.
jmegaffin
1
@ Byte56 Merci pour la bonne réponse, j'ai commencé à implémenter une solution mais j'ai rencontré un petit obstacle. J'ai peut-être mal compris. J'ai posté une question sur stackoverflow car je sentais que c'était plus un problème de math / programmation stackoverflow.com/questions/16089074/…
Caius Eugene