Eu estou trabalhando em uma solução que envolve determinar a rota de menor esforço entre dois pontos de um prédio. (Imagine estudantes em seu primeiro dia de universidade, e que precisam saber onde fica e como chegar a uma dada sala de aula em um prédio, ou como ir da sala atual para a próxima aula.)

Basicamente eu tenho uma estrutura cartesiana onde cada andar está mapeado. Eu também tenho indicadores de pontos de acesso (portas, rampas para deficientes, escadarias) e os pontos onde estes pontos se conectam (Escadaria do Térreo se conecta com escadaria do 2º andar em X48 Y4, por exemplo), mais ou menos como a imagem abaixo:

![inserir a descrição da imagem aqui][1]

Onde **ciano** indica uma escadaria, e **azul-estranho** elevadores, entre outros marcadores não exibidos.

(Para os daltônicos, minhas sinceras desculpas e algumas informações adicionais: as escadarias estão localizadas na parte superior direita dos mapas; os elevadores, próximos ao centro.)

Eu comecei meu código baseado em uma variante do algoritmo de Dijkstra chamado [A-Estrela (A*)][2], que é basicamente o [problema do caminho mais curto][3] com algumas otimizações. (Curiosidade: Vários jogos implementam variantes do A* para determinar a rota de personagens em um mapa.)

![inserir a descrição da imagem aqui][4]

A* é perfeito para determinar rotas em um mesmo andar, porém eu tenho que levar em consideração os vários andares, cada um com um layout diferente.


Pergunta
--
Existe alguma maneira mais apropriada para solucionar este problema?  

<sub>Ou, de forma mais clara (obrigado bfavaretto),</sub>  

Dado o fator adicional de N andares, existe algum algoritmo que seja mais indicado do que o A*?


  [1]: https://i.sstatic.net/qZRPJ.png
  [2]: http://en.wikipedia.org/wiki/A*_search_algorithm
  [3]: http://en.wikipedia.org/wiki/Shortest_path_problem
  [4]: https://i.sstatic.net/6aNIN.gif