算法-如何高效找到最短路径?

算法-如何高效找到最短路径?

晚风撩人 发布于 2017-05-28 字数 227 浏览 1179 回复 1

计算红色格子间最短距离,只能横向和竖向走,其间获取会有障碍物(黑色格子)存在于某些单元格内视为障碍物,碰到障碍物需走其他路线

请输入图片描述

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

归属感 2017-07-18 1 楼

A* 算法是解决此类问题比较常用的,也推荐你看一下 A* Pathfinding for Beginners,如果问题规模不大,可以考虑 Dijkstra 算法,其实都是动态规划的思想,根据你的实际问题,可以自行设计做下变形。优先确定一下障碍物摆放是否是有规律的,可以首先扫描一次排除其中的孤岛区域。可以参看一下这个问题:@寻路算法:被围住的区域@请教游戏开发中角色寻路算法

运行期间最为高效的途径应该是查表,表可能会比较臃肿,但这时候得到的是"数字集合",在这个基础上还是可以做压缩优化的。