java - 递归地在 map 上查找 "islands"区域

Question

我有一张由六边形字段组成的 map 。在这张 map 上，每个字段(我们称之为十六进制)都属于某个玩家并由坐标定义。

我需要一个 List<List<Hex>>某个玩家的魔咒。这意味着，如果我输入玩家拥有的所有六角形数组，我需要获取有关哪些六角形组合在一起的信息。

让我举例说明:

输入 -> 绿色玩家的所有六边形 -> List<Hex> playersHexes是:

{0.0; 0.1; 0.2; 1.0; 1.3; 2.1; 2.3}

输出应该是 -> 绿色玩家的“岛屿”:

{0.0; 0.1; 0.2; 1.0} , {1.3; 2.3} , {2.1}

我怎样才能递归地实现这个？我能够毫无问题地找到一些 Hex 的邻居，但这只是针对某个 hex 的一次迭代。

//playersHexes are all the hexes that a player owns
//map is the current map used - contains information about certain hexes
//map is not a HashMap! It's my custom object..
private void findIslands(List<Hex> playersHexes, Map map)
{
    List<Hex> island = new ArrayList<Hex>();
    int curPos = 0;
    for(Hex hex : playersHexes){
        island.add(hex);
        //remove the hex if it's allready gone through it?
        playersHexes.remove(curPos);
        List<Hex> neighbours = map.getNeighboursOf(hex);
        for(Hex neighbour : neighbours)
        {

        }
        //hexList is the output place - the target is to fill hexList with
        //islands(List<Hex>) of hexes..
        this.hexList.add(curPos, island);
        curPos++;
    }
}

任何帮助表示赞赏 - 具有工作递归函数的伪代码就足够了。谢谢!

Answer 1

这是我的想法:

private void findIslands(List<Hex> playersHexes, Hex currentHex, Map map, List<Hex> island)
{
  List<Hex> neighbours = map.getNeighboursOf(currentHex);

  // for each neighbour we check if it belongs to player and if it is not already part of this island
  for(Hex neighbour : neighbours) {
     if (!island.contains(neighbour) && playersHexes.contains(neighbour))  {
        island.add(neighbour);

        // now find all connecting neighbours of the current neighbour
        findIslands(playersHexes, neighbour, map, island);
     }
  }
  // now we have in island all connecting Hexes of current hex
}

所以这将从一个特定的十六进制开始找到所有连接的六边形。您需要做的就是像这样创建一段时间:

while (Player has hexes that are not islands yet) {
   // call findIsland() on one of those hexes and add the resulting list to your List<List<Hex>>
}

我敢肯定你会弄清楚的实际实现 ;)