Search code examples
c#algorithmgrid-layoutarray-algorithms

Enumerate neighboring cells in a 'rhombus'-shape on a grid


I'm currently working on a project which features a grid with cells. Every cell has the ability to query its neighboring cells with a function that accepts a relative 'x' and 'y'-coordinate. This works fine, but now I want to query a set of neighboring cells that, when combined, form a rhombus, like this:

* * * * * * * * *
* * * * 0 * * * *
* * * 0 0 0 * * *
* * 0 0 0 0 0 * *
* 0 0 0 C 0 0 0 *
* * 0 0 0 0 0 * *
* * * 0 0 0 * * *
* * * * 0 * * * *
* * * * * * * * *

'C' is the cell on which the query is supposedly called...

Now, the best thing that I have come up with so far is this imperative nightmare:

private IEnumerable<Cell> GetRhombusNeighours()
{
    yield return _getRelativeCell(-3, 0);

    yield return _getRelativeCell(-2, 1);
    yield return _getRelativeCell(-2, 0);
    yield return _getRelativeCell(-2, -1);

    yield return _getRelativeCell(-1, -2);
    yield return _getRelativeCell(-1, -1);
    yield return _getRelativeCell(-1, 0);
    yield return _getRelativeCell(-1, 1);
    yield return _getRelativeCell(-1, 2);

    yield return _getRelativeCell(0, -3);
    yield return _getRelativeCell(0, -2);
    yield return _getRelativeCell(0, -1);
    yield return _getRelativeCell(0, 0);
    yield return _getRelativeCell(0, 1);
    yield return _getRelativeCell(0, 2);
    yield return _getRelativeCell(0, 3);

    yield return _getRelativeCell(1, -2);
    yield return _getRelativeCell(1, -1);
    yield return _getRelativeCell(1, 0);
    yield return _getRelativeCell(1, 1);
    yield return _getRelativeCell(1, 2);

    yield return _getRelativeCell(2, 1);
    yield return _getRelativeCell(2, 0);
    yield return _getRelativeCell(2, -1);

    yield return _getRelativeCell(3, 0);
}

I could make this method a bit more dynamic with some for loops, likely at the cost of decreasing the readability. But, isn't there some kind of algorithm available which exactly solves this problem? I'm working in C#, but I'm open to language-independent advice!

There's no need for edge/border detection; that's covered already. I'm purely interested in collecting the relative 'X'- and 'Y'-coordinates!


Solution

  • You could iterate over the entire X/Y square and decide if they are inside the rhombus for each X/Y pair:

    for(int y = -3; y <= 3; y++)
    {
        for(int x = -3; x <= 3; x++)
        {
            if(Math.Abs(x) + Math.Abs(y) <= 3)
            {
                yield return _getRelativeCell(x, y);
            }
         }
     }
    

    This is not tested, but you should get the idea.

    To make it more self-documenting you can also move the if() into a method, say:

    bool IsInRhombus(int x, int y)
    {
        return Math.Abs(x) + Math.Abs(y) <= 3;
    }