2

我有一个类似国际象棋的网格系统，我想构建一个算法来获取给定图块周围给定范围内的正方形，假设距离应该以十字形方式计算（对角线计数 2）。

因此，假设圆是中心点，这里是一个示例图像：

具有交叉距离的网格系统

我找到了这个解决方案（我正在使用 javascript）：

function findRange(tile, range){

    var tiles = [];
    for(row = 0; row < rows; row++){
      for(col = 0; col < cols; col++){
        if( (Math.abs(row - tile.y) + Math.abs(col - tile.x)) <= range )
          tiles.push([col,row]);
      }
    }
    return tiles;

  }

基本上，我遍历所有图块，然后将坐标的绝对值差之和与我的范围进行比较。我的意思是，它有效（令我惊讶）；但是，由于某种原因，它感觉不对，感觉有点花哨，而且循环每个图块也可能不是最佳选择：虽然我正在使用小网格，我不认为循环这些是一项昂贵的操作.

从好的方面来说，代码真的很小。

我问了我的一个从事游戏开发的朋友想出一个解决这个问题的方法，他提出了这个建议（在 C++ 中）：

Node *GetNodeAt(float x, float y)
{    
    float width = m_nodeSize * m_columns;
    float height = m_nodeSize * m_rows;

    if( x < 0.0f || y < 0.0f || 
        x >= width || y >= height)
        return nullptr;

    int r = y/m_nodeSize;
    int c = x/m_nodeSize;
    int target = (m_columns*r + c);

    return &m_nodesArray[target];
}

std::list<Node*> GetCrossArea(Node *origin, int range, bool addOriginNode)
{
    std::list<Node*> area;
    Node *n;
    for(int k = range; k >= -range; k--)    
    {
        n = GetNodeAt(origin->GetPosition().x + m_nodeSize * k, origin->GetPosition().y);

        if(k == range || k == -range)
            area.push_back(n);
        else
        {
            if(n != origin)
                area.push_back(n);
            else if(addOriginNode)
                area.push_back(n);

            Node *nVert;
            int verticalSteps = (range - abs(k));
            for(int q = verticalSteps; q > 0; q--)
            {
                nVert = GetNodeAt(n->GetPosition().x, n->GetPosition().y + m_nodeSize * verticalSteps);
                area.push_back(nVert);
                nVert = GetNodeAt(n->GetPosition().x, n->GetPosition().y + (1 - m_nodeSize) * verticalSteps);
                area.push_back(nVert);
                verticalSteps--;

            }
        }       
    }
    return area;
}

问题

有没有更好的算法来解决这个问题？如果不是，建议的解决方案中哪个更好？我的方法是否遗漏了一些完全明显的东西？

4

4 回答 4

1

只打你需要的瓷砖怎么样？

对于距离小于或等于range距离的所有图块：

function findRange(tile, range){

    var tiles = [];

    starty = Math.max(0,      (tile.y - range));
    endy = Math.min(rows - 1, (tile.y + range));

    for(row = starty ; row <= endy ; row++){

        xrange = range - Math.abs(row - tile.y);

        startx = Math.max(0,      (tile.x - xrange));
        endx = Math.min(cols - 1, (tile.x + xrange));

        for(col = startx ; col <= endx ; col++){
            tiles.push([col,row]);
         }
     }

     return tiles;

}

理由：

找到满足此条件的所有单元格的目标：

 (Math.abs(row - tile.y) + Math.abs(col - tile.x)) <= range

因为 的结果Math.abs(col - tile.x)永远不会是负数，我们知道我们只需要查看那些满足的行中的单元格

 Math.abs(row - tile.y) <= range

这相当于

 tile.y - range <= row <= tile.y + range

为了考虑网格的边缘，我们必须将这些范围限制在 0 并且rows - 1- 所以它变成

 Math.max(0, (tile.y - range)) <= row <= Math.min(rows - 1, (tile.y + range))

所以第一个 for 循环开始于Math.max(0, (tile.y - range))并结束于Math.min(rows - 1, (tile.y + range))

现在，一旦你选择了一行，我们考虑哪些列将满足我们的第一个条件：

 (Math.abs(row - tile.y) + Math.abs(col - tile.x)) <= range

这相当于

 Math.abs(col - tile.x) <= range - Math.abs(row - tile.y)

这进一步等同于

 tile.x - (range - Math.abs(row - tile.y))
      <= col <= 
 tile.x + (range - Math.abs(row - tile.y))

再一次，考虑到边缘，

 Math.min(0, (tile.x - (range - Math.abs(row - tile.y)))) 
      <= col <= 
 Math.max(cols - 1, (tile.x + (range - Math.abs(row - tile.y))))

为了让它更清楚一点，拉出公共(range - Math.abs(row - tile.y))位并调用它xrange来获取

 Math.min(0, (tile.x - xrange)) 
      <= col <= 
 Math.max(cols - 1, (tile.x + xrange))
于 2013-07-23T15:20:55.003 回答
1

这是答案的大纲

首先仔细查看图表中的模式。请注意，它关于通过 的垂直线和水平线是对称的(0,0)。（它也是关于通过同一点的对角线对称的，但我暂时忽略它）。当然，我(0,0)是在相对意义上使用的。

其次，仅考虑（相对）感兴趣中心的 NE 象限。要找到距离为 1 的单元格，依次将每个坐标加 1。距离原点 2 处的单元格是距离原点 1 处的单元格距离 1 处的单元格（从不减少坐标以避免倒退并实施一些规则以防止在 relative 处重复计算单元格(1,1)）。距离为 3 的单元格……现在你应该明白了。这有点递归。

一旦你计算出 NE 象限中感兴趣单元格的坐标，将它们反映在穿过（相对）的垂直线(0,0)和穿过同一单元格的水平线以及两条线的位置。

我忽略了关于对角线的对称性，因为将单元索引旋转大约 45° 比通过正交轴反射它们要复杂一些。

我会把它留给一个比我（或希望）更好的 Javascript 程序员来把它变成代码。

编辑

不失一般性，让感兴趣区域的原点位于像元处，而感兴趣区域(0,0)的半径为R。然后循环

do r = 0, R
    do s = 0, r
        pushTile([s,r-s])
    end do
end do

如果我的计算正确，应该推动序列

`(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3), ...`

这些是距0,1,2,3,...原点一定距离的单元格的坐标。

这不是我认为可能更早的递归算法，我现在不认为需要递归。

循环完成后，您将获得 NE 象限中所有单元格的坐标，包括其两个轴，即所有坐标均为非负数的单元格。首先围绕垂直轴反射，对于具有 +ve x 坐标的每个单元格，将单元格(-x,y)插入到列表中。然后围绕水平轴反映：对于每个具有 +ve y 坐标的单元格，将单元格添加(x,-y)到列表中。

如果感兴趣区域的原点不在，(0,0)则计算从中心到 的偏移量(0,0)，运行上述计算，然后在另一个方向上应用偏移量。

于 2013-07-23T15:34:43.907 回答
1

我参加聚会迟到了，但我只需要解决这个问题，所以我想我会发布这个解决方案，IMO 比其他人更干净。它使用“在一个象限中解决”的方法，但避免了处理双重访问/等。

//<visit the starting tile u,v here>
for(d=1; d <= max_dist; d++)
{ 
    for(i=0; i < d; i++)
    {
        j = d-i;
        //<visit tiles (u+i,v+j), (u+j,v-i), (u-i,v-j), (u-j,v+i) here>
    }
}
于 2020-02-21T21:45:44.527 回答
-1

为此，算法实际上并不是完全必要的。您只需要知道原点的坐标，然后从那里得到周围的正方形。顺便说一句，瓷砖的数组必须按行的顺序排列，然后是 cols 才能工作。

function getSurroundingTiles(tiles, originY, originX) {
    var newTiles = [];

    if (tiles[originY + 1][originX - 1]) {
        newTiles.push(tiles[originY + 1][originX - 1]);
    }

    if (tiles[originY + 1][originX]) {
        newTiles.push(tiles[originY + 1][originX]);
    }

    if (tiles[originY + 1][originX + 1]) {
        newTiles.push(tiles[originY + 1][originX + 1]);
    }

    if (tiles[originY][originX + 1]) {
        newTiles.push(tiles[originY][originX + 1]);
    }

    if (tiles[originY - 1][originX + 1]) {
        newTiles.push(tiles[originY - 1][originX + 1]);
    }

    if (tiles[originY - 1][originX]) {
        newTiles.push(tiles[originY - 1][originX]);
    }

    if (tiles[originY - 1][originX - 1]) {
        newTiles.push(tiles[originY - 1][originX - 1]);
    }

    if (tiles[originY][originX - 1]) {
        newTiles.push(tiles[originY][originX - 1]);
    }

    return newTiles;
}
于 2013-07-23T17:53:35.267 回答