На шестиугольном графике как сохранить трехмерные координаты в качестве индекса для одномерного контейнера / извлечь элемент из одномерного контейнера, используя трехмерные координаты?

Question

Я пытаюсь сохранить график шестиугольников, используя кубические координаты, как указано в https://www.redblobgames.com/grids/hexagons/#coordinates

Я хочу использовать вектор или некоторый легко повторяемый контейнер для хранения объектов Hex, в основном наборы трехмерных целочисленных координат плюс вектор, содержащий индексы смежных гексов.

Моя проблема в том, что у меня возникли проблемы с поиском функций для преобразования кубических координат X / Y / Z (что допускает отрицательные целочисленные значения) в соответствующие одномерные индексы контейнера. Учитывая любой действительный набор координат, я хочу иметь возможность получить конкретный номер индекса гекса.

Мне известна функция, которая работает так:

1D_index = f (x, y, z) = x + (max_width) * y + (max_width) (max_height) * z,

для декартовой сетки, но у меня возникли проблемы при создании аналогичной функции для в шестиугольнике:

Мой класс Hex и контейнер выглядит так:

class Hex
{
private:
    int xCell, yCell, zCell;
    std::vector<int>neighbours;

public:
    Hex();
    Hex(int x, int y, int z) : _x(x), _y(y), _z(z);
    ~Hex();
};


std::vector<Hex*>hexGraph;

Чтобы заполнить график несвязанными узлами, я использую просто перечисление всех координат, которые могут существовать, учитывая положительные и отрицательные размеры графика x / y / z:

for(int x = effectiveWorldNegX; x < effectiveWorldPosX; x++)
        for(int y = effectiveWorldPosY; y > effectiveWorldNegY; y--)
            hexGraph.push_back(new Hex(x,y,(x*-1)-y)); // x+y+z=0, so z=(-x-y)

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

for(std::vector<Hex*>iterator it = hexGraph.begin(); it != hexGraph.end(); ++it)
{
(*it)->neighbours.push_back( /* Index of upper left hex node */ )
(*it)->neighbours.push_back( /* Index of upper center hex node */ )
(*it)->neighbours.push_back( /* Index of upper right hex node */ )
...

}

И так далее, но для этого мне нужен способ найти индекс, скажем, любой ячейки + 1x , -1y, + 0z.

Начиная с l oop, все, что я определил, это 1) точный порядок, в котором гексы возвращаются в вектор hexGraph, учитывая начало / конец моих циклов

2) Мне может или не нужно смещать все значения координат на отрицательное расстояние X / Y / Z от 0, чтобы удалить негативы

, но где я могу go отсюда?

Помощь очень ценится.

Answer 1

Один из способов решения этой проблемы - присвоить id каждой вершине графа, а затем ссылаться на соседние вершины по идентификаторам.

Пример

using VertexId = size_t;

class Hex {
    std::vector<VertexId>neighbours;
  public:
    Hex(int x, int y, int z);
};

class VertexStorage {    
    std::unordered_map<VertexId, Hex> _id_to_hex;
    std::unordered_map<Hex, VertexId> _hex_to_id;
  public:
    // check if hex is in storage, return id
    // if not, assign new id an push tostorage
    // id could be increasing counter
    VertexId getId(const Hex &hex);
    Hex getHex(VertexId id);
};