在地图上递归地查找“岛屿”

Question

在地图上递归地查找“岛屿”

javarecursion

4

我有一个由六边形领域组成的地图。在这张地图上，每个领域（我们称之为Hex）都属于某个玩家，并且通过坐标进行定义。

我需要获得某个玩家Hex的List>。这意味着如果我输入一个该玩家拥有的所有Hex数组，我需要获取关于这些Hex哪些是分组在一起的信息。

让我举个例子：输入->绿色玩家拥有的所有Hex -> List 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++;
    }
}

任何帮助都将不胜感激 - 具有可工作递归函数的伪代码即可。谢谢！

- Dropout

3个回答

1

Here is my idea:

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循环：

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

实际的实现方式你肯定能够想出来的；）

- Blub

看起来不错，我会测试一下，稍等片刻。谢谢！ - Dropout

1

以下是一些简略的伪代码，但这就是我实现它的方式

function main()
  get allIslands for the player
  for each island
    create islandGroup
    process(island, islandGroup, allIslands)



function process(island, islandGroup, allIslands)
  add this island  
  remove this island from the parent list
  getNeighbourIslands(island, allIslands)
  for each neighbourIsland
    process(neighbourIsland, islandGroup, allIslands)

function getNeighbourIslands(island, allIslands)
  return allIslands.getNeighbours(island)

通过传递allIslands列表，您可以确保不会解析相同的岛屿，并且不会陷入无限循环。当递归结束时，您应该得到一堆IslandGroups。

编辑：getNeighbourIslands应返回岛屿的直接邻居列表，您不必担心它们的邻居，它们将稍后自行扫描。

- M21B8

这看起来是一个正确的答案，但我更喜欢Edgar的方法。无论如何+1 - 有人可能会喜欢你的答案..谢谢！ - Dropout

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Walser · Accepted Answer

从空的岛屿列表（六边形列表）开始
循环遍历属于玩家的有序六边形列表：
对于每个六边形，检查它是否属于现有岛屿（与任何一个岛屿的六边形相邻）
如果是：将其添加到该岛屿中
如果不是：创建一个新的岛屿，由该六边形组成。

（伪）代码（未经测试）：注意：为方便起见，使用辅助类Island（面向对象）。

class Island {

    private final List<Hex> hexes = new LinkedList<Hex>();

    public void add (Hex hex) {
        hexes.add(hex);
    }

    public List<Hex> getHexes () {
        return hexes;
    }

    public boolean isAdjacent (Hex hex) {
        for (Hex h : hexes) {
            if (h.isAdjacent(hex)) {
                return true;
            }
        }
        return false;
    }
}

private List<Island> createIslands (List<Hex> playersHexes,  Map map) {
    Collections.sort(playersHexes); // assuming it's comparable, otherwise use an iterator
    List<Island> islands=new LinkedList<Island>();
    for (Hex hex: playersHexes) {
        Island found=null;
        for (Island island: islands) {
            if (island.isAdjacent(hex)) {
                found=island;
                break;
            }
        }
        if (found==null) {
            found=new Island();
            islands.add(found);
        }
        found.add(hex);
    }
    return islands;
}