Волновой алгоритм для гексагональной сетки

[OmegaBerkut]

Здравствуйте.
Подскажите пожалуйста, как правильно получать соседние клетки для матрицы, которая представляется в виде шестиугольной сетки ?

[evg_m]

как правильно получать соседние клетки для матрицы,

Если именно как ПОЛУЧИТЬ то нужно знать как закодировано( как хранятся).
Если как ЗАКОДИРОВАТЬ (хранить), чтобы было удобно получить ...

-- 11 -- 12 -- 13 -- ...
-- -- 21 -- 22 -- 23 ...
-- 31 -- 32 -- 33 -- ...
-- -- 41 -- 42 -- 43 ...
-- 51 -- 52 -- 53 -- ...

-- неиспользуемые и несуществующие ячейки (показаны исключительно для удобства восприятия)

для 32 соседями будут 12 21 22 41 42 52.

[OmegaBerkut]

evg_m
Выглядит это - картинка во вложении.
Предполагается хранение в обычной матрице. Для организации работы волнового алгоритма - это наиболее оптимально.
У отдельно взятой клетки может быть до шести соседей, что есть самоочевидно ...
Нужно получать массив из этих "до шести соседей", и распространять волну.
Как в таком варианте получать соседей ?

[evg_m]

смотри выше ПРЕДЛАГАЕМЫЙ пример матрицы (числа это номер строки. номер столбца)
тоже в картинке но здесь есть цвета 2.JPG

-- неиспользуемые и несуществующие ячейки (показаны исключительно для удобства восприятия)

чтобы увидеть шестиугольник (синие ячейки вокруг красной)

[OmegaBerkut]

evg_m
С таким вариантом я вижу проблемы с индексацией.
Изначатьно у меня массив координат объектов (со скриншота).
Для поиска путей все объекты должны выстроиться в матрицу ...
Пускать волны по вашему варианту я смогу, но прямая индексация будет выдавать артефакты в виде "несуществующих" ячеек.

[evg_m]

С таким вариантом я вижу проблемы с индексацией.

-- неиспользуемые и несуществующие ячейки (показаны исключительно для удобства восприятия)

их нет в массиве. А все прочие имеют сплошную нумерацию (без пропусков).
прочерки введены исключительно для наглядности "шестиугольного сдвига" ячеек.

действительное и "наглядное" виды
11 12 13 14  11 .. 12 .. 13 .. 14 ..
21 22 23 24  .. 21 .. 22 .. 23 .. 24
31 32 33 34  31 .. 32 .. 33 .. 34 ..
41 42 43 44  .. 41 .. 42 .. 43 .. 44
51 52 53 54  51 .. 52 .. 53 .. 54 ..

[OmegaBerkut]

evg_m, хорошо, тогда скажу от чё: вопрос стоял изначально такой - как получить соседние клетки ?
Перефразирую на более "понятный" вариант ...
Есть некоторые координаты X, Y, которые указывают на клетку в квадратной матрице. Как получить соседние клетки при условии того, что матрица рассматривается как гексагональная сетка ? Ещё проще - как посчитать координаты соседних клеток ...
Как построить матрицу - я знаю. Квадратное смещение (вправо/вверх) зависит от того, какая используется гексагональная сетка - вертикальная/горизонтальная (соответственно). У меня сетка вертикальная. Но это всё вода ...

Я задавал этот вопрос тогда, когда у меня не было возможности самому на бумажке просчитывать варианты.
Думал сэкономить время примерно следующим ответом:

Для чётного X в квадратной матрице "соседние" клетки (в гексе) имеют следующие координаты - (X-2; Y), (X-1; Y-1), (X-1; Y), (X+1; Y-1), (X+1; Y), (X+2; Y).
Аналогично для нечётного X координаты - (X-2; Y), (X-1; Y), (X-1; Y+1), (X+1; Y), (X+1; Y+1), (X+2; Y).

Может где ошибся, поправьте пжалста.

[evg_m]

для 32 соседями будут 12 21 22 41 42 52.

 x.y     3.2  
1.2  3-2.2-0
2.1  3-1.2-1 
2.2  3-1.2-0
4.1  3+1.2-1
4.2  3+1.2-0
5.2  3+2.2-0

[phomm]

http://www.redblobgames.com/grids/hexagons/
http://www-cs-students.stanford.edu/...ramming/grids/
и вообще редблоб почитать полезно.

[OmegaBerkut]

Сообщение от phomm

редблоб почитать полезно

Как раз таки эту статью я и читал, когда ковырялся в гугле.
Вторая статья - тоже будет полезна. Спасибо.