Создание игровых карт на основе диаграмм Вороного

Я написал статью о генерации полигональных карт при помощи диаграмм Вороного, но не объяснил, как писать её код. В этой статье я расскажу об основах создания вот таких карт с примерами кода на Javascript:

Многие люди хотят самостоятельно писать шум Вороного и симплекс-шум. Я обычно пользуюсь библиотеками. Вот чем я буду пользоваться:

1. симплекс-шум: jwagner/simplex-noise.
2. Вороной: mapbox/delaunator.

Если вы не работаете с Javascript, то для большинства языков тоже существуют библиотеки шума, а Delaunator был портирован на многие языки.

Первым делом нужно загрузить библиотеки. Можно использовать npm или yarn, но в этой статье я буду загружать их при помощи тегов script. В документации Delaunator есть информация об этом, но в библиотеке симплекс-шума её нет, поэтому я использую для их загрузки unpkg:

<script src="https://unpkg.com/simplex-noise@2.4.0/simplex-noise.js"></script>
<script src="https://unpkg.com/delaunator@4.0.1/delaunator.min.js"></script>

Я сохранил свой исходный код в файл и вставил его для отрисовки:

<canvas id="map" width="1000" height="1000"></canvas>
<script src="voronoi-maps-tutorial.js"></script>

1. Порождающие точки

В случае карты с квадратными тайлами мы бы обошли её в цикле и сгенерировали бы тайл для каждой точки:

const GRIDSIZE = 25;
let points = [];
for (let x = 0; x <= GRIDSIZE; x++) {
    for (let y = 0; y <= GRIDSIZE; y++) {
        points.push({x, y});
    }
}

В случае Вороного нам нужно указывать местоположения полигонов. Хотя для Вороного мы можем использовать те же точки, одна из причин использования Вороного заключается в разрушении одинаковых линий сетки. Давайте добавим координатам флуктуации:

const GRIDSIZE = 25;
const JITTER = 0.5;
let points = [];
for (let x = 0; x <= GRIDSIZE; x++) {
    for (let y = 0; y <= GRIDSIZE; y++) {
        points.push({x: x + JITTER * (Math.random() - Math.random()),
                     y: y + JITTER * (Math.random() - Math.random())});
    }
}

Чтобы увидеть, выглядит ли это красиво, давайте их отрисуем:

function drawPoints(canvas, points) {
    let ctx = canvas.getContext('2d');
    ctx.save();
    ctx.scale(canvas.width / GRIDSIZE, canvas.height / GRIDSIZE);
    ctx.fillStyle = "hsl(0, 50%, 50%)";
    for (let {x, y} of points) {
        ctx.beginPath();
        ctx.arc(x, y, 0.1, 0, 2*Math.PI);
        ctx.fill();
    }
    ctx.restore();
}

drawPoints(document.getElementById("diagram-points"), points);

Точки с флуктуациями

Эти точки можно сделать лучше, но пока это множество выглядит вполне приемлемо.

2. Ячейки Вороного

Теперь мы можем создать ячейки Вороного на основе каждой из порождающих точек. Не совсем очевидно, что библиотеку Delaunator для построения триангуляции Делоне может создавать ячейки Вороного. Чтобы понять, почему это так, можно прочитать руководство по Delaunator, в котором показан пример кода для построения ячеек Вороного (без усечения).

Первым этапом будет выполнение алгоритма триангуляции Делоне:

let delaunay = Delaunator.from(points, loc => loc.x, loc => loc.y);

Затем нужно вычислить центры описанных окружностей треугольников. По различным причинам я буду использовать вариацию Вороного, использующую центры тяжести. Код этой статьи будет работать и с центрами описанных окружностей, и с центрами тяжести, так что можете поэкспериментировать с разными центрами треугольников и посмотреть, что подходит вам больше.

function calculateCentroids(points, delaunay) {
    const numTriangles = delaunay.halfedges.length / 3;
    let centroids = [];
    for (let t = 0; t < numTriangles; t++) {
        let sumOfX = 0, sumOfY = 0;
        for (let i = 0; i < 3; i++) {
            let s = 3*t + i;
            let p = points[delaunay.triangles[s]];
            sumOfX += p.x;
            sumOfY += p.y;
        }
        centroids[t] = {x: sumOfX / 3, y: sumOfY / 3};
    }
    return centroids;
}

Давайте создадим объект, чтобы хранить всё в нём:

let map = {
    points,
    numRegions: points.length,
    numTriangles: delaunay.halfedges.length / 3,
    numEdges: delaunay.halfedges.length,
    halfedges: delaunay.halfedges,
    triangles: delaunay.triangles,
    centers: calculateCentroids(points, delaunay)
};

И теперь мы можем отрисовывать ячейки Вороного. Этот код основан на коде из руководства по Delaunator

function triangleOfEdge(e)  { return Math.floor(e / 3); }
function nextHalfedge(e) { return (e % 3 === 2) ? e - 2 : e + 1; }

function drawCellBoundaries(canvas, map) {
    let {points, centers, halfedges, triangles, numEdges} = map;
    let ctx = canvas.getContext('2d');
    ctx.save();
    ctx.scale(canvas.width / GRIDSIZE, canvas.height / GRIDSIZE);
    ctx.lineWidth = 0.02;
    ctx.strokeStyle = "black";
    for (let e = 0; e < numEdges; e++) {
        if (e < delaunay.halfedges[e]) {
            const p = centers[triangleOfEdge(e)];
            const q = centers[triangleOfEdge(halfedges[e])];
            ctx.beginPath();
            ctx.moveTo(p.x, p.y);
            ctx.lineTo(q.x, q.y);
            ctx.stroke();
        }
    }
    ctx.restore();
}
drawCellBoundaries(document.getElementById("diagram-boundaries"), map);

Границы ячеек

Выглядит вполне неплохо, за исключением краёв карты, но давайте пока о них забудем и найдём решение этой проблемы позже.

3. Форма острова

Следующий этап заключается в добавлении карты высот. Я адаптирую методики, использованные в моей статье о создании рельефа из шума [перевод на Хабре]. Мы будем назначать высоту не каждому тайлу, а каждой ячейке Вороного. Давайте поместим их в массив, индексированный по номеру ячейки.

const WAVELENGTH = 0.5;
function assignElevation(map) {
    const noise = new SimplexNoise();
    let {points, numRegions} = map;
    let elevation = [];
    for (let r = 0; r < numRegions; r++) {
        let nx = points[r].x / GRIDSIZE - 1/2,
            ny = points[r].y / GRIDSIZE - 1/2;
        // start with noise:
        elevation[r] = (1 + noise.noise2D(nx / WAVELENGTH, ny / WAVELENGTH)) / 2;
        // modify noise to make islands:
        let d = 2 * Math.max(Math.abs(nx), Math.abs(ny)); // should be 0-1
        elevation[r] = (1 + elevation[r] - d) / 2;
    }
    return elevation;
}

map.elevation = assignElevation(map);

Отрисуем эти ячейки. Я снова воспользуюсь кодом на основе руководства по Delaunator.

function edgesAroundPoint(delaunay, start) {
    const result = [];
    let incoming = start;
    do {
        result.push(incoming);
        const outgoing = nextHalfedge(incoming);
        incoming = delaunay.halfedges[outgoing];
    } while (incoming !== -1 && incoming !== start);
    return result;
}

function drawCellColors(canvas, map, colorFn) {
    let ctx = canvas.getContext('2d');
    ctx.save();
    ctx.scale(canvas.width / GRIDSIZE, canvas.height / GRIDSIZE);
    let seen = new Set();  // of region ids
    let {triangles, numEdges, centers} = map;
    for (let e = 0; e < numEdges; e++) {
        const r = triangles[nextHalfedge(e)];
        if (!seen.has(r)) {
            seen.add(r);
            let vertices = edgesAroundPoint(delaunay, e)
                .map(e => centers[triangleOfEdge(e)]);
            ctx.fillStyle = colorFn(r);
            ctx.beginPath();
            ctx.moveTo(vertices[0].x, vertices[0].y);
            for (let i = 1; i < vertices.length; i++) {
                ctx.lineTo(vertices[i].x, vertices[i].y);
            }
            ctx.fill();
        }
    }
}

drawCellColors(
    document.getElementById("diagram-cell-elevations"),
    map,
    r => map.elevation[r] < 0.5? "hsl(240, 30%, 50%)" : "hsl(90, 20%, 50%)"
);

Высоты ячеек

Пусть неидеально, зато сработало. Чтобы получить нужные формы, придётся немного поднастроить параметры, но основа у нас уже есть.

4. Биомы

Далее мы создадим биомы. Я снова воспользуюсь методиками из моей статьи о создании рельефа из шума [перевод на Хабре]. Основной принцип заключается в добавлении второй карты шума:

function assignMoisture(map) {
    const noise = new SimplexNoise();
    let {points, numRegions} = map;
    let moisture = [];
    for (let r = 0; r < numRegions; r++) {
        let nx = points[r].x / GRIDSIZE - 1/2,
            ny = points[r].y / GRIDSIZE - 1/2;
        moisture[r] = (1 + noise.noise2D(nx / WAVELENGTH, ny / WAVELENGTH)) / 2;
    }
    return moisture;
}

map.moisture = assignMoisture(map);

Затем мы можем использовать карту высот и карту влажности для выбора цвета биома:

function biomeColor(map, r) {
    let e = (map.elevation[r] - 0.5) * 2,
        m = map.moisture[r];
    if (e < 0.0) {
        r = 48 + 48*e;
        g = 64 + 64*e;
        b = 127 + 127*e;
    } else {
        m = m * (1-e); e = e**4; // tweaks
        r = 210 - 100 * m;
        g = 185 - 45 * m;
        b = 139 - 45 * m;
        r = 255 * e + r * (1-e),
        g = 255 * e + g * (1-e),
        b = 255 * e + b * (1-e);
    }
    return `rgb(${r|0}, ${g|0}, ${b|0})`;
}

drawCellColors(
    document.getElementById("diagram-cell-biomes"),
    map,
    r => biomeColor(map, r)
);

Биомы

О, выглядит вполне приемлемо!

5. Дальнейшие шаги

Надеюсь, это вам поможет с началом проекта, но нужно ещё многое сделать.

Например, можно было заметить, что карта в начале статьи имеет прямые края, а у созданной нами края неровные. Я сделал так: добавил новые точки вне карты, чтобы области по краям карты имели ещё одну точку за краями, с которой могли бы соединяться.

points.push({x: -10, y: GRIDSIZE/2});
points.push({x: GRIDSIZE+10, y: GRIDSIZE/2});
points.push({y: -10, x: GRIDSIZE/2});
points.push({y: GRIDSIZE+10, x: GRIDSIZE/2});
points.push({x: -10, y: -10});
points.push({x: GRIDSIZE+10, y: GRIDSIZE+10});
points.push({y: -10, x: GRIDSIZE+10});
points.push({y: GRIDSIZE+10, x: -10});

Можно реализовать и другие улучшения:

• упорядочить код так, чтобы его можно было встроить в ваш собственный проект.
• улучшить расположение точек при помощи более качественной флуктуации или «синего шума» на основе poisson-disk-sampling или этого кода Мартина Робертса
• избавиться от странных форм по краям карты или усекать их
• использовать формулу получше, чтобы изменить форму острова
• использовать больше октав для шума высот и влажности; см. моё руководство по шуму для карт

Я описал множество других функций и возможностей для экспериментов в своей статье о генераторе полигональных карт.

Весь код генерации диаграмм из этой статьи находится здесь: voronoi-maps-tutorial.js. Я использовал org-mode редактора emacs, чтобы извлечь код из этой страницы в файл javascript, а затем запустил файл javascript на странице для генерации диаграмм. Код, приведённый в статье, идентичен с исполняемым.