在类网格系统中获得最接近的平方

Question

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

因此，鉴于圆是中心点，下面是示例图像：

<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLnN0YWNrLmltZ3VyLmNvbS9WbTRiaS5wbmcifQ==” alt =“具有十字形距离的网格系统”>

我已经找到了此解决方案（我正在使用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;
}

问题
是否有更知名的算法可以解决此问题？如果不是，哪种建议的解决方案更好？我的方法中是否缺少一些显而易见的东西？

我有一个类似国际象棋的网格系统，我想建立一种算法来获得给定图块周围给定范围内的正方形，假定距离应以类似十字的方式计算（...

Answer 1

这里是答案的提纲

[首先，认真研究一下图中的模式。请注意，它关于通过(0,0)的垂直和水平线是对称的。 （关于同一点的对角线也是对称的，但我暂时将其忽略）。当然，我是相对来说使用(0,0)。

Answer 2

只打所需的砖怎么样？

Answer 3

我来晚了，但是我只需要解决这个问题，所以我认为我应该发布这个解决方案，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>
    }
}

Answer 4

为此，实际上并不完全需要一种算法。您只需要知道原点的坐标，然后从那里得到正方形即可。顺便说一句，图块的数组必须按行的顺序排列，然后按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;
}