一个简单的应用场景，流程图连线
源码：
addExample("A星路径查找", function () {
return {
template: `<div><div ref="main"></div></div>`,
data() { return {}; },
computed: {},
methods: {},
mounted() {
var container = this.$refs.main;
var render = new CanvasShapeRender(container, {
width: 700,
height: 700,
background: '#efefef'
})
var group = render.addShape({ type: 'group', x: 50, y: 50 })
const start = Vector.create(2, 2)
const end = Vector.create(8, 6)
let dragObj
const tileMap = group.addShape({
type: 'tileMap',
visibleGrid: true,
onCreateTileData(col, row) {
if (row === start.y && col === start.x) {
return {
type: 'rect',
color: '#ff0000',
value: 1,
canMove: true
}
}
else if (row === end.y && col === end.x) {
return {
type: 'rect',
color: '#00ff00',
value: 2,
canMove: true
}
} else {
return {
type: 'rect',
color: '#ddd',
value: 0
}
}
},
onAfterDrawMapCell(ctx, col, row, x, y, data) {
if (!gui.visibleDist || data.value !== 4) {
return
}
ctx.beginPath()
ctx.fillStyle = '#000'
ctx.font = '12px sans-serif'
ctx.textAlign = 'start'
ctx.textBaseline = 'base'
const getDist = distOps[gui.dist]
const startDist = Number(data.startDist.toFixed(2)) // Number(getDist({ col: start.x, row: start.y }, { col, row }).toFixed(2))
const endDist = Number(data.endDist.toFixed(2))// Number(getDist({ col, row }, { col: end.x, row: end.y }).toFixed(2))
const dist = Number(data.dist.toFixed(2))//Number((endDist + startDist).toFixed(2))
ctx.fillText('' + startDist, x, y + 10)
ctx.fillText('' + endDist, x, y + this.cellSize[1] - 5)
ctx.beginPath()
ctx.font = '14px sans-serif'
ctx.textAlign = 'center'
ctx.textBaseline = 'middle'
// CanvasRenderingContext2D.prototype.textBaseline
ctx.fillText('' + dist, x + this.cellSize[0] / 2, y + this.cellSize[1] / 2)
},
cellSize: [50, 50],
mapSize: [10, 10],
mousedown(e) {
const downPoint = e.downPoint
const [x, y] = group.transformLocalCoord(downPoint.x, downPoint.y)
const [col, row] = this.getMapCoordinate(x, y)
const data = this.getCellData(col, row)
if (data && data.canMove) {
dragObj = {
col,
row,
data
}
} else if (data && (data.value == 0 || data.value == 3)) {
dragObj = {
col,
row,
data: {
value: data.value
}
}
}
},
drag(e) {
if (dragObj) {
const point = e.point
const [x, y] = group.transformLocalCoord(point.x, point.y)
let [col, row] = this.getMapCoordinate(x, y)
const data = this.getCellData(col, row)
if (dragObj.data.value === 0 && !data.canMove) {
// 变成障碍
data.value = 3
data.color = '#666'
this.setCellData(col, row, data)
render.requestDraw()
} else if (dragObj.data.value === 3 && !data.canMove) {
// 移除障碍
data.value = 0
data.color = '#ddd'
this.setCellData(col, row, data)
render.requestDraw()
}
else if (dragObj.data.canMove && data && data !== dragObj.data) {
this.setCellData(dragObj.col, dragObj.row, data)
this.setCellData(col, row, dragObj.data)
if (dragObj.data.value === 1) {
start.x = col
start.y = row
}
if (dragObj.data.value === 2) {
end.x = col
end.y = row
}
dragObj.col = col
dragObj.row = row
render.requestDraw()
}
}
},
mouseup() {
dragObj = null
}
})
render.requestDraw()
const map = tileMap.map // 0 空 1 起点 2终点 3障碍
const clear = () => {
tileMap.visitMap(tileMap.map, (r, c, data) => {
if (data.value === 4) {
data.value = 0
data.color = '#ddd'
}
})
render.requestDraw()
}
const renderPaths = (paths, color, renderPath, duration = 1000) => {
if (paths.length <= 0) {
return
}
let start = performance.now()
let len = paths.length - 1
const animate = (time) => {
const d = performance.now() - start
const p = Math.min(d / duration, 1)
const index = Math.floor(p * len);
const data = paths[index]
if (renderPath || !data.isPath) {
tileMap.setCellData(data.col, data.row, {
...data,
type: 'rect',
value: 4,
color: color
})
}
render.requestDraw()
if (p < 1) {
requestAnimationFrame(animate)
}
}
requestAnimationFrame(animate)
}
// 计算两个点的距离
//Manhattan Distance
const getManhattanDist = (a, b) => {
// 曼哈顿距离
return Math.abs(a.col - b.col) + Math.abs(a.row - b.row)
}
// 欧几里得距离( Euclidean distance)也称欧氏距离
const getEuclideanDist = (a, b) => {
const x = a.col - b.col
const y = a.row - b.row
return Math.sqrt(x * x + y * y)
}
//，切比雪夫距离（Chebyshev distance）
const getChebyshevDist = (a, b) => {
const x = a.col - b.col
const y = a.row - b.row
return Math.max(Math.abs(x), Math.abs(y))
}
const distOps = {
getManhattanDist,
getEuclideanDist,
getChebyshevDist
}
// 返回最短路径
const findPath = function* (start, end, _map) {
// 创建图顶点信息
const map = _map.map((rd, row) => {
return rd.map((cd, col) => {
return {
...cd,
row,
col,
value: cd.value,
isPath: false,
visited: false,// 是否访问过
// 无有可走的路
closed: false, // 已经查找过
parent: null,
startDist: 0, // 起点距离当前格子
endDist: 0, // 当前距离终点
dist: 0, // 总距离
weight: 0, // 权重
order: 0,
}
})
})
const rows = map.length, cols = map[0].length
const getNode = (col, row) => {
if (col < 0 || col >= cols || row < 0 || row >= rows) {
return null
}
return map[row][col]
}
// 找相邻的
const getAdjacent = (node) => {
const c = node.col
const r = node.row
const left = getNode(c - 1, r) // left
const top = getNode(c, r - 1) // top
const right = getNode(c + 1, r) // right
const bottom = getNode(c, r + 1) // bottom
return [left, top, right, bottom].filter(Boolean)
}
const getCost=()=>{
return 0.1
}
const findNearestDistance = (node) => {
const adjacent = getAdjacent(node)
let min = Infinity, minNode
// let resultNode;
adj:
for (let i = 0; i < adjacent.length; i++) {
const adj = adjacent[i]
// 如果已关闭或是障碍，不处理
if (adj.closed || adj.value === 3) {
continue;
}
let startDist=node.startDist+getCost(adj,node) //getDist(adj,node)
// 如果还未访问
if (!adj.visited) {
// g(n)表示从初始结点到任意结点n的代价，
// h(n)表示从结点n到目标点的启发式评估代价（heuristic estimated cost）。
// f=g(n)+h(n)
// getDist(startNode, adj)
adj.startDist = startDist
adj.endDist = getDist(adj, endNode)
adj.dist = adj.startDist + adj.endDist //getDist(adj, startNode)
adj.parent = node
adj.visited = true
openList.push(adj)
// 如果是空闲
if (adj.value === 0) {
visitedPaths.push(adj)
}
}else{
if(startDist<node.startDist){
adj.parent = node
adj.startDist = startDist
adj.dist = adj.startDist + adj.endDist //getDist(adj, startNode)
}
}
if (adj.value === 2) {
return adj
}
}
openList.sort((a, b) => a.dist - b.dist)
// openList.sort((a, b) => a.dist === b.dist ? a.dist - b.dist : a.order - b.order)
}
const getDist = distOps[gui.dist]
// 查找邻居四个方位，上下左右
let current = null
let startNode = getNode(start[0], start[1])
let endNode = getNode(end[0], end[1])
let paths = []
let visitedPaths = []
let openList = []
openList.push(startNode)
let resultNode;
path:
while (openList.length) {
yield { visitedPaths, paths };
current = openList.shift()
current.closed = true;
if (current === endNode) {
resultNode = current
break
}
resultNode = findNearestDistance(current)
if (resultNode) {
break
}
}
current = resultNode ? resultNode.parent : null
while (current && current !== startNode) {
current.isPath = true;
paths.unshift(current)
current = current.parent
}
return {
paths: paths,
visitedPaths
}
}
const resultGenerator = (result) => {
let current;
do {
current = result.next();
} while (!current.done)
return current.value
}
const stepGenerator = (generatorFn, callback) => {
let result;
let isStart = false
const next = () => {
if (!isStart) {
isStart = true;
result = generatorFn()
}
let current = result.next();
callback(current.value)
if (current.done) {
isStart = false
}
}
return {
next,
}
}
const distList = Object.keys(distOps)
const step = stepGenerator(function* () {
return yield* findPath([start.x, start.y], [end.x, end.y], map)
}, ({ visitedPaths, paths }) => {
renderPaths(visitedPaths, '#aaa', false)
renderPaths(paths, '#ffff00', true)
})
const gui = addGuiScheme(this.$gui, {
source: {
dist: 'getEuclideanDist',
visibleDist: false,
start: () => {
const { paths, visitedPaths } = resultGenerator(findPath([start.x, start.y], [end.x, end.y], map))
renderPaths(visitedPaths, '#aaa', false)
renderPaths(paths, '#ffff00', true)
},
step: () => {
step.next()
},
clear() {
clear()
}
},
schemes: {
dist: { type: 'list', params: distList }
},
onChange() {
render.requestDraw()
}
})
}
}
})
