多线程Bot路径规划中避免单元格重叠的实现方案咨询

这个场景我之前做类似网格寻路项目时碰到过，核心问题是竞态条件：多个Bot线程在路径搜索、状态更新的过程中没有同步，导致两个Bot同时“看到”同一个单元格可用，进而同时移动过去造成重叠。下面是具体的修复方案，从核心线程安全到UI优化一步步来：

1. 给cellStates的读写加互斥锁 #

每个Bot维护的cellStates是共享状态（通过观察者模式同步），必须确保路径搜索、状态修改的原子性——简单说就是，一个Bot在查路径、改状态的时候，其他Bot不能同时修改或读取这个状态。

修改Bot线程的run方法 #

在Bot类里加一个锁对象，然后把路径搜索、状态预占的逻辑放在锁内：

// 在Bot类中添加锁对象（每个Bot实例一个，保护自己的cellStates）
private final Object stateLock = new Object();

@Override 
public void run() { 
    // 初始位置通知
    notifyObserver(ChangeStateEvent.builder()
            .identifier(npc.getIdentifier())
            .newState(NPCWalkState.builder()
                    .row(startVertex.getRow())
                    .column(startVertex.getColumn())
                    .build())
            .build());

    while (!startVertex.equals(goalVertex)) { 
        ThreadUtils.delaySeconds(speed);
        Vertex nextStep = null;

        // 加锁：确保路径搜索、状态修改是原子操作
        synchronized (stateLock) {
            // 基于最新状态找路径
            nextStep = pathSearch.find(startVertex, goalVertex, cellStates).get(1);
            
            // 检查目标单元格是否已经被抢占（防止其他Bot先一步修改了状态）
            if (cellStates[nextStep.getRow()][nextStep.getColumn()]) {
                // 如果已被阻塞，跳过本次循环，重新找路径
                continue;
            }
            
            // 先预占目标单元格，再释放原位置
            cellStates[nextStep.getRow()][nextStep.getColumn()] = true;
            cellStates[startVertex.getRow()][startVertex.getColumn()] = false;
        }

        // 发送状态变更通知给其他Bot和表格
        ChangeStateEvent event = ChangeStateEvent.builder()
                .identifier(npc.getIdentifier())
                .newState(NPCWalkState.builder()
                        .row(nextStep.getRow())
                        .column(nextStep.getColumn())
                        .build())
                .previousState(NPCWalkState.builder()
                        .row(startVertex.getRow())
                        .column(startVertex.getColumn())
                        .build())
                .build();
        notifyObserver(event);

        startVertex = new Vertex(nextStep); 
    } 
}

修改Bot的receiveNotification方法 #

同样在锁内更新cellStates，避免在路径搜索过程中被打断：

@Override 
public void receiveNotification(ChangeStateEvent data) { 
    synchronized (stateLock) {
        if (null != data.getPreviousState()) { 
            int free_row = data.getPreviousState().getRow(); 
            int free_column = data.getPreviousState().getColumn(); 
            int blocked_row = data.getNewState().getRow(); 
            int blocked_column = data.getNewState().getColumn(); 
            cellStates[free_row][free_column] = false; 
            cellStates[blocked_row][blocked_column] = true; 
        } else { 
            int blocked_row = data.getNewState().getRow(); 
            int blocked_column = data.getNewState().getColumn(); 
            cellStates[blocked_row][blocked_column] = true; 
        }
    }
}

2. 优化表格UI的线程安全 #

表格的单元格内容是List<T>，多个线程同时修改同一个List会出现并发问题，建议把单元格的List换成线程安全的实现：

// 初始化表格单元格时，用CopyOnWriteArrayList替代普通List
List<T> cellContent = new CopyOnWriteArrayList<>();
table.setValueAt(cellContent, row, column);

这样在receiveNotification里添加/移除元素时，就不会出现ConcurrentModificationException，也能保证UI显示的一致性。

3. 为什么原来的代码会出问题？ #

原来的逻辑中，路径搜索和状态更新是分离的：Bot先找路径，再发送通知修改cellStates。这中间的时间窗口里，其他Bot可能已经基于旧的cellStates找到了同一个目标单元格，导致两个Bot同时移动过去。加锁后，路径搜索、状态预占、状态更新变成了原子操作，彻底堵上了这个时间窗口。

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