java - 搜索网格中每个图 block 的相邻图 block 的有效方法？

Question

我有这个 A* 搜索算法，生成一个图 block 到另一个图 block 的路径。该算法要求每个图 block 都有一个其邻居的列表，目前我用于搜索每个图 block 的所有相邻图 block 的代码如下所示:

/* PathTile is simply a class that holds an x,y coordinate, an unique ID and 
   an arraylist of neighbouring tiles. A method called intersect() allows me 
   to check if the tile's edge is touching other tiles. */

private void generatePathTileNeighbors()
{
    for(int i = 0; i < pathTiles.size(); i++)
    {
        PathTile thisTile = pathTiles.get(i);

        for(int j = 0; j < pathTiles.size(); j++)
        {
            PathTile otherTile = pathTiles.get(j);
            if(!thisTile.uniqueID.equals(otherTile.uniqueID)){
                if(thisTile.intersect(otherTile)){
                    thisTile.addNeighbor(otherTile);
                    System.out.println(thisTile.uniqueID);
                }
            }
        }
    }
}

我很确定这绝对是最糟糕的方法。对于包含数千个图 block 的网格，加载每个图 block 的所有相邻图 block 需要几分钟的时间。什么是更有效的方法来做到这一点？谢谢!

] 1 ) - 我的网格是什么样的

Answer 1

为什么不只使用二维数组和索引作为查找邻居的点。 例如，tiles[0][0] 将有邻居tiles[1][0]、tiles[0][1]，甚至如果您愿意的话，tiles[1][1]。

此外，最好在图 block 初始化期间添加neighbour。因此你会得到这样的东西

Tile tiles = new Tile[n][m];
for(int i=0; i<n; i++){
   for(int j=0; j<m ; j++){
     Tile tile  = new Tile();
     if(i-1 >= 0)
       tile.addNeighbour(tiles[i-1][j]);
     if(i+1 < n)
       tile.addNeighbour(tiles[i+1][j]);
     if(j-1 >= 0)
       tile.addNeighbour(tiles[i][j-1]);
     if(j+1 < m)
       tile.addNeighbour(tiles[i][j+1]);
     tiles[i][j] = tile;
   }
}