algorithm - 在不同楼层寻找A到B的路径

Question

我有一个问题，我将考虑使用什么算法或方法来解决寻找从 A 点到 B 点的路径的特定问题，其中两个点不在同一平面上(位于复合体的不同楼层/层) - 可能不在同一栋大楼上)。

我正在考虑两者A*和 Dijkstra's算法。然而，基于该算法(如果我错了，请纠正我)仅关注单个 map 图。对于上述算法来说，拥有不同的 map (由于许多楼层和许多建筑物)可能会有不同的故事。

根据难度，我为所有 map 设计了一种格式，以遵循数据的一致性。在每个 map 中，存在建筑物名称、楼层号、每层可能具有的部分以及平面图(转换为二维单字符数组)的数据。例如(两个 map 位于不同的文件中):

//MainFloor1             //MainFloor2
Main                    Main
1st                     2nd
1:Wall                  1:Wall
2:Door                  2:Door
3:Elevator              3:Elevator
#                       4:Room1
1111441111              5:Room2
1        1              #
1        1              1111441111
1        1              1552  2441
1111221111              1551  1441
#                       1551  1441
//End-MainFloor1        1111221111
                        #
                        //End-MainFloor2

根据给定的 map ，如果我想考虑从 A 点(MainFloor1 的第一个“2”下方)到 B 点(MainFloor2 左上角的第一个“4”)将返回结果.

// X is the path from Point A to Point B
1111X41111 1111X41111
1   X    1 1552XXXB41 
1   X    1 1551  1441 
1   X    1 1551  1441 
1111A21111 1111221111

我将考虑或采取什么方法来根据给定的 map 输入生成这样的结果？

谢谢

Answer 1

A*、BFS 等都是适用于 graphs 的算法。您的问题可以被视为一个图表，其中两个节点(顶点)之间存在一条边，如果它们相邻且位于同一楼层，或如果它们代表同一部电梯，但位于不同楼层。

请注意，您可以在内存中显式构建图形，但您不必这样做 - 您可以简单地将其视为从探路者的角度来看的图形。