La méthode de ./44 telle quelle ne t'apportera pas gd-chose, c'est efficace uniquement si tu as de grands espaces 2d dans lesquels tu peux te déplacer librement... (ce qui n'est pas le cas ici, tu ne peux pas voler dans les espaces vides)

Là puisque tu n'as pas d'objets mobiles tu devrais plutôt calculer explicitement le graphe du niveau, avec un sommet à chaque case... Ensuite tu peux appliquer des transformations, alors je sais pas mais moralement je me dis qu'il faudrait essayer de trouver des "blocs" avec un faible nombre de sommets d'entrée et de sortie ; par exemple si tu as une échelle :

<- A -> X
   ^    |
   |    v
   X -> X
   ^    |
   |    v
   X -> X
   ^    |
   |    v
-> B -> C ->

tu peux considérer que les sommets A, B et C sont les seuls sommets d'entrée-sortie accessibles de l'extérieur de l'échelle, donc tu peux réduire le bloc au graphe suivant, en cachant les sommets X :

<- A
   ^ \
   |  x
-> B -> C ->

L'idée étant que si tu cherches un chemin entre le point U et le point V, soit l'une des extrêmités est cachée dans le bloc, et alors on utilise le graphe non simplifié, soit aucune des extrêmités n'est cachée, et alors tu peux utiliser le graphe simplifié. Tu peux généraliser à un nombre arbitraire de blocs, et même une hiérarchie de blocs (par exemple, si ton échelle est trèèès longue, un bloc pour le bas de l'échelle, un bloc pour le haut de l'échelle, et un super-bloc pour l'union des deux).

Il ne reste plus qu'à trouver comment construire la hiérarchie des blocs, par exemple, si ton graphe satisfait la condition "pour tout sous-ensemble de points du graphe il y a une partition de ce sous-ensemble en deux blocs de taille à peu près égale et dont le nombre de points d'entrée-sorties est inférieur à M fixé", alors on peut facilement trouver une solution au problème du pathfinding entre U et V quelconques en O(M^2 log N) où N est le nb de sommets du graphe de départ ^^