RCP：gef智能寻路算法（A star）

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## RCP：gef智能寻路算法（A star）

anrainie 2014-06-12 11:07:00 浏览484

1、Astar单向寻路

2、地图预读

3、弗洛伊德平滑算法

Astar寻路的实现：

```ANode minFNode = null;
while (true) {
minFNode = findMinNode(openList);
openList.remove(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++) {
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])) {
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);
nodes[i].setParent(n.getParent());
}
}
}
}```

```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();
}
}
}```

```    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);
.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;
}```

，效果如图：

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.FOUR_DIR
| AStarConnectionRouter.FLOYD_SIMPLIFY
| AStarConnectionRouter.TEST);

anrainie
+ 关注