J'essaie d'accélérer mon cheminement et j'ai découvert A * avec JPS . Il taille essentiellement les tuiles avant de les ajouter à l'ensemble OPEN.
Puis-je utiliser cette technique avec ma grille qui ne permet que des directions droites?
Si vous lisez l'article , vous verrez qu'ils répertorient cela comme un problème ouvert dans la section "Conclusions":
"Une direction intéressante pour les travaux futurs est d'étendre les points de saut à d'autres types de grilles, comme les hexagones ou les texes (Yap 2002). Nous proposons d'y parvenir en développant une série de règles d'élagage analogues à celles données pour les grilles carrées."
Ainsi, pour appliquer la recherche de points de saut à votre grille orthogonale, vous devez décider quels points doivent compter comme points de saut sur cette grille. Après y avoir réfléchi un instant, je pense - mais je n'ai pas prouvé! - que les règles suivantes (basées sur les définitions 1 et 2 du document, quelque peu reformulées pour plus de lisibilité) puissent fonctionner:
Un nœud y est le point de saut du nœud x, se dirigeant dans la direction d, si y est accessible à partir de x en se déplaçant directement dans la direction d, et est le nœud le plus proche de x pour satisfaire au moins une des conditions suivantes:
Bien entendu, les mots "vertical" et "horizontal" peuvent être échangés dans la définition ci-dessus. Le fait est que nous devons choisir un moyen de briser la symétrie afin de ne considérer qu'un seul des chemins possibles pour traverser une région rectangulaire ouverte. Harabor et Grastien le font en préférant les chemins "diagonaux d'abord", mais comme nous ne pouvons pas le faire, nous devons faire en préférant les chemins verticaux d'abord (ou horizontaux d'abord).
Il pourrait également être possible de développer des règles d'élagage alternatives qui produisent des chemins plus «naturels», comme préférer le cap actuel au virage, ou peut-être même préférer les chemins d'escalier qui tournent constamment. La règle que j'ai donnée ci-dessus est tout simplement la traduction la plus simple de la règle Harabor & Grastien en une grille orthogonale à laquelle je pouvais penser.
En fait, si vous regardez la définition d'un itinéraire à 45 degrés, il est toujours possible de transformer un chemin avec un itinéraire à 45 degrés en un chemin sans virage à 45 degrés. Et c'est aussi optimal (vous pouvez facilement le prouver par contradiction).
Ainsi, le moyen le plus simple consiste à exécuter la recherche de points de saut, puis à la transformer en route orthogonale.
la source