Как я заставил сотни тысяч NPC ходить по лабиринту 1024×1024, убрав поиск пути
Осенью 2004 я сел писать прототип на C++ и SDL2. Задача была одна: мир-лабиринт размером 1024×1024 клетки и толпа персонажей, которые по нему осмысленно ходят — не по скрипту, не по рельсам, а из точки в точку через двери и комнаты.
Не десятки персонажей. Не тысячи. В константах прототипа стоит:
#define WORLD_WIDTH 1024 #define ROOMS 16384 #define CONNECTIONS 128 #define MAX_OBJECTS 1048576
Миллион. И это не бравада в дефайне — оно работает, потому что архитектура построена вокруг одной мысли: персонаж не ищет путь.
Дальше — как именно. Весь код свой, литературу по алгоритмам я не читал; до всего доходил из первых принципов и проверял на практике. Уже потом выяснил, что у похожей схемы есть название и статьи с середины двухтысячных. Мне это ничего не добавило и не убавило — рассказываю так, как оно строилось.
Почему очевидный путь не работает
Очевидное решение — дать каждому персонажу искать дорогу самому. Волна в ширину от него до цели, или A*.
Считаем. Мир — миллион клеток. Одна волна в худшем случае обходит весь мир. Персонажей — сотни тысяч. Даже если волна укладывается в микросекунды, помножьте на число персонажей и на число кадров, и вы получите машину, которая занимается исключительно поиском пути.
Дальше обычно начинается лечение симптомов: кешировать пути, искать не каждый кадр, а раз в N, завести пул потоков, ограничить «активных» персонажей. Всё это отодвигает потолок, но не убирает его — стоимость по-прежнему растёт с числом персонажей.
Я пошёл в другую сторону. Не «как ускорить поиск», а «как сделать так, чтобы искать не надо было вообще».
Идея: персонаж читает число
Представьте, что в каждой клетке мира заранее написано число: «отсюда до двери — столько-то шагов». Тогда персонажу не нужно ничего искать. Он смотрит на своё число, смотрит на числа четырёх соседей, шагает в меньшее. И так, шаг за шагом, приходит к двери.
двери персонаж
↓ ↓
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ 1 │ 2 │ 3 │ 4 │███│ 6 │ 7 │ 8 │
├───┼───┼───┼───┼───┼───┼───┼───┤
│ 2 │ 3 │ 4 │ 5 │███│ 7 │ 8 │ 9 │
└───┴───┴───┴───┴───┴───┴───┴───┘
персонаж стоит на 9 → смотрит соседей: 8 и 8 → шагает на 8 → 7 → ...Стоимость шага — четыре чтения из массива и сравнение. Константа. Она не зависит ни от размера мира, ни от расстояния до цели, ни, главное, от числа персонажей. Миллион персонажей — это миллион раз по четыре чтения, и всё.
Числа считаются один раз при генерации мира. Волна из двери: соседям двери — единица, их соседям — двойка, и так пока не кончится комната.
std::queue<int> q;
temp[door_cell] = 0;
q.push(door_cell);
while (!q.empty())
{
int cur = q.front(); q.pop();
unsigned short curd = temp[cur];
for (int d = 0; d < 4; ++d)
{
cell* nb = world[cur].side(d);
if (!nb) continue;
int ni = nb->get_n();
if (zones[ni] != room_zone) continue; // ← вот эта строчка решает всё
if (world[ni].type == WALL) continue;
if (temp[ni] == UNREACH)
{
temp[ni] = curd + 1;
q.push(ni);
}
}
}Про подчёркнутую строчку — ниже, она тут самая важная.
Проблема: полей нужно слишком много
Схема выше прекрасна, пока цель одна. Но персонажи ходят в разные места. Если считать поле на каждую возможную цель — это миллион полей по миллиону клеток. Не бывает.
Значит, поле на весь мир строить нельзя. Нужно, чтобы поле было маленьким.
Уровень 1: комнаты как граф
Мир разбивается на комнаты. У каждой клетки есть номер комнаты — массив zones, нумерация с единицы, ноль означает «не комната» (коридор, стена, пустота).
Двери собираются по комнатам: пробегаем весь мир, каждую клетку типа DOOR записываем в списки тех комнат, которых она касается. Дверь между двумя комнатами попадает в оба списка — это и делает её дверью.
for (size_t i = 0; i < totalCells; ++i)
{
if (world[i].type != DOOR) continue;
for (int d = 0; d < 4; ++d)
{
cell* nb = world[i].side(d);
int z = zones[nb->get_n()]; // 1-based
if (z >= 1 && z <= room_n)
room_doors[z - 1].push_back((int)i);
}
}Теперь у нас есть граф: комнаты — узлы, двери — рёбра. Соседство лежит в neighbours[room * CONNECTIONS + k].
┌────────┐ дверь ┌────────┐
│ комн.7 ├─────────┤ комн.12│
└───┬────┘ └───┬────┘
│дверь │дверь
┌───┴────┐ ┌───┴────┐
│ комн.3 ├─────────┤ комн.40│
└────────┘ дверь └────────┘Ключевое: этот граф на четыре порядка меньше мира. Миллион клеток превратился в 16 384 узла.
По нему я гоняю волну из каждой комнаты и складываю результат в таблицу «сколько дверей пройти от комнаты A до комнаты B»:
void build_distances(unsigned short* neighbours, unsigned short* distances, int room_count)
{
for (int i = 0; i < room_count; ++i)
for (int j = 0; j < room_count; ++j)
distances[i * room_count + j] = UNREACH;
for (int s = 0; s < room_count; ++s)
{
std::queue<int> q;
distances[s * room_count + s] = 0;
q.push(s);
while (!q.empty())
{
int u = q.front(); q.pop();
unsigned short du = distances[s * room_count + u];
for (int k = 0; k < CONNECTIONS; ++k)
{
int v = neighbours[u * CONNECTIONS + k];
if (v == UNREACH) continue;
if (distances[s * room_count + v] > du + 1)
{
distances[s * room_count + v] = du + 1;
q.push(v);
}
}
}
}
}Уровень 2: поля внутри комнаты
if (zones[ni] != room_zone) continue;
Она обрезает волну границей комнаты. Волна из двери не растекается по всему миру — она заливает только свою комнату и останавливается.
Это и есть ответ на «полей слишком много». Поле теперь стоит не миллион клеток, а размер одной комнаты. И считается оно не «на каждую цель в мире», а на каждую дверь — а дверей конечное, известное на генерации число.
┌─────────────────┐ ┌─────────────────┐
│ 4 3 2 3 4 5 6 7 │ │ 7 6 5 4 3 2 3 4 │
│ 3 2 1 2 3 4 5 6 │ │ 6 5 4 3 2 1 2 3 │
│ 2 1 0═══════════╪═══╪═══════════0 1 2 │
│ 3 2 1 2 3 4 5 6 │дв.│ 6 5 4 3 2 1 2 3 │
└─────────────────┘ └─────────────────┘
комната 7 комната 12
у каждой комнаты — своё поле до этой двери,
и заливка одной комнаты не залезает в соседнююШаг персонажа: три чтения
Вся навигация в рантайме укладывается в три действия.
Первое. В какую соседнюю комнату идти? Смотрим таблицу расстояний между комнатами и выбираем соседа, который ближе к цели, чем мы:
unsigned short best_room_dist = distances[current_room * room_count + target_room];
for (int k = 0; k < CONNECTIONS; ++k)
{
int r = neighbours[current_room * CONNECTIONS + k];
if (r == UNREACH) continue;
unsigned short d = distances[r * room_count + target_room];
if (d < best_room_dist) { best_room_dist = d; next_room = r; }
}Второе. Через какую дверь? Из дверей нашей комнаты берём те, что касаются выбранной соседней, и среди них — ту, до которой нам ближе (по её же полю):
for (int f = 0; f < (int)room_doors[current_room].size(); ++f)
{
int door_cell = room_doors[current_room][f];
for (int d = 0; d < 4; ++d)
{
cell* nb = world[door_cell].side(d);
if (zones[nb->get_n()] - 1 == next_room)
{
unsigned short v = paths[f * totalCells + current_cell];
if (v < best_path_val) { best_path_val = v; best_door_index = f; }
}
}
}Третье. Собственно шаг — спуск по полю выбранной двери:
size_t base = (size_t)best_door_index * totalCells;
unsigned short best = paths[base + current_cell];
int best_side = -1;
for (int d = 0; d < 4; ++d)
{
cell* nb = world[current_cell].side(d);
int ni = nb->get_n();
if (world[ni].type == WALL) continue;
unsigned short v = paths[base + ni];
if (v < best) { best = v; best_side = d; }
}
if (best_side != -1)
obj.pos = world[current_cell].side(best_side)->get_n();Ни одной волны. Ни одного A*. Ни одного цикла, длина которого зависит от расстояния до цели. Только чтения из заранее посчитанных массивов.
персонаж в комнате 7, идёт в комнату 40
│
├─ 1. таблица комнат → «следующая комната 12»
├─ 2. двери комнаты 7 → «дверь №2, она ведёт в 12»
└─ 3. поле двери №2 → «сосед справа меньше, шагаю вправо»
│
повторить на следующем кадреПерсонаж не знает маршрута. Он вообще не знает, что такое маршрут. Он каждый кадр отвечает на один вопрос — «куда шагнуть прямо сейчас» — и из этих ответов складывается дорога через полмира.
Раскладка paths: почему полей меньше, чем дверей
Полей у нас по одному на дверь, а дверей в мире много. Хранить каждое поле отдельной плоскостью на миллион клеток было бы разорительно.
Но поля разных комнат не пересекаются — каждое обрезано своей зоной. Значит их можно класть в одну плоскость.
Плоскость f содержит поля f-х дверей всех комнат сразу:
плоскость 0: [поле 0-й двери комн.1][поле 0-й двери комн.2][...] ← не пересекаются плоскость 1: [поле 1-й двери комн.1][поле 1-й двери комн.2][...] ...
Отсюда base = f * totalCells в коде выше. Число плоскостей — это максимальное число дверей у одной комнаты, а не общее число дверей в мире.
Чем за это заплачено
distances ROOMS × ROOMS × 2 байта = 512 МиБ paths плоскости × 1024×1024 × 2 = 256 МиБ neighbours ROOMS × CONNECTIONS × 2 = 4 МиБ
Три четверти гигабайта, выделенных один раз на генерации мира.
Это выглядит много, и первая реакция обычно — «надо сэкономить». Не надо. Именно полнота этих таблиц покупает константу на шаг персонажа. Как только начинаешь считать что-то лениво или держать в кеше, появляется промах кеша — а промах означает, что кто-то посреди кадра встал считать волну. При сотнях тысяч персонажей это ровно та непредсказуемость, ради избавления от которой всё и строилось.
Память здесь обменяна на время, причём по фиксированному курсу, известному заранее. Для мира с сотнями тысяч ходячих персонажей это правильная сторона размена.
Мелочи, которые тоже не случайны: расстояния лежат в unsigned short, недостижимость — это 65535, а не отдельный флаг и не -1 в знаковом типе. На таких объёмах два байта против четырёх — это разница между 512 МиБ и гигабайтом.
Отладка: поле видно глазами
Отдельно скажу про то, что сэкономило больше всего времени.
Поле расстояний — это готовая картинка. Ноль у двери, дальше темнее. Я вывел его прямо в текстуру SDL: клавишами влево-вправо листаешь двери, зелёным подсвечивается комната под курсором, красным — персонажи.
unsigned short d = paths[base + i];
unsigned char color = 0;
if (d == 65535) color = 0; // недостижимо → чёрное
else if (d == 0) color = 255; // источник → белое
else {
unsigned short dd = (d > 255) ? 255 : d;
color = 255 - (unsigned char)dd;
}
Ошибки в заливке видно мгновенно: комната залилась не до конца — значит где-то дыра в связности; поле перетекло к соседям — значит сломалась обрезка по зонам; чёрное пятно в середине комнаты — недостижимый карман, который персонажи никогда не покинут.
Это то, что я бы посоветовал каждому, кто делает что-то на сетках: рисуйте свои промежуточные данные. Не логи, не числа в консоль — картинку. Один кадр отладочного хитмапа заменяет час чтения кода.
Что из этого выросло
Прототип занимает около 5000 строк своего кода поверх SDL2. Там нет движка, нет фреймворка, нет чужих библиотек кроме самого SDL — весь стек от структуры клетки и графа комнат до меню и отрисовки написан руками. Этот прототип был написан в октябре 2004 года.
А потом на этой архитектуре выросла ГИГАХРУЩ — браузерная игра про вылазки в самособирающуюся хрущёвку размером с город.
Язык другой — TypeScript вместо C++. Объём другой — сотни тысяч строк вместо тысяч. Но принципиально там то же самое: мир 1024×1024, комнаты как граф, поля вместо поиска, персонаж читает число и шагает в меньшее. Всё, что нужно для толпы, было доказано вот в этом маленьком прототипе на SDL.
Поэтому я и рассказываю про него, а не про текущую версию. Текущая — это тот же концепт, обросший контентом. А идея целиком лежит в пяти с небольшим тысячах строк, и её видно.
Играть в ГИГАХРУЩ: tenevik.itch.io/gigahrush