From 852664df1caf38831793b341edcada9dd7b6c22a Mon Sep 17 00:00:00 2001
From: Junjie <fallin.jie@qq.com>
Date: 星期三, 06 五月 2026 19:28:33 +0800
Subject: [PATCH] #dfs
---
src/main/java/com/zy/common/utils/NavigateSolution.java | 701 ++++++++++++++++++++++++++++++++++++++++++++++++++++-----
1 files changed, 632 insertions(+), 69 deletions(-)
diff --git a/src/main/java/com/zy/common/utils/NavigateSolution.java b/src/main/java/com/zy/common/utils/NavigateSolution.java
index adf527f..fe2324e 100644
--- a/src/main/java/com/zy/common/utils/NavigateSolution.java
+++ b/src/main/java/com/zy/common/utils/NavigateSolution.java
@@ -1,15 +1,19 @@
package com.zy.common.utils;
import com.alibaba.fastjson.JSON;
+import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
+import com.alibaba.fastjson.TypeReference;
import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper;
import com.core.common.SpringUtils;
import com.core.exception.CoolException;
import com.zy.asrs.entity.BasMap;
import com.zy.asrs.service.BasMapService;
import com.zy.common.model.NavigateNode;
+import com.zy.core.enums.RedisKeyType;
import com.zy.core.enums.MapNodeType;
import java.util.*;
+import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
/**
@@ -17,14 +21,146 @@
*/
public class NavigateSolution {
+ private static final long REDIS_MAP_CACHE_TTL_SECONDS = 60 * 60 * 24L;
+ private static final long MAP_CACHE_TTL_MS = 5000L;
+ private static final long SIMPLE_PATH_SEARCH_TIMEOUT_MS = 10_000L;
+ private static final Map<String, CachedNavigateMap> NAVIGATE_MAP_CACHE = new ConcurrentHashMap<>();
+ private static final Map<String, CachedNavigateMapIndex> NAVIGATE_MAP_INDEX_CACHE = new ConcurrentHashMap<>();
+
// Open琛ㄧ敤浼樺厛闃熷垪
public PriorityQueue<NavigateNode> Open = new PriorityQueue<NavigateNode>();
- //Close琛ㄧ敤鏅�氱殑鏁扮粍
- public ArrayList<NavigateNode> Close = new ArrayList<NavigateNode>();
+ //Close琛ㄧ敤鍧愭爣key闆嗗悎锛孫(1)鏌ユ壘
+ public Set<String> Close = new HashSet<>();
//鐢ㄦ潵瀛樻斁宸茬粡鍑虹幇杩囩殑缁撶偣銆�
Map<String, Integer> bestGMap = new HashMap<>();
public List<List<NavigateNode>> getStationMap(int lev) {
+ return cloneNavigateMap(loadCachedNavigateMap("station", lev));
+ }
+
+ public NavigateMapIndex getStationMapIndex(int lev) {
+ return loadCachedNavigateMapIndex("station", lev);
+ }
+
+ public List<List<NavigateNode>> getRgvTrackMap(int lev) {
+ return cloneNavigateMap(loadCachedNavigateMap("rgv", lev));
+ }
+
+ private List<List<NavigateNode>> loadCachedNavigateMap(String mapType, int lev) {
+ String cacheKey = mapType + ":" + lev;
+ long now = System.currentTimeMillis();
+ CachedNavigateMap cachedNavigateMap = NAVIGATE_MAP_CACHE.get(cacheKey);
+ if (cachedNavigateMap != null && now - cachedNavigateMap.cacheAtMs <= MAP_CACHE_TTL_MS) {
+ return cachedNavigateMap.navigateMap;
+ }
+
+ List<List<NavigateNode>> redisNavigateMap = loadNavigateMapFromRedis(mapType, lev);
+ if (isValidNavigateMap(redisNavigateMap)) {
+ enrichNavigateMapMetadata(redisNavigateMap);
+ NAVIGATE_MAP_CACHE.put(cacheKey, new CachedNavigateMap(now, redisNavigateMap));
+ return redisNavigateMap;
+ }
+ clearMapCache(lev);
+
+ List<List<NavigateNode>> navigateNodeList = buildNavigateMap(mapType, lev);
+ enrichNavigateMapMetadata(navigateNodeList);
+ cacheNavigateMap(cacheKey, mapType, lev, navigateNodeList, now);
+ return navigateNodeList;
+ }
+
+ private NavigateMapIndex loadCachedNavigateMapIndex(String mapType, int lev) {
+ String cacheKey = mapType + ":" + lev;
+ long now = System.currentTimeMillis();
+ CachedNavigateMapIndex cachedNavigateMapIndex = NAVIGATE_MAP_INDEX_CACHE.get(cacheKey);
+ if (cachedNavigateMapIndex != null && now - cachedNavigateMapIndex.cacheAtMs <= MAP_CACHE_TTL_MS) {
+ return cachedNavigateMapIndex.navigateMapIndex;
+ }
+
+ List<List<NavigateNode>> navigateMap = loadCachedNavigateMap(mapType, lev);
+ NavigateMapIndex navigateMapIndex = buildNavigateMapIndex(lev, navigateMap);
+ NAVIGATE_MAP_INDEX_CACHE.put(cacheKey, new CachedNavigateMapIndex(now, navigateMapIndex));
+ return navigateMapIndex;
+ }
+
+ public static void refreshAllMapCaches() {
+ BasMapService basMapService = SpringUtils.getBean(BasMapService.class);
+ List<Integer> levList = basMapService.getLevList();
+ if (levList == null || levList.isEmpty()) {
+ NAVIGATE_MAP_CACHE.clear();
+ return;
+ }
+ LinkedHashSet<Integer> distinctLevSet = new LinkedHashSet<>(levList);
+ for (Integer lev : distinctLevSet) {
+ if (lev == null) {
+ continue;
+ }
+ refreshMapCache(lev);
+ }
+ }
+
+ public static void refreshMapCache(Integer lev) {
+ if (lev == null) {
+ return;
+ }
+ long now = System.currentTimeMillis();
+ NavigateSolution navigateSolution = new NavigateSolution();
+ List<List<NavigateNode>> stationMap = navigateSolution.buildNavigateMap("station", lev);
+ navigateSolution.enrichNavigateMapMetadata(stationMap);
+ navigateSolution.cacheNavigateMap("station:" + lev, "station", lev, stationMap, now);
+ navigateSolution.cacheNavigateMapIndex("station:" + lev, lev, stationMap, now);
+ List<List<NavigateNode>> rgvMap = navigateSolution.buildNavigateMap("rgv", lev);
+ navigateSolution.enrichNavigateMapMetadata(rgvMap);
+ navigateSolution.cacheNavigateMap("rgv:" + lev, "rgv", lev, rgvMap, now);
+ }
+
+ public static void clearMapCache(Integer lev) {
+ if (lev == null) {
+ return;
+ }
+ NAVIGATE_MAP_CACHE.remove("station:" + lev);
+ NAVIGATE_MAP_CACHE.remove("rgv:" + lev);
+ NAVIGATE_MAP_INDEX_CACHE.remove("station:" + lev);
+ RedisUtil redisUtil = SpringUtils.getBean(RedisUtil.class);
+ redisUtil.del(buildRedisCacheKey("station", lev), buildRedisCacheKey("rgv", lev));
+ }
+
+ private void cacheNavigateMap(String localCacheKey,
+ String mapType,
+ int lev,
+ List<List<NavigateNode>> navigateNodeList,
+ long cacheAtMs) {
+ RedisUtil redisUtil = SpringUtils.getBean(RedisUtil.class);
+ redisUtil.set(buildRedisCacheKey(mapType, lev),
+ JSON.toJSONString(navigateNodeList),
+ REDIS_MAP_CACHE_TTL_SECONDS);
+ NAVIGATE_MAP_CACHE.put(localCacheKey, new CachedNavigateMap(cacheAtMs, navigateNodeList));
+ }
+
+ private void cacheNavigateMapIndex(String localCacheKey,
+ int lev,
+ List<List<NavigateNode>> navigateNodeList,
+ long cacheAtMs) {
+ NAVIGATE_MAP_INDEX_CACHE.put(localCacheKey, new CachedNavigateMapIndex(cacheAtMs, buildNavigateMapIndex(lev, navigateNodeList)));
+ }
+
+ private List<List<NavigateNode>> loadNavigateMapFromRedis(String mapType, int lev) {
+ RedisUtil redisUtil = SpringUtils.getBean(RedisUtil.class);
+ Object cachedValue = redisUtil.get(buildRedisCacheKey(mapType, lev));
+ if (!(cachedValue instanceof String) || ((String) cachedValue).trim().isEmpty()) {
+ return null;
+ }
+ try {
+ return JSON.parseObject((String) cachedValue, new TypeReference<List<List<NavigateNode>>>() {});
+ } catch (Exception ignore) {
+ return null;
+ }
+ }
+
+ private static String buildRedisCacheKey(String mapType, int lev) {
+ return RedisKeyType.NAVIGATE_MAP_TEMPLATE_.key + mapType + "_" + lev;
+ }
+
+ private List<List<NavigateNode>> buildNavigateMap(String mapType, int lev) {
BasMapService basMapService = SpringUtils.getBean(BasMapService.class);
BasMap basMap = basMapService.getOne(new QueryWrapper<BasMap>().eq("lev", lev));
if (basMap == null) {
@@ -32,7 +168,6 @@
}
List<List<JSONObject>> dataList = JSON.parseObject(basMap.getData(), List.class);
-
List<List<NavigateNode>> navigateNodeList = new ArrayList<>();
for (int i = 0; i < dataList.size(); i++) {
List<JSONObject> row = dataList.get(i);
@@ -41,26 +176,33 @@
JSONObject map = row.get(j);
NavigateNode navigateNode = new NavigateNode(i, j);
- String mergeType = map.getString("mergeType");
String nodeType = map.getString("type");
+ String mergeType = map.getString("mergeType");
String nodeValue = map.getString("value");
if(nodeType == null) {
navigateNode.setValue(MapNodeType.DISABLE.id);
- }else if(nodeType.equals("devp") || (nodeType.equals("merge") && mergeType.equals("devp"))) {
+ } else if ("station".equals(mapType)
+ && (nodeType.equals("devp") || (nodeType.equals("merge") && "devp".equals(mergeType)))) {
navigateNode.setValue(MapNodeType.NORMAL_PATH.id);
-
- JSONObject valueObj = JSON.parseObject(map.getString("value"));
- List<String> directionList = valueObj.getJSONArray("direction").toJavaList(String.class);
+ JSONObject valueObj = JSON.parseObject(nodeValue);
+ List<String> directionList = valueObj == null || valueObj.getJSONArray("direction") == null
+ ? new ArrayList<>()
+ : valueObj.getJSONArray("direction").toJavaList(String.class);
navigateNode.setDirectionList(directionList);
- } else if (nodeType.equals("rgv")) {
+ } else if ("station".equals(mapType) && nodeType.equals("rgv")) {
navigateNode.setValue(MapNodeType.NORMAL_PATH.id);
- JSONObject valueObj = JSON.parseObject(map.getString("value"));
-
JSONObject newNodeValue = new JSONObject();
newNodeValue.put("rgvCalcFlag", 1);
nodeValue = JSON.toJSONString(newNodeValue);
- //RGV鏆備笉鎺у埗琛岃蛋鏂瑰悜锛岄粯璁や笂涓嬪乏鍙抽兘鍙蛋
+ List<String> directionList = new ArrayList<>();
+ directionList.add("top");
+ directionList.add("bottom");
+ directionList.add("left");
+ directionList.add("right");
+ navigateNode.setDirectionList(directionList);
+ } else if ("rgv".equals(mapType) && nodeType.equals("rgv")) {
+ navigateNode.setValue(MapNodeType.NORMAL_PATH.id);
List<String> directionList = new ArrayList<>();
directionList.add("top");
directionList.add("bottom");
@@ -73,57 +215,165 @@
navigateNode.setNodeType(nodeType);
navigateNode.setNodeValue(nodeValue);
+ applyNodeMetadata(navigateNode);
navigateNodeRow.add(navigateNode);
}
navigateNodeList.add(navigateNodeRow);
}
-
- return navigateNodeList;
+ return cropNavigateMap(navigateNodeList);
}
- public List<List<NavigateNode>> getRgvTrackMap(int lev) {
- BasMapService basMapService = SpringUtils.getBean(BasMapService.class);
- BasMap basMap = basMapService.getOne(new QueryWrapper<BasMap>().eq("lev", lev));
- if (basMap == null) {
- throw new CoolException("鍦板浘涓嶅瓨鍦�");
- }
-
- List<List<JSONObject>> dataList = JSON.parseObject(basMap.getData(), List.class);
-
- List<List<NavigateNode>> navigateNodeList = new ArrayList<>();
- for (int i = 0; i < dataList.size(); i++) {
- List<JSONObject> row = dataList.get(i);
- List<NavigateNode> navigateNodeRow = new ArrayList<>();
- for (int j = 0; j < row.size(); j++) {
- JSONObject map = row.get(j);
- NavigateNode navigateNode = new NavigateNode(i, j);
-
- String nodeType = map.getString("type");
- if(nodeType == null) {
- navigateNode.setValue(MapNodeType.DISABLE.id);
- }else if(nodeType.equals("rgv")){
- navigateNode.setValue(MapNodeType.NORMAL_PATH.id);
- JSONObject valueObj = JSON.parseObject(map.getString("value"));
-
- //RGV鏆備笉鎺у埗琛岃蛋鏂瑰悜锛岄粯璁や笂涓嬪乏鍙抽兘鍙蛋
- List<String> directionList = new ArrayList<>();
- directionList.add("top");
- directionList.add("bottom");
- directionList.add("left");
- directionList.add("right");
- navigateNode.setDirectionList(directionList);
- }else {
- navigateNode.setValue(MapNodeType.DISABLE.id);
- }
-
- navigateNode.setNodeType(nodeType);
- navigateNode.setNodeValue(map.getString("value"));
- navigateNodeRow.add(navigateNode);
+ private List<List<NavigateNode>> cloneNavigateMap(List<List<NavigateNode>> sourceMap) {
+ List<List<NavigateNode>> cloneMap = new ArrayList<>();
+ for (List<NavigateNode> row : sourceMap) {
+ List<NavigateNode> cloneRow = new ArrayList<>();
+ for (NavigateNode node : row) {
+ cloneRow.add(node == null ? null : node.clone());
}
- navigateNodeList.add(navigateNodeRow);
+ cloneMap.add(cloneRow);
+ }
+ return cloneMap;
+ }
+
+ private void enrichNavigateMapMetadata(List<List<NavigateNode>> navigateMap) {
+ if (navigateMap == null || navigateMap.isEmpty()) {
+ return;
+ }
+ for (List<NavigateNode> row : navigateMap) {
+ for (NavigateNode node : row) {
+ applyNodeMetadata(node);
+ }
+ }
+ }
+
+ private void applyNodeMetadata(NavigateNode node) {
+ if (node == null) {
+ return;
+ }
+ if (node.getNodeValue() == null || node.getNodeValue().trim().isEmpty()) {
+ if (node.getBridgeStationIds() == null) {
+ node.setBridgeStationIds(Collections.emptyList());
+ }
+ if (node.getLiftTransfer() == null) {
+ node.setLiftTransfer(Boolean.FALSE);
+ }
+ if (node.getRgvCalcFlag() == null) {
+ node.setRgvCalcFlag(Boolean.FALSE);
+ }
+ return;
+ }
+ JSONObject valueObj = parseNodeValue(node.getNodeValue());
+ if (valueObj == null) {
+ if (node.getBridgeStationIds() == null) {
+ node.setBridgeStationIds(Collections.emptyList());
+ }
+ if (node.getLiftTransfer() == null) {
+ node.setLiftTransfer(Boolean.FALSE);
+ }
+ if (node.getRgvCalcFlag() == null) {
+ node.setRgvCalcFlag(Boolean.FALSE);
+ }
+ return;
+ }
+ node.setStationId(valueObj.getInteger("stationId"));
+ JSONArray bridgeStationArray = valueObj.getJSONArray("bridgeStationIds");
+ if (bridgeStationArray == null || bridgeStationArray.isEmpty()) {
+ node.setBridgeStationIds(Collections.emptyList());
+ } else {
+ node.setBridgeStationIds(Collections.unmodifiableList(new ArrayList<>(bridgeStationArray.toJavaList(Integer.class))));
+ }
+ Object isLiftTransfer = valueObj.get("isLiftTransfer");
+ if (isLiftTransfer == null) {
+ node.setLiftTransfer(Boolean.FALSE);
+ } else {
+ String isLiftTransferText = String.valueOf(isLiftTransfer);
+ node.setLiftTransfer("1".equals(isLiftTransferText) || "true".equalsIgnoreCase(isLiftTransferText));
+ }
+ node.setRgvCalcFlag(valueObj.containsKey("rgvCalcFlag"));
+ }
+
+ private boolean isValidNavigateMap(List<List<NavigateNode>> navigateMap) {
+ if (navigateMap == null || navigateMap.isEmpty() || navigateMap.get(0) == null || navigateMap.get(0).isEmpty()) {
+ return false;
}
- return navigateNodeList;
+ int activeNodeCount = 0;
+ for (List<NavigateNode> row : navigateMap) {
+ if (row == null || row.isEmpty()) {
+ return false;
+ }
+ for (NavigateNode node : row) {
+ if (node == null) {
+ return false;
+ }
+ if (node.getValue() == MapNodeType.DISABLE.id) {
+ continue;
+ }
+ activeNodeCount++;
+ if (node.getNodeType() == null) {
+ return false;
+ }
+ if (node.getDirectionList() == null || node.getDirectionList().isEmpty()) {
+ return false;
+ }
+ }
+ }
+ return activeNodeCount > 0;
+ }
+
+ /**
+ * 鍙繚鐣欏弬涓庤矾寰勮绠楃殑浜岀淮鍖哄煙锛屽幓鎺変笂涓嬪乏鍙虫暣鐗囨棤鏁堢┖鐧藉尯銆�
+ */
+ private List<List<NavigateNode>> cropNavigateMap(List<List<NavigateNode>> navigateMap) {
+ if (navigateMap == null || navigateMap.isEmpty() || navigateMap.get(0) == null || navigateMap.get(0).isEmpty()) {
+ return navigateMap;
+ }
+
+ int minX = Integer.MAX_VALUE;
+ int maxX = Integer.MIN_VALUE;
+ int minY = Integer.MAX_VALUE;
+ int maxY = Integer.MIN_VALUE;
+ boolean hasActiveNode = false;
+ for (int x = 0; x < navigateMap.size(); x++) {
+ List<NavigateNode> row = navigateMap.get(x);
+ if (row == null) {
+ continue;
+ }
+ for (int y = 0; y < row.size(); y++) {
+ NavigateNode node = row.get(y);
+ if (node == null || node.getValue() == MapNodeType.DISABLE.id) {
+ continue;
+ }
+ hasActiveNode = true;
+ minX = Math.min(minX, x);
+ maxX = Math.max(maxX, x);
+ minY = Math.min(minY, y);
+ maxY = Math.max(maxY, y);
+ }
+ }
+
+ if (!hasActiveNode) {
+ return navigateMap;
+ }
+
+ List<List<NavigateNode>> croppedMap = new ArrayList<>();
+ for (int x = minX; x <= maxX; x++) {
+ List<NavigateNode> sourceRow = navigateMap.get(x);
+ List<NavigateNode> croppedRow = new ArrayList<>();
+ for (int y = minY; y <= maxY; y++) {
+ NavigateNode sourceNode = sourceRow.get(y);
+ NavigateNode targetNode = new NavigateNode(x - minX, y - minY);
+ targetNode.setValue(sourceNode.getValue());
+ targetNode.setNodeType(sourceNode.getNodeType());
+ targetNode.setNodeValue(sourceNode.getNodeValue());
+ targetNode.setDirectionList(sourceNode.getDirectionList() == null
+ ? null
+ : new ArrayList<>(sourceNode.getDirectionList()));
+ croppedRow.add(targetNode);
+ }
+ croppedMap.add(croppedRow);
+ }
+ return croppedMap;
}
public NavigateNode astarSearchJava(List<List<NavigateNode>> map, NavigateNode start, NavigateNode end) {
@@ -143,13 +393,13 @@
}
//灏嗚繖涓粨鐐瑰姞鍏ュ埌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)
@@ -161,7 +411,7 @@
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);
// 浠呭綋鎵惧埌鏇村皬鐨勪唬浠锋椂鎵嶆洿鏂颁笌鍏pen锛岄伩鍏嶇瓑浠蜂唬浠峰弽澶嶅叆闃熷鑷寸埗閾炬姈鍔�
if (recordedG == null || node.getG() < recordedG) {
@@ -210,6 +460,14 @@
AtomicInteger pathCount = new AtomicInteger(0);
Map<Integer, NavigateNode> guideNodeMap = buildGuideNodeMap(map, guideStationIds);
+ SimplePathSearchContext searchContext = new SimplePathSearchContext(
+ start,
+ end,
+ maxDepth,
+ maxPaths,
+ maxCost,
+ System.currentTimeMillis() + SIMPLE_PATH_SEARCH_TIMEOUT_MS
+ );
dfsAllSimplePaths(map, start, end,
visited, path, results,
@@ -218,7 +476,8 @@
maxDepth, maxPaths, maxCost,
pathCount,
guideStationIds,
- guideNodeMap
+ guideNodeMap,
+ searchContext
);
return results;
@@ -241,8 +500,13 @@
int maxCost,
AtomicInteger pathCount,
List<Integer> guideStationIds,
- Map<Integer, NavigateNode> guideNodeMap
+ Map<Integer, NavigateNode> guideNodeMap,
+ SimplePathSearchContext searchContext
) {
+ if (isSimplePathSearchTimedOut(searchContext, results, pathCount, depth)) {
+ return;
+ }
+
// 闃茬垎锛氭潯鏁伴檺鍒�
if (maxPaths > 0 && pathCount.get() >= maxPaths) return;
@@ -262,6 +526,10 @@
neighbors = sortNeighborsByGuide(current, path, neighbors, guideStationIds, guideNodeMap);
for (NavigateNode next : neighbors) {
+ if (isSimplePathSearchTimedOut(searchContext, results, pathCount, depth)) {
+ return;
+ }
+
// 闃茬垎锛氭潯鏁伴檺鍒�
if (maxPaths > 0 && pathCount.get() >= maxPaths) return;
@@ -291,13 +559,41 @@
maxDepth, maxPaths, maxCost,
pathCount,
guideStationIds,
- guideNodeMap
+ guideNodeMap,
+ searchContext
);
// 鍥炴函
path.removeLast();
visited.remove(nk);
}
+ }
+
+ private boolean isSimplePathSearchTimedOut(SimplePathSearchContext searchContext,
+ List<List<NavigateNode>> results,
+ AtomicInteger pathCount,
+ int depth) {
+ if (searchContext == null || searchContext.timeoutLogged) {
+ return searchContext != null && searchContext.timeoutLogged;
+ }
+ if (System.currentTimeMillis() < searchContext.deadlineMs) {
+ return false;
+ }
+
+ searchContext.timeoutLogged = true;
+ Integer startStationId = extractStationId(searchContext.startNode);
+ Integer endStationId = extractStationId(searchContext.endNode);
+ com.zy.core.News.warn("绔欑偣璺緞鍊欓�夋灇涓捐秴鏃惰繑鍥烇紝startStationId={}锛宔ndStationId={}锛宼imeoutMs={}锛宖oundPathCount={}锛宺esultSize={}锛宒epth={}锛宮axDepth={}锛宮axPaths={}锛宮axCost={}",
+ startStationId,
+ endStationId,
+ SIMPLE_PATH_SEARCH_TIMEOUT_MS,
+ pathCount == null ? 0 : pathCount.get(),
+ results == null ? 0 : results.size(),
+ depth,
+ searchContext.maxDepth,
+ searchContext.maxPaths,
+ searchContext.maxCost);
+ return true;
}
private String keyOf(NavigateNode n) {
@@ -399,8 +695,14 @@
}
private Integer extractStationId(NavigateNode node) {
- JSONObject valueObj = parseNodeValue(node == null ? null : node.getNodeValue());
- return valueObj == null ? null : valueObj.getInteger("stationId");
+ if (node == null) {
+ return null;
+ }
+ if (node.getStationId() != null) {
+ return node.getStationId();
+ }
+ applyNodeMetadata(node);
+ return node.getStationId();
}
private JSONObject parseNodeValue(String nodeValue) {
@@ -531,6 +833,13 @@
return bestNode;
}
+ public NavigateNode findStationNavigateNode(NavigateMapIndex navigateMapIndex, int stationId) {
+ if (navigateMapIndex == null) {
+ return null;
+ }
+ return navigateMapIndex.getBestStationNode(stationId);
+ }
+
private int countExternalConnectionCount(Integer currentStationId, List<NavigateNode> neighbors) {
Set<Integer> connectedStationIdSet = new LinkedHashSet<>();
if (neighbors == null || neighbors.isEmpty()) {
@@ -544,23 +853,125 @@
private Set<Integer> resolveAdjacentStationIds(Integer currentStationId, NavigateNode node) {
Set<Integer> stationIdSet = new LinkedHashSet<>();
- JSONObject valueObj = parseNodeValue(node == null ? null : node.getNodeValue());
- if (valueObj == null) {
+ if (node == null) {
return stationIdSet;
}
- Integer directStationId = valueObj.getInteger("stationId");
+ Integer directStationId = extractStationId(node);
if (directStationId != null && !directStationId.equals(currentStationId)) {
stationIdSet.add(directStationId);
}
- if (valueObj.getJSONArray("bridgeStationIds") == null) {
- return stationIdSet;
- }
- for (Integer bridgeStationId : valueObj.getJSONArray("bridgeStationIds").toJavaList(Integer.class)) {
+ for (Integer bridgeStationId : node.getBridgeStationIds() == null ? Collections.<Integer>emptyList() : node.getBridgeStationIds()) {
if (bridgeStationId != null && !bridgeStationId.equals(currentStationId)) {
stationIdSet.add(bridgeStationId);
}
}
return stationIdSet;
+ }
+
+ public List<NavigateNode> getNeighborNodes(NavigateMapIndex navigateMapIndex, NavigateNode node) {
+ if (navigateMapIndex == null || node == null) {
+ return Collections.emptyList();
+ }
+ return navigateMapIndex.getNeighborNodes(node);
+ }
+
+ public Set<Integer> getConnectedStationIds(NavigateMapIndex navigateMapIndex,
+ Integer currentStationId,
+ NavigateNode node) {
+ if (navigateMapIndex == null || node == null) {
+ return Collections.emptySet();
+ }
+ return navigateMapIndex.getConnectedStationIds(currentStationId, node);
+ }
+
+ private NavigateMapIndex buildNavigateMapIndex(int lev, List<List<NavigateNode>> navigateMap) {
+ if (navigateMap == null || navigateMap.isEmpty()) {
+ return new NavigateMapIndex(lev,
+ new ArrayList<>(),
+ Collections.emptyMap(),
+ Collections.emptyMap(),
+ Collections.emptyMap(),
+ Collections.emptyMap());
+ }
+
+ enrichNavigateMapMetadata(navigateMap);
+ Map<String, NavigateNodeMeta> nodeMetaMap = new LinkedHashMap<>();
+ Map<String, List<NavigateNode>> neighborNodeMap = new LinkedHashMap<>();
+ Map<String, Set<Integer>> connectedStationIdMap = new LinkedHashMap<>();
+
+ for (List<NavigateNode> row : navigateMap) {
+ for (NavigateNode node : row) {
+ if (node == null || node.getValue() == MapNodeType.DISABLE.id) {
+ continue;
+ }
+ String nodeKey = buildNodeKey(node);
+ nodeMetaMap.put(nodeKey, buildNavigateNodeMeta(node));
+ List<NavigateNode> neighborList = extend_current_node(navigateMap, node);
+ neighborNodeMap.put(nodeKey, Collections.unmodifiableList(new ArrayList<>(neighborList)));
+ }
+ }
+
+ Map<Integer, NavigateNode> stationNodeMap = new LinkedHashMap<>();
+ Map<Integer, Integer> stationExternalCountMap = new HashMap<>();
+ Map<Integer, Integer> stationNeighborCountMap = new HashMap<>();
+ for (List<NavigateNode> row : navigateMap) {
+ for (NavigateNode node : row) {
+ if (node == null || node.getValue() == MapNodeType.DISABLE.id) {
+ continue;
+ }
+ String nodeKey = buildNodeKey(node);
+ Integer stationId = extractStationId(node);
+ Set<Integer> connectedStationIds = resolveAdjacentStationIds(stationId, neighborNodeMap.get(nodeKey));
+ connectedStationIdMap.put(nodeKey, Collections.unmodifiableSet(connectedStationIds));
+ if (stationId == null) {
+ continue;
+ }
+ int externalConnectionCount = connectedStationIds.size();
+ int neighborCount = neighborNodeMap.get(nodeKey).size();
+ Integer bestExternalCount = stationExternalCountMap.get(stationId);
+ Integer bestNeighborCount = stationNeighborCountMap.get(stationId);
+ if (bestExternalCount == null
+ || externalConnectionCount > bestExternalCount
+ || (externalConnectionCount == bestExternalCount && (bestNeighborCount == null || neighborCount > bestNeighborCount))) {
+ stationNodeMap.put(stationId, node);
+ stationExternalCountMap.put(stationId, externalConnectionCount);
+ stationNeighborCountMap.put(stationId, neighborCount);
+ }
+ }
+ }
+ return new NavigateMapIndex(lev,
+ navigateMap,
+ Collections.unmodifiableMap(nodeMetaMap),
+ Collections.unmodifiableMap(stationNodeMap),
+ Collections.unmodifiableMap(neighborNodeMap),
+ Collections.unmodifiableMap(connectedStationIdMap));
+ }
+
+ private Set<Integer> resolveAdjacentStationIds(Integer currentStationId, List<NavigateNode> neighbors) {
+ Set<Integer> connectedStationIdSet = new LinkedHashSet<>();
+ if (neighbors == null || neighbors.isEmpty()) {
+ return connectedStationIdSet;
+ }
+ for (NavigateNode neighbor : neighbors) {
+ connectedStationIdSet.addAll(resolveAdjacentStationIds(currentStationId, neighbor));
+ }
+ return connectedStationIdSet;
+ }
+
+ private String buildNodeKey(NavigateNode node) {
+ if (node == null) {
+ return "";
+ }
+ return node.getX() + "_" + node.getY();
+ }
+
+ private NavigateNodeMeta buildNavigateNodeMeta(NavigateNode node) {
+ return new NavigateNodeMeta(
+ extractStationId(node),
+ node == null || node.getBridgeStationIds() == null ? Collections.emptyList() : node.getBridgeStationIds(),
+ node != null && Boolean.TRUE.equals(node.getLiftTransfer()),
+ node != null && Boolean.TRUE.equals(node.getRgvCalcFlag())
+ );
}
public NavigateNode findTrackSiteNoNavigateNode(List<List<NavigateNode>> map, int trackSiteNo) {
@@ -609,4 +1020,156 @@
//------------------A*鍚彂鍑芥暟-end------------------//
+ public static class NavigateMapIndex {
+ private final int lev;
+ private final List<List<NavigateNode>> navigateMap;
+ private final Map<String, NavigateNodeMeta> nodeMetaMap;
+ private final Map<Integer, NavigateNode> stationNodeMap;
+ private final Map<String, List<NavigateNode>> neighborNodeMap;
+ private final Map<String, Set<Integer>> connectedStationIdMap;
+
+ private NavigateMapIndex(int lev,
+ List<List<NavigateNode>> navigateMap,
+ Map<String, NavigateNodeMeta> nodeMetaMap,
+ Map<Integer, NavigateNode> stationNodeMap,
+ Map<String, List<NavigateNode>> neighborNodeMap,
+ Map<String, Set<Integer>> connectedStationIdMap) {
+ this.lev = lev;
+ this.navigateMap = navigateMap == null ? new ArrayList<>() : navigateMap;
+ this.nodeMetaMap = nodeMetaMap == null ? Collections.emptyMap() : nodeMetaMap;
+ this.stationNodeMap = stationNodeMap == null ? Collections.emptyMap() : stationNodeMap;
+ this.neighborNodeMap = neighborNodeMap == null ? Collections.emptyMap() : neighborNodeMap;
+ this.connectedStationIdMap = connectedStationIdMap == null ? Collections.emptyMap() : connectedStationIdMap;
+ }
+
+ public int getLev() {
+ return lev;
+ }
+
+ public List<List<NavigateNode>> getNavigateMap() {
+ return navigateMap;
+ }
+
+ public NavigateNode getBestStationNode(Integer stationId) {
+ if (stationId == null) {
+ return null;
+ }
+ return stationNodeMap.get(stationId);
+ }
+
+ public List<NavigateNode> getNeighborNodes(NavigateNode node) {
+ if (node == null) {
+ return Collections.emptyList();
+ }
+ return neighborNodeMap.getOrDefault(node.getX() + "_" + node.getY(), Collections.emptyList());
+ }
+
+ public Set<Integer> getConnectedStationIds(Integer currentStationId, NavigateNode node) {
+ if (node == null) {
+ return Collections.emptySet();
+ }
+ Set<Integer> stationIdSet = connectedStationIdMap.getOrDefault(node.getX() + "_" + node.getY(), Collections.emptySet());
+ if (currentStationId == null || stationIdSet.isEmpty()) {
+ return stationIdSet;
+ }
+ if (!stationIdSet.contains(currentStationId)) {
+ return stationIdSet;
+ }
+ Set<Integer> filterStationIdSet = new LinkedHashSet<>();
+ for (Integer stationId : stationIdSet) {
+ if (stationId != null && !stationId.equals(currentStationId)) {
+ filterStationIdSet.add(stationId);
+ }
+ }
+ return filterStationIdSet;
+ }
+
+ public Integer getStationId(NavigateNode node) {
+ NavigateNodeMeta meta = getNodeMeta(node);
+ return meta == null ? null : meta.stationId;
+ }
+
+ public List<Integer> getBridgeStationIds(NavigateNode node) {
+ NavigateNodeMeta meta = getNodeMeta(node);
+ return meta == null ? Collections.emptyList() : meta.bridgeStationIds;
+ }
+
+ public boolean isLiftTransfer(NavigateNode node) {
+ NavigateNodeMeta meta = getNodeMeta(node);
+ return meta != null && meta.liftTransfer;
+ }
+
+ public boolean isRgvCalcFlag(NavigateNode node) {
+ NavigateNodeMeta meta = getNodeMeta(node);
+ return meta != null && meta.rgvCalcFlag;
+ }
+
+ private NavigateNodeMeta getNodeMeta(NavigateNode node) {
+ if (node == null) {
+ return null;
+ }
+ return nodeMetaMap.get(node.getX() + "_" + node.getY());
+ }
+ }
+
+ private static class NavigateNodeMeta {
+ private final Integer stationId;
+ private final List<Integer> bridgeStationIds;
+ private final boolean liftTransfer;
+ private final boolean rgvCalcFlag;
+
+ private NavigateNodeMeta(Integer stationId,
+ List<Integer> bridgeStationIds,
+ boolean liftTransfer,
+ boolean rgvCalcFlag) {
+ this.stationId = stationId;
+ this.bridgeStationIds = bridgeStationIds == null ? Collections.emptyList() : bridgeStationIds;
+ this.liftTransfer = liftTransfer;
+ this.rgvCalcFlag = rgvCalcFlag;
+ }
+ }
+
+ private static class SimplePathSearchContext {
+ private final NavigateNode startNode;
+ private final NavigateNode endNode;
+ private final int maxDepth;
+ private final int maxPaths;
+ private final int maxCost;
+ private final long deadlineMs;
+ private boolean timeoutLogged;
+
+ private SimplePathSearchContext(NavigateNode startNode,
+ NavigateNode endNode,
+ int maxDepth,
+ int maxPaths,
+ int maxCost,
+ long deadlineMs) {
+ this.startNode = startNode;
+ this.endNode = endNode;
+ this.maxDepth = maxDepth;
+ this.maxPaths = maxPaths;
+ this.maxCost = maxCost;
+ this.deadlineMs = deadlineMs;
+ }
+ }
+
+ private static class CachedNavigateMap {
+ private final long cacheAtMs;
+ private final List<List<NavigateNode>> navigateMap;
+
+ private CachedNavigateMap(long cacheAtMs, List<List<NavigateNode>> navigateMap) {
+ this.cacheAtMs = cacheAtMs;
+ this.navigateMap = navigateMap;
+ }
+ }
+
+ private static class CachedNavigateMapIndex {
+ private final long cacheAtMs;
+ private final NavigateMapIndex navigateMapIndex;
+
+ private CachedNavigateMapIndex(long cacheAtMs, NavigateMapIndex navigateMapIndex) {
+ this.cacheAtMs = cacheAtMs;
+ this.navigateMapIndex = navigateMapIndex;
+ }
+ }
}
--
Gitblit v1.9.1