Unity3D Hex Grid neighbor search with radius

Question

I am trying to develop a small Game with a Hex Grid. I need to find the Neighbors of one Hex Tile in a specific radius.

Here is a screenshot of my Problem: Screenshot

I followed this awesome tutorial along and implemented some of the systems presented here: https://www.redblobgames.com/grids/hexagons/

public GameObject[] GetNeighbarsInRange(Vector2 pos, int range) {

    List<GameObject> tiles = new List<GameObject>();


    int min = -range, max = range;

    for (int x = min; x <= max; x++) {

        for(int y = min; y <= max; y++) {

            for(int z = min; z <= max; z++) {

                if (x + y + z == 0) {

                    Vector2 newPos = getVector2Coord(new Vector3(x, y, z)), newTilePos = new Vector2(pos.x + newPos.x, pos.y + newPos.y);
                    tiles.Add(getTile(newTilePos));

                }

            }

        }

    }

    return tiles.ToArray();

}

public Vector2 getVector2Coord(Vector3 pos) {

    int x = (int) pos.x, z = (int) pos.z;
    int newX = x, newZ = z + (x - (x&1)) / 2;
    return new Vector2(newX, newZ);

}

public Vector3 getVector3Coord(Vector2 pos) {

    int x = (int) pos.x, y = (int) pos.y;
    int tileX = x, tileZ = y - (x - (x&1)) / 2, tileY = -tileX - tileZ;
    return new Vector3(tileX, tileY, tileZ);

}

Here you can see my Neighbor calculation and my Cube to Offset Coords and my Offset Coords to Cube Functions. My Grid is based on the Offset Coord System, I am saving my Grid in a 2D Array and when I search for neighbors I convert them into the Cube Format. My Problem is for the even cols its working fine but for the odd cols, it is not. My Question is how can I fix this?

It is btw. the same if I increase the radius to 2 instead of 1.

Kind regards,

Alex

(Sorry for my bad English I am from Germany:D)

Answer 1

It looks like you just forgot to convert your center tile to cubic coordinates before trying to add cubic offsets to it:

public GameObject[] GetNeighbarsInRange(Vector2 pos, int range) {
    // Add this line to the top of your method.
    var centerCubePos = getVector3Coord(pos);

    List<GameObject> tiles = new List<GameObject>();

...then later down, make sure you're adding your offsets in cubic coordinates, where the math all works out uniformly. Convert only the final result back to offset coordinates.

    var cubePosOffset = new Vector3(x, y, z));
    var newTilePos = getVector2Coord(centerCubePos + cubePosOffset);
    tiles.Add(getTile(newTilePos));

---

Also, a note on efficiency:

for x...
   for y...
       for z...
           if(x + y + z == 0)
           ...

Here you're looping over \$(2 \cdot range + 1)^3\$ cells and skipping most of them, to find just \$3 \cdot (range)\cdot (range + 1) + 1\$ results that you actually want - a cubic amount of work for a square number of results. At a radius of 2 you're checking 125 cells for 19 actual hits. At 3 you're checking 343 cells for 37 hits.

We can do this much more efficiently.

One small change would be:

for x...
   for y...
       // Once we know x & y, there's only one z that can satisfy 
       // x + y + z == 0, so just set it directly instead of looping again:
       z = -x - y;
       // Reject out-of-range zs calculated this way.
       if(z < min || z > max) 
           continue;

Now we're doing only a square amount of work, though we still generate some coordinates we have to skip (at a radius of 2 we search 25 cells for 19 hits, at a radius of 3 we search 49 cells for 37 hits).

Much better, but we could go further if we wanted to and skip no cells at all, by using the technique described as "Spiral Rings" on the Red Blob Games site.

Answer 2

You can get neighbor search with radius alghoritm from my fog of war method:

private void UpdateFogOfWar() {
    var playerCell = tilesGrid.WorldToCell(this.transform.position);

    for (int y = -viewRadius; y <= viewRadius; y++) {
        for (int x = -viewRadius; x <= viewRadius; x++) {
            if ((x * x) + (y * y) <= (viewRadius * viewRadius))
                fogOfWarTilemap.SetTile(new Vector3Int(playerCell.x + x, playerCell.y + y, playerCell.z), null);
        }
    }

    UpdatePathFindingGridTable();
}