From 3372040097ad2c01aeb6fd6485e89f19bf81b316 Mon Sep 17 00:00:00 2001
From: Junjie <fallin.jie@qq.com>
Date: 星期三, 18 三月 2026 17:02:34 +0800
Subject: [PATCH] #
---
src/main/java/com/zy/common/utils/NavigateSolution.java | 181 ++++++++++++++++++++++++++++++++++++++++++--
1 files changed, 171 insertions(+), 10 deletions(-)
diff --git a/src/main/java/com/zy/common/utils/NavigateSolution.java b/src/main/java/com/zy/common/utils/NavigateSolution.java
index ef7d708..6dd6c57 100644
--- a/src/main/java/com/zy/common/utils/NavigateSolution.java
+++ b/src/main/java/com/zy/common/utils/NavigateSolution.java
@@ -2,7 +2,7 @@
import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;
-import com.baomidou.mybatisplus.mapper.EntityWrapper;
+import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper;
import com.core.common.SpringUtils;
import com.core.exception.CoolException;
import com.zy.asrs.entity.BasMap;
@@ -26,7 +26,7 @@
public List<List<NavigateNode>> getStationMap(int lev) {
BasMapService basMapService = SpringUtils.getBean(BasMapService.class);
- BasMap basMap = basMapService.selectOne(new EntityWrapper<BasMap>().eq("lev", lev));
+ BasMap basMap = basMapService.getOne(new QueryWrapper<BasMap>().eq("lev", lev));
if (basMap == null) {
throw new CoolException("鍦板浘涓嶅瓨鍦�");
}
@@ -83,7 +83,7 @@
public List<List<NavigateNode>> getRgvTrackMap(int lev) {
BasMapService basMapService = SpringUtils.getBean(BasMapService.class);
- BasMap basMap = basMapService.selectOne(new EntityWrapper<BasMap>().eq("lev", lev));
+ BasMap basMap = basMapService.getOne(new QueryWrapper<BasMap>().eq("lev", lev));
if (basMap == null) {
throw new CoolException("鍦板浘涓嶅瓨鍦�");
}
@@ -183,6 +183,18 @@
int maxPaths, // 鏈�澶ц繑鍥炴潯鏁�. 寤鸿锛�100/500/2000锛�<=0 琛ㄧず涓嶉檺鍒讹紙涓嶅缓璁級
int maxCost // 鏈�澶ф�讳唬浠�(鍚嫄鐐规儵缃�). <=0 琛ㄧず涓嶉檺鍒�
) {
+ return allSimplePaths(map, start, end, maxDepth, maxPaths, maxCost, Collections.emptyList());
+ }
+
+ public List<List<NavigateNode>> allSimplePaths(
+ List<List<NavigateNode>> map,
+ NavigateNode start,
+ NavigateNode end,
+ int maxDepth,
+ int maxPaths,
+ int maxCost,
+ List<Integer> guideStationIds
+ ) {
List<List<NavigateNode>> results = new ArrayList<>();
if (map == null || map.isEmpty() || map.get(0).isEmpty()) return results;
if (start == null || end == null) return results;
@@ -197,13 +209,16 @@
path.add(start);
AtomicInteger pathCount = new AtomicInteger(0);
+ Map<Integer, NavigateNode> guideNodeMap = buildGuideNodeMap(map, guideStationIds);
dfsAllSimplePaths(map, start, end,
visited, path, results,
0, // depth
0, // cost
maxDepth, maxPaths, maxCost,
- pathCount
+ pathCount,
+ guideStationIds,
+ guideNodeMap
);
return results;
@@ -224,7 +239,9 @@
int maxDepth,
int maxPaths,
int maxCost,
- AtomicInteger pathCount
+ AtomicInteger pathCount,
+ List<Integer> guideStationIds,
+ Map<Integer, NavigateNode> guideNodeMap
) {
// 闃茬垎锛氭潯鏁伴檺鍒�
if (maxPaths > 0 && pathCount.get() >= maxPaths) return;
@@ -242,6 +259,7 @@
// 鎵╁睍閭诲眳锛堜弗鏍煎鐢ㄤ綘鑷繁鐨勫彲琛岃蛋鏂瑰悜瑙勫垯锛�
ArrayList<NavigateNode> neighbors = extend_current_node(map, current);
if (neighbors == null || neighbors.isEmpty()) return;
+ neighbors = sortNeighborsByGuide(current, path, neighbors, guideStationIds, guideNodeMap);
for (NavigateNode next : neighbors) {
// 闃茬垎锛氭潯鏁伴檺鍒�
@@ -271,7 +289,9 @@
depth + 1,
newCost,
maxDepth, maxPaths, maxCost,
- pathCount
+ pathCount,
+ guideStationIds,
+ guideNodeMap
);
// 鍥炴函
@@ -282,6 +302,112 @@
private String keyOf(NavigateNode n) {
return n.getX() + "_" + n.getY();
+ }
+
+ private Map<Integer, NavigateNode> buildGuideNodeMap(List<List<NavigateNode>> map, List<Integer> guideStationIds) {
+ Map<Integer, NavigateNode> guideNodeMap = new HashMap<>();
+ if (map == null || map.isEmpty() || guideStationIds == null || guideStationIds.isEmpty()) {
+ return guideNodeMap;
+ }
+ for (Integer stationId : guideStationIds) {
+ if (stationId == null || guideNodeMap.containsKey(stationId)) {
+ continue;
+ }
+ NavigateNode stationNode = findStationNavigateNode(map, stationId);
+ if (stationNode != null) {
+ guideNodeMap.put(stationId, stationNode);
+ }
+ }
+ return guideNodeMap;
+ }
+
+ private ArrayList<NavigateNode> sortNeighborsByGuide(NavigateNode current,
+ LinkedList<NavigateNode> path,
+ ArrayList<NavigateNode> neighbors,
+ List<Integer> guideStationIds,
+ Map<Integer, NavigateNode> guideNodeMap) {
+ if (current == null || neighbors == null || neighbors.size() <= 1
+ || guideStationIds == null || guideStationIds.isEmpty()
+ || guideNodeMap == null || guideNodeMap.isEmpty()) {
+ return neighbors;
+ }
+
+ Integer nextGuideStationId = resolveNextGuideStationId(path, guideStationIds);
+ if (nextGuideStationId == null) {
+ return neighbors;
+ }
+ NavigateNode guideTargetNode = guideNodeMap.get(nextGuideStationId);
+ if (guideTargetNode == null) {
+ return neighbors;
+ }
+
+ neighbors.sort((left, right) -> compareGuideNeighbor(current, left, right, nextGuideStationId, guideTargetNode));
+ return neighbors;
+ }
+
+ private Integer resolveNextGuideStationId(LinkedList<NavigateNode> path, List<Integer> guideStationIds) {
+ if (path == null || path.isEmpty() || guideStationIds == null || guideStationIds.isEmpty()) {
+ return null;
+ }
+
+ int cursor = 0;
+ Set<Integer> seen = new HashSet<>();
+ for (NavigateNode node : path) {
+ Integer stationId = extractStationId(node);
+ if (stationId == null || !seen.add(stationId)) {
+ continue;
+ }
+ if (cursor < guideStationIds.size() && stationId.equals(guideStationIds.get(cursor))) {
+ cursor++;
+ }
+ }
+ if (cursor >= guideStationIds.size()) {
+ return null;
+ }
+ return guideStationIds.get(cursor);
+ }
+
+ private int compareGuideNeighbor(NavigateNode current,
+ NavigateNode left,
+ NavigateNode right,
+ Integer nextGuideStationId,
+ NavigateNode guideTargetNode) {
+ int leftDirect = isGuideStation(left, nextGuideStationId) ? 0 : 1;
+ int rightDirect = isGuideStation(right, nextGuideStationId) ? 0 : 1;
+ if (leftDirect != rightDirect) {
+ return Integer.compare(leftDirect, rightDirect);
+ }
+
+ int leftDistance = calcNodeCost(left, guideTargetNode);
+ int rightDistance = calcNodeCost(right, guideTargetNode);
+ if (leftDistance != rightDistance) {
+ return Integer.compare(leftDistance, rightDistance);
+ }
+
+ int leftTurnCost = calcNodeExtraCost(current, left, guideTargetNode);
+ int rightTurnCost = calcNodeExtraCost(current, right, guideTargetNode);
+ if (leftTurnCost != rightTurnCost) {
+ return Integer.compare(leftTurnCost, rightTurnCost);
+ }
+
+ return 0;
+ }
+
+ private boolean isGuideStation(NavigateNode node, Integer stationId) {
+ Integer nodeStationId = extractStationId(node);
+ return nodeStationId != null && nodeStationId.equals(stationId);
+ }
+
+ private Integer extractStationId(NavigateNode node) {
+ if (node == null || !"devp".equals(node.getNodeType())) {
+ return null;
+ }
+ try {
+ JSONObject valueObj = JSON.parseObject(node.getNodeValue());
+ return valueObj == null ? null : valueObj.getInteger("stationId");
+ } catch (Exception ignore) {
+ return null;
+ }
}
public ArrayList<NavigateNode> extend_current_node(List<List<NavigateNode>> map, NavigateNode current_node) {
@@ -302,22 +428,22 @@
for(String direction : directionList) {
if(direction.equals("top")) {
- NavigateNode node = getValidNavigateNode(map, x - 1, y);
+ NavigateNode node = getValidNavigateNode(map, current_node, x - 1, y, direction);
if(node != null) {
neighbour_node.add(node);
}
}else if(direction.equals("bottom")) {
- NavigateNode node = getValidNavigateNode(map, x + 1, y);
+ NavigateNode node = getValidNavigateNode(map, current_node, x + 1, y, direction);
if(node != null) {
neighbour_node.add(node);
}
}else if(direction.equals("left")) {
- NavigateNode node = getValidNavigateNode(map, x, y - 1);
+ NavigateNode node = getValidNavigateNode(map, current_node, x, y - 1, direction);
if(node != null) {
neighbour_node.add(node);
}
}else if(direction.equals("right")) {
- NavigateNode node = getValidNavigateNode(map, x, y + 1);
+ NavigateNode node = getValidNavigateNode(map, current_node, x, y + 1, direction);
if(node != null) {
neighbour_node.add(node);
}
@@ -325,6 +451,22 @@
}
return neighbour_node;
+ }
+
+ /**
+ * 閭绘帴鐐规牎楠岋細鍙揪 + 鏂瑰悜涓�鑷达紙褰撳墠鑺傜偣涓庝笅涓�鑺傜偣瀵规湰娆¤璧版柟鍚戜竴鑷达級
+ */
+ public NavigateNode getValidNavigateNode(List<List<NavigateNode>> map, NavigateNode currentNode, int x, int y, String moveDirection) {
+ NavigateNode node = getValidNavigateNode(map, x, y);
+ if (node == null) {
+ return null;
+ }
+
+ if (!isDirectionConsistent(currentNode, node, moveDirection)) {
+ return null;
+ }
+
+ return node;
}
public NavigateNode getValidNavigateNode(List<List<NavigateNode>> map, int x, int y) {
@@ -341,6 +483,25 @@
return node;
}
+ private boolean isDirectionConsistent(NavigateNode currentNode, NavigateNode nextNode, String moveDirection) {
+ if (currentNode == null || nextNode == null) {
+ return false;
+ }
+
+ if (moveDirection == null) {
+ return false;
+ }
+
+ List<String> currentDirectionList = currentNode.getDirectionList();
+ List<String> nextDirectionList = nextNode.getDirectionList();
+ if (currentDirectionList == null || nextDirectionList == null) {
+ return false;
+ }
+
+ // 褰撳墠鑺傜偣鍏佽鍚� moveDirection 鍑哄彂锛屼笖涓嬩竴鑺傜偣鍦ㄨ鏂瑰悜涓婁繚鎸佷竴鑷达紝鎵嶅厑璁搁�氳
+ return currentDirectionList.contains(moveDirection) && nextDirectionList.contains(moveDirection);
+ }
+
public NavigateNode findStationNavigateNode(List<List<NavigateNode>> map, int stationId) {
for(int x = 0; x < map.size(); x++) {
for(int y = 0; y < map.get(0).size(); y++) {
--
Gitblit v1.9.1