studio/src/editor/engine/robloxterrain/DensityGrid.js

/**
 * DensityGrid — хранилище для Roblox-style smooth terrain.
 *
 * Содержит два параллельных массива одного размера:
 *   - matData[idx]: Uint8 — id материала (0=пусто, 1+=palette[i])
 *   - densityData[idx]: Uint8 — плотность 0..255 (0=пусто, 255=solid)
 *     Промежуточные значения позволяют **плавные** поверхности
 *     (Surface Nets интерполирует позицию вершины).
 *
 * Размер ячейки — 4м (как Roblox). Карта 500×128×500 м = 125×32×125 = 500K
 * ячеек = 500 КБ matData + 500 КБ density = 1 МБ. Это в 200 раз компактнее
 * чем voxel-terrain старой системы на той же площади.
 *
 * Палитра — общая с TERRAIN_MATERIALS (`grass`, `rock`, `sand`, ...).
 *
 * Сериализация — компактный RLE (matData отдельно от density).
 */

import { TERRAIN_MATERIALS } from '../TerrainManager';

/** Размер одной ячейки в метрах. Roblox использует 4м. */
export const CELL_SIZE = 4;

/** Threshold: ячейка считается solid если density >= 128 (0..255). */
export const DENSITY_THRESHOLD = 128;

export class DensityGrid {
    /**
     * @param {Object} opts
     * @param {{x,y,z}} opts.origin — мировые координаты ячейки (0,0,0). Размер целочисленный (в cell-units, потом × CELL_SIZE = м).
     * @param {{x,y,z}} opts.size — размер в ячейках
     * @param {string[]} [opts.palette]
     */
    constructor(opts) {
        const { origin, size, palette } = opts;
        if (!origin || !size) throw new Error('DensityGrid: origin and size required');
        this.origin = { x: origin.x|0, y: origin.y|0, z: origin.z|0 };
        this.size = { x: size.x|0, y: size.y|0, z: size.z|0 };
        // Палитра по умолчанию: [пусто, и всё что есть в TERRAIN_MATERIALS]
        this.palette = palette ? palette.slice() : ['', ...Object.keys(TERRAIN_MATERIALS)];
        this._matIdByKey = new Map();
        for (let i = 0; i < this.palette.length; i++) {
            if (this.palette[i]) this._matIdByKey.set(this.palette[i], i);
        }
        // Strides для линейной индексации: data[z*sxy + y*sx + x]
        this._sx = this.size.x;
        this._sxy = this.size.x * this.size.y;
        const total = this.size.x * this.size.y * this.size.z;
        this.matData = new Uint8Array(total);
        this.densityData = new Uint8Array(total);
    }

    /** Линейный индекс. */
    _idx(ix, iy, iz) {
        return iz * this._sxy + iy * this._sx + ix;
    }

    /** В пределах ли grid. */
    inBounds(ix, iy, iz) {
        return ix >= 0 && ix < this.size.x
            && iy >= 0 && iy < this.size.y
            && iz >= 0 && iz < this.size.z;
    }

    /** Получить density (0..255). Вне bounds → 0. */
    getDensity(ix, iy, iz) {
        if (!this.inBounds(ix, iy, iz)) return 0;
        return this.densityData[this._idx(ix, iy, iz)];
    }

    /** Получить material-id (0=пусто). Вне bounds → 0. */
    getMatId(ix, iy, iz) {
        if (!this.inBounds(ix, iy, iz)) return 0;
        return this.matData[this._idx(ix, iy, iz)];
    }

    /** Получить material-key ('grass' и т.п.) или ''. */
    getMatKey(ix, iy, iz) {
        const m = this.getMatId(ix, iy, iz);
        return this.palette[m] || '';
    }

    /** Решение: считается ли ячейка "solid". */
    isSolid(ix, iy, iz) {
        return this.getDensity(ix, iy, iz) >= DENSITY_THRESHOLD;
    }

    /**
     * Установить density + material для ячейки.
     * @param {number} density 0..255
     * @param {string|null} matKey
     */
    set(ix, iy, iz, density, matKey) {
        if (!this.inBounds(ix, iy, iz)) return;
        const idx = this._idx(ix, iy, iz);
        this.densityData[idx] = Math.max(0, Math.min(255, density|0));
        if (matKey != null) {
            let m = this._matIdByKey.get(matKey);
            if (m === undefined) {
                if (this.palette.length >= 255) return;
                m = this.palette.length;
                this.palette.push(matKey);
                this._matIdByKey.set(matKey, m);
            }
            this.matData[idx] = m;
        }
        // Если density упал до 0 — обнуляем mat (логически empty).
        if (this.densityData[idx] === 0) this.matData[idx] = 0;
    }

    /** Очистить полностью. */
    clear() {
        this.matData.fill(0);
        this.densityData.fill(0);
    }

    /** Подсчёт solid-ячеек. */
    countSolid() {
        let n = 0;
        for (let i = 0; i < this.densityData.length; i++) {
            if (this.densityData[i] >= DENSITY_THRESHOLD) n++;
        }
        return n;
    }

    /** Преобразование cell-coord → world position center (метры). */
    cellToWorld(ix, iy, iz) {
        return {
            x: (this.origin.x + ix + 0.5) * CELL_SIZE,
            y: (this.origin.y + iy + 0.5) * CELL_SIZE,
            z: (this.origin.z + iz + 0.5) * CELL_SIZE,
        };
    }

    // =========================================================================
    // СЕРИАЛИЗАЦИЯ — RLE
    // =========================================================================

    serialize() {
        const matRLE = this._encodeRLE(this.matData);
        const densityRLE = this._encodeRLE(this.densityData);
        return {
            format: 'robloxterrain-v1',
            origin: this.origin,
            size: this.size,
            palette: this.palette,
            mat: this._uint8ToBase64(matRLE),
            density: this._uint8ToBase64(densityRLE),
        };
    }

    _encodeRLE(arr) {
        const buf = [];
        const N = arr.length;
        let i = 0;
        while (i < N) {
            const v = arr[i];
            let run = 1;
            while (i + run < N && arr[i + run] === v && run < 65535) run++;
            buf.push(run & 0xff, (run >> 8) & 0xff, v);
            i += run;
        }
        return new Uint8Array(buf);
    }

    static _decodeRLE(bytes, totalLength) {
        const out = new Uint8Array(totalLength);
        let outIdx = 0;
        let i = 0;
        while (i < bytes.length && outIdx < totalLength) {
            const run = bytes[i] | (bytes[i + 1] << 8);
            const v = bytes[i + 2];
            i += 3;
            for (let k = 0; k < run && outIdx < totalLength; k++) {
                out[outIdx++] = v;
            }
        }
        return out;
    }

    static deserialize(obj) {
        if (!obj || obj.format !== 'robloxterrain-v1') {
            throw new Error('DensityGrid: bad format ' + (obj?.format ?? 'undefined'));
        }
        const grid = new DensityGrid({
            origin: obj.origin,
            size: obj.size,
            palette: obj.palette,
        });
        const matRLE = DensityGrid._base64ToUint8(obj.mat);
        const densityRLE = DensityGrid._base64ToUint8(obj.density);
        const total = grid.matData.length;
        grid.matData = DensityGrid._decodeRLE(matRLE, total);
        grid.densityData = DensityGrid._decodeRLE(densityRLE, total);
        return grid;
    }

    _uint8ToBase64(arr) {
        let binary = '';
        const chunkSize = 8192;
        for (let i = 0; i < arr.length; i += chunkSize) {
            const chunk = arr.subarray(i, Math.min(i + chunkSize, arr.length));
            binary += String.fromCharCode.apply(null, chunk);
        }
        return btoa(binary);
    }

    static _base64ToUint8(b64) {
        const binary = atob(b64);
        const out = new Uint8Array(binary.length);
        for (let i = 0; i < binary.length; i++) out[i] = binary.charCodeAt(i);
        return out;
    }
}