Jump point search
# Jump point search

Le terme anglais : Jump Point Search (JPS (Harabor et Grastien 2012), littéralement « Recherche du point par saut ») un algorithme de recherche de chemin. C'est une variante de l'algorithme A*, optimisée pour le cas des grilles à coût uniforme.

L'évolution, JPS+ (Harabor et Grastien 2014), réduit les symétries dans la procédure de recherche, en supprimant des parties non nécessaire du graphe d'après une de leurs recherches de 2011.

Si cette technique est avant tout utilisée pour l'intelligence artificielle, en particulier dans les jeux vidéo, d'autres auteurs ont proposé de les utiliser pour la construction des immeubles de grande hauteur, afin d'en améliorer la productivité.

## Améliorations

Il existe également différentes autres variantes, JPS+ Bucket, BLJPS, BLJPS2, $BLJPS_Subgoal^,$

La technique de compression RLE des tables de chemins optimaux (anglais : Compressing Optimal Paths with Run Length Encoding (Strasser, Botea et Harabor 2015)), permet également d'améliorer l'efficacité de tous ces algorithmes en compressant la table de pré-calcul, permettant l'utilisation de moins de ressources mémoires et un accès plus court aux informations.

