Как эффективно хранить путевые точки
У меня есть игра с очень большой картой, и мне нужно сохранить много путевых точек (миллионы, если не миллиарды), чтобы затем использовать их для поиска пути, используя алгоритм A *.
Что мне нужно:
- Эффективный способ хранить много из них
- Быстрый способ получить к ним доступ напрямую по алгоритму A *.
Сначала я думал использовать простой вектор, но это скоро будет использовать всю доступную память.
Тогда я подумал, что должен использовать mysql, возможно, это хорошая идея, так как я могу запросить базу данных для области путевых точек.
Большая проблема в том, что для A * мне нужно как можно быстрее получить доступ к путевым точкам, поэтому, возможно, мне нужен уникальный идентификатор для каждой путевой точки.
Каков наилучший способ сделать это?
Решение
Я думаю, вы должны подумать о том, чтобы перейти на более низкий уровень, управляя своей памятью самостоятельно — звоня new а также delete явно для каждого узла вашего графа; и ссылки на ваши узлы по адресу памяти. Если вы беспокоитесь о выделении большого количества маленьких кусочков памяти, вы можете рассмотреть возможность использования tcmalloc библиотека.
Узлы должны содержать списки смежности. Если график статичен, я бы предложил хранить смежность в динамически создаваемом массиве в каждом узле, размер которого точно соответствует количеству соседей. Если число соседей может измениться со временем, std::vector может быть следующая лучшая вещь.
Примечание: я предполагаю, что график нерегулярен. Для регулярных графиков (например, сетки, как указано в Potatoswatter) местоположение узлов можно узнать неявно.
Другие решения
Других решений пока нет …