Гексагональная матрица (нужен совет)

[brazhe]

Вот, нужно мне задать элементы на гексагональной решетке --- чтобы у каждого элемента было по 6 ближайших соседей. Посоветуйте, пожалуйста, как это можно сделать

[elide]

это можно сделать с помошью указателей (:
а вообще, можно вопрос по подробней?

[t.t]

На самом деле проще и экономичнее всего сделать это через обыкновенные массивы.

Если в квадратичной матрице сдвинуть каждую, скажем, чётную строку на пол-ячейки влево, то получится хексагональная матрица (для полноты картины нужно ещё каждый квадрат-ячейку заменить шестиугольником, но все соседства при этом останутся те же). Как это реализовать через индексы, думаю, из такой картинки вам сразу станет понятно.

[brazhe]

t.t, наверное так и сделаю, спасибо за совет. Правильно ли я понял, что нужно просто в обычном массиве переопределить "соседей" ?

[flook]

это можно сделать с помошью указателей (:

Шикарно! А чего нельзя сделать с помощью указателей? :P

[t.t]

t.t, наверное так и сделаю, спасибо за совет. Правильно ли я понял, что нужно просто в обычном массиве переопределить "соседей" ?

Ну да. Можно к примеру макрос написать, который будет определять по индексам, являются ли элементы соседями. Если на бумаге это нарисовать -- сразу станет понятно, какая именно там чехарда с индексами; мне рисовать лень, а в уме я всегда с такой фигнёй путаюсь.

[Asgard]

Можно ещё создать массив связных списков. Имхо, это проще для понимания...

[brazhe]

То есть типа
----------------------------
Node:
link_to_neighbour1
link_to_neighbour2
link_to_neighbour3
link_to_neighbour4
link_to_neighbour5
link_to_neighbour6

cargo
----------------------------

Насоздавать таких штук и перелинковать их, так что ли?

[t.t]

Можно ещё создать массив связных списков. Имхо, это проще для понимания...

Честно говоря, не вижу, чем сложен для понимания вариант со сдвигом строк, тем паче, что обёртки над ним можно написать какие душе угодно. А вот во сколько раз массив элементов будет жрать меньше памяти, чем массив связных списков из тех же элементов? При больших размерах массива это может оказаться критично.

[brazhe]

Насколько я понял, возможны два варианта сдвига:
Такой: (как описывал t.t)

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
[indent][(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)]
[(2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5)]
[indent][(3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5)]
[(4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5)]
[indent][(5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)]

И такой:

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
[indent][(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)]
[indent][indent][(2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5)]
[indent][indent][indent][(3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5)]
[indent][indent][indent][indent][(4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5)]
[indent][indent][indent][indent][indent][(5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)]


Интересно, какой предпочтительнее?

[t.t]

Предпочтительнее для чего? Просто эти два варианта задают два участка решётки разной формы: первый -- похожий на прямоугольник, второй -- похожий на ромб. Больше никакой разницы между ними нет; а как отразится именно эта разница -- зависит от задачи.

[brazhe]

Ну, просто во втором случае индексы соседей не зависят от четности строки, так что оперировать ими вроде бы должно быть проще?

[t.t]

Проще. Но экономия от +i%2 столь незначительна, что её можно и не учитывать.

[brazhe]

Для машины --- да

Но вот во втором варианте у граничных элементов по 2 "пустых соседа", а в первом --- вдоль строк по три, а вдоль столбцов --- по два. Наверное, по этому признаку мне больше подойдет "ромбик" --- он симметричнее.

[t.t]

Наверное, "прямоугольник" чаще встречается просто из-за естественной тяги детей индустриальной цивилизации ко всему квадратному

[brazhe]

Наверное
Если бы я писал игру с гексагон. картой, то выбрал бы прямоугольный вариант, а так -- мне оно без разницы. А вот бонус в симметрии мне полезней, наверное.