Finding Distance Between Adjacent Objects Held in a HashMap

Question

I'm sorry if the title is a bit awkward, I wasn't quite sure how to phrase my problem.

So - I'm trying to build a boardgame, and I'm stuck trying to make an efficient way of checking distances between territories on the board.

I have a "Territory" class, which makes a Territory object for each tile on the gameboard. Each Territory Object has a "String name" and a "List< String> adjacentTerritories" containing the names of all territories adjacent to it.

I also have a "HashMap< String, Territory> territoriesMap", containing all of the territories on the board.

The way I've come up with works, but it's hardcoded for checking up to three territories away from the initial and it's not particularly elegant. I was wondering if there was a way to do this task more efficiently, perhaps even a way that allows me to perform this check for any distance? Please forgive me if I make a mistake in asking this question or miss some obvious answer, I'm mostly self-taught.

This function below takes in my HashMap of all territories as well as the two territories it wants to find the distance between (source and target).

public void checkDistance(String source, String target, HashMap<String, Territories> territoriesMap) {
    int targetDistance = 0;
    List<String> sourceAdj = territoriesMap.get(source).getAdjacentTerritory();
    if (sourceAdj.contains(target)) { targetDistance = 1; }
    else {
        for (String adjacent1 : sourceAdj) {
            List<String> nextAdj = territoriesMap.get(adjacent1).getAdjacentTerritory();
            if (nextAdj.contains(target)) { targetDistance = 2; }
            else {
                for (String adjacent2 : nextAdj) {
                    List<String> lastAdj = territoriesMap.get(adjacent2).getAdjacentTerritory();
                    if (lastAdj.contains(target)) { targetDistance = 3; }
                }
            }
        }
    }
    System.out.println(targetDistance);

I feel like I'm...close, but I'm having trouble figuring out how to streamline this. Any help at all would be appreciated - even pointing me towards reading material would be a huge help.

Answer 1

We can use Breadth-First Search to compute these distances. Here's an example implementation:

public int computeDistance(String source, String target, Map<String, Territory> territoriesMap) {
    Queue<String> q = new ArrayDeque<>();
    Map<String, Integer> dist = new HashMap<>();
    q.add(source);
    dist.put(source, 0);
    while (!q.isEmpty()) {
        Territory cur = territoriesMap.get(q.poll());
        int curDist = dist.get(cur.getName());
        for (String neighbor : cur.getAdjacentTerritories()) {
            if (neighbor.equals(target))
                return curDist + 1;
            if (!dist.containsKey(neighbor)) {
                dist.put(neighbor, curDist + 1);
                q.add(neighbor);
            }
        }
    }
    return -1; // not connected by a path
}

Note that with small modifications (actually simplifications) we can find the distance from a source to all reachable targets as follows:

public Map<String, Integer> computeAllDistances(String source, Map<String, Territory> territoriesMap) {
    Queue<String> q = new ArrayDeque<>();
    Map<String, Integer> dist = new HashMap<>();
    q.add(source);
    dist.put(source, 0);
    while (!q.isEmpty()) {
        Territory cur = territoriesMap.get(q.poll());
        int curDist = dist.get(cur.getName());
        for (String neighbor : cur.getAdjacentTerritories()) {
            if (!dist.containsKey(neighbor)) {
                dist.put(neighbor, curDist + 1);
                q.add(neighbor);
            }
        }
    }
    return dist;
}