Сталкивались с тем, что процедурный генератор карт подвисает на пару секунд прямо посреди загрузки? Вроде всё логично: набросали вариант, прогнали BFS, убедились что карта проходима, повторили. Но итераций таких — сотни, и каждая тащит полный обход графа. Давайте разберём, как брейк-радары позволяют выбрасывать провальные кандидаты ещё до старта тяжёлого обхода.
По сути, процедурный генератор — это машина перебора. Вы накидываете вариант, проверяете условия (карта связна, путь существует, длина маршрута не меньше N шагов), если не подходит — выбрасываете и пробуете снова. Банальный подход: BFS на каждый вариант. На карте 100×100 с тысячей итераций вы быстро упрётесь в потолок.
Брейк-радар — это дешёвая проверка *до* тяжёлого алгоритма. Если она говорит «этот вариант точно плохой» — прерываете итерацию сразу, BFS даже не стартует. Хороший радар: O(1) или O(маленькое), зато отсекает значительную долю провалов.
Итак, три примера на пальцах.
Трасса с кольцом
Представьте генератор трасс как у какого-нибудь Mini Motor Racing — тайлы с прямыми, поворотами влево и вправо. Чтобы трасса замкнулась, сумма поворотов должна быть ровно ±360°. Это геометрический факт, BFS здесь вообще не нужен:
int netRotation = 0;
foreach (var tile in generatedTrack)
netRotation += tile.rotationDelta; // +90 или -90
if (Mathf.Abs(netRotation) != 360)
return false; // выбрасываем без BFS
Сумма не сходится — трасса физически не замкнётся. Ноль смысла проверять связность.
Данж с изолированными комнатами
Генерируем подземелье, нужно убедиться что все комнаты достижимы. Полный BFS — O(W×H). Но перед ним работает грубый инвариант: если комнат N, то минимальное число соединений для связного графа — N−1 (дерево). Дверей меньше — данж гарантированно несвязен:
int rooms = CountRooms();
int doors = CountDoorTiles();
if (doors < rooms - 1)
return false; // математически несвязно, BFS не нужен
Конечно же, это нижняя оценка — двери могут вести в тупики, и BFS всё равно понадобится для финальной проверки. Но очевидные провалы убираем бесплатно.
Минимальная длина пути
Классика головоломок и платформеров: путь от старта до финиша должен быть не короче K шагов. BFS даст точный ответ, но Манхэттенское расстояние даёт бесплатную нижнюю оценку:
int manhattan = Mathf.Abs(start.x - end.x) + Mathf.Abs(start.y - end.y);
if (manhattan >= minPathLength)
return false; // реальный путь не короче манхэттена — а нам нужно именно короче
Ну и тут важно не перепутать направление неравенства. Манхэттен — *нижняя* граница для кратчайшего пути на сетке без диагоналей. Реальный путь будет длиннее или равен. Так что если манхэттен уже не дотягивает до минимума — дальше незачем смотреть.
Чтож, итог простой: брейк-радар — не замена BFS, а фильтр перед ним. Хорошая система генерации выстраивает радары по возрастанию стоимости — сначала O(1) по счётчикам, потом что-то дешёвое по периметру, и только потом полный обход. Моё решение тут точно не единственное, у каждой задачи свои инварианты, которые можно поймать заранее. Но принцип один: чем раньше выбросили плохой вариант — тем быстрее нашли хороший.
Буду рад обсудить в комментариях, какие радары используете вы.
#мат_геймдев #КодПодСкопой #процедурнаягенерация