#算法优化

Junjie

12 小时以前 71a5ae03389119dc6975d7cfb87e63601f3c5305

#算法优化

 src/main/java/com/zy/asrs/controller/BasMapController.java

@@ -13,6 +13,7 @@
import com.core.common.BaseRes;
import com.core.common.Cools;
import com.core.common.R;
import com.zy.common.utils.NavigateSolution;
import com.zy.common.web.BaseController;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;
@@ -71,6 +72,9 @@
    @ManagerAuth
    public R add(BasMap basMap) {
        basMapService.save(basMap);
        if (basMap != null && basMap.getLev() != null) {
            NavigateSolution.refreshMapCache(basMap.getLev());
        }
        return R.ok();
    }

@@ -80,7 +84,17 @@
        if (Cools.isEmpty(basMap) || null==basMap.getId()){
            return R.error();
        }
        BasMap oldBasMap = basMapService.getById(basMap.getId());
        basMapService.updateById(basMap);
        if (oldBasMap != null && oldBasMap.getLev() != null) {
            NavigateSolution.clearMapCache(oldBasMap.getLev());
        }
        Integer refreshLev = basMap.getLev() != null
                ? basMap.getLev()
                : oldBasMap == null ? null : oldBasMap.getLev();
        if (refreshLev != null) {
            NavigateSolution.refreshMapCache(refreshLev);
        }
        return R.ok();
    }

@@ -88,7 +102,11 @@
    @ManagerAuth
    public R delete(@RequestParam(value="ids[]") Integer[] ids){
         for (Integer id : ids){
            BasMap basMap = basMapService.getById(id);
            basMapService.removeById(id);
            if (basMap != null && basMap.getLev() != null) {
                NavigateSolution.clearMapCache(basMap.getLev());
            }
        }
        return R.ok();
    }

 src/main/java/com/zy/asrs/service/impl/BasMapEditorServiceImpl.java

@@ -19,6 +19,7 @@
import com.zy.asrs.service.BasStationService;
import com.zy.asrs.service.DeviceConfigService;
import com.zy.asrs.utils.MapExcelUtils;
import com.zy.common.utils.NavigateSolution;
import com.zy.common.utils.RedisUtil;
import com.zy.core.enums.RedisKeyType;
import com.zy.core.enums.SlaveType;
@@ -111,7 +112,7 @@
            persistFloorMap(lev, storedData, toFreeEditorDoc(lev, storedData));
        }
        rebuildDeviceAndStationSync();
        clearMapCaches();
        clearMapCaches(levList);
    }

    @Override
@@ -121,7 +122,7 @@
        List<List<HashMap<String, Object>>> storedData = compileToStoredMapData(normalizedDoc);
        persistFloorMap(normalizedDoc.getLev(), storedData, normalizedDoc);
        rebuildDeviceAndStationSync();
        clearMapCaches();
        clearMapCaches(Collections.singletonList(normalizedDoc.getLev()));
    }

    private void persistFloorMap(Integer lev,
@@ -977,9 +978,19 @@
        return JSON.toJSONString(list, SerializerFeature.DisableCircularReferenceDetect);
    }

    private void clearMapCaches() {
    private void clearMapCaches(List<Integer> levList) {
        redisUtil.del(RedisKeyType.LOC_MAP_BASE.key);
        redisUtil.del(RedisKeyType.LOC_MAST_MAP_LIST.key);
        if (levList == null || levList.isEmpty()) {
            return;
        }
        LinkedHashSet<Integer> distinctLevSet = new LinkedHashSet<>(levList);
        for (Integer lev : distinctLevSet) {
            if (lev == null) {
                continue;
            }
            NavigateSolution.refreshMapCache(lev);
        }
    }

    private String normalizeType(String type) {

 src/main/java/com/zy/common/model/NavigateNode.java

@@ -27,6 +27,9 @@
    private String nodeValue;//节点数据
    private String nodeType;//节点类型

    public NavigateNode() {
    }

    public NavigateNode(int x, int y) {
        this.x = x;
        this.y = y;

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

@@ -2,20 +2,27 @@

import com.alibaba.fastjson.JSON;
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;

/**
 * A*算法实现类
 */
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 Map<String, CachedNavigateMap> NAVIGATE_MAP_CACHE = new ConcurrentHashMap<>();

    // Open表用优先队列
    public PriorityQueue<NavigateNode> Open = new PriorityQueue<NavigateNode>();
@@ -25,6 +32,101 @@
    Map<String, Integer> bestGMap = new HashMap<>();

    public List<List<NavigateNode>> getStationMap(int lev) {
        return cloneNavigateMap(loadCachedNavigateMap("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)) {
            NAVIGATE_MAP_CACHE.put(cacheKey, new CachedNavigateMap(now, redisNavigateMap));
            return redisNavigateMap;
        }
        clearMapCache(lev);

        List<List<NavigateNode>> navigateNodeList = buildNavigateMap(mapType, lev);
        cacheNavigateMap(cacheKey, mapType, lev, navigateNodeList, now);
        return navigateNodeList;
    }

    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.cacheNavigateMap("station:" + lev, "station", lev, stationMap, now);
        List<List<NavigateNode>> rgvMap = navigateSolution.buildNavigateMap("rgv", lev);
        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);
        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 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 +134,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 +142,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");
@@ -77,53 +185,103 @@
            }
            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("地图不存在");
    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());
            }
            cloneMap.add(cloneRow);
        }
        return cloneMap;
        }

        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);
    private boolean isValidNavigateMap(List<List<NavigateNode>> navigateMap) {
        if (navigateMap == null || navigateMap.isEmpty() || navigateMap.get(0) == null || navigateMap.get(0).isEmpty()) {
            return false;
                }

                navigateNode.setNodeType(nodeType);
                navigateNode.setNodeValue(map.getString("value"));
                navigateNodeRow.add(navigateNode);
        int activeNodeCount = 0;
        for (List<NavigateNode> row : navigateMap) {
            if (row == null || row.isEmpty()) {
                return false;
            }
            navigateNodeList.add(navigateNodeRow);
            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;
        }

        return navigateNodeList;
    /**
     * 只保留参与路径计算的二维区域，去掉上下左右整片无效空白区。
     */
    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) {
@@ -609,4 +767,13 @@

    //------------------A*启发函数-end------------------//

    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;
        }
    }
}

 src/main/java/com/zy/core/config/NavigateMapCacheInitializer.java

New file
@@ -0,0 +1,31 @@
package com.zy.core.config;

import com.zy.common.utils.NavigateSolution;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import org.springframework.context.ApplicationContext;
import org.springframework.context.ApplicationListener;
import org.springframework.context.event.ContextRefreshedEvent;
import org.springframework.stereotype.Component;

@Component
public class NavigateMapCacheInitializer implements ApplicationListener<ContextRefreshedEvent> {

    private static final Logger logger = LogManager.getLogger(NavigateMapCacheInitializer.class);

    @Override
    public void onApplicationEvent(ContextRefreshedEvent event) {
        ApplicationContext parent = event.getApplicationContext().getParent();
        if (parent != null) {
            return;
        }

        long start = System.currentTimeMillis();
        try {
            NavigateSolution.refreshAllMapCaches();
            logger.info("地图缓存刷新完成，cost={}ms", System.currentTimeMillis() - start);
        } catch (Exception e) {
            logger.error("地图缓存刷新失败", e);
        }
    }
}

 src/main/java/com/zy/core/enums/RedisKeyType.java

@@ -16,6 +16,7 @@
    LOG_LIMIT("log_limit_"),
    SYSTEM_CONFIG_MAP("system_config_map"),
    FAKE_TASK_NO_AREA("fake_task_no_area"),
    NAVIGATE_MAP_TEMPLATE_("navigate_map_template_"),
    IN_STATION_ROUTE_CACHE("in_station_route_cache_"),
    OUT_STATION_ROUTE_CACHE("out_station_route_cache_"),
    STATION_REACHABLE_CACHE("station_reachable_cache_"),

 src/main/java/com/zy/core/thread/impl/ZyStationV5Thread.java

@@ -197,10 +197,12 @@
            return getCommand(StationCommandType.MOVE, taskNo, stationId, targetStationId, palletSize, pathLenFactor);
        }

        long startNs = System.nanoTime();
        StationTaskLoopService taskLoopService = loadStationTaskLoopService();
        StationTaskLoopService.LoopEvaluation loopEvaluation = taskLoopService == null
                ? new StationTaskLoopService.LoopEvaluation(taskNo, stationId, StationTaskLoopService.LoopIdentitySnapshot.empty(), 0, 0, false)
                : taskLoopService.evaluateLoop(taskNo, stationId, true);
        long loopEvalNs = System.nanoTime();
        log.info("输送线堵塞重规划环线识别，taskNo={}, stationId={}, scopeType={}, localStationCount={}, sourceLoopStationCount={}",
                taskNo,
                stationId,
@@ -208,6 +210,7 @@
                loopEvaluation.getLoopIdentity().getLocalStationCount(),
                loopEvaluation.getLoopIdentity().getSourceLoopStationCount());
        List<List<NavigateNode>> candidatePathList = calcCandidatePathNavigateNodes(taskNo, stationId, targetStationId, pathLenFactor);
        long candidatePathNs = System.nanoTime();
        List<StationCommand> candidateCommandList = new ArrayList<>();
        for (List<NavigateNode> candidatePath : candidatePathList) {
            StationCommand rerouteCommand = buildMoveCommand(taskNo, stationId, targetStationId, palletSize, candidatePath);
@@ -216,6 +219,7 @@
            }
            candidateCommandList.add(rerouteCommand);
        }
        long buildCommandNs = System.nanoTime();

        StationV5RunBlockReroutePlanner.PlanResult planResult = runBlockReroutePlanner.plan(
                taskNo,
@@ -223,6 +227,17 @@
                loopEvaluation,
                candidateCommandList
        );
        long planNs = System.nanoTime();
        logRunBlockRerouteCost(taskNo,
                stationId,
                targetStationId,
                candidatePathList == null ? 0 : candidatePathList.size(),
                candidateCommandList.size(),
                startNs,
                loopEvalNs,
                candidatePathNs,
                buildCommandNs,
                planNs);
        if (candidateCommandList.isEmpty()) {
            log.warn("输送线堵塞重规划失败，候选路径为空，taskNo={}, planCount={}, stationId={}, targetStationId={}",
                    taskNo, planResult.getPlanCount(), stationId, targetStationId);
@@ -423,4 +438,35 @@
            return null;
        }
    }

    private void logRunBlockRerouteCost(Integer taskNo,
                                        Integer stationId,
                                        Integer targetStationId,
                                        int candidatePathCount,
                                        int candidateCommandCount,
                                        long startNs,
                                        long loopEvalNs,
                                        long candidatePathNs,
                                        long buildCommandNs,
                                        long planNs) {
        long totalMs = nanosToMillis(planNs - startNs);
        if (totalMs < 1000L) {
            return;
        }
        log.warn("输送线堵塞重规划耗时较长, taskNo={}, stationId={}, targetStationId={}, total={}ms, loopEval={}ms, candidatePath={}ms, buildCommand={}ms, planner={}ms, candidatePathCount={}, candidateCommandCount={}",
                taskNo,
                stationId,
                targetStationId,
                totalMs,
                nanosToMillis(loopEvalNs - startNs),
                nanosToMillis(candidatePathNs - loopEvalNs),
                nanosToMillis(buildCommandNs - candidatePathNs),
                nanosToMillis(planNs - buildCommandNs),
                candidatePathCount,
                candidateCommandCount);
    }

    private long nanosToMillis(long nanos) {
        return nanos <= 0L ? 0L : nanos / 1_000_000L;
    }
}

 src/test/java/com/zy/common/utils/NavigatePerformanceBenchmarkTest.java

New file
@@ -0,0 +1,354 @@
package com.zy.common.utils;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;
import com.zy.asrs.service.impl.BasMapEditorServiceImpl;
import com.zy.asrs.utils.MapExcelUtils;
import com.zy.common.model.NavigateNode;
import com.zy.core.enums.MapNodeType;
import org.junit.jupiter.api.Assumptions;
import org.junit.jupiter.api.Test;
import org.springframework.test.util.ReflectionTestUtils;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

import static org.junit.jupiter.api.Assertions.assertFalse;

class NavigatePerformanceBenchmarkTest {

    private static final int CALC_MAX_DEPTH = 120;
    private static final int CALC_MAX_PATHS = 500;
    private static final int CALC_MAX_COST = 300;

    @Test
    void benchmarkExcelMaps() throws Exception {
        // 手工压测入口，避免默认测试套件被性能测试拖慢。
        Assumptions.assumeTrue(Boolean.getBoolean("manualBench"));

        Path mapDir = Path.of("src/main/resources/map");
        List<Path> mapFileList;
        try (Stream<Path> stream = Files.list(mapDir)) {
            mapFileList = stream
                    .filter(path -> path.getFileName().toString().endsWith(".xlsx"))
                    .sorted(Comparator.comparing(path -> path.getFileName().toString()))
                    .collect(Collectors.toList());
        }

        List<String> reportLineList = new ArrayList<>();
        for (Path mapFile : mapFileList) {
            reportLineList.addAll(benchmarkMapFile(mapFile));
        }

        reportLineList.forEach(System.out::println);
        assertFalse(reportLineList.isEmpty(), "未生成任何地图性能报告");
    }

    private List<String> benchmarkMapFile(Path mapFile) throws IOException {
        MapExcelUtils mapExcelUtils = new MapExcelUtils();
        BasMapEditorServiceImpl editorService = new BasMapEditorServiceImpl();

        HashMap<Integer, List<List<HashMap<String, Object>>>> rawDataMap = mapExcelUtils.readExcel(mapFile.toString());
        List<Integer> levList = rawDataMap.keySet().stream().sorted().collect(Collectors.toList());

        List<String> reportLineList = new ArrayList<>();
        for (Integer lev : levList) {
            @SuppressWarnings("unchecked")
            List<List<HashMap<String, Object>>> storedData =
                    (List<List<HashMap<String, Object>>>) ReflectionTestUtils.invokeMethod(
                            editorService,
                            "convertRawExcelData",
                            rawDataMap.get(lev)
                    );
            List<List<NavigateNode>> stationMap = buildStationMap(storedData);
            Map<Integer, NavigateNode> stationNodeMap = collectStationNodeMap(stationMap);
            if (stationNodeMap.size() < 2) {
                continue;
            }

            BenchmarkSummary summary = benchmarkStationPairs(stationMap, stationNodeMap);
            reportLineList.add(summary.format(mapFile.getFileName().toString(), lev));
        }
        return reportLineList;
    }

    private BenchmarkSummary benchmarkStationPairs(List<List<NavigateNode>> stationMap,
                                                   Map<Integer, NavigateNode> stationNodeMap) {
        NavigateSolution navigateSolution = new NavigateSolution();
        List<Integer> stationIdList = new ArrayList<>(stationNodeMap.keySet());
        stationIdList.sort(Integer::compareTo);

        BenchmarkSummary summary = new BenchmarkSummary(stationIdList.size());
        warmup(navigateSolution, stationMap, stationNodeMap, stationIdList);

        for (int i = 0; i < stationIdList.size(); i++) {
            for (int j = i + 1; j < stationIdList.size(); j++) {
                Integer startStationId = stationIdList.get(i);
                Integer endStationId = stationIdList.get(j);

                NavigateNode startNode = stationNodeMap.get(startStationId);
                NavigateNode endNode = stationNodeMap.get(endStationId);
                if (startNode == null || endNode == null) {
                    continue;
                }

                resetMapSearchState(stationMap);
                long astarStartNs = System.nanoTime();
                NavigateNode astarResult = navigateSolution.astarSearchJava(stationMap, startNode, endNode);
                long astarElapsedNs = System.nanoTime() - astarStartNs;
                int astarPathLen = calcBacktrackPathLength(astarResult, stationMap);

                long allPathsStartNs = System.nanoTime();
                List<List<NavigateNode>> candidatePathList = navigateSolution.allSimplePaths(
                        stationMap,
                        startNode,
                        endNode,
                        CALC_MAX_DEPTH,
                        CALC_MAX_PATHS,
                        CALC_MAX_COST
                );
                long allPathsElapsedNs = System.nanoTime() - allPathsStartNs;

                summary.record(
                        startStationId,
                        endStationId,
                        astarElapsedNs,
                        allPathsElapsedNs,
                        astarPathLen,
                        candidatePathList == null ? 0 : candidatePathList.size()
                );
            }
        }
        return summary;
    }

    private void warmup(NavigateSolution navigateSolution,
                        List<List<NavigateNode>> stationMap,
                        Map<Integer, NavigateNode> stationNodeMap,
                        List<Integer> stationIdList) {
        int warmupPairCount = Math.min(5, Math.max(0, stationIdList.size() - 1));
        for (int i = 0; i < warmupPairCount; i++) {
            Integer startStationId = stationIdList.get(i);
            Integer endStationId = stationIdList.get(stationIdList.size() - 1 - i);
            NavigateNode startNode = stationNodeMap.get(startStationId);
            NavigateNode endNode = stationNodeMap.get(endStationId);
            if (startNode == null || endNode == null) {
                continue;
            }
            resetMapSearchState(stationMap);
            navigateSolution.astarSearchJava(stationMap, startNode, endNode);
            navigateSolution.allSimplePaths(
                    stationMap,
                    startNode,
                    endNode,
                    CALC_MAX_DEPTH,
                    CALC_MAX_PATHS,
                    CALC_MAX_COST
            );
        }
    }

    private Map<Integer, NavigateNode> collectStationNodeMap(List<List<NavigateNode>> stationMap) {
        NavigateSolution navigateSolution = new NavigateSolution();
        Set<Integer> stationIdSet = new LinkedHashSet<>();
        for (List<NavigateNode> row : stationMap) {
            for (NavigateNode node : row) {
                Integer stationId = extractStationId(node);
                if (stationId != null) {
                    stationIdSet.add(stationId);
                }
            }
        }

        Map<Integer, NavigateNode> stationNodeMap = new LinkedHashMap<>();
        for (Integer stationId : stationIdSet) {
            NavigateNode node = navigateSolution.findStationNavigateNode(stationMap, stationId);
            if (node != null) {
                stationNodeMap.put(stationId, node);
            }
        }
        return stationNodeMap;
    }

    private Integer extractStationId(NavigateNode node) {
        if (node == null || node.getNodeValue() == null || node.getNodeValue().trim().isEmpty()) {
            return null;
        }
        try {
            JSONObject valueObject = JSON.parseObject(node.getNodeValue());
            return valueObject == null ? null : valueObject.getInteger("stationId");
        } catch (Exception ignore) {
            return null;
        }
    }

    private void resetMapSearchState(List<List<NavigateNode>> stationMap) {
        for (List<NavigateNode> row : stationMap) {
            for (NavigateNode node : row) {
                node.setFather(null);
                node.setF(0);
                node.setG(0);
                node.setH(0);
                node.setIsInflectionPoint(false);
                node.setDirection(null);
            }
        }
    }

    private int calcBacktrackPathLength(NavigateNode endNode, List<List<NavigateNode>> stationMap) {
        if (endNode == null) {
            return 0;
        }
        int maxDepth = stationMap.size() * stationMap.get(0).size() + 5;
        int length = 0;
        Set<String> visited = new LinkedHashSet<>();
        NavigateNode current = endNode;
        while (current != null && visited.add(current.getX() + "_" + current.getY()) && length < maxDepth) {
            length++;
            current = current.getFather();
        }
        return length;
    }

    private List<List<NavigateNode>> buildStationMap(List<List<HashMap<String, Object>>> storedData) {
        List<List<NavigateNode>> stationMap = new ArrayList<>();
        for (int rowIndex = 0; rowIndex < storedData.size(); rowIndex++) {
            List<HashMap<String, Object>> row = storedData.get(rowIndex);
            List<NavigateNode> navigateNodeRow = new ArrayList<>();
            for (int colIndex = 0; colIndex < row.size(); colIndex++) {
                HashMap<String, Object> cell = row.get(colIndex);
                NavigateNode node = new NavigateNode(rowIndex, colIndex);
                String nodeType = cell == null ? null : stringValue(cell.get("type"));
                String mergeType = cell == null ? null : stringValue(cell.get("mergeType"));
                String nodeValue = cell == null ? null : stringValue(cell.get("value"));

                if ("devp".equals(nodeType) || ("merge".equals(nodeType) && "devp".equals(mergeType))) {
                    node.setValue(MapNodeType.NORMAL_PATH.id);
                    JSONObject valueObject = JSON.parseObject(nodeValue);
                    node.setDirectionList(valueObject == null
                            ? new ArrayList<>()
                            : valueObject.getJSONArray("direction").toJavaList(String.class));
                } else {
                    node.setValue(MapNodeType.DISABLE.id);
                }

                node.setNodeType(nodeType);
                node.setNodeValue(nodeValue);
                navigateNodeRow.add(node);
            }
            stationMap.add(navigateNodeRow);
        }
        return stationMap;
    }

    private String stringValue(Object value) {
        return value == null ? null : String.valueOf(value);
    }

    private static class BenchmarkSummary {
        private final int stationCount;
        private int pairCount;
        private long astarTotalNs;
        private long allPathsTotalNs;
        private final List<Long> astarElapsedNsList = new ArrayList<>();
        private final List<Long> allPathsElapsedNsList = new ArrayList<>();
        private int maxCandidateCount;
        private int maxAstarPathLen;
        private int worstAstarStartStationId;
        private int worstAstarEndStationId;
        private long worstAstarElapsedNs;
        private int worstAllPathsStartStationId;
        private int worstAllPathsEndStationId;
        private long worstAllPathsElapsedNs;
        private int worstAllPathsCandidateCount;

        private BenchmarkSummary(int stationCount) {
            this.stationCount = stationCount;
        }

        private void record(int startStationId,
                            int endStationId,
                            long astarElapsedNs,
                            long allPathsElapsedNs,
                            int astarPathLen,
                            int candidateCount) {
            pairCount++;
            astarTotalNs += astarElapsedNs;
            allPathsTotalNs += allPathsElapsedNs;
            astarElapsedNsList.add(astarElapsedNs);
            allPathsElapsedNsList.add(allPathsElapsedNs);
            maxCandidateCount = Math.max(maxCandidateCount, candidateCount);
            maxAstarPathLen = Math.max(maxAstarPathLen, astarPathLen);

            if (astarElapsedNs > worstAstarElapsedNs) {
                worstAstarElapsedNs = astarElapsedNs;
                worstAstarStartStationId = startStationId;
                worstAstarEndStationId = endStationId;
            }
            if (allPathsElapsedNs > worstAllPathsElapsedNs) {
                worstAllPathsElapsedNs = allPathsElapsedNs;
                worstAllPathsStartStationId = startStationId;
                worstAllPathsEndStationId = endStationId;
                worstAllPathsCandidateCount = candidateCount;
            }
        }

        private String format(String mapFileName, Integer lev) {
            return String.format(
                    Locale.ROOT,
                    "map=%s lev=%d stations=%d pairs=%d | A*=avg %.3fms p95 %.3fms max %.3fms pair=%d->%d | allSimplePaths=avg %.3fms p95 %.3fms max %.3fms pair=%d->%d candidates=%d | maxPathLen=%d maxCandidates=%d",
                    mapFileName,
                    lev,
                    stationCount,
                    pairCount,
                    toMillis(avg(astarTotalNs, pairCount)),
                    toMillis(percentile(astarElapsedNsList, 0.95d)),
                    toMillis(worstAstarElapsedNs),
                    worstAstarStartStationId,
                    worstAstarEndStationId,
                    toMillis(avg(allPathsTotalNs, pairCount)),
                    toMillis(percentile(allPathsElapsedNsList, 0.95d)),
                    toMillis(worstAllPathsElapsedNs),
                    worstAllPathsStartStationId,
                    worstAllPathsEndStationId,
                    worstAllPathsCandidateCount,
                    maxAstarPathLen,
                    maxCandidateCount
            );
        }

        private double avg(long totalNs, int count) {
            if (count <= 0) {
                return 0.0d;
            }
            return (double) totalNs / count;
        }

        private double percentile(List<Long> valueList, double percentile) {
            if (valueList == null || valueList.isEmpty()) {
                return 0.0d;
            }
            List<Long> sortedList = new ArrayList<>(valueList);
            sortedList.sort(Long::compareTo);
            int index = (int) Math.ceil(percentile * sortedList.size()) - 1;
            index = Math.max(0, Math.min(index, sortedList.size() - 1));
            return sortedList.get(index);
        }

        private double toMillis(double nanos) {
            return nanos / 1_000_000.0d;
        }
    }
}