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:
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*), que é basicamente o problema do caminho mais curto com algumas otimizações. (Curiosidade: Vários jogos implementam variantes do A* para determinar a rota de personagens em um mapa.)
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?
Ou, de forma mais clara (obrigado bfavaretto),
Dado o fator adicional de N andares, existe algum algoritmo que seja mais indicado do que o A*?
Disclaimer:
Imagem isométrica original de DougIllustrations.com.