Procedural Generation: Tạo Map Game Tự Động Với Thuật Toán

Procedural Generation: Tạo Map Game Tự Động Với Các Thuật Toán Kinh Điển

Procedural generation (PCG) là kỹ thuật sử dụng thuật toán để tạo nội dung game tự động thay vì thiết kế thủ công. Từ các dungeon ngẫu nhiên trong Diablo đến vũ trụ vô hạn trong No Man's Sky, PCG đã trở thành công cụ không thể thiếu trong game development hiện đại. Bài viết này sẽ hướng dẫn bạn các thuật toán PCG phổ biến nhất với code ví dụ bằng C# trong Unity. Khám phá thêm các dự án sử dụng procedural generation tại kho source game LamGame.

1. Perlin Noise Và Terrain Generation

Perlin Noise là thuật toán noise phổ biến nhất trong game development, được phát minh bởi Ken Perlin năm 1983. Khác với random noise thông thường (white noise) tạo ra các giá trị hoàn toàn ngẫu nhiên, Perlin Noise tạo ra các giá trị có tính liên tục - các điểm gần nhau có giá trị tương tự nhau, tạo ra pattern tự nhiên giống địa hình thực tế. Unity cung cấp sẵn hàm Mathf.PerlinNoise(x, y) trả về giá trị từ 0 đến 1.

Để tạo terrain phong phú hơn, chúng ta sử dụng kỹ thuật Fractal Brownian Motion (fBM) - chồng nhiều lớp Perlin Noise với tần số và biên độ khác nhau. Mỗi lớp gọi là một octave. Octave đầu tiên tạo hình dạng tổng thể (núi, thung lũng), các octave sau thêm chi tiết nhỏ hơn (đồi nhỏ, gồ ghề).

using UnityEngine;

public class TerrainGenerator : MonoBehaviour
{
    public int width = 256;
    public int height = 256;
    public float scale = 20f;
    public int octaves = 6;
    public float persistence = 0.5f;
    public float lacunarity = 2f;
    public int seed = 42;

    public float[,] GenerateHeightMap()
    {
        float[,] heightMap = new float[width, height];
        System.Random prng = new System.Random(seed);
        Vector2[] offsets = new Vector2[octaves];
        for (int i = 0; i < octaves; i++)
            offsets[i] = new Vector2(prng.Next(-100000, 100000),
                                     prng.Next(-100000, 100000));

        float maxHeight = 0f, minHeight = float.MaxValue;

        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                float amplitude = 1f, frequency = 1f, noiseHeight = 0f;
                for (int i = 0; i < octaves; i++)
                {
                    float sampleX = (x - width / 2f) / scale * frequency + offsets[i].x;
                    float sampleY = (y - height / 2f) / scale * frequency + offsets[i].y;
                    float perlinValue = Mathf.PerlinNoise(sampleX, sampleY) * 2 - 1;
                    noiseHeight += perlinValue * amplitude;
                    amplitude *= persistence;
                    frequency *= lacunarity;
                }
                heightMap[x, y] = noiseHeight;
                if (noiseHeight > maxHeight) maxHeight = noiseHeight;
                if (noiseHeight < minHeight) minHeight = noiseHeight;
            }
        }
        // Normalize về 0-1
        for (int y = 0; y < height; y++)
            for (int x = 0; x < width; x++)
                heightMap[x, y] = Mathf.InverseLerp(minHeight, maxHeight, heightMap[x, y]);

        return heightMap;
    }
}

Sau khi có height map, bạn có thể áp dụng các biome rules dựa trên độ cao và moisture map (một Perlin Noise map khác): vùng thấp + ẩm = đầm lầy, vùng thấp + khô = sa mạc, vùng cao = núi tuyết. Kỹ thuật này tạo ra world map đa dạng và tự nhiên.

2. Wave Function Collapse (WFC)

Wave Function Collapse là thuật toán PCG hiện đại và mạnh mẽ, lấy cảm hứng từ cơ học lượng tử. WFC hoạt động bằng cách: bắt đầu với một grid mà mỗi cell có thể là bất kỳ tile nào (superposition), sau đó lần lượt "collapse" từng cell - chọn một tile cụ thể và propagate constraints đến các cell lân cận. Quá trình lặp lại cho đến khi tất cả cell đều được xác định.

WFC đặc biệt phù hợp cho việc tạo level design tự động vì nó đảm bảo kết quả luôn hợp lệ theo các rules đã định nghĩa. Ví dụ, nếu bạn định nghĩa rằng tile đường phải nối với tile đường, tile cỏ nối với tile cỏ hoặc tile đường, WFC sẽ tự động tạo ra map với đường đi hợp lý mà không cần logic phức tạp.

public class SimplifiedWFC
{
    private int width, height;
    private List<int>[,] possibilities;
    private Dictionary<int, HashSet<int>>[] rules; // rules cho 4 hướng

    public void Collapse()
    {
        while (HasUncollapsedCells())
        {
            // 1. Tìm cell có ít khả năng nhất (lowest entropy)
            var (cx, cy) = FindLowestEntropyCell();
            // 2. Chọn ngẫu nhiên một tile từ các khả năng
            int chosen = ChooseWeightedRandom(possibilities[cx, cy]);
            possibilities[cx, cy] = new List<int> { chosen };
            // 3. Propagate constraints đến neighbors
            Propagate(cx, cy);
        }
    }

    private void Propagate(int x, int y)
    {
        Queue<(int, int)> stack = new Queue<(int, int)>();
        stack.Enqueue((x, y));
        while (stack.Count > 0)
        {
            var (cx, cy) = stack.Dequeue();
            for (int dir = 0; dir < 4; dir++)
            {
                int nx = cx + DX[dir], ny = cy + DY[dir];
                if (!InBounds(nx, ny)) continue;
                // Lọc bỏ các tile không tương thích
                int before = possibilities[nx, ny].Count;
                possibilities[nx, ny].RemoveAll(tile =>
                    !IsCompatible(possibilities[cx, cy], tile, dir));
                if (possibilities[nx, ny].Count < before)
                    stack.Enqueue((nx, ny));
            }
        }
    }
}

3. BSP (Binary Space Partitioning) Dungeon Generation

BSP là thuật toán kinh điển để tạo dungeon layout cho roguelike game. Ý tưởng rất đơn giản: bắt đầu với một hình chữ nhật lớn (toàn bộ dungeon), chia đôi nó theo chiều ngang hoặc dọc một cách ngẫu nhiên, tiếp tục chia đôi các phần con cho đến khi đạt kích thước tối thiểu. Mỗi leaf node trở thành một phòng, sau đó kết nối các phòng sibling bằng hành lang.

BSP tạo ra dungeon có cấu trúc rõ ràng với các phòng không chồng lấn và luôn có đường đi giữa mọi phòng. Thuật toán này dễ implement và cho kết quả tốt, đặc biệt phù hợp cho game roguelike truyền thống. Bạn có thể thêm variation bằng cách randomize kích thước phòng trong mỗi partition, thêm các phòng đặc biệt (boss room, treasure room), hoặc kết hợp với cellular automata để tạo cave-like areas bên trong phòng.

public class BSPDungeon
{
    public class BSPNode
    {
        public RectInt area;
        public BSPNode left, right;
        public RectInt? room;
    }

    public BSPNode Generate(RectInt area, int minSize)
    {
        BSPNode node = new BSPNode { area = area };
        if (area.width < minSize * 2 && area.height < minSize * 2)
        {
            // Leaf node - tạo phòng
            int roomW = Random.Range(minSize, area.width - 2);
            int roomH = Random.Range(minSize, area.height - 2);
            int roomX = area.x + Random.Range(1, area.width - roomW - 1);
            int roomY = area.y + Random.Range(1, area.height - roomH - 1);
            node.room = new RectInt(roomX, roomY, roomW, roomH);
            return node;
        }
        bool splitH = area.width > area.height
            ? false : area.height > area.width ? true : Random.value > 0.5f;
        if (splitH)
        {
            int split = Random.Range(minSize, area.height - minSize);
            node.left = Generate(new RectInt(area.x, area.y, area.width, split), minSize);
            node.right = Generate(new RectInt(area.x, area.y + split, area.width, area.height - split), minSize);
        }
        else
        {
            int split = Random.Range(minSize, area.width - minSize);
            node.left = Generate(new RectInt(area.x, area.y, split, area.height), minSize);
            node.right = Generate(new RectInt(area.x + split, area.y, area.width - split, area.height), minSize);
        }
        return node;
    }
}

4. Cellular Automata Cho Cave Generation

Cellular Automata là thuật toán đơn giản nhưng hiệu quả để tạo hang động tự nhiên. Bắt đầu với một grid ngẫu nhiên (mỗi cell có 45-55% chance là wall), sau đó áp dụng rules lặp đi lặp lại: nếu một cell có từ 4 neighbors trở lên là wall thì nó trở thành wall, ngược lại trở thành floor. Sau 4-5 iterations, pattern ngẫu nhiên ban đầu sẽ tự tổ chức thành các cave tự nhiên với đường viền mượt mà.

Kỹ thuật này tạo ra cave trông rất organic và tự nhiên, khác biệt hoàn toàn với các phòng hình chữ nhật của BSP. Tuy nhiên, cellular automata không đảm bảo tất cả các vùng floor đều kết nối với nhau. Bạn cần thêm bước flood fill để xác định các vùng riêng biệt và kết nối chúng bằng tunnel, hoặc loại bỏ các vùng nhỏ quá.

5. Kết Hợp Các Thuật Toán

Sức mạnh thực sự của PCG nằm ở việc kết hợp nhiều thuật toán. Ví dụ, bạn có thể sử dụng BSP để tạo layout tổng thể của dungeon, cellular automata để tạo chi tiết bên trong mỗi phòng, Perlin Noise để quyết định biome và decoration placement, và WFC để tạo các pattern trang trí trên tường và sàn. Mỗi thuật toán đóng vai trò một layer trong pipeline generation, tạo ra kết quả phong phú và đa dạng hơn nhiều so với sử dụng đơn lẻ.

Một tip quan trọng khi làm PCG: luôn sử dụng seed-based random thay vì random thuần túy. Điều này cho phép bạn reproduce cùng một kết quả với cùng seed, rất hữu ích cho debugging, sharing level giữa players (daily challenge), và đảm bảo deterministic behavior trong multiplayer. Trong C#, sử dụng System.Random(seed) thay vì UnityEngine.Random khi cần reproducibility.

Procedural generation mở ra khả năng vô hạn cho game content. Hãy bắt đầu với một thuật toán đơn giản, hiểu rõ cách nó hoạt động, rồi dần dần kết hợp và mở rộng. Nếu bạn muốn tìm hiểu thêm hoặc tìm kiếm cơ hội trong lĩnh vực game development, hãy ghé thăm trang việc làm game của LamGame.