这一章把直线连接改为折线连接,沿用原来连接点的关系信息。关于折线的计算,使用的是开源的 AStar 算法进行路径规划,启发方式为 曼哈顿距离,且不允许对角线移动。
请大家动动小手,给我一个免费的 Star 吧~
大家如果发现了 Bug,欢迎来提 Issue 哟~
github源码
gitee源码
示例地址
灵感来源主要来自于下面优秀的文章:
关联线探究,如何连接流程图的两个节点
主要参考了:如何挑选连接点及其真正的出入口、算法的选型。具体代码没有仔细了解,毕竟布局和元素的想法不一样,没必要参考代码。
路径规划之 A* 算法
主要了解一下算法的介绍。
欧式距离、曼哈顿距离、切比雪夫距离、Octile距离
主要了解一下 AStar 算法的各种启发方式的差异。
路径规划可视化动画
形象的感受路径搜索的差异。
至于算法本身,在目前阶段下不是必须深入分析,这里应用为主。
最优路径
参考这张图,基于当前案例,可以把折线想象为路径,目标就是查找最优路径,例如:
又或者:
上面明显不是我们直觉最优的路径选择,如:
- 太贴近节点了
- 转弯太多
更希望是这样:
开启调试模式,来说说连接点的出入口:
人为地,距离”连接点“偏离一些,定义所谓的”出入口“(途中绿色的点),作为折线真的起点和终点。
把连线先移除,看看其他点:
一共定义了 3 种点:
- 连接点(红色)
- 出入口(绿色)
- 途径点(蓝色)
关于途径点,是人为挑选的,主要(中心点除外)来自于图中不同颜色区域(线框),这里定义了 ?种区域:
- 连接点最小区域
为什么不叫节点区域呢?因为此前设计的连接点是动态的,它可以节点内部的其他位置,只是目前定义的都是上下左右边缘而已。所以,它可能比节点区域更小。
- 连线不可通过区域
- 连线不可通过扩展区域
两个区域共同所在的最小区域
- 连线通过区域
- 连线通过扩展区域
同理,两个区域共同所在的最小区域
算法建模(关键)
上面说了那么多点和区域,最终目的就是为了建模,可供算法使用。
这个模型,就是一个数组矩阵 matrix,可以理解成一个格子地图,如:
0 代表可通过,1 代表不可通过(称之为“墙”吧),对应的数组矩阵,就是
[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
计算结果是一个途径格子坐标数组:
坐标就是数组1、2层下标,可以视作 x、y 轴。
[
[5, 3],
[6, 3],
[7, 3],
[8, 3],
[8, 4],
[8, 5]
]
主要问题来了,毕竟在这里的画板,不同于算法示例那样“走格子”,800×800 的画布大小,不可能建一个 800×800 数组矩阵,性能可吃不消,别说更大的画布了。
所以,如何建模才是这个案例画折线的关键!
这里,拿一个大一点的例子说明:
既然,拿“像素”当作格子不现实,可以拿“点”作为格子不就好了吗?
数组矩阵变成:
[
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]
]
这里缺少了“墙”,哪些是墙?其实就是上面说的不可通过区域:
“墙”不同于连接点,需要补充一些点:
数组矩阵变成(增加了 2 列、2 行):
[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
然后给数组矩阵设置“墙”:
这里把 2 定义为墙,所以 0、1 均能通过,方便后面区分和理解。
[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 2, 2, 2, 0, 0, 0, 2, 2, 2, 0],
[0, 2, 2, 2, 0, 0, 0, 2, 2, 2, 0],
[0, 2, 2, 2, 0, 0, 0, 2, 2, 2, 0],
[0, 2, 2, 2, 0, 0, 0, 2, 2, 2, 0],
[0, 2, 2, 2, 0, 0, 0, 2, 2, 2, 0],
[0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]
连接点、连接线的出入口不应该是“墙”,调整一下:
设置为 1,方便区分
起点:[2, 3]
终点:[8, 5]
现在交给算法,计算结果得出:
就是:
画成线:
主要思路就是如此,虽然不是完美的,请看:
原因主要是算法并不知道拐弯的“代价”,暂且如此吧。
思路的介绍到此为止,下一章再说说代码大概是如何实现的。
More Stars please!勾勾手指~
源码
gitee源码
示例地址
未经允许不得转载:大白鲨游戏网 » 前端使用 Konva 实现可视化设计器(13)- 折线 – 最优路径应用【思路篇】