Терен, който се чупи там, където играчът го среже: плочи на Вороной и обхождане в игра с Three.js

В нашата арена игра Faultwarden никога не удряте враг. Ударът ви отваря линия от каменни плочи в пропаст и всяко парче от летящия остров, което пропастта откъсне от светещия Сърдечен камък в средата, се отчупва и пада заедно с всички врагове върху него. Цялата игра стои върху един въпрос, на който кодът отговаря много пъти в секунда, включително за прицела: ако тези плочи се отворят, какво остава свързано със сърцето? Този дневник на разработката показва как строим острова от клетки на Вороной, как обхождането на графа отговаря на въпроса за далеч под милисекунда и кои правила пазят играта честна.

#Защо плочи на Вороной, а не шестоъгълна мрежа

Шестоъгълната мрежа е лесният избор за чупещ се под и точно затова я избегнахме: еднаквите шестоъгълници карат всяка арена да прилича на всяка друга игра с падащи плочки. Клетките на Вороной дават неправилни каменни плочи, едни широки, други малки, а очертанието на острова може да е всякакво. Освен това дават наготово графа на съседите, а той е всичко, което логиката на чупенето изисква.

Диаграмата на Вороной взима набор от точки, наречени центрове, и дава на всяка от тях частта от равнината, която е по-близо до нея, отколкото до всеки друг център. Частите са изпъкнали многоъгълници със общи страни със съседите си. Използваме малката библиотека d3-delaunay, която изчислява триангулацията на Делоне и диаграмата на Вороной от плосък масив с координати и казва за всеки център кои са съседите му.

#Строене на острова

Генераторът в island.ts минава през пет стъпки, всичките от един зародиш, така че един и същ зародиш винаги дава един и същ остров:

1. Очертанието. Радиусът на острова във всяка посока е основен радиус плюс няколко синусоиди със случайни фази, което дава меки издатини и заливи вместо кръг.
2. Центровете. Точки се хвърлят на случаен принцип в очертанието и се запазват само ако са достатъчно далеч от всички вече запазени. Самото минимално разстояние се мени плавно по острова, така че едни места получават широки плочи, а други малки. Първият център стои точно в средата: това ще е сърцето.
3. Пръстен от призрачни центрове. Извън очертанието добавяме два пръстена от допълнителни центрове, които никога не стават плочи. Без тях външните клетки биха се разтеглили до края на ограничаващия правоъгълник; с тях крайните плочи се затварят с естествен, леко назъбен ръб.
4. Едно изглаждане. Всеки истински център се премества в средата на клетката си (една стъпка от алгоритъма на Лойд), което изравнява размерите, без да ги прави еднакви. Центърът на сърцето остава на мястото си.
5. Окончателната диаграма. Плочите получават многоъгълниците си, списъците със съседи и отметка, когато съсед е призрачен: това са крайните плочи, по които враговете се катерят.

import { Delaunay } from 'd3-delaunay';

const d = new Delaunay(Float64Array.from(sites)); // [x0, z0, x1, z1, ...]
const v = d.voronoi([-bound, -bound, bound, bound]);

for (let i = 0; i < realCount; i++) {
  const ring = v.cellPolygon(i); // затворен контур: първата точка == последната
  plates.push({ id: i, poly: ring.slice(0, -1), nbr: [], rim: false });
}
for (let i = 0; i < realCount; i++) {
  for (const j of d.neighbors(i)) {
    if (j >= realCount) plates[i].rim = true; // призрачен съсед: плочата е на ръба
    else plates[i].nbr.push(j);
  }
}

Две практични бележки. d3 работи с x и y, а подът в Three.js лежи в x и z, затова следете в коя посока обикалят многоъгълниците, когато ги превръщате в мрежи, иначе горните стени ще гледат надолу. А за да намерите плочата под дадена точка, не ви трябва проверка в многоъгълник: плочата е просто най-близкият център, който малка мрежа от кофички намира бързо.

#Въпросът: какво още е свързано?

Всяка плоча има състояние: цяла, отворена в пропаст, откъсваща се, падаща или изчезнала. Ударът отваря линия от плочи. След това играта пита кои стоящи плочи още могат да стигнат до опора, като минават през стоящи съседи. Сърцето винаги е опора. Отговорът е обикновено обхождане на графа на съседите:

function connected(anchors, removed) {
  const seen = new Uint8Array(plates.length);
  const queue = [];
  for (const a of anchors) {
    if (standing(a) && !removed.has(a) && !seen[a]) {
      seen[a] = 1;
      queue.push(a);
    }
  }
  while (queue.length) {
    const i = queue.pop();
    for (const j of plates[i].nbr) {
      if (seen[j] || !standing(j) || removed.has(j)) continue;
      seen[j] = 1;
      queue.push(j);
    }
  }
  return seen; // 1 = още е свързана с опора
}

Всичко стоящо, до което обхождането не е стигнало, е откъснато. Второ минаване групира тези плочи в парчета със същия вид обхождане, така че играта знае кои плочи вървят заедно. Петте ни острова имат между 55 и 96 плочи и цялата проверка струва няколко микросекунди, няколко десетки при първото пускане. Това е важно, защото същата функция работи за прицела при всеки кадър, за безопасното автоматично прицелване на сензорни екрани и за всеки възможен удар, който ботовете за изпитване обмислят.

Параметърът removed прави предвиждането евтино: играта никога не променя истинското състояние, за да попита „ами ако“. Тя подава плочите, които ударът би отворил, като множество, а обхождането ги смята за изчезнали.

#Правила, които пазят играта честна

Обхождането казва истината за свързаността. Какво да се прави с нея решава дизайнът на играта, а първата ни версия беше твърде сурова: един небрежен удар близо до средата можеше да събори половината остров. Правилата, до които стигнахме:

• Сърцето никога не се откъсва и не се отваря. Тест пропуква всички плочи около сърцето и проверява, че то остава цяло. Ако сърцето можеше да падне, играта щеше да свършва на формалност.
• Тежките парчета се задържат. Парчета до определен размер се отчупват веднага. По-големите стенат и се държат, докато пропастта се затвори, и падат след няколко секунди само ако все още са откъснати. Видимо предупреждение дава на играча време да издигне плоча и да затвори пролуката.
• Прицелът показва цената. Преди удара плочите, които ще паднат, се очертават, а малък етикет показва колко земя ще загубите. На първия остров голям разрез иска потвърждение.
• Някои врагове също са опори. Пазачът е вкоренен в плочата под себе си, така че обхождането тръгва и от него и разрезът около него не прави нищо. Само около три секунди след собствения му удар в земята той е свободен и това е мигът за разреза.

Всяко правило има тест. Един от тях избира крайна плоча, поставя враг върху нея, пропуква всичките ѝ вътрешни съседи и проверява, че и плочата, и врагът падат до секунда и половина.

#Да изглежда като камък, а не като диаграма

Диаграма на Вороной, нарисувана директно, се познава от пръв поглед. В 3D изгледа всяка плоча е изтеглена в дебела плоскост със скосен горен ръб, тревна шапка, леко отдръпната от ръба, и скални страни с оттенък, който се мени от плоча на плоча. Шевовете между плочите са тъмни линии, които се пропукват, преди плочата да падне, така че играчът разчита формата на разреза, преди да се случи. Когато парче пада, плочите му пазят взаимното си положение и се накланят заедно, а прахът и звукът идват от шевовете, които са се скъсали. Ръководството за процедурни звукови ефекти с Web Audio API показва как се прави този пукот без нито един записан звук.

#Изпитване с ботове

Чупещият се терен лесно става нечестен, затова балансът се проверява с ботове, които играят по истинските правила: пробват всяка посока, ползват същата функция predict като прицела и избягват разрези, които биха ги съборили. Пускане на 3 ноември 2026 г. с шест зародиша на остров даде на внимателния и на обикновения бот по шест победи от шест на всеки от петте острова, а бот, който играе като начинаещ, спечели между една и шест. Целият метод е описан в ботове за изпитване, които доказват, че всяко ниво може да се мине, а цикълът с фиксирана стъпка, който прави тези пускания повторяеми, в цикъл на игра с фиксирана стъпка в JavaScript.

Faultwarden е безплатна и е обявена като „Очаквайте скоро“ в каталога с игри на PN Scripts. Ако сте нови в 3D в браузъра, започнете с браузърни игри с Three.js и WebGL.

#Често задавани въпроси

Трябва ли ми физичен двигател за чупещ се терен?

Не и за такъв вид чупене. Дали парче пада е въпрос за граф, на който отговаря обхождане на съседните плочи. Самото падане може да е обикновена анимация; физичен двигател си струва само когато счупените парчета трябва да се търкалят и да се удрят реалистично.

Колко клетки на Вороной може да понесе браузърът?

Построяването на диаграмата за хиляди центрове отнема милисекунди, а обхождането е линейно спрямо броя на плочите. Истинската граница е рисуването: обединете плочите в няколко мрежи или използвайте инстанциране и престроявайте само плочите, които са се променили.

Защо се добавят призрачни центрове извън очертанието?

Без тях външните клетки се разтеглят до ограничаващия правоъгълник и образуват дълги шипове. Призрачните центрове затварят крайните плочи на естествено разстояние и дават назъбен бряг вместо прави ръбове.

Как да не позволите един удар да събори половината карта?

Ограничете какво може да падне наведнъж: малките парчета се отчупват, големите се държат, докато пролуката се затвори, и падат по-късно само ако още са откъснати. Покажете на играча какво ще падне, преди да е потвърдил удара.

#Източници

• d3-delaunay в GitHub (на английски)
• Алгоритъм на Лойд (на английски)
• Документация на three.js: ExtrudeGeometry (на английски)