经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
前端使用 Konva 实现可视化设计器(14)- 折线 - 最优路径应用【代码篇】
来源:cnblogs  作者:xachary  时间:2024/6/12 16:21:55  对本文有异议

话接上回《前端使用 Konva 实现可视化设计器(13)- 折线 - 最优路径应用【思路篇】》,这一章继续说说相关的代码如何构思的,如何一步步构建数据模型可供 AStar 算法进行路径规划,最终画出节点之间的连接折线。

请大家动动小手,给我一个免费的 Star 吧~

大家如果发现了 Bug,欢迎来提 Issue 哟~

github源码

gitee源码

示例地址

补充说明

上一章说到使用了开源 AStar 算法,它并不支持计算折线拐弯的代价,最终结果会出现不必要的拐弯,现已经把算法替换成自定义 AStar 算法,支持计算拐弯代价,减少了不必要的折线拐弯。

AStar 算法基本逻辑可以参考《C++: A*(AStar)算法》,本示例的自定义 AStar 算法,是在此基础上增加支持:格子代价、拐弯代价。

代码不长,可以直接看看:

关键要理解 AStar 算法的基本思路,特别是“open 和 closed 列表”、“每个节点的 f, g, h 值”

  1. // src\Render\utils\aStar.ts
  2. export interface Node {
  3. x: number
  4. y: number
  5. cost?: number
  6. parent?: Node
  7. }
  8. export default function aStar(config: {
  9. from: Node
  10. to: Node
  11. matrix: number[][]
  12. maxCost: number
  13. }): Node[] {
  14. const { from, to, matrix, maxCost = 1 } = config
  15. const grid: Node[][] = matrixToGrid(matrix)
  16. const start = grid[from.y][from.x]
  17. const goal = grid[to.y][to.x]
  18. // 初始化 open 和 closed 列表
  19. const open: Node[] = [start]
  20. const closed = new Set<Node>()
  21. // 初始化每个节点的 f, g, h 值
  22. const f = new Map<Node, number>()
  23. const g = new Map<Node, number>()
  24. const h = new Map<Node, number>()
  25. g.set(start, 0)
  26. h.set(start, manhattanDistance(start, goal))
  27. f.set(start, g.get(start)! + h.get(start)!)
  28. // A* 算法主循环
  29. while (open.length > 0) {
  30. // 从 open 列表中找到 f 值最小的节点
  31. const current = open.reduce((a, b) => (f.get(a)! < f.get(b)! ? a : b))
  32. // 如果当前节点是目标节点,返回路径
  33. if (current === goal) {
  34. return reconstructPath(goal)
  35. }
  36. // 将当前节点从 open 列表中移除,并加入 closed 列表
  37. open.splice(open.indexOf(current), 1)
  38. closed.add(current)
  39. // 遍历当前节点的邻居
  40. for (const neighbor of getNeighbors(current, grid)) {
  41. // 如果邻居节点已经在 closed 列表中,跳过
  42. if (closed.has(neighbor)) {
  43. continue
  44. }
  45. // 计算从起点到邻居节点的距离(转弯距离增加)
  46. const tentativeG =
  47. g.get(current)! +
  48. (neighbor.cost ?? 0) +
  49. ((current.x === current.parent?.x && current.x !== neighbor.x) ||
  50. (current.y === current.parent?.y && current.y !== neighbor.y)
  51. ? Math.max(grid.length, grid[0].length)
  52. : 0)
  53. // 如果邻居节点不在 open 列表中,或者新的 g 值更小,更新邻居节点的 g, h, f 值,并将其加入 open 列表
  54. if (!open.includes(neighbor) || tentativeG < g.get(neighbor)!) {
  55. g.set(neighbor, tentativeG)
  56. h.set(neighbor, manhattanDistance(neighbor, goal))
  57. f.set(neighbor, g.get(neighbor)! + h.get(neighbor)!)
  58. neighbor.parent = current
  59. if (!open.includes(neighbor)) {
  60. open.push(neighbor)
  61. }
  62. }
  63. }
  64. }
  65. // 如果 open 列表为空,表示无法到达目标节点,返回 null
  66. return []
  67. // 数据转换
  68. function matrixToGrid(matrix: number[][]) {
  69. const mt: Node[][] = []
  70. for (let y = 0; y < matrix.length; y++) {
  71. if (mt[y] === void 0) {
  72. mt[y] = []
  73. }
  74. for (let x = 0; x < matrix[y].length; x++) {
  75. mt[y].push({
  76. x,
  77. y,
  78. cost: matrix[y][x]
  79. })
  80. }
  81. }
  82. return mt
  83. }
  84. // 从目标节点开始,沿着 parent 指针重构路径
  85. function reconstructPath(node: Node): Node[] {
  86. const path = [node]
  87. while (node.parent) {
  88. path.push(node.parent)
  89. node = node.parent
  90. }
  91. return path.reverse()
  92. }
  93. // 计算曼哈顿距离
  94. function manhattanDistance(a: Node, b: Node): number {
  95. return Math.abs(a.x - b.x) + Math.abs(a.y - b.y)
  96. }
  97. // 获取当前节点的邻居
  98. function getNeighbors(node: Node, grid: Node[][]): Node[] {
  99. const neighbors = []
  100. const { x, y } = node
  101. if (x > 0 && (grid[y][x - 1].cost ?? 0) < maxCost) {
  102. neighbors.push(grid[y][x - 1])
  103. }
  104. if (x < grid[0].length - 1 && (grid[y][x + 1].cost ?? 0) < maxCost) {
  105. neighbors.push(grid[y][x + 1])
  106. }
  107. if (y > 0 && (grid[y - 1][x].cost ?? 0) < maxCost) {
  108. neighbors.push(grid[y - 1][x])
  109. }
  110. if (y < grid.length - 1 && (grid[y + 1][x].cost ?? 0) < maxCost) {
  111. neighbors.push(grid[y + 1][x])
  112. }
  113. return neighbors
  114. }
  115. }

在数据结构上,还有优化空间,应该可以减少性能和内存的消耗,暂且如此。

算法建模

主要逻辑在 src\Render\draws\LinkDraw.ts 的 draw 方法的画连接线的部分:

事前准备,把所有 节点、连接点、连接对 整理出来:

  1. override draw() {
  2. this.clear()
  3. // stage 状态
  4. const stageState = this.render.getStageState()
  5. const groups = this.render.layer.find('.asset') as Konva.Group[]
  6. const points = groups.reduce((ps, group) => {
  7. return ps.concat(Array.isArray(group.getAttr('points')) ? group.getAttr('points') : [])
  8. }, [] as LinkDrawPoint[])
  9. const pairs = points.reduce((ps, point) => {
  10. return ps.concat(point.pairs ? point.pairs : [])
  11. }, [] as LinkDrawPair[])
  12. // 略
  13. }

主要逻辑,请看代码备注(一些工具方法,后面单独说明):

  1. override draw() {
  2. // 略
  3. // 连接线(根据连接对绘制)
  4. for (const pair of pairs) {
  5. // 连接起点节点、连接点
  6. const fromGroup = groups.find((o) => o.id() === pair.from.groupId)
  7. const fromPoint = points.find((o) => o.id === pair.from.pointId)
  8. // 连接终点节点、连接点
  9. const toGroup = groups.find((o) => o.id() === pair.to.groupId)
  10. const toPoint = points.find((o) => o.id === pair.to.pointId)
  11. // 最小区域
  12. const fromGroupLinkArea = this.getGroupLinkArea(fromGroup)
  13. const toGroupLinkArea = this.getGroupLinkArea(toGroup)
  14. // 两区域的最短距离(用于动态缩短连接点及其出入口的距离)
  15. const groupDistance = this.getGroupPairDistance(fromGroupLinkArea, toGroupLinkArea)
  16. // 不可通过区域
  17. const fromGroupForbiddenArea = this.getGroupForbiddenArea(
  18. fromGroupLinkArea,
  19. groupDistance - 2
  20. )
  21. const toGroupForbiddenArea = this.getGroupForbiddenArea(toGroupLinkArea, groupDistance - 2)
  22. // 两区域扩展
  23. const groupForbiddenArea = this.getGroupPairArea(fromGroupForbiddenArea, toGroupForbiddenArea)
  24. // 连线通过区域
  25. const groupAccessArea = this.getGroupPairArea(
  26. this.getGroupAccessArea(fromGroupForbiddenArea, groupDistance),
  27. this.getGroupAccessArea(toGroupForbiddenArea, groupDistance)
  28. )
  29. if (fromGroup && toGroup && fromPoint && toPoint) {
  30. // 起点、终点的锚点
  31. const fromAnchor = fromGroup.findOne(`#${fromPoint.id}`)
  32. const toAnchor = toGroup.findOne(`#${toPoint.id}`)
  33. // 锚点信息
  34. const fromAnchorPos = this.getAnchorPos(fromAnchor)
  35. const toAnchorPos = this.getAnchorPos(toAnchor)
  36. if (fromAnchor && toAnchor) {
  37. // 连接出入口
  38. const fromEntry: Konva.Vector2d = this.getEntry(
  39. fromAnchor,
  40. fromGroupLinkArea,
  41. groupDistance
  42. )
  43. const toEntry: Konva.Vector2d = this.getEntry(toAnchor, toGroupLinkArea, groupDistance)
  44. type matrixPoint = {
  45. x: number
  46. y: number
  47. type?: 'from' | 'to' | 'from-entry' | 'to-entry'
  48. }
  49. // 可能点(人为定义的希望折线可以拐弯的位置)
  50. let matrixPoints: matrixPoint[] = []
  51. // 通过区域 四角
  52. matrixPoints.push({ x: groupAccessArea.x1, y: groupAccessArea.y1 })
  53. matrixPoints.push({ x: groupAccessArea.x2, y: groupAccessArea.y2 })
  54. matrixPoints.push({ x: groupAccessArea.x1, y: groupAccessArea.y2 })
  55. matrixPoints.push({ x: groupAccessArea.x2, y: groupAccessArea.y1 })
  56. // 最小区域 四角
  57. matrixPoints.push({ x: groupForbiddenArea.x1, y: groupForbiddenArea.y1 })
  58. matrixPoints.push({ x: groupForbiddenArea.x2, y: groupForbiddenArea.y2 })
  59. matrixPoints.push({ x: groupForbiddenArea.x1, y: groupForbiddenArea.y2 })
  60. matrixPoints.push({ x: groupForbiddenArea.x2, y: groupForbiddenArea.y1 })
  61. // 起点
  62. matrixPoints.push({
  63. ...fromAnchorPos,
  64. type: 'from'
  65. })
  66. // 起点 出口
  67. matrixPoints.push({ ...fromEntry, type: 'from-entry' })
  68. // 终点
  69. matrixPoints.push({
  70. ...toAnchorPos,
  71. type: 'to'
  72. })
  73. // 终点 入口
  74. matrixPoints.push({ ...toEntry, type: 'to-entry' })
  75. // 通过区域 中点
  76. matrixPoints.push({
  77. x: (groupAccessArea.x1 + groupAccessArea.x2) * 0.5,
  78. y: (groupAccessArea.y1 + groupAccessArea.y2) * 0.5
  79. })
  80. // 去重
  81. matrixPoints = matrixPoints.reduce(
  82. (arr, item) => {
  83. if (item.type === void 0) {
  84. if (arr.findIndex((o) => o.x === item.x && o.y === item.y) < 0) {
  85. arr.push(item)
  86. }
  87. } else {
  88. const idx = arr.findIndex((o) => o.x === item.x && o.y === item.y)
  89. if (idx > -1) {
  90. arr.splice(idx, 1)
  91. }
  92. arr.push(item)
  93. }
  94. return arr
  95. },
  96. [] as typeof matrixPoints
  97. )
  98. // 上文提到的:“墙”不同于连接点,需要补充一些点
  99. const columns = [
  100. ...matrixPoints.map((o) => o.x),
  101. // 增加列
  102. fromGroupForbiddenArea.x1,
  103. fromGroupForbiddenArea.x2,
  104. toGroupForbiddenArea.x1,
  105. toGroupForbiddenArea.x2
  106. ].sort((a, b) => a - b)
  107. // 去重
  108. for (let x = columns.length - 1; x > 0; x--) {
  109. if (columns[x] === columns[x - 1]) {
  110. columns.splice(x, 1)
  111. }
  112. }
  113. const rows = [
  114. ...matrixPoints.map((o) => o.y),
  115. // 增加行
  116. fromGroupForbiddenArea.y1,
  117. fromGroupForbiddenArea.y2,
  118. toGroupForbiddenArea.y1,
  119. toGroupForbiddenArea.y2
  120. ].sort((a, b) => a - b)
  121. // 去重
  122. for (let y = rows.length - 1; y > 0; y--) {
  123. if (rows[y] === rows[y - 1]) {
  124. rows.splice(y, 1)
  125. }
  126. }
  127. // 屏蔽区域(序号)
  128. const columnFromStart = columns.findIndex((o) => o === fromGroupForbiddenArea.x1)
  129. const columnFromEnd = columns.findIndex((o) => o === fromGroupForbiddenArea.x2)
  130. const rowFromStart = rows.findIndex((o) => o === fromGroupForbiddenArea.y1)
  131. const rowFromEnd = rows.findIndex((o) => o === fromGroupForbiddenArea.y2)
  132. const columnToStart = columns.findIndex((o) => o === toGroupForbiddenArea.x1)
  133. const columnToEnd = columns.findIndex((o) => o === toGroupForbiddenArea.x2)
  134. const rowToStart = rows.findIndex((o) => o === toGroupForbiddenArea.y1)
  135. const rowToEnd = rows.findIndex((o) => o === toGroupForbiddenArea.y2)
  136. // 算法矩阵起点、终点
  137. let matrixStart: Konva.Vector2d | null = null
  138. let matrixEnd: Konva.Vector2d | null = null
  139. // 算法地图矩阵
  140. const matrix: Array<number[]> = []
  141. for (let y = 0; y < rows.length; y++) {
  142. // 新增行
  143. if (matrix[y] === void 0) {
  144. matrix[y] = []
  145. }
  146. for (let x = 0; x < columns.length; x++) {
  147. // 不可通过区域(把范围内的点设定为“墙”)
  148. if (
  149. x >= columnFromStart &&
  150. x <= columnFromEnd &&
  151. y >= rowFromStart &&
  152. y <= rowFromEnd
  153. ) {
  154. // 起点节点范围内
  155. matrix[y][x] = 2
  156. } else if (
  157. x >= columnToStart &&
  158. x <= columnToEnd &&
  159. y >= rowToStart &&
  160. y <= rowToEnd
  161. ) {
  162. // 终点节点范围内
  163. matrix[y][x] = 2
  164. } else {
  165. // 可通过区域
  166. matrix[y][x] = 0
  167. }
  168. // 起点、终点 -> 算法 起点、终点
  169. if (columns[x] === fromAnchorPos.x && rows[y] === fromAnchorPos.y) {
  170. matrixStart = { x, y }
  171. } else if (columns[x] === toAnchorPos.x && rows[y] === toAnchorPos.y) {
  172. matrixEnd = { x, y }
  173. }
  174. // 从 不可通过区域 中找 起点、出口、终点、入口,设置为 可通过(因为与不可通过区域有重叠,所以要单独设置一下)
  175. if (fromEntry.x === fromAnchorPos.x) {
  176. if (
  177. columns[x] === fromAnchorPos.x &&
  178. rows[y] >= Math.min(fromEntry.y, fromAnchorPos.y) &&
  179. rows[y] <= Math.max(fromEntry.y, fromAnchorPos.y)
  180. ) {
  181. matrix[y][x] = 1
  182. }
  183. } else if (fromEntry.y === fromAnchorPos.y) {
  184. if (
  185. columns[x] >= Math.min(fromEntry.x, fromAnchorPos.x) &&
  186. columns[x] <= Math.max(fromEntry.x, fromAnchorPos.x) &&
  187. rows[y] === fromAnchorPos.y
  188. ) {
  189. matrix[y][x] = 1
  190. }
  191. }
  192. if (toEntry.x === toAnchorPos.x) {
  193. if (
  194. columns[x] === toAnchorPos.x &&
  195. rows[y] >= Math.min(toEntry.y, toAnchorPos.y) &&
  196. rows[y] <= Math.max(toEntry.y, toAnchorPos.y)
  197. ) {
  198. matrix[y][x] = 1
  199. }
  200. } else if (toEntry.y === toAnchorPos.y) {
  201. if (
  202. columns[x] >= Math.min(toEntry.x, toAnchorPos.x) &&
  203. columns[x] <= Math.max(toEntry.x, toAnchorPos.x) &&
  204. rows[y] === toAnchorPos.y
  205. ) {
  206. matrix[y][x] = 1
  207. }
  208. }
  209. }
  210. }
  211. if (matrixStart && matrixEnd) {
  212. // 算法使用
  213. const way = aStar({
  214. from: matrixStart,
  215. to: matrixEnd,
  216. matrix,
  217. maxCost: 2
  218. })
  219. // 画线
  220. this.group.add(
  221. new Konva.Line({
  222. name: 'link-line',
  223. // 用于删除连接线
  224. groupId: fromGroup.id(),
  225. pointId: fromPoint.id,
  226. pairId: pair.id,
  227. //
  228. points: _.flatten(
  229. way.map((o) => [
  230. this.render.toStageValue(columns[o.x]),
  231. this.render.toStageValue(rows[o.y])
  232. ])
  233. ),
  234. stroke: 'red',
  235. strokeWidth: 2
  236. })
  237. )
  238. }
  239. }
  240. }
  241. }
  242. // 略
  243. }

关于代码里提到的“动态缩短连接点及其出入口的距离”,上面代码里的“groupDistance”变量,由于我们人为定义了连接点的出入口,出入口距离连接点是存在一些距离的,当两个节点距离太近的时候,其实就是两个出入口在某一方向上挨在一起,导致算法认为“无路可走”,无法绘制连接线了:

image

因此,当两个节点距离太近的时候,动态缩小这个距离:
image

这里定义了,动态的距离范围在 6px ~ 背景网格大小 之间,取决于两个节点之间的最短距离。

  1. getGroupPairDistance(groupArea1: Area, groupArea2: Area): number {
  2. const xs = [groupArea1.x1, groupArea1.x2, groupArea2.x1, groupArea2.x2]
  3. const maxX = Math.max(...xs)
  4. const minX = Math.min(...xs)
  5. const dx = maxX - minX - (groupArea1.x2 - groupArea1.x1 + (groupArea2.x2 - groupArea2.x1))
  6. const ys = [groupArea1.y1, groupArea1.y2, groupArea2.y1, groupArea2.y2]
  7. const maxY = Math.max(...ys)
  8. const minY = Math.min(...ys)
  9. const dy = maxY - minY - (groupArea1.y2 - groupArea1.y1 + (groupArea2.y2 - groupArea2.y1))
  10. //
  11. return this.render.toBoardValue(
  12. Math.min(this.render.bgSize, Math.max(dx < 6 ? 6 : dx, dy < 6 ? 6 : dy) * 0.5)
  13. )
  14. }

另外,代码里计算 不可通过区域 的“groupDistance - 2”,减去2个像素点原因是,人为与外层区域留了点空隙,距离缩小至动态范围内,两节点总有空间用于计算数据模型。

下面,逐个说明一下工具方法:

其实就是,所有锚点占用的最小矩形区域

  1. // 元素(连接点们)最小区域(绝对值)
  2. getGroupLinkArea(group?: Konva.Group): Area {
  3. let area: Area = {
  4. x1: 0,
  5. y1: 0,
  6. x2: 0,
  7. y2: 0
  8. }
  9. if (group) {
  10. // stage 状态
  11. const stageState = this.render.getStageState()
  12. const anchors = group.find('.link-anchor')
  13. const positions = anchors.map((o) => o.absolutePosition())
  14. area = {
  15. x1: Math.min(...positions.map((o) => o.x)) - stageState.x,
  16. y1: Math.min(...positions.map((o) => o.y)) - stageState.y,
  17. x2: Math.max(...positions.map((o) => o.x)) - stageState.x,
  18. y2: Math.max(...positions.map((o) => o.y)) - stageState.y
  19. }
  20. }
  21. return area
  22. }

其实就是在传入区域基础上,增加内边距(目前 gap 也就是 groupDistance):

  1. // 连线不可通过区域
  2. getGroupForbiddenArea(groupArea: Area, gap: number): Area {
  3. const area: Area = {
  4. x1: groupArea.x1 - gap,
  5. y1: groupArea.y1 - gap,
  6. x2: groupArea.x2 + gap,
  7. y2: groupArea.y2 + gap
  8. }
  9. return area
  10. }

同上

  1. // 连线通过区域
  2. getGroupAccessArea(groupArea: Area, gap: number): Area {
  3. const area: Area = {
  4. x1: groupArea.x1 - gap,
  5. y1: groupArea.y1 - gap,
  6. x2: groupArea.x2 + gap,
  7. y2: groupArea.y2 + gap
  8. }
  9. return area
  10. }

两个区域占用的最小矩形区域

  1. // 两区域扩展
  2. getGroupPairArea(groupArea1: Area, groupArea2: Area): Area {
  3. const area: Area = {
  4. x1: Math.min(groupArea1.x1, groupArea2.x1),
  5. y1: Math.min(groupArea1.y1, groupArea2.y1),
  6. x2: Math.max(groupArea1.x2, groupArea2.x2),
  7. y2: Math.max(groupArea1.y2, groupArea2.y2)
  8. }
  9. return area
  10. }

通过元素最小区域和锚点,得出该锚点的出入口

  1. // 连接出入口
  2. getEntry(anchor: Konva.Node, groupLinkArea: Area, gap: number): Konva.Vector2d {
  3. // stage 状态
  4. const stageState = this.render.getStageState()
  5. let entry: Konva.Vector2d = {
  6. x: 0,
  7. y: 0
  8. }
  9. const fromPos = anchor.absolutePosition()
  10. if (fromPos.x - stageState.x === groupLinkArea.x1) {
  11. entry = {
  12. x: fromPos.x - gap - stageState.x,
  13. y: fromPos.y - stageState.y
  14. }
  15. } else if (fromPos.x - stageState.x === groupLinkArea.x2) {
  16. entry = {
  17. x: fromPos.x + gap - stageState.x,
  18. y: fromPos.y - stageState.y
  19. }
  20. } else if (fromPos.y - stageState.y === groupLinkArea.y1) {
  21. entry = {
  22. x: fromPos.x - stageState.x,
  23. y: fromPos.y - gap - stageState.y
  24. }
  25. } else if (fromPos.y - stageState.y === groupLinkArea.y2) {
  26. entry = {
  27. x: fromPos.x - stageState.x,
  28. y: fromPos.y + gap - stageState.y
  29. }
  30. }
  31. return entry
  32. }

到此,折线绘制的主要逻辑就完成了。

已知缺陷

从 Issue 中得知,当节点进行说 transform rotate 旋转的时候,对齐就会出问题。相应的,绘制连接线(折线)的场景也有类似的问题,大家多多支持,后面抽空研究处理一下(-_-)。。。

More Stars please!勾勾手指~

源码

gitee源码

示例地址

原文链接:https://www.cnblogs.com/xachary/p/18241664

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号