基于HashMap存储的相邻领地间距离计算方案咨询

Hey there! Let's work through this distance calculation problem for your board game—this is a super common challenge when dealing with networked game spaces, so I’ve got some practical, efficient approaches tailored to your setup.

The Go-To: Breadth-First Search (BFS) #

Since each adjacent territory has a distance of 1 (unweighted graph), BFS is perfect here. It naturally finds the shortest path (which translates directly to your distance metric) efficiently, with a time complexity of O(N + E) where N is the number of territories and E is the number of adjacent connections.

Here’s a Java implementation that fits your Territory class and HashMap<String, Territory> setup:

import java.util.*;

public class BoardGameDistanceCalculator {
    public int calculateShortestDistance(String startName, String targetName, HashMap<String, Territory> territoryMap) {
        // Handle edge cases first
        if (!territoryMap.containsKey(startName) || !territoryMap.containsKey(targetName)) {
            throw new IllegalArgumentException("One or both territory names are invalid");
        }
        if (startName.equals(targetName)) {
            return 0; // Distance to self is 0
        }

        // BFS essentials: queue for traversal, visited to avoid cycles, distance tracker
        Queue<String> traversalQueue = new LinkedList<>();
        Set<String> visitedTerritories = new HashSet<>();
        Map<String, Integer> distanceMap = new HashMap<>();

        // Initialize with starting territory
        traversalQueue.add(startName);
        visitedTerritories.add(startName);
        distanceMap.put(startName, 0);

        while (!traversalQueue.isEmpty()) {
            String currentTerritory = traversalQueue.poll();
            int currentDistance = distanceMap.get(currentTerritory);

            // Check all adjacent territories
            for (String neighborName : territoryMap.get(currentTerritory).adjacentTerritories) {
                // Found our target: return immediately (BFS guarantees shortest path)
                if (neighborName.equals(targetName)) {
                    return currentDistance + 1;
                }
                // If we haven't visited this neighbor yet, add it to the queue
                if (!visitedTerritories.contains(neighborName)) {
                    visitedTerritories.add(neighborName);
                    distanceMap.put(neighborName, currentDistance + 1);
                    traversalQueue.add(neighborName);
                }
            }
        }

        // If we exit the loop without finding the target, it's unreachable
        return -1;
    }
}

Optimize with Caching #

If you’re going to query the same territory pairs multiple times (which is almost guaranteed in a board game), adding a cache will save you from redundant BFS runs. We can store computed distances in a nested map:

private Map<String, Map<String, Integer>> distanceCache = new HashMap<>();

public int getCachedDistance(String startName, String targetName, HashMap<String, Territory> territoryMap) {
    // Check if we already have this distance calculated
    if (distanceCache.containsKey(startName) && distanceCache.get(startName).containsKey(targetName)) {
        return distanceCache.get(startName).get(targetName);
    }

    // Calculate the distance if not cached
    int distance = calculateShortestDistance(startName, targetName, territoryMap);

    // Update the cache (store both directions since distance is symmetric)
    distanceCache.computeIfAbsent(startName, k -> new HashMap<>()).put(targetName, distance);
    if (distance != -1) {
        distanceCache.computeIfAbsent(targetName, k -> new HashMap<>()).put(startName, distance);
    }

    return distance;
}

Precompute All Distances (For Static Boards) #

If your board’s territory adjacency never changes during gameplay (which is standard for most board games), precomputing all pairwise distances during game initialization is the most efficient option. Queries become O(1) lookups afterward.

Here’s how to implement that:

public Map<String, Map<String, Integer>> precomputeAllTerritoryDistances(HashMap<String, Territory> territoryMap) {
    Map<String, Map<String, Integer>> allDistances = new HashMap<>();

    for (String startTerritory : territoryMap.keySet()) {
        Map<String, Integer> distancesFromStart = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.add(startTerritory);
        visited.add(startTerritory);
        distancesFromStart.put(startTerritory, 0);

        while (!queue.isEmpty()) {
            String current = queue.poll();
            int currentDist = distancesFromStart.get(current);

            for (String neighbor : territoryMap.get(current).adjacentTerritories) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    distancesFromStart.put(neighbor, currentDist + 1);
                    queue.add(neighbor);
                }
            }
        }

        allDistances.put(startTerritory, distancesFromStart);
    }

    return allDistances;
}

Which Approach Should You Choose? #

• Use BFS alone if your board’s adjacency can change dynamically (e.g., territories get blocked/unlocked during gameplay).
• Add caching if you have frequent repeat queries but still need dynamic adjacency support.
• Precompute all distances if your board is static—this gives you the fastest possible query times once the game is initialized.

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