andrey
126c7525fd
Вместо прежнего обмена id4 и id10 — вставка: «Издалека» (id4) стоит на 10-м месте, а id5..id10 сдвинуты на позицию вверх (индексы 3..8). Порядок: 1,2,3,5,6,7,8,9,10,4,11..100. - Меняется только порядок записей: данные уровней (имя, размер, зона, бюджет, клетки) не тронуты, «Издалека» как была. - Единственный «блип» размеров теперь на индексе 9; тест монотонности усилен (исключается только он), добавлен кейс «порядок вставки». - 464/464, паритет step 273/273 сохранён.
379 lines
20 KiB
JavaScript
379 lines
20 KiB
JavaScript
#!/usr/bin/env node
|
||
// Генератор уровней кампании: 96 сгенерированных уровней (id 5..100) набора
|
||
// из 100 (первые 4 уровня — ручные в index.html).
|
||
//
|
||
// Печатает готовый блок массива CAMPAIGN_LEVELS в КОМПАКТНОМ формате клеток:
|
||
// { id, name: 'Схема №N', w, h, wrap: false, budget,
|
||
// zone: { x, y, w, h }, cells: [[x,y], ...] }
|
||
// где cells — координаты клеток ВРАГА (цвет 2). Данные СТАТИЧНЫ: генератор нужен
|
||
// только для воспроизводимости/обновления — рантайм в index.html ничего не генерирует.
|
||
//
|
||
// Детерминированность: seeded PRNG (mulberry32) с фиксированным SEED; Math.random
|
||
// не применяется. Повторный запуск даёт идентичный вывод.
|
||
//
|
||
// Запуск:
|
||
// node tools/gen-campaign-levels.mjs # напечатать блок из 96 уровней
|
||
// node tools/gen-campaign-levels.mjs --check # проверить себя (валидация) и выйти
|
||
//
|
||
// Как обновлять уровни:
|
||
// 1. Поправьте SEED/расписание ниже и запустите скрипт.
|
||
// 2. Вставьте напечатанный блок в CAMPAIGN_LEVELS в index.html (после 4 ручных
|
||
// уровней; блок идёт от строки-маркера «// --- 96 сгенерированных ...»).
|
||
// 3. Прогоните тесты: cd tests && npm test (тест сверяет вывод генератора с вшитым
|
||
// блоком, так что забыть перевставить вывод не даст).
|
||
//
|
||
// Расписание: среди 96 СГЕНЕРИРОВАННЫХ уровней размер поля монотонно растёт с ~60
|
||
// до 300 (неубывание). В итоговом массиве из 100 уровней ручной «Издалека» (id4)
|
||
// ВСТАВЛЕН на 10-е место (индекс 9), а id5..id10 сдвинуты вверх (индексы 3..8).
|
||
// Из-за этого единственный «блип» размеров — на индексе 9: idx8=id10 66×66, а
|
||
// idx9=«Издалека» 60×60. Генератор печатает id5..id100 в естественном порядке;
|
||
// сама вставка «Издалека» делается только в index.html (в генераторе её нет).
|
||
// Бюджет растёт с размером, число фигур растёт с размером. Зоны разнообразны, НО
|
||
// зоны «всё поле» у сгенерированных уровней НЕТ (используются 7 типов: половина /
|
||
// центр / левый-верхний угол / правый-нижний угол / вертикальная полоса /
|
||
// горизонтальная полоса / произвольный прямоугольник; всё поле оставлено только
|
||
// ручным «Разминке» и «Рою»). Часть уровней — с врагом ВНЕ зоны игрока. Ружьё
|
||
// Госпера — задумка (уровни заведомо почти непроходимы), решаемость не проверяется.
|
||
//
|
||
// Фигуры — те же, что в PATTERNS (ASCII: '1' = живая клетка). Формы дублируются
|
||
// здесь явно (совпадают с PATTERNS), чтобы генератор был самодостаточным .mjs.
|
||
|
||
import { fileURLToPath } from 'node:url';
|
||
|
||
// ASCII-формы фигур врага (совпадают с PATTERNS: beehive/blinker/toad/loaf/
|
||
// pulsar/gun; заданы здесь явно для самодостаточности генератора).
|
||
export const SHAPES = {
|
||
beehive: ['.11.', '1..1', '.11.'],
|
||
blinker: ['111'],
|
||
toad: ['.111', '111.'],
|
||
loaf: ['.11.', '1..1', '.1.1', '..1.'],
|
||
pulsar: [
|
||
'..111...111..',
|
||
'.............',
|
||
'1....1.1....1',
|
||
'1....1.1....1',
|
||
'1....1.1....1',
|
||
'..111...111..',
|
||
'.............',
|
||
'..111...111..',
|
||
'1....1.1....1',
|
||
'1....1.1....1',
|
||
'1....1.1....1',
|
||
'.............',
|
||
'..111...111..'
|
||
],
|
||
gun: [
|
||
'........................1...........',
|
||
'......................1.1...........',
|
||
'............11......11............11',
|
||
'...........1...1....11............11',
|
||
'11........1.....1...11..............',
|
||
'11........1...1.11....1.1...........',
|
||
'..........1.....1.......1...........',
|
||
'...........1...1....................',
|
||
'............11......................'
|
||
]
|
||
};
|
||
|
||
// ASCII-форма → список клеток [x,y] (левый верхний угол bbox = (0,0)).
|
||
export function parseShape(rows) {
|
||
const cells = [];
|
||
for (let y = 0; y < rows.length; y++) {
|
||
const line = rows[y];
|
||
for (let x = 0; x < line.length; x++) if (line[x] === '1') cells.push([x, y]);
|
||
}
|
||
return cells;
|
||
}
|
||
|
||
// Габариты bbox набора клеток.
|
||
function bbox(cells) {
|
||
let w = 0, h = 0;
|
||
for (const [x, y] of cells) { if (x + 1 > w) w = x + 1; if (y + 1 > h) h = y + 1; }
|
||
return { w, h };
|
||
}
|
||
|
||
// mulberry32 — компактный seeded PRNG (детерминированный, без Math.random).
|
||
export function mulberry32(a) {
|
||
return function () {
|
||
a |= 0;
|
||
a = (a + 0x6D2B79F5) | 0;
|
||
let t = Math.imul(a ^ (a >>> 15), 1 | a);
|
||
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
|
||
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
|
||
};
|
||
}
|
||
|
||
const SEED = 0x5eed1234;
|
||
const LEVEL_COUNT = 96; // сгенерированных уровней
|
||
const ID_OFFSET = 4; // id = ID_OFFSET + g + 1 (id 5..100)
|
||
const FIRST_SIZE = 60; // размер первого сгенерированного уровня (после ручных 30/40/60/60)
|
||
const LAST_SIZE = 300; // размер последнего (максимум поля)
|
||
|
||
// Размер поля g-го сгенерированного уровня (g=0..95): монотонно от 60 до 300,
|
||
// чётный. Формула-ориентир из плана; монотонность дополнительно гарантируется
|
||
// накоплением максимума в generateLevels().
|
||
export function sizeFor(g) {
|
||
const raw = FIRST_SIZE + (LAST_SIZE - FIRST_SIZE) * Math.pow(g / (LEVEL_COUNT - 1), 1.25);
|
||
let s = Math.round(Math.round(raw) / 2) * 2; // чётный размер
|
||
if (s < FIRST_SIZE) s = FIRST_SIZE;
|
||
if (s > LAST_SIZE) s = LAST_SIZE;
|
||
return s;
|
||
}
|
||
|
||
// Бюджет игрока: растёт с размером поля.
|
||
export function budgetFor(size) {
|
||
let b = Math.round(size * 0.8 + 20);
|
||
if (b < 20) b = 20;
|
||
if (b > 350) b = 350;
|
||
return b;
|
||
}
|
||
|
||
// Сетка занятости: 1 — клетка фигуры. Фигуры не перекрываются и не соприкасаются
|
||
// (проверяем 8-окрестность каждой клетки), чтобы на поле читались отдельные фигуры.
|
||
function makeOccupancy(w, h) {
|
||
const occ = new Uint8Array(w * h);
|
||
return {
|
||
canPlace(cells, ox, oy) {
|
||
for (const [x, y] of cells) {
|
||
for (let dy = -1; dy <= 1; dy++) {
|
||
for (let dx = -1; dx <= 1; dx++) {
|
||
const nx = ox + x + dx, ny = oy + y + dy;
|
||
if (nx < 0 || ny < 0 || nx >= w || ny >= h) continue;
|
||
if (occ[ny * w + nx]) return false;
|
||
}
|
||
}
|
||
}
|
||
return true;
|
||
},
|
||
mark(cells, ox, oy) { for (const [x, y] of cells) occ[(oy + y) * w + (ox + x)] = 1; }
|
||
};
|
||
}
|
||
|
||
// Попытка поставить фигуру целиком в поле (детерминированная).
|
||
function tryPlace(cells, w, h, occ, rng) {
|
||
const bb = bbox(cells);
|
||
if (bb.w > w || bb.h > h) return null;
|
||
for (let attempt = 0; attempt < 200; attempt++) {
|
||
const ox = Math.floor(rng() * (w - bb.w + 1));
|
||
const oy = Math.floor(rng() * (h - bb.h + 1));
|
||
if (occ.canPlace(cells, ox, oy)) { occ.mark(cells, ox, oy); return { ox, oy }; }
|
||
}
|
||
return null;
|
||
}
|
||
|
||
// Дополняющие прямоугольники вокруг зоны (сверху/снизу/слева/справа):
|
||
// каждый целиком ВНЕ зоны — кандидат для гарантированной постановки врага вне зоны.
|
||
function complementRects(zone, w, h) {
|
||
const rects = [];
|
||
if (zone.y > 0) rects.push({ x: 0, y: 0, w: w, h: zone.y });
|
||
if (zone.y + zone.h < h) rects.push({ x: 0, y: zone.y + zone.h, w: w, h: h - (zone.y + zone.h) });
|
||
if (zone.x > 0) rects.push({ x: 0, y: 0, w: zone.x, h: h });
|
||
if (zone.x + zone.w < w) rects.push({ x: zone.x + zone.w, y: 0, w: w - (zone.x + zone.w), h: h });
|
||
return rects;
|
||
}
|
||
|
||
// Поставить фигуру ГАРАНТИРОВАННО вне зоны игрока (весь bbox — в одном из
|
||
// дополняющих прямоугольников). Фолбэк (null) — вызывающий ставит обычным способом.
|
||
function tryPlaceOutsideZone(cells, w, h, zone, occ, rng) {
|
||
const bb = bbox(cells);
|
||
const rects = complementRects(zone, w, h).filter(r => bb.w <= r.w && bb.h <= r.h);
|
||
if (!rects.length) return null;
|
||
for (let attempt = 0; attempt < 120; attempt++) {
|
||
const r = rects[Math.floor(rng() * rects.length)];
|
||
const ox = r.x + Math.floor(rng() * (r.w - bb.w + 1));
|
||
const oy = r.y + Math.floor(rng() * (r.h - bb.h + 1));
|
||
if (occ.canPlace(cells, ox, oy)) { occ.mark(cells, ox, oy); return { ox, oy }; }
|
||
}
|
||
return null;
|
||
}
|
||
|
||
// Тип зоны g-го уровня (детерминированно по g%8). Тип «всё поле» (kind 0) у
|
||
// СГЕНЕРИРОВАННЫХ уровней УБРАН: kind 0 перенаправлен в «центр» (см. makeZone),
|
||
// поэтому реально используются 7 типов: 1 половина (верх/низ), 2 ЦЕНТР,
|
||
// 3 левый-верхний угол, 4 правый-нижний угол, 5 узкая вертикальная полоса,
|
||
// 6 узкая горизонтальная полоса, 7 произвольный прямоугольник.
|
||
function zoneKind(g) { return g % 8; }
|
||
|
||
// Прямоугольник зоны уровня (в пределах поля), с seeded-вариацией внутри типа.
|
||
function makeZone(g, size, rng) {
|
||
const kind = zoneKind(g);
|
||
const W = size, H = size;
|
||
// kind 0 (исторически «всё поле») и kind 2 — оба дают ЦЕНТР. Центр не занимает
|
||
// всё поле и не расходует rng, поэтому замена kind 0 → центр меняет зону только
|
||
// у этих уровней, не сдвигая последовательность PRNG (раскладка врага остаётся).
|
||
if (kind === 0 || kind === 2) { // центр
|
||
const zw = Math.max(6, Math.round(W * 0.55));
|
||
const zh = Math.max(6, Math.round(H * 0.55));
|
||
return { x: Math.floor((W - zw) / 2), y: Math.floor((H - zh) / 2), w: zw, h: zh };
|
||
}
|
||
if (kind === 1) { // половина верх/низ
|
||
const zh = Math.max(6, Math.floor(H * 0.5));
|
||
const y = (g % 16 === 1) ? 0 : (H - zh);
|
||
return { x: 0, y, w: W, h: zh };
|
||
}
|
||
if (kind === 3) { // левый-верхний угол
|
||
const zw = Math.max(6, Math.min(W, Math.floor(W * (0.3 + rng() * 0.35))));
|
||
const zh = Math.max(6, Math.min(H, Math.floor(H * (0.3 + rng() * 0.35))));
|
||
return { x: 0, y: 0, w: zw, h: zh };
|
||
}
|
||
if (kind === 4) { // правый-нижний угол
|
||
const zw = Math.max(6, Math.min(W, Math.floor(W * (0.3 + rng() * 0.35))));
|
||
const zh = Math.max(6, Math.min(H, Math.floor(H * (0.3 + rng() * 0.35))));
|
||
return { x: W - zw, y: H - zh, w: zw, h: zh };
|
||
}
|
||
if (kind === 5) { // узкая вертикальная полоса
|
||
const zw = Math.max(3, Math.min(W, Math.floor(W * (0.12 + rng() * 0.15))));
|
||
const x = Math.floor(rng() * (W - zw + 1));
|
||
return { x, y: 0, w: zw, h: H };
|
||
}
|
||
if (kind === 6) { // узкая горизонтальная полоса
|
||
const zh = Math.max(3, Math.min(H, Math.floor(H * (0.12 + rng() * 0.15))));
|
||
const y = Math.floor(rng() * (H - zh + 1));
|
||
return { x: 0, y, w: W, h: zh };
|
||
}
|
||
// kind === 7 — произвольный прямоугольник
|
||
const zw = Math.max(6, Math.min(W, Math.floor(W * (0.25 + rng() * 0.45))));
|
||
const zh = Math.max(6, Math.min(H, Math.floor(H * (0.25 + rng() * 0.45))));
|
||
const x = Math.floor(rng() * (W - zw + 1));
|
||
const y = Math.floor(rng() * (H - zh + 1));
|
||
return { x, y, w: zw, h: zh };
|
||
}
|
||
|
||
// Сгенерировать один уровень (детерминированно; rng — общий на весь набор).
|
||
// g — индекс среди сгенерированных (0..95); size задаётся снаружи (монотонный график).
|
||
function genLevel(g, size, rng) {
|
||
const w = size, h = size;
|
||
const budget = budgetFor(size);
|
||
const many = (g % 4 === 1);
|
||
const zone = makeZone(g, size, rng);
|
||
// Враг «вне зоны» форсируем на части уровней (g%3==0), кроме слотов g%8==0:
|
||
// раньше это была зона «всё поле» (там форс был невозможен). Условие оставлено
|
||
// прежним, чтобы замена kind 0 → центр не сдвигала раскладку остальных уровней.
|
||
const wantOutside = (zoneKind(g) !== 0) && (g % 3 === 0);
|
||
|
||
const occ = makeOccupancy(w, h);
|
||
const cellsAll = [];
|
||
|
||
const shapeCount = Math.min(16, 3 + Math.floor(size / 30) + (many ? 2 : 0));
|
||
const wantPulsar = (g % 3 === 0) || many;
|
||
const wantGun = (g % 12 === 5) && (size >= 46);
|
||
|
||
let needOutside = wantOutside;
|
||
function addShape(type) {
|
||
const cells = parseShape(SHAPES[type]);
|
||
let pos = needOutside ? tryPlaceOutsideZone(cells, w, h, zone, occ, rng) : null;
|
||
if (pos) needOutside = false; // фигура вне зоны поставлена
|
||
else pos = tryPlace(cells, w, h, occ, rng);
|
||
if (!pos) return false;
|
||
for (const [x, y] of cells) cellsAll.push([pos.ox + x, pos.oy + y]);
|
||
return true;
|
||
}
|
||
|
||
// Ружьё ставим первым (самое крупное и капризное к месту), затем пульсар.
|
||
let placed = 0;
|
||
if (wantGun && addShape('gun')) placed++;
|
||
if (wantPulsar && addShape('pulsar')) placed++;
|
||
|
||
const pool = ['beehive', 'blinker', 'toad', 'loaf', 'beehive', 'toad'];
|
||
for (let k = 0; k < shapeCount * 4 && placed < shapeCount; k++) {
|
||
if (addShape(pool[Math.floor(rng() * pool.length)])) placed++;
|
||
}
|
||
|
||
const id = ID_OFFSET + g + 1;
|
||
return { id, name: 'Схема №' + id, w, h, wrap: false, budget, zone, cells: cellsAll };
|
||
}
|
||
|
||
// Печать одной записи в компактном формате cells: [[x,y], ...].
|
||
function formatLevel(lv) {
|
||
const cells = lv.cells.map(([x, y]) => '[' + x + ',' + y + ']').join(', ');
|
||
return [
|
||
" { id: " + lv.id + ", name: '" + lv.name + "', w: " + lv.w + ", h: " + lv.h +
|
||
', wrap: false, budget: ' + lv.budget + ',',
|
||
' zone: { x: ' + lv.zone.x + ', y: ' + lv.zone.y + ', w: ' + lv.zone.w + ', h: ' + lv.zone.h + ' },',
|
||
' cells: [' + cells + '] },'
|
||
].join('\n');
|
||
}
|
||
|
||
// Сгенерировать весь набор (детерминированно). Размеры не убывают: накопление
|
||
// максимума гарантирует монотонность даже если формула даст плато/дрейф.
|
||
export function generateLevels() {
|
||
const rng = mulberry32(SEED >>> 0);
|
||
const out = [];
|
||
let prev = 0;
|
||
for (let g = 0; g < LEVEL_COUNT; g++) {
|
||
let size = sizeFor(g);
|
||
if (size < prev) size = prev;
|
||
prev = size;
|
||
out.push(genLevel(g, size, rng));
|
||
}
|
||
return out;
|
||
}
|
||
|
||
// Валидация набора (для --check). Возвращает список ошибок (пустой = OK).
|
||
export function validate(levels) {
|
||
const errs = [];
|
||
if (levels.length !== LEVEL_COUNT) errs.push('уровней не ' + LEVEL_COUNT + ': ' + levels.length);
|
||
const kindSeen = new Set();
|
||
let outsideCount = 0, prevSize = 0;
|
||
levels.forEach((lv, g) => {
|
||
const expectedId = ID_OFFSET + g + 1;
|
||
if (lv.id !== expectedId) errs.push('L' + expectedId + ': id не ' + expectedId + ' (' + lv.id + ')');
|
||
if (!(Array.isArray(lv.cells) && lv.cells.length > 0)) errs.push('L' + lv.id + ': пустой враг');
|
||
for (const [x, y] of lv.cells) {
|
||
if (x < 0 || y < 0 || x >= lv.w || y >= lv.h) errs.push('L' + lv.id + ': клетка вне поля ' + x + ',' + y);
|
||
}
|
||
if (lv.zone.x < 0 || lv.zone.y < 0 || lv.zone.x + lv.zone.w > lv.w || lv.zone.y + lv.zone.h > lv.h) {
|
||
errs.push('L' + lv.id + ': зона вне поля');
|
||
}
|
||
// Наложение клеток врага недопустимо.
|
||
const seen = new Set();
|
||
for (const [x, y] of lv.cells) {
|
||
const key = x + ':' + y;
|
||
if (seen.has(key)) errs.push('L' + lv.id + ': наложение клеток в ' + key);
|
||
seen.add(key);
|
||
}
|
||
// Монотонность размеров.
|
||
if (lv.w !== lv.h) errs.push('L' + lv.id + ': поле не квадратное');
|
||
if (lv.w < prevSize) errs.push('L' + lv.id + ': размер ' + lv.w + ' меньше предыдущего ' + prevSize);
|
||
prevSize = lv.w;
|
||
// Типы зон и «враг вне зоны». У сгенерированных уровней зоны «всё поле» быть
|
||
// не должно (она осталась только у ручных «Разминки»/«Роя»).
|
||
if (lv.zone.w === lv.w && lv.zone.h === lv.h) {
|
||
errs.push('L' + lv.id + ': зона занимает всё поле (у сгенерированных запрещено)');
|
||
}
|
||
kindSeen.add(zoneKind(g));
|
||
const z = lv.zone;
|
||
const outside = lv.cells.some(([x, y]) => !(x >= z.x && x < z.x + z.w && y >= z.y && y < z.y + z.h));
|
||
if (outside) outsideCount++;
|
||
});
|
||
if (prevSize !== LAST_SIZE) errs.push('последний размер не ' + LAST_SIZE + ': ' + prevSize);
|
||
// У сгенерированных остаётся 7 типов зон (kind 0 перенаправлен в центр): 1..7.
|
||
for (let k = 1; k <= 7; k++) if (!kindSeen.has(k)) errs.push('не встретился тип зоны ' + k);
|
||
if (outsideCount < 1) errs.push('нет уровня с врагом вне зоны');
|
||
return errs;
|
||
}
|
||
|
||
// Печать блока целиком.
|
||
export function renderBlock(levels) {
|
||
return levels.map(formatLevel).join('\n');
|
||
}
|
||
|
||
function main() {
|
||
const levels = generateLevels();
|
||
const errs = validate(levels);
|
||
if (errs.length) {
|
||
console.error('gen-campaign-levels: ОШИБКИ:\n' + errs.join('\n'));
|
||
process.exit(1);
|
||
}
|
||
if (process.argv.includes('--check')) {
|
||
console.log('gen-campaign-levels: OK — ' + levels.length + ' уровней');
|
||
return;
|
||
}
|
||
// Шапка-маркер + сами записи (для вставки в CAMPAIGN_LEVELS после 4 ручных).
|
||
console.log(' // --- 96 сгенерированных уровней: tools/gen-campaign-levels.mjs (SEED 0x5eed1234) ---');
|
||
console.log(renderBlock(levels));
|
||
}
|
||
|
||
// Запуск как скрипт (при импорте для переиспользования формы main не выполняется).
|
||
if (process.argv[1] && fileURLToPath(import.meta.url) === process.argv[1]) main();
|