Un algorithme d'étoiles dans un espace de configuration 3D

Question

J'ai fait des recherches sur l'algorithme A * et d'autres algorithmes basés sur des graphes mais la plupart des tutoriels et des implémentations sont faits avec une grille 2D et 2 paramètres (coordonnées x, y).

Est-ce que quelqu'un a de bons tutoriels avec des exemples (C++ ou Java) ou des liens sur A * dans un espace de configuration différent. Tels que l'environnement 3D ou hors réseau, avec x, y, z ou x, y, orientation, ou toute autre chose ...

Merci

Answer 1

Le général algorithme A * ne comprend pas une grille ni dimension. C'est un algorithme de plus court chemin pour un graphe pondéré. Ce que sont les nœuds et les arêtes de ce graphique est complètement spécifique au scénario.

Dans le cas d'une grille 2D, les noeuds sont les cellules de la grille et les arêtes spécifient la contiguïté. Un graphique similaire peut être construit à partir d'une grille 3D. Si vous ne voulez pas vous limiter aux grilles, vous pouvez construire n'importe quel graphe avec une connectivité arbitraire.

Les nœuds n'ont pas nécessairement besoin de correspondre aux positions et les poids n'ont pas nécessairement besoin de correspondre aux distances. Par exemple, le Pinocchio System utilise A * pour développer une incorporation de squelette. La distance ici est la qualité/énergie d'inclusion (bien que l'énergie ne soit pas accumulée le long d'un chemin). Les nœuds correspondent à des plongements partiels.