查找在HashMap中保持的相邻对象之间的距离(Finding Distance Between Adjacent Objects Held in a HashMap)

我很抱歉，如果标题有点尴尬，我不太确定如何说出我的问题。

所以 - 我正在努力建立一个桌面游戏，而且我一直试图以有效的方式检查棋盘上的区域之间的距离。

我有一个“Territory”类，它为游戏板上的每个tile创建一个Territory对象。每个Territory对象都有一个“String name”和一个“List <String> adjacentTerritories”，其中包含与其相邻的所有地区的名称。

我还有一个“HashMap <String，Territory> territoriesMap”，其中包含了棋盘上的所有区域。

我提出工作的方式，但它是硬编码远离初始检查三个地区，它不是特别优雅。我想知道是否有办法更有效地完成这项任务，甚至可以让我对任何距离执行此检查？如果我在提出这个问题时犯了错误或错过了一些明显的答案，请原谅我，我大多是自学成才。

下面的这个函数接收我所有地区的HashMap以及它想要找到（源和目标）之间距离的两个地区。

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'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.

最满意答案

我们可以使用广度优先搜索来计算这些距离。这是一个示例实现：

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 }

请注意，通过较小的修改（实际上是简化），我们可以找到从源到所有可到达目标的距离，如下所示：

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; }

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; }

更多推荐