本路由继承自AbstactRouter，参数只有EditPart（编辑器内容控制器），gridLength（寻路用单元格大小），style（FLOYD,FLOYD_FLAT,FOUR_DIR）。
字符集编码为GBK，本文只做简单的代码解析，源码戳我
如果源码不全，可以联系本人。
算法实现主要有三：
1、Astar单向寻路
2、地图预读
3、弗洛伊德平滑算法
Astar寻路的实现：
ANode minFNode = null; while (true) { minFNode = findMinNode(openList); openList.remove(minFNode); closedList.add(minFNode); if (minFNode == null || minFNode.equals(endNode)) break; search(minFNode, openList, closedList, startNode, endNode); } private void search(ANode node, List<ANode> openList, List<ANode> closedList, ANode startNode, ANode endNode) { ANode[] nodes = findAroundNode(node); for (int i = 0, len = nodes.length; i < len; i++) { if (nodes[i].getLevel() == ANodeLevel.DEAD) continue; nodes[i].g = (i > 3 ? nodes[i].getLevel().RE : nodes[i].getLevel().BE) + node.g; nodes[i].h = caculateH(nodes[i], endNode); if (closedList.contains(nodes[i])) continue; if (!openList.contains(nodes[i])) { openList.add(nodes[i]); nodes[i].setParent(node); } else if (openList.contains(nodes[i])) { int idx = openList.indexOf(nodes[i]); ANode n = openList.get(idx); if (nodes[i].g < n.g) { openList.remove(idx); closedList.add(n); nodes[i].setParent(n.getParent()); openList.add(idx, nodes[i]); } } } }
在网上大部分版本的Astar算法里，障碍只有两个参考值，即是可通过和不可通过
但在实际情况里，有可能会有较难度过的小溪，难以度过的河流，不能跨越的深涧，于是我在算法里引入了难易度概念，由ANodeLevel体现。
package galaxy.ide.configurable.editor.gef.router; /** * 节点等级，RE直角边，BE斜角边 * * @author caiyu * @date 2014-5-15 */ public enum ANodeLevel { EASY(10, 14), NORMAL(20, 28), HARD(50, 68), DEAD(2000, 2800); /** * 直角边 */ public final int RE; /** * 斜角边 */ public final int BE; ANodeLevel(int RE, int BE) { this.RE = RE; this.BE = BE; } }
引入了四个难易程度，当然，这些难易程度自己可以调整。
障碍的难易程度是预读的，体现在代码：
private void preReadingNodes(Point startPoint) { Rectangle r; for (Object c : this.editPart.getChildren()) { if (c instanceof GraphicalEditPart) { r = ((GraphicalEditPart) c).getFigure().getBounds(); preReader.read(r, startPoint, D); } } }
预读器preReader源码如下：
public void read(Rectangle r, Point startPoint, final int D) { ANodeLevel level = ANodeLevel.HARD; if (r.contains(this.startPoint) || r.contains(this.endPoint)) level = ANodeLevel.NORMAL; int xS = ANodePreReader.calculateIndex(r.x, startPoint.x, D); int xE = ANodePreReader .calculateIndex(r.x + r.width(), startPoint.x, D); int yS = ANodePreReader.calculateIndex(r.y, startPoint.y, D); int yE = ANodePreReader.calculateIndex(r.y + r.height(), startPoint.y, D); Map<Integer, ANodeLevel> map; for (int x = xS; x < xE; x++) { for (int y = yS; y < yE; y++) { map = pool.get(x); if (map == null) { map = new HashMap<Integer, ANodeLevel>(); pool.put(x, map); } map.put(y, level); } } } public ANode getNode(int x, int y) { ANode node = new ANode(x, y); Map<Integer, ANodeLevel> map = pool.get(x); node.setLevel(map == null ? ANodeLevel.EASY : map.get(y) == null ? ANodeLevel.EASY : map.get(y)); return node; } public static int calculateIndex(int v1, int v2, int distance) { int offset = (v1 - v2) % distance; return offset > 0 ? (v1 - v2) / distance + 1 : offset == 0 ? (v1 - v2) / distance : (v1 - v2) / distance - 1; }
完成了以上，即可以实现智能绘图，应用该路由 new AStarConnectionRouter2(editPart, 20, AStarConnectionRouter.NONE);（不会在GEF中应用路由器的去看《GEF whole update》这本书）
如图所示：
可以看出，这个算法还有缺陷，并不平滑。我们加入弗洛伊德平滑算法new AStarConnectionRouter2(editPart, 20, AStarConnectionRouter.FLOYD);
，效果如图：
弗洛伊德平滑算法的原理：
1、如果A、B、C三点在同一直线上，视为三点共线，则去除B点
2、清理所有共线点之后，遍历任一点和其他点之间有无障碍物，如果没有，则去除两点之间的全部点。
算法实现：
/** * 弗洛伊德平滑处理 * * @param D * @param startPoint * * @param points */ public void floyd(ANode node, Point startPoint, int D) { if ((this.style & FLOYD_SIMPLIFY) != FLOYD_SIMPLIFY && (this.style & FLOYD) != FLOYD) return; ANode fatherNode, currentNode = node, grandNode; // 去除共线 while (true) { fatherNode = currentNode.getParent(); if (fatherNode == null) break; grandNode = fatherNode.getParent(); if (grandNode == null) break; if (fatherNode.xIndex - currentNode.xIndex == grandNode.xIndex - fatherNode.xIndex && fatherNode.yIndex - currentNode.yIndex == grandNode.yIndex - fatherNode.yIndex) { currentNode.setParent(grandNode); } else currentNode = fatherNode; } currentNode = node; if ((this.style & FLOYD) != FLOYD) return; // 去除拐点 while (true) { fatherNode = currentNode.getParent(); if (fatherNode == null) break; while (true) { grandNode = fatherNode.getParent(); if (grandNode == null) break; if (linkable(currentNode, grandNode, startPoint, D)) { currentNode.setParent(grandNode); } fatherNode = grandNode; } currentNode = currentNode.getParent(); if (currentNode == null) break; } }
但是，上图的效果并不美观，有两个参考方案：
1、自己重写ConnectionFigure，使拐点圆滑
2、Astar算法只参考上下左右四个方向
只参考四个方向的使用例子new AStarConnectionRouter2(editPart, 20, AStarConnectionRouter.FLOYD| AStarConnectionRouter.FOUR_DIR);
如图所示：
以上，即实现了全部效果。
注意，在RouterStyle里有个TEST选项，该选项是测试使用，使用过程中会有大量bug。
new AStarConnectionRouter2(editPart, 20,
AStarConnectionRouter.FOUR_DIR
| AStarConnectionRouter.FLOYD_SIMPLIFY
| AStarConnectionRouter.TEST);
该测试用于展示在寻路过程中AStar算法遍历到的节点，如图所示：
下一次再实现一个圆滑的弧线拐角，再来和大家分享。
源码下载请移步：http://pan.baidu.com/s/1hqgNN2s
