| | |
|---|
| | | |
|---|
| | | // Open表用优先队列 |
|---|
| | | public PriorityQueue<NavigateNode> Open = new PriorityQueue<NavigateNode>(); |
|---|
| | | //Close表用普通的数组 |
|---|
| | | public ArrayList<NavigateNode> Close = new ArrayList<NavigateNode>(); |
|---|
| | | //Close表用坐标key集合，O(1)查找 |
|---|
| | | public Set<String> Close = new HashSet<>(); |
|---|
| | | //用来存放已经出现过的结点。 |
|---|
| | | Map<String, Integer> bestGMap = new HashMap<>(); |
|---|
| | | |
|---|
| | |
|---|
| | | } |
|---|
| | | |
|---|
| | | //将这个结点加入到Close表中 |
|---|
| | | Close.add(current_node); |
|---|
| | | Close.add(keyOf(current_node)); |
|---|
| | | //对当前结点进行扩展，得到一个四周结点的数组 |
|---|
| | | ArrayList<NavigateNode> neighbour_node = extend_current_node(map, current_node); |
|---|
| | | //对这个结点遍历，看是否有目标结点出现 |
|---|
| | | for (NavigateNode node : neighbour_node) { |
|---|
| | | // 已在关闭列表中的节点不再处理，避免父链反复改写形成环 |
|---|
| | | if (Close.contains(node)) { |
|---|
| | | if (Close.contains(keyOf(node))) { |
|---|
| | | continue; |
|---|
| | | } |
|---|
| | | // G + H + E (对启发函数增加去拐点方案calcNodeExtraCost) |
|---|
| | |
|---|
| | | node.setH(calcNodeCost(node, end)); |
|---|
| | | node.setF(node.getG() + node.getH()); |
|---|
| | | |
|---|
| | | String key = node.getX() + "_" + node.getY(); |
|---|
| | | String key = keyOf(node); |
|---|
| | | Integer recordedG = bestGMap.get(key); |
|---|
| | | // 仅当找到更小的代价时才更新与入Open，避免等价代价反复入队导致父链抖动 |
|---|
| | | if (recordedG == null || node.getG() < recordedG) { |
|---|
