#算法优化

Junjie

11 小时以前 71a5ae03389119dc6975d7cfb87e63601f3c5305

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