Java如何实现递归拆分多线程同时终止原线程的并发寻路功能？

你现有代码无法正常拆分线程、终止执行的核心问题集中在状态共享、线程安全、参数传递三个方面，以下是具体修改方案： #

现有代码的致命问题 #

• 访问记录VISITED是实例私有变量，每个新创建的线程都有自己独立的访问集合，既无法避免多线程重复走相同路径，也无法全局感知终点是否被访问。
• 你直接修改共享的Grid对象的root属性，多线程并发修改会导致数据紊乱，每个线程的起始点应该作为私有变量存储，不要修改公共的Grid配置。
• 新创建的Multithreaded实例没有传入任何共享状态（访问集合、Grid对象、当前累计代价），新启动的线程内部modelThreaded为空，根本无法正常执行逻辑。
• 没有全局终止信号，某个线程找到终点后其他线程无法感知，会持续空跑。
• 入口方法runPathfinder同步调用executeThread，会卡住主线程，无法等待所有子线程执行完成再处理结果。

修正方案 #

1. 调整类结构拆分共享/私有变量 #

将全局共享的状态（访问记录、终止标记、Grid对象）和线程私有状态（当前起始点、当前累计代价）拆分，新线程创建时传入共享状态和自身的私有参数：

public class Multithreaded extends ParentClass implements Runnable {
    // 全局共享状态，所有线程共用
    private final Set<Tile> VISITED;
    private final Grid model;
    private final AtomicBoolean foundTarget;
    private final CountDownLatch latch;
    // 线程私有状态
    private final Tile currentStart;
    private final int currentCost;
    private final HashMap<Tile, Integer> globalTileData;

    // 入口构造方法，仅第一次初始化时调用
    public Multithreaded(Grid model) {
        super();
        this.VISITED = ConcurrentHashMap.newKeySet(); // 线程安全的Set
        this.model = model;
        this.foundTarget = new AtomicBoolean(false);
        this.globalTileData = new HashMap<>();
        this.latch = new CountDownLatch(1);
        this.currentStart = model.getRoot();
        this.currentCost = 1;
    }

    // 拆分新线程时调用的构造方法，传入共享状态和当前线程的私有参数
    public Multithreaded(Set<Tile> VISITED, Grid model, AtomicBoolean foundTarget, 
                        CountDownLatch latch, HashMap<Tile, Integer> globalTileData, 
                        Tile currentStart, int currentCost) {
        super();
        this.VISITED = VISITED;
        this.model = model;
        this.foundTarget = foundTarget;
        this.latch = latch;
        this.globalTileData = globalTileData;
        this.currentStart = currentStart;
        this.currentCost = currentCost;
    }

    @Override
    public void run() {
        executeThread();
    }

    @Override
    protected int runPathfinder(Grid model, List<Tile> path) {
        // 启动第一个线程
        Thread firstThread = new Thread(this);
        firstThread.start();
        try {
            latch.await(); // 等待所有线程执行完成（或找到目标后终止）
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
        int cost = globalTileData.get(model.getTarget()) - 1;
        this.statistics.setPathFound(true, cost);
        this.painter.drawPath(path, model);
        return cost;
    }

    private void executeThread() {
        Tile currentTile = this.currentStart;
        int iteration = 0;
        // 先判断全局是否已经找到目标，找到直接终止
        while (!foundTarget.get() && !VISITED.contains(model.getTarget())) {
            // 当前节点已经被其他线程访问过，直接终止
            if (VISITED.contains(currentTile)) {
                break;
            }
            VISITED.add(currentTile);
            synchronized (globalTileData) {
                globalTileData.put(currentTile, currentCost + iteration);
            }
            // 到达目标点，更新全局标记
            if (currentTile.equals(model.getTarget())) {
                foundTarget.set(true);
                latch.countDown();
                return;
            }
            List<Tile> posNeighbors = model.getTileNeighbors(currentTile);
            List<Tile> validNeighbors = getForward(posNeighbors);
            // 死路，直接终止当前线程
            if (validNeighbors.isEmpty()) {
                break;
            }
            // 只有一个邻居，当前线程继续走，不开新线程
            if (validNeighbors.size() == 1) {
                currentTile = validNeighbors.get(0);
                iteration++;
                continue;
            }
            // 多个邻居，拆分新线程，当前线程终止
            for (Tile neighbor : validNeighbors) {
                if (!VISITED.contains(neighbor)) {
                    // 给每个邻居新建线程，传入共享状态和新的起始点、代价
                    Multithreaded worker = new Multithreaded(VISITED, model, foundTarget, 
                            latch, globalTileData, neighbor, currentCost + iteration + 1);
                    new Thread(worker).start();
                }
            }
            break;
        }
    }

    private List<Tile> getForward(List<Tile> posNeighbors) {
        List<Tile> validNeighbors = new ArrayList<>();
        for (Tile posNeighbor : posNeighbors) {
            if (posNeighbor != null && !posNeighbor.isWall() && !VISITED.contains(posNeighbor)) {
                validNeighbors.add(posNeighbor);
            }
        }
        return validNeighbors;
    }
}

2. 关键逻辑说明 #

• 用ConcurrentHashMap.newKeySet()实现线程安全的全局访问记录，避免重复路径。
• 用AtomicBoolean作为全局终止信号，任意线程找到目标后所有线程都会直接终止。
• 用CountDownLatch让主线程等待寻路完成，再处理结果。
• 仅当遇到>=2个有效邻居时才拆分新线程，单个邻居时当前线程继续执行，避免不必要的线程开销。
• 新线程创建时传入所有共享状态和自身的起始参数，不会修改公共Grid对象的属性，避免线程安全问题。

疑问解答 #

• executeThread()放在run()方法中的写法是正确的，之前不生效是因为新创建的Multithreaded实例没有拿到有效参数。
• 不能直接调用runnable.run()，该方法是同步在当前线程执行，不会开启新线程，必须调用thread.start()才会在独立线程中执行逻辑。

内容的提问来源于stack exchange，提问作者Struggling Student