Лучший контейнер для хранения узлов карты тайла?
Я программирую изометрический 2D-сценарий, в котором мне придется использовать A * pathfinding. Лучше ли иметь вектор для хранения всех узлов листов (и каждый раз, когда я запрашиваю «соседний узел запад-юг», вычислять его и проверять, существует ли он с некоторыми математическими вычислениями), или, скорее, я напрямую подготавливаю все узлы с указателями на 9 соседних узлов и обнулить их, если это предел? Эта опция немного потребляет память, но стоит ли?
Каков наилучший способ хранения узлов мозаичной карты в целом, std :: vector, std :: list, custom?
Решение
С сеточной картой, (одномерный) массив / вектор может сделать эту работу.
«Математика» для вычисления / проверки соседей очень проста.
Вы можете добавить фальшивые плитки вокруг вашей карты, чтобы упростить / оптимизировать проверку.
Таким образом, для карты 3х3 вы строите карту 5х5 с непроходимой плиткой на границе.
XXXXX
X...X
X...X
X...X
XXXXX
Север / Юг: индекс +/- 5
Восток / Запад: индекс +/- 1
Другие решения
Я бы предложил использовать опцию, которую вы дали каждому узлу, хранящему 9 указателей, каждый на соседа. Если у вас нет огромный Количество узлов, использование памяти будет незначительным на современном оборудовании, и поиск пути будет намного быстрее, если вы сможете легко возвращать соседей узлам, а не выполнять поиск каждый узел ты должен найти.
Короче, использование памяти не будет тот высокий, и поиск пути будет быстрее, чем с другими схемами.