#dfs

Junjie

1 天以前 852664df1caf38831793b341edcada9dd7b6c22a

 src/main/java/com/zy/common/utils/NavigateUtils.java

@@ -27,6 +27,8 @@
import com.zy.asrs.service.StationCycleCapacityService;
import com.zy.asrs.service.StationPathPolicyService;
import com.zy.core.News;
import lombok.extern.slf4j.Slf4j;
import org.springframework.scheduling.annotation.Scheduled;
import com.zy.core.model.StationObjModel;
import com.zy.core.model.command.StationCommand;
import com.zy.core.enums.StationCommandType;
@@ -52,6 +54,7 @@
import java.util.LinkedHashMap;

@Component
@Slf4j
public class NavigateUtils {

    private static final long STATION_PATH_SLOW_LOG_THRESHOLD_MS = 500L;
@@ -77,8 +80,23 @@
    @Autowired
    private StationTaskTraceRegistry stationTaskTraceRegistry;

    private final Object runtimeSnapshotLock = new Object();
    private volatile CachedStationPathRuntimeSnapshot cachedRuntimeSnapshot;

    private volatile CachedLoopMergeGuardContext cachedLoopMergeGuardContext;

    @Scheduled(fixedDelay = 1500, initialDelay = 3000)
    public void refreshStationPathCaches() {
        try {
            BaseRuntimeSnapshot snapshot = buildBaseRuntimeSnapshot(null);
            cachedRuntimeSnapshot = new CachedStationPathRuntimeSnapshot(System.currentTimeMillis(), snapshot);
        } catch (Exception ignore) {
        }
        try {
            LoopMergeGuardContext context = buildLoopMergeGuardContext();
            cachedLoopMergeGuardContext = new CachedLoopMergeGuardContext(System.currentTimeMillis(), context);
        } catch (Exception ignore) {
        }
    }

    public List<NavigateNode> calcOptimalPathByStationId(Integer startStationId,
                                                         Integer endStationId,
@@ -95,29 +113,74 @@
                                                                 Integer endStationId,
                                                                 Integer currentTaskNo,
                                                                 Double pathLenFactor) {
        StationPathResolvedPolicy resolvedPolicy = resolveStationPathPolicy(startStationId, endStationId);
        StationPathRuntimeSnapshot runtimeSnapshot = loadStationPathRuntimeSnapshot(currentTaskNo);
        StationPathSearchContext context = buildStationPathSearchContext(
                startStationId,
                endStationId,
                resolvedPolicy,
                StationPathCalcMode.REROUTE,
                runtimeSnapshot
        );
        if (context.allList.isEmpty()) {
            return new ArrayList<>();
        }
        long totalStartNs = System.nanoTime();
        log.info("站点路径候选计算入口，startStationId={}，endStationId={}，taskNo={}，pathLenFactor={}",
                startStationId, endStationId, currentTaskNo, pathLenFactor);
        try {
            StationPathResolvedPolicy resolvedPolicy = resolveStationPathPolicy(startStationId, endStationId);
            log.info("站点路径候选策略解析完成，startStationId={}，endStationId={}，taskNo={}，matchedRule={}，ruleCode={}，profileCode={}，costMs={}",
                    startStationId,
                    endStationId,
                    currentTaskNo,
                    resolvedPolicy != null && resolvedPolicy.matchedRule(),
                    resolvedPolicy == null || resolvedPolicy.getRuleEntity() == null ? null : resolvedPolicy.getRuleEntity().getRuleCode(),
                    resolvedPolicy == null ? null : resolvedPolicy.getDefaultProfileCode(),
                    elapsedMillis(totalStartNs));
            StationPathRuntimeSnapshot runtimeSnapshot = loadStationPathRuntimeSnapshot(currentTaskNo);
            List<NavigateNode> shortFallbackPath = buildRerouteShortFallbackPath(
                    startStationId,
                    endStationId,
                    currentTaskNo,
                    resolvedPolicy,
                    runtimeSnapshot
            );
            StationPathSearchContext context = buildStationPathSearchContext(
                    startStationId,
                    endStationId,
                    resolvedPolicy,
                    StationPathCalcMode.REROUTE,
                    runtimeSnapshot
            );
            if (context.allList.isEmpty()) {
                List<List<NavigateNode>> fallbackCandidateList = normalizeCandidatePaths(Collections.singletonList(shortFallbackPath));
                log.warn("站点路径候选计算结束，原因=empty_search_context，startStationId={}，endStationId={}，taskNo={}，fallbackCandidateCount={}，fallbackPath={}，totalCostMs={}",
                        startStationId,
                        endStationId,
                        currentTaskNo,
                        fallbackCandidateList.size(),
                        JSON.toJSONString(extractStationIdList(shortFallbackPath)),
                        elapsedMillis(totalStartNs));
                return fallbackCandidateList;
            }

        List<List<NavigateNode>> orderedPathList = orderStationPathCandidates(
                context.allList,
                context.resolvedPolicy,
                currentTaskNo,
                pathLenFactor,
                startStationId,
                endStationId,
                runtimeSnapshot
        );
        return normalizeCandidatePaths(orderedPathList);
            long orderStartNs = System.nanoTime();
            List<List<NavigateNode>> orderedPathList = orderStationPathCandidates(
                    context.allList,
                    context.resolvedPolicy,
                    currentTaskNo,
                    pathLenFactor,
                    startStationId,
                    endStationId,
                    runtimeSnapshot
            );
            List<List<NavigateNode>> candidatePathList = appendShortFallbackCandidate(orderedPathList, shortFallbackPath);
            List<List<NavigateNode>> normalizedPathList = normalizeCandidatePaths(candidatePathList);
            log.info("站点路径候选计算结束，startStationId={}，endStationId={}，taskNo={}，rawCandidateCount={}，orderedPathCount={}，fallbackPathLen={}，normalizedPathCount={}，orderCostMs={}，totalCostMs={}",
                    startStationId,
                    endStationId,
                    currentTaskNo,
                    context.allList.size(),
                    orderedPathList == null ? null : orderedPathList.size(),
                    shortFallbackPath == null ? 0 : shortFallbackPath.size(),
                    normalizedPathList.size(),
                    elapsedMillis(orderStartNs),
                    elapsedMillis(totalStartNs));
            return normalizedPathList;
        } catch (Exception e) {
            log.error("站点路径候选计算异常，startStationId={}，endStationId={}，taskNo={}，pathLenFactor={}，costMs={}",
                    startStationId, endStationId, currentTaskNo, pathLenFactor, elapsedMillis(totalStartNs), e);
            throw e;
        }
    }

    public Map<Integer, Set<Integer>> loadUndirectedStationGraphSnapshot() {
@@ -397,6 +460,54 @@
            return new DirectPathSearchResult(degradedPath, includeWaypoint, false);
        }
        return DirectPathSearchResult.empty(includeWaypoint, includeSoftPreference);
    }

    private List<NavigateNode> buildRerouteShortFallbackPath(Integer startStationId,
                                                             Integer endStationId,
                                                             Integer currentTaskNo,
                                                             StationPathResolvedPolicy resolvedPolicy,
                                                             StationPathRuntimeSnapshot runtimeSnapshot) {
        long startNs = System.nanoTime();
        try {
            List<NavigateNode> path = findStationDirectPath(
                    startStationId,
                    endStationId,
                    currentTaskNo,
                    0.0d,
                    StationPathCalcMode.OPTIMAL,
                    resolvedPolicy,
                    runtimeSnapshot
            );
            List<NavigateNode> normalizedPath = normalizeStationPath(path);
            log.info("站点路径堵塞重规划短路径保底计算完成，startStationId={}，endStationId={}，taskNo={}，pathLen={}，path={}，costMs={}",
                    startStationId,
                    endStationId,
                    currentTaskNo,
                    normalizedPath.size(),
                    JSON.toJSONString(extractStationIdList(normalizedPath)),
                    elapsedMillis(startNs));
            return normalizedPath;
        } catch (Exception e) {
            log.warn("站点路径堵塞重规划短路径保底计算失败，startStationId={}，endStationId={}，taskNo={}，costMs={}，error={}",
                    startStationId,
                    endStationId,
                    currentTaskNo,
                    elapsedMillis(startNs),
                    e.toString());
            return new ArrayList<>();
        }
    }

    private List<List<NavigateNode>> appendShortFallbackCandidate(List<List<NavigateNode>> orderedPathList,
                                                                  List<NavigateNode> shortFallbackPath) {
        List<List<NavigateNode>> candidatePathList = new ArrayList<>();
        if (orderedPathList != null && !orderedPathList.isEmpty()) {
            candidatePathList.addAll(orderedPathList);
        }
        if (shortFallbackPath != null && !shortFallbackPath.isEmpty()) {
            candidatePathList.add(shortFallbackPath);
        }
        return candidatePathList;
    }

    private List<NavigateNode> searchDirectPath(DirectStationPathContext context,
@@ -1688,22 +1799,21 @@
            }
            return cachedSnapshot.baseRuntimeSnapshot.toCacheHitSnapshot();
        }
        synchronized (runtimeSnapshotLock) {
            cachedSnapshot = cachedRuntimeSnapshot;
            if (cachedSnapshot != null && now - cachedSnapshot.cacheAtMs <= STATION_PATH_RUNTIME_SNAPSHOT_TTL_MS) {
                if (stepCostMap != null) {
                    stepCostMap.put("baseSnapshotCacheHit", 0L);
                }
                return cachedSnapshot.baseRuntimeSnapshot.toCacheHitSnapshot();
            }
            long stepStartNs = System.nanoTime();
            BaseRuntimeSnapshot baseRuntimeSnapshot = buildBaseRuntimeSnapshot(stepCostMap);
        // 缓存过期：用过期缓存兜底（@Scheduled 定时任务会很快刷新），避免多线程阻塞
        if (cachedSnapshot != null) {
            if (stepCostMap != null) {
                stepCostMap.put("buildBaseSnapshot", elapsedMillis(stepStartNs));
                stepCostMap.put("baseSnapshotStale", 0L);
            }
            cachedRuntimeSnapshot = new CachedStationPathRuntimeSnapshot(System.currentTimeMillis(), baseRuntimeSnapshot);
            return baseRuntimeSnapshot;
            return cachedSnapshot.baseRuntimeSnapshot.toCacheHitSnapshot();
        }
        // 极端情况：从未有过缓存（启动首次调用），同步构建
        long stepStartNs = System.nanoTime();
        BaseRuntimeSnapshot baseRuntimeSnapshot = buildBaseRuntimeSnapshot(stepCostMap);
        if (stepCostMap != null) {
            stepCostMap.put("buildBaseSnapshot", elapsedMillis(stepStartNs));
        }
        cachedRuntimeSnapshot = new CachedStationPathRuntimeSnapshot(System.currentTimeMillis(), baseRuntimeSnapshot);
        return baseRuntimeSnapshot;
    }

    private BaseRuntimeSnapshot buildBaseRuntimeSnapshot(Map<String, Long> stepCostMap) {
@@ -1766,6 +1876,22 @@
    }

    private LoopMergeGuardContext loadLoopMergeGuardContext() {
        long now = System.currentTimeMillis();
        CachedLoopMergeGuardContext cached = cachedLoopMergeGuardContext;
        if (cached != null && now - cached.cacheAtMs <= STATION_PATH_RUNTIME_SNAPSHOT_TTL_MS) {
            return new LoopMergeGuardContext(cached.context);
        }
        // 缓存过期：用过期缓存兜底（@Scheduled 定时任务会很快刷新）
        if (cached != null) {
            return new LoopMergeGuardContext(cached.context);
        }
        // 极端情况：从未有过缓存，同步构建
        LoopMergeGuardContext context = buildLoopMergeGuardContext();
        cachedLoopMergeGuardContext = new CachedLoopMergeGuardContext(System.currentTimeMillis(), context);
        return new LoopMergeGuardContext(context);
    }

    private LoopMergeGuardContext buildLoopMergeGuardContext() {
        LoopMergeGuardContext context = new LoopMergeGuardContext();
        try {
            if (stationCycleCapacityService == null) {
@@ -2654,6 +2780,8 @@
        }
        Integer lev = startStation.getStationLev();
        stepCostMap.put("loadStartStation", elapsedMillis(stepStartNs));
        log.info("站点路径搜索上下文加载起点完成，startStationId={}，endStationId={}，mode={}，lev={}，costMs={}",
                startStationId, endStationId, calcMode, lev, stepCostMap.get("loadStartStation"));

        stepStartNs = System.nanoTime();
        NavigateSolution navigateSolution = new NavigateSolution();
@@ -2670,6 +2798,16 @@
            throw new CoolException("未找到该 终点 对应的节点");
        }
        stepCostMap.put("loadStationMapAndNode", elapsedMillis(stepStartNs));
        log.info("站点路径搜索上下文加载地图完成，startStationId={}，endStationId={}，mode={}，mapRows={}，startNode=({},{})，endNode=({},{})，costMs={}",
                startStationId,
                endStationId,
                calcMode,
                stationMap.size(),
                startNode.getX(),
                startNode.getY(),
                endNode.getX(),
                endNode.getY(),
                stepCostMap.get("loadStationMapAndNode"));

        stepStartNs = System.nanoTime();
        StationPathProfileConfig profileConfig = resolvedPolicy.getProfileConfig() == null
@@ -2683,9 +2821,17 @@
                endStationId,
                calcMode == null ? "" : calcMode.name());
        int calcMaxDepth = safeInt(profileConfig.getCalcMaxDepth(), 120);
        int calcMaxPaths = safeInt(profileConfig.getCalcMaxPaths(), 500);
        int calcMaxPaths = safeInt(profileConfig.getCalcMaxPaths(), 50);
        int calcMaxCost = safeInt(profileConfig.getCalcMaxCost(), 300);
        List<Integer> guideStationSequence = buildGuideStationSequence(startStationId, endStationId, resolvedPolicy.getRuleConfig());
        log.info("站点路径候选枚举开始，startStationId={}，endStationId={}，mode={}，calcMaxDepth={}，calcMaxPaths={}，calcMaxCost={}，guideStationSequence={}",
                startStationId,
                endStationId,
                calcMode,
                calcMaxDepth,
                calcMaxPaths,
                calcMaxCost,
                JSON.toJSONString(guideStationSequence));
        stepStartNs = System.nanoTime();
        List<List<NavigateNode>> allList = navigateSolution.allSimplePaths(
                stationMap,
@@ -2698,6 +2844,12 @@
        );
        stepCostMap.put("allSimplePaths", elapsedMillis(stepStartNs));
        rawCandidateCount = allList.size();
        log.info("站点路径候选枚举完成，startStationId={}，endStationId={}，mode={}，rawCandidateCount={}，costMs={}",
                startStationId,
                endStationId,
                calcMode,
                rawCandidateCount,
                stepCostMap.get("allSimplePaths"));
        if (allList.isEmpty()) {
            logStationPathSearchContextSlow(startStationId, endStationId, calcMode, lev, rawCandidateCount, filteredCandidateCount, stepCostMap, totalStartNs);
            return StationPathSearchContext.empty(resolvedPolicy);
@@ -2707,6 +2859,14 @@
        allList = filterNonAutoStationPaths(allList, statusMap);
        stepCostMap.put("filterNonAutoStation", elapsedMillis(stepStartNs));
        filteredCandidateCount = allList.size();
        log.info("站点路径候选自动状态过滤完成，startStationId={}，endStationId={}，mode={}，rawCandidateCount={}，filteredCandidateCount={}，statusCount={}，costMs={}",
                startStationId,
                endStationId,
                calcMode,
                rawCandidateCount,
                filteredCandidateCount,
                statusMap.size(),
                stepCostMap.get("filterNonAutoStation"));
        if (allList.isEmpty()) {
            News.info("[WCS Debug] 站点路径候选全部被过滤，存在非自动站点,startStationId={},endStationId={}", startStationId, endStationId);
            logStationPathSearchContextSlow(startStationId, endStationId, calcMode, lev, rawCandidateCount, filteredCandidateCount, stepCostMap, totalStartNs);
@@ -3083,6 +3243,16 @@
        }
    }

    private static class CachedLoopMergeGuardContext {
        private final long cacheAtMs;
        private final LoopMergeGuardContext context;

        private CachedLoopMergeGuardContext(long cacheAtMs, LoopMergeGuardContext context) {
            this.cacheAtMs = cacheAtMs;
            this.context = context;
        }
    }

    private static class PathCandidateMetrics {
        private List<NavigateNode> path;
        private int pathLen;
@@ -3136,6 +3306,16 @@
    private static class LoopMergeGuardContext {
        private final Set<Integer> loopStationIdSet = new HashSet<>();
        private final Map<Integer, Set<Integer>> loopNeighborMap = new HashMap<>();

        private LoopMergeGuardContext() {
        }

        private LoopMergeGuardContext(LoopMergeGuardContext source) {
            this.loopStationIdSet.addAll(source.loopStationIdSet);
            for (Map.Entry<Integer, Set<Integer>> entry : source.loopNeighborMap.entrySet()) {
                this.loopNeighborMap.put(entry.getKey(), new LinkedHashSet<>(entry.getValue()));
            }
        }
    }

    private static class LoopMergeEntry {