Zdobądź pierścień płytek w siatce sześciokąta

Dzięki temu postowi : Sześciokątne płytki i znajdowanie sąsiadujących z nimi sąsiadów , jestem w stanie zebrać sąsiednie płytki do danej płytki. Ale prawie utknąłem na algorytmie, który daje mi tylko „pierścień” płytek określonych przez przesunięcie. Algorytm podany w tym artykule Przepełnienie stosu nie dba dokładnie o kolejność, w jakiej zbiera kafelki.

Wiem, że z każdym przesunięciem dodaje się 6 płytek.

• Przesunięcie 1 daje 6 płytek (pierwsze sąsiadujące płytki).
• Offset 2 daje 12.
• Offset 3 daje 18 itd.

Z każdym przesunięciem następuje stały wzrost o 6. Zakładam więc, że powinna istnieć reguła, która dostosowuje się do tych przesunięć. Nie mogę tego dokładnie rozgryźć. Ktoś?

A hexagonal ring with the radius of N consists of 6 straight lines, each with length N - see my extremely crude example below :) For N=2:

The arrows cover 2 hexes each.

I assume you have some functions which give you the neighbouring tile in a specific direction, like north(), southeast() etc. So your algorithm, in pseudocode, should be something like this:

var point = startingPoint.north(N)
for i = 0..N-1:
    result.add(point)
    point = point.southeast(1);
for i = 0..N-1:
    result.add(point)
    point = point.south(1);
for i = 0..N-1:
    result.add(point)
    point = point.southwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.northwest(1);
for i = 0..N-1:
    result.add(point)
    point = point.north(1);
for i = 0..N-1:
    result.add(point)
    point = point.northeast(1);

Note that this should work also for edge cases N=1, returning 6 tiles, and N=0 returning an empty set.

I know the code isn't perfect :) There is some redundancy here. In my projects using regularly tiled maps (hexagonal or otherwise) I usually have an enum "Direction", which allows me to do this more smoothly:

var point = startingPoint.inDir(N, Direction.North)
var dir = Direction.SouthEast.
for d = 0..Direction.count():
    for i = 0..N-1:
        result.add(point)
        point = point.inDir(1, dir);
    dir = nextDirection(dir);

Uważam, że ten artykuł stanowi bardzo dobre odniesienie do algorytmów siatki heksagonalnej, a jego sekcja „Odległości” zapewnia metodę określania liczby kroków między dwoma kafelkami. W przypadku konwersji współrzędnych osiowych (x-y) into cube coordinates (x-y-z), the distance is always equal to the largest of the coordinate offsets between the two tiles, or max(|dx|, |dy|, |dz|).

Wyczerpujące przeszukanie całej siatki pod kątem płytek w żądanej odległości to $O(n^2)$ z wymiarami siatki, ale jest to prosta implementacja, która działa dobrze w przypadku małych siatek.