基于瓦片的RTS游戏：构建ResourceField资源分组数据结构的实现问题

方案一：带参数的递归遍历 #

你不需要每次递归都新建列表，把存储连通块的临时列表作为参数传入递归方法即可，同时给每个节点添加「已处理」标记避免重复遍历。具体步骤：

• 遍历resourceList，跳过已标记为处理过的节点
• 遇到未处理节点时，创建新的临时列表，将当前节点加入并标记为已处理
• 调用递归方法，传入当前节点、临时列表和已处理标记集合
• 递归方法内，遍历当前节点的所有相邻资源节点：
  • 若节点未处理，就加入临时列表、标记为已处理，再递归调用自身处理该相邻节点
• 递归结束后，用临时列表实例化ResourceField

伪代码示例：

Set<Node> processedNodes = new HashSet<>();
List<ResourceField> resourceFields = new ArrayList<>();

public void groupResources(List<Node> resourceList) {
    for (Node node : resourceList) {
        if (!processedNodes.contains(node)) {
            List<Node> connectedNodes = new ArrayList<>();
            collectConnectedNodes(node, connectedNodes);
            resourceFields.add(new ResourceField(connectedNodes));
        }
    }
}

private void collectConnectedNodes(Node current, List<Node> connectedNodes) {
    processedNodes.add(current);
    connectedNodes.add(current);
    // 获取当前节点的相邻资源节点（四/八方向按需实现，需判断地图边界）
    List<Node> neighbors = getAdjacentResourceNodes(current);
    for (Node neighbor : neighbors) {
        if (!processedNodes.contains(neighbor)) {
            collectConnectedNodes(neighbor, connectedNodes);
        }
    }
}

方案二：非递归DFS/BFS（更推荐） #

递归处理大规模连通块时可能触发栈溢出，用非递归的深度优先搜索（DFS）或广度优先搜索（BFS）更稳妥，逻辑和递归一致，仅用栈/队列替代递归栈：

BFS队列实现示例 #

public void groupResources(List<Node> resourceList) {
    Set<Node> processedNodes = new HashSet<>();
    List<ResourceField> resourceFields = new ArrayList<>();
    
    for (Node node : resourceList) {
        if (!processedNodes.contains(node)) {
            Queue<Node> queue = new LinkedList<>();
            List<Node> connectedNodes = new ArrayList<>();
            
            queue.add(node);
            processedNodes.add(node);
            
            while (!queue.isEmpty()) {
                Node current = queue.poll();
                connectedNodes.add(current);
                
                List<Node> neighbors = getAdjacentResourceNodes(current);
                for (Node neighbor : neighbors) {
                    if (!processedNodes.contains(neighbor)) {
                        processedNodes.add(neighbor);
                        queue.add(neighbor);
                    }
                }
            }
            
            resourceFields.add(new ResourceField(connectedNodes));
        }
    }
}

关键注意事项 #

• 相邻规则：明确是四方向（上下左右）还是八方向（含对角线），实现getAdjacentResourceNodes时要判断瓦片坐标是否在100×100地图范围内，避免越界
• 效率优化：无需从resourceList移除节点，靠processedNodes标记跳过即可，移除操作会增加时间复杂度
• 节点标识：确保Node类正确重写equals和hashCode，或用坐标字符串（如x + "," + y）作为processedNodes的存储键，避免重复标记

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