不同楼层之间的寻路

helloxiaoming

[em24]起点和终点在不同的楼层的寻路怎么实现，用A*的话连接两个楼层之间的点的f值怎么算，f函数怎么写比较好?

kaikai

直接用直线距离也可，有解的话总是可以找到。
当然效果取决于楼层之间通道的数量和分布。

helloxiaoming

直接用距离的话，算法总是先往目标的正下方/上方搜索，如果楼梯不在同一个方向，感觉效率很低。

kaikai

那么先把楼层按可达区域划分为若干节点。按楼层之间的通道建立节点的联系。
将寻路拆分为大尺度上寻找从出发点所在区域到目标点所在区域的节点路径；
小尺度上在节点内由a*寻找起始节点中出发点到楼层通道的、中间节点中的楼层通道到楼层通道、末尾节点中的楼层通道到目标点的路径。
最后连接所有路径。
大尺度上的节点使用哪种方式寻路则还需要由具体情况决定。
如果区域节点之间存在多个通道，则在小尺度寻路时还需要枚举选择不同通道时的权做比较。
如果连续多层出现多个通道可用，则可考虑对每层的通道作为中间状态用动态规划求最佳路径。
当不必找到最优路径的时候，则可随机选取通道。