优化更新

jianghaiyue

2025-11-05 642f20dd1b068e23146b8ec96c5eac8b63c96b87

 algo-zkd/src/main/java/com/algo/service/AStarPathPlanner.java

@@ -367,8 +367,9 @@
            }
        }

        // 减少等待选项
        if (Math.random() < 0.2) {
        // 必要时（有冲突）生成等待节点；当前节点的所有邻居在短期内都被阻挡则等待
        boolean allNeighborsBlocked = checkIfAllNeighborsBlocked(current, constraintChecker, physicalConfig);
        if (allNeighborsBlocked) {
            long waitTime = timeResolution;
            long waitUntilTime = current.timePoint + waitTime;
            String waitKey = createSpaceTimeKey(current.code, waitUntilTime);
@@ -392,6 +393,52 @@
                }
            }
        }
    }

    /**
     * 检查当前节点的邻居是否在短期内都被阻挡
     */
    private boolean checkIfAllNeighborsBlocked(SpaceTimeAStarNode current,
                                               EnhancedConstraintChecker constraintChecker,
                                               CTUPhysicalConfig physicalConfig) {
        // 获取当前节点的所有空间邻居
        List<Map<String, String>> neighbors = getNeighbors(current.code);
        
        if (neighbors.isEmpty()) {
            return true;
        }
        
        // 检查未来几个时间片内的占用情况
        int checkTimeSteps = 3;
        boolean allBlocked = true;
        
        for (int step = 1; step <= checkTimeSteps; step++) {
            long checkTime = current.timePoint + (step * timeResolution);
            
            // 检查是否有至少一个邻居在当前时间片可用
            for (Map<String, String> neighbor : neighbors) {
                String neighborCode = neighbor.get("code");
                long arrivalTime = checkTime;
                
                // 对齐到时间分辨率
                arrivalTime = alignToTimeResolution(arrivalTime);
                
                // 检查这个邻居在当前时间片是否可用
                if (constraintChecker.isValidMove(current.code, neighborCode, 
                        current.timePoint, arrivalTime)) {
                    // 至少有一个邻居可用，不需要等待
                    allBlocked = false;
                    break;
                }
            }
            
            // 如果找到可用邻居，不需要等待
            if (!allBlocked) {
                break;
            }
        }
        
        return allBlocked;
    }

    /**
@@ -566,17 +613,85 @@
            codeList.add(pathCode);
        }

        codeList = optimizePathByRemovingBacktrack(codeList);

        PlannedPath plannedPath = new PlannedPath("", "", codeList);
        
        // 使用统一的时间计算器计算精确时间
        long startTime = pathNodes.get(0).timePoint;
        CTUPhysicalConfig defaultConfig = createDefaultPhysicalConfig();
        timeCalculator.calculatePathTiming(plannedPath, startTime, defaultConfig, 0.0);
        
        return plannedPath;
    }

    /**
     * 优化路径：去除空间上的重复点（避免来回走）
     * 检测并移除 A->B->A 模式的来回走，避免不必要的绕行
     *
     * @param codeList 原始路径代码列表
     * @return 优化后的路径代码列表
     */
    private List<PathCode> optimizePathByRemovingBacktrack(List<PathCode> codeList) {
        if (codeList == null || codeList.size() <= 2) {
            return codeList;
        }

        List<PathCode> optimized = new ArrayList<>();
        int i = 0;
        
        while (i < codeList.size()) {
            PathCode current = codeList.get(i);
            
            // 检查是否是来回走模式：A->B->A（连续三个点，第一个和第三个相同）
            // 如果出现来回走，跳过B和第二个A，直接到下一个不同的点
            if (i < codeList.size() - 2) {
                PathCode next = codeList.get(i + 1);
                PathCode nextNext = codeList.get(i + 2);
                
                // 检测来回走：当前位置 == 下下个位置，且中间位置不同
                if (current.getCode().equals(nextNext.getCode()) && 
                    !current.getCode().equals(next.getCode())) {
                    // 来回走：跳过B和第二个A，直接处理下一个不同的点
                    // 找到下一个与当前点不同的位置
                    int j = i + 2;
                    while (j < codeList.size() && codeList.get(j).getCode().equals(current.getCode())) {
                        j++;
                    }
                    // 如果找到了不同的点，或者到达末尾，跳过来回走的部分
                    if (j < codeList.size()) {
                        i = j; // 跳到下一个不同的点
                        continue;
                    } else {
                        // 如果后面都是相同点，保留当前点（可能是目标点）
                        break;
                    }
                }
            }
            
            // 正常添加当前点
            optimized.add(current);
            i++;
        }
        
        // 确保目标点被包含
        if (!optimized.isEmpty() && !codeList.isEmpty()) {
            PathCode lastOriginal = codeList.get(codeList.size() - 1);
            PathCode lastOptimized = optimized.get(optimized.size() - 1);
            if (!lastOriginal.getCode().equals(lastOptimized.getCode())) {
                optimized.add(lastOriginal);
            }
        }
        
        // 重新计算方向（因为优化后跳过了中间点，方向需要更新）
        for (int k = 0; k < optimized.size(); k++) {
            PathCode code = optimized.get(k);
            if (k < optimized.size() - 1) {
                PathCode nextCode = optimized.get(k + 1);
                String direction = calculateDirection(code.getCode(), nextCode.getCode());
                code.setDirection(direction);
            }
        }
        
        return optimized;
    }

    /**
     * 创建时空键
     *
     * @param code      位置代码