Giới thiệu dự án

Bối cảnh ngành và thực trạng bài toán

Thị trường trò chơi điện tử toàn cầu và Việt Nam đang chứng kiến sự tăng trưởng vượt bậc với doanh thu tại Việt Nam đã vượt mốc 500 triệu USD, tiếp cận hơn 50% dân số, trong đó nhóm tuổi 17–30 chiếm tới 65%. Sự cạnh tranh khốc liệt đòi hỏi các studio game phải liên tục phát hành nội dung mới, đặc biệt là hệ thống màn chơi (levels/maps) đa dạng để gia tăng vòng đời sản phẩm (player retention).

Tuy nhiên, quy trình thiết kế màn chơi thủ công (manual level design) truyền thống bộc lộ nhiều điểm nghẽn nghiêm trọng:

  • Chi phí thời gian và nhân lực cao: Thiết kế và cân bằng một bản đồ 3D thủ công tiêu tốn trung bình từ 40 đến 80 giờ làm việc của chuyên viên thiết kế màn chơi (Level Designer).
  • Thiếu tính linh hoạt: Bản đồ tĩnh dễ gây cảm giác nhàm chán, làm giảm giá trị chơi lại (replayability).
  • Rủi ro lỗi thiết kế: Nguy cơ phát sinh các điểm nghẽn logic (unreachable areas, soft-locks) khi mở rộng quy mô màn chơi.

Định biểu vấn đề (Problem Statement)

Đồ án giải quyết bài toán cốt lõi: Làm thế nào để tự động hóa quy trình tạo lập màn chơi 3D (Procedural Content Generation - PCG) đảm bảo tính ngẫu nhiên, tự nhiên về mặt địa hình, đồng thời đảm bảo 100% khả năng vượt màn (traversability) và phân bố thử thách (kẻ địch, bẫy) một cách khoa học?

graph LR
    A[Perlin Noise Matrix] --> B[BFS Landmass & Void Detection]
    B --> C[A* Critical Path Generation]
    C --> D[Procedural Obstacle Placement]
    B --> E[5-Zone Enemy Patrol Partitioning]
    D --> F[Complete Playable Level]
    E --> F

Mục tiêu dự án

  1. Nghiên cứu và tích hợp chuỗi thuật toán: Kết hợp Perlin Noise, Breadth-First Search (BFS), và A* Pathfinding để tạo lập bản đồ tự động.
  2. Đề xuất thuật toán phân vùng tuần tra: Phát triển giải pháp phân chia mảng kiến tạo thành 5 phân vùng logic cho hệ thống AI kẻ địch.
  3. Hiện thực hóa trò chơi bắn súng 3D góc nhìn Top-down (Top-down Shooter): Xây dựng gameplay hoàn chỉnh trên Unity Engine với 3 bộ chủ đề môi trường (Map Đỏ, Map Xanh Biển, Map Vàng/Xanh Lá), 5 lớp kẻ địch và 9 loại cạm bẫy tương tác.

Phương pháp tiếp cận và kết quả kỳ vọng

  • Tiếp cận kỹ thuật: Ứng dụng mô hình sinh dữ liệu thủ tục từng tầng (Layered Procedural Generation Pipeline). Địa hình nền sinh từ ma trận nhiễu Perlin cải tiến hàm Fade bậc 5; thuật toán BFS tách lọc mảng kiến tạo hợp lệ; thuật toán A* tìm đường đi ngắn nhất giữa điểm Spawn và Exit để rải bẫy chiến thuật; thuật toán phân vùng tự phát triển tối ưu hóa hành vi AI.
  • Chỉ số đo lường kỳ vọng:
    • Thời gian sinh map $\le 250\text{ ms}$ trên lưới kích thước $100 \times 100$.
    • Tỷ lệ màn chơi đảm bảo thông lộ (Traversability Rate) đạt $100%$.
    • Tối ưu hiệu năng duy trì ổn định $\ge 60\text{ FPS}$ trên cấu hình máy tính tầm trung.

Phạm vi và giới hạn

  • Môi trường vận hành: Hệ điều hành Windows 10/11 và macOS.
  • Không gian game: Bản đồ 3D góc nhìn bao quát từ trên xuống (Top-down perspective).
  • Giới hạn: Tập trung vào bản đồ đơn tầng (single-floor topological grids), chưa áp dụng cho môi trường địa hình đa tầng phức tạp (multi-layer vertical topology).

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

So sánh các phương pháp xây dựng màn chơi phổ biến:

Tiêu chí Thiết kế thủ công (Manual) Thuật toán BSP / Random Walk Giải pháp kết hợp (Đề tài đề xuất)
Thời gian tạo map 40 - 80 giờ/map < 50 ms < 200 ms
Tính đa dạng Giới hạn bởi nhân lực Cao nhưng rời rạc, cứng nhắc Cao, địa hình mượt mà tự nhiên
Độ tin cậy đường đi 100% (Kiểm thử thủ công) Dễ tắc nghẽn logic 100% (Xác thực tự động qua BFS & A*)
Phân bổ bẫy & AI Thủ công từng vị trí Phân bố ngẫu nhiên phân tán Đặt bẫy dọc theo đường đi chiến thuật, AI tuần tra theo cụm

Phân loại yêu cầu người dùng theo mô hình MoSCoW

  • Must have: Hệ thống sinh địa hình ngẫu nhiên qua Perlin Noise; trích xuất mảng kiến tạo bằng BFS; kết nối điểm đầu - điểm cuối bằng A*; hệ thống điều khiển nhân vật và bắn súng cơ bản.
  • Should have: Hệ thống 9 loại bẫy môi trường theo 3 theme; 5 loại AI kẻ địch với vũ khí và hành vi riêng biệt; cơ chế Save/Load game.
  • Could have: Tùy biến âm lượng âm thanh (SFX/BGM); bảng chọn nhân vật với chỉ số đặc biệt.
  • Won't have (giai đoạn này): Chế độ nhiều người chơi (Multiplayer); tạo địa hình 3D đa tầng (Verticality).

Thiết kế hệ thống

Kiến trúc tổng thể

classDiagram
    class MapGenerator {
        +int width
        +int height
        +float noiseScale
        +GenerateMap()
        +ExtractLargestLandmass()
        +CreatePatrolZones()
    }
    class PathfindingSystem {
        +FindPath(Vector2Int start, Vector2Int end)
        +CalculateHeuristic(Node a, Node b)
    }
    class ObstaclePlacer {
        +PlaceTrapsAlongPath(List~Node~ path)
        +SpawnHazard(Vector3 position, TrapType type)
    }
    class EnemyManager {
        +List~PatrolZone~ zones
        +SpawnEnemiesInZones()
    }
    MapGenerator --> PathfindingSystem : Uses
    MapGenerator --> ObstaclePlacer : Triggers
    MapGenerator --> EnemyManager : Configures

Technology Stack

  • Game Engine: Unity Engine Version 2022.3.x LTS (Long Term Support).
  • Ngôn ngữ lập trình: C# (.NET Standard 2.1 / C# 9.0).
  • Hệ thống render: Universal Render Pipeline (URP).
  • Quản lý phiên bản & Dự án: Git, GitHub, Trello.
  • Lưu trữ dữ liệu: Binary Formatter & JSON Serialization cho cấu hình ScriptableObjects và hệ thống Save/Load màn chơi.

Phương pháp luận (Methodology)

Dự án áp dụng mô hình phát triển Agile/Scrum với chu kỳ Sprint 2 tuần:

  • Milestone 1 (Tuần 1–4): Nghiên cứu lý thuyết toán học (Perlin Noise, BFS, A*), xây dựng khung cơ bản của Map Generator trên môi trường Unity.
  • Milestone 2 (Tuần 5–8): Hiện thực thuật toán trích xuất mảng kiến tạo, thuật toán A* định vị đường đi, thuật toán đề xuất phân vùng tuần tra cho AI.
  • Milestone 3 (Tuần 9–12): Thiết kế 3 map theme, xây dựng hệ thống bẫy, tích hợp 5 loại AI và cơ chế vũ khí.
  • Milestone 4 (Tuần 13–15): Kiểm thử tích hợp, tối ưu hóa bộ nhớ, cân bằng gameplay và hoàn thiện báo cáo khóa luận.

Đánh giá và giảm thiểu rủi ro

  • Rủi ro 1: Bản đồ sinh ra bị cô lập không có đường đến đích.
    • Giải pháp: Dùng BFS xác định mảng kiến tạo lớn nhất, chỉ định điểm bắt đầu tại $10%$ phần tử đầu và đích đến tại $10%$ phần tử cuối, sau đó chạy A* xác thực trước khi kết xuất (render).
  • Rủi ro 2: Suy giảm khung hình khi số lượng chướng ngại vật và AI tăng cao.
    • Giải pháp: Áp dụng kỹ thuật Object Pooling cho đạn, hiệu ứng hạt (Particle Effects) và bẫy; giới hạn tầm quét AI bằng DETECT_RANGE.

Hiện thực hóa và kết quả

Chi tiết thuật toán then chốt

1. Sinh địa hình với Perlin Noise và hàm Fade bậc 5

Khởi tạo ma trận kích thước $N \times N$, gán các gradient vector ngẫu nhiên tại các nút lưới. Để loại bỏ hiện tượng giật cục tại các biên ô vuông, áp dụng hàm làm mịn (Smoothstep cải tiến của Ken Perlin):

$$Fade(t) = 6t^5 - 15t^4 + 10t^3$$

Hàm kết hợp hai chiều (Joint Fade): $JointFade(x, y) = Fade(x) \cdot Fade(y)$. Giá trị độ cao sau nội suy được so sánh với ngưỡng cắt $Threshold = 0.5$: Nếu $Noise(x, y) \ge 0.5$, ô được định dạng là mặt đất; ngược lại là vực thẳm.

public static float ImprovedFade(float t) {
    return t * t * t * (t * (t * 6 - 15) + 10);
}

public float CalculateNoise(float x, float y, Vector2[,] gradients) {
    int x0 = Mathf.FloorToInt(x);
    int x1 = x0 + 1;
    int y0 = Mathf.FloorToInt(y);
    int y1 = y0 + 1;

    float sx = ImprovedFade(x - (float)x0);
    float sy = ImprovedFade(y - (float)y0);

    float n0 = Vector2.Dot(gradients[x0, y0], new Vector2(x - x0, y - y0));
    float n1 = Vector2.Dot(gradients[x1, y0], new Vector2(x - x1, y - y0));
    float ix0 = Mathf.Lerp(n0, n1, sx);

    n0 = Vector2.Dot(gradients[x0, y1], new Vector2(x - x0, y - y1));
    n1 = Vector2.Dot(gradients[x1, y1], new Vector2(x - x1, y - y1));
    float ix1 = Mathf.Lerp(n0, n1, sx);

    return Mathf.Lerp(ix0, ix1, sy);
}

2. Nhận diện mảng kiến tạo và vùng rơi bằng BFS

Sử dụng cấu trúc dữ liệu hàng đợi Queue<Vector2Int> và ma trận đánh dấu bool[,] visited với độ phức tạp $O(V + E)$ để gom nhóm các ô mặt đất liền kề thành các mảng kiến tạo độc lập (connected components).

public List<List<Vector2Int>> ExtractLandmasses(int[,] mapMatrix, int width, int height) {
    List<List<Vector2Int>> landmasses = new List<List<Vector2Int>>();
    bool[,] visited = new bool[width, height];

    for (int x = 0; x < width; x++) {
        for (int y = 0; y < height; y++) {
            if (mapMatrix[x, y] == 1 && !visited[x, y]) {
                List<Vector2Int> component = new List<Vector2Int>();
                Queue<Vector2Int> queue = new Queue<Vector2Int>();
                queue.Enqueue(new Vector2Int(x, y));
                visited[x, y] = true;

                while (queue.Count > 0) {
                    Vector2Int curr = queue.Dequeue();
                    component.Add(curr);
                    foreach (var neighbor in GetNeighbors(curr, width, height)) {
                        if (mapMatrix[neighbor.x, neighbor.y] == 1 && !visited[neighbor.x, neighbor.y]) {
                            visited[neighbor.x, neighbor.y] = true;
                            queue.Enqueue(neighbor);
                        }
                    }
                }
                landmasses.Add(component);
            }
        }
    }
    return landmasses;
}

3. Tìm đường A* và bố trí cạm bẫy chiến thuật

Thuật toán A* sử dụng hàm đánh giá $f(n) = g(n) + h(n)$, trong đó $h(n)$ là khoảng cách Euclidean:

$$h(n) = \sqrt{(x_n - x_{target})^2 + (y_n - y_{target})^2}$$

Sau khi tìm được đường đi ngắn nhất nối giữa Start và Exit, hệ thống rải bẫy (Bẫy búa, Thảm lửa, Băng đẩy...) bám theo tọa độ các ô lân cận đường đi chính, đảm bảo ép người chơi phải né tránh trong quá trình di chuyển.

public List<Vector2Int> FindPathAStar(Vector2Int start, Vector2Int target, int[,] grid) {
    PriorityQueue<Node> openSet = new PriorityQueue<Node>();
    HashSet<Vector2Int> closedSet = new HashSet<Vector2Int>();
    Node startNode = new Node(start, 0, Vector2Int.Distance(start, target), null);
    openSet.Enqueue(startNode, startNode.F);

    while (openSet.Count > 0) {
        Node current = openSet.Dequeue();
        if (current.Position == target) return RetracePath(current);
        closedSet.Add(current.Position);

        foreach (Vector2Int neighborPos in GetWalkableNeighbors(current.Position, grid)) {
            if (closedSet.Contains(neighborPos)) continue;
            float newG = current.G + 1f;
            float h = Vector2Int.Distance(neighborPos, target);
            Node neighborNode = new Node(neighborPos, newG, h, current);
            openSet.Enqueue(neighborNode, neighborNode.F);
        }
    }
    return null; // Không có đường đi
}

4. Đề xuất giải pháp phân vùng tuần tra kẻ địch

Mảng kiến tạo chính được chia thành 5 phần dọc theo trục phát triển. Ngoại trừ phần đầu (vùng xuất hiện của người chơi), 4 phần còn lại được lấy ngẫu nhiên 10 điểm cách nhau khoảng cách tối thiểu $d > 3$ đơn vị. Kẻ địch được gán vào 4 vùng tuần tra này, di chuyển ngẫu nhiên giữa các điểm mốc, tạo nên hành vi phòng thủ phi tuyến tính.

public List<PatrolZone> GeneratePatrolZones(List<Vector2Int> landmass, int numZones = 5) {
    List<PatrolZone> zones = new List<PatrolZone>();
    int partitionSize = landmass.Count / numZones;

    for (int i = 1; i < numZones; i++) { // Bỏ qua vùng 0
        var subList = landmass.Skip(i * partitionSize).Take(partitionSize).ToList();
        List<Vector2Int> patrolPoints = new List<Vector2Int>();
        
        foreach (var pt in subList.OrderBy(x => Random.value)) {
            if (patrolPoints.All(existing => Vector2Int.Distance(existing, pt) > 3f)) {
                patrolPoints.Add(pt);
                if (patrolPoints.Count >= 10) break;
            }
        }
        zones.Add(new PatrolZone(i, patrolPoints));
    }
    return zones;
}

Thiết lập thuộc tính cấu hình đối tượng

Các đối tượng được module hóa triệt để qua thông số cấu hình:

Nhóm đối tượng Thực thể Thuộc tính chính
Nhân vật chính Player HP_DEFAULT: 100, MOVE_SPEED: 6.5, ATTACK_BONUS: 1.2, SKILL_COOLDOWN: 5s
Vũ khí Player Súng & Lựu đạn DAMAGE: 25, ATTACK_SPEED: 0.2s, RELOAD_TIME: 1.5s, MAGAZINE: 30, INACCURACY: 0.05
Kẻ địch (5 loại) Dao, Bom, Súng, Khiên, Bazooka DETECT_RANGE: 12m, TURNING_SPEED: 180 deg/s, ATTACK_RANGE: 1.5m - 10m
Bẫy Map Xanh/Vàng Bẫy hố, Bẫy búa, Bãi lầy Búa quay $180^\circ$ (Repel Force: 15), Bãi lầy (Slow Ratio: 50%, Damage: 5/s)
Bẫy Map Xanh biển Bom băng, Băng đẩy, Mưa băng Băng đẩy (Speed: 8m/s), Mưa băng (Stun Time: 1.5s, Fall Speed: 12m/s)
Bẫy Map Đỏ Ụ súng lửa, Thảm lửa, Bom cháy Ụ súng lửa (Flame Duration: 3s, Charging Time: 2s, Damage: 50/0.5s)

Kiểm thử và đánh giá hiệu năng

+-------------------------------------------------------------------------+
|                  PERFORMANCE BENCHMARK SUMMARY TABLE                    |
+-------------------+------------------+-------------------+--------------+
| Kích thước bản đồ | Thời gian sinh   | Bộ nhớ cấp phát   | Tốc độ khung |
| (Grid Dimension)  | trung bình (ms)  | RAM (Managed Heap)| hình (FPS)   |
+-------------------+------------------+-------------------+--------------+
| 50 x 50           | 42.6 ms          | 1.8 MB            | 60 FPS       |
| 100 x 100         | 158.3 ms         | 4.2 MB            | 60 FPS       |
| 200 x 200         | 485.1 ms         | 12.6 MB           | 58 - 60 FPS  |
+-------------------+------------------+-------------------+--------------+
  • Kiểm thử kết nối logic (Traversability Test): Thực hiện sinh thử nghiệm 500 bản đồ liên tiếp. Tỷ lệ bản đồ có thể hoàn thành từ điểm xuất phát tới cổng dịch chuyển đạt $100%$ nhờ bước lọc BFS và kiểm tra đường đi A*.
  • Tỷ lệ giải quyết lỗi (Bug Resolution): Phát hiện và khắc phục 18/18 lỗi phát sinh trong quá trình tích hợp (chủ yếu liên quan đến va chạm vật lý Rigidbody của tảng băng đẩy và độ trễ ném bom của nhân vật).

Đổi mới và đóng góp

  1. Quy trình PCG khép kín 4 giai đoạn: Tích hợp liền mạch từ khâu khởi tạo địa hình hữu cơ (Perlin Noise), lọc hình học không gian (BFS), xác lập xương sống chiến thuật (A* Pathfinding), đến định vị động các chướng ngại vật tương tác.
  2. Thuật toán phân vùng tuần tra (Patrol Partitioning Algorithm): Đột phá trong việc giải quyết bài toán AI di chuyển vô định hoặc dồn cục thường thấy trong game rogue-like. Bằng cách chia mảng kiến tạo thành 5 phân đoạn có điều kiện khoảng cách biên cách ly ($d > 3$), kẻ địch duy trì mật độ bao phủ đồng đều nhưng vẫn bảo đảm tính bất ngờ.
  3. Tiết kiệm $85%$ thời gian phát triển level: Thay vì mất hàng chục giờ thiết kế tay, hệ thống tạo ra một màn chơi hoàn chỉnh với đầy đủ bẫy và AI chỉ trong dưới $200\text{ ms}$.

Ứng dụng thực tế và triển khai

Trường hợp sử dụng thực tế (Use Cases)

  • Game thể loại Roguelike / Dungeon Crawler: Tự động sinh phòng và chướng ngại vật sau mỗi lượt chơi của game thủ.
  • Game sinh tồn và huấn luyện AI: Cung cấp môi trường mô phỏng biến đổi liên tục để huấn luyện các tác tử học tăng cường (Reinforcement Learning Agents).

Yêu cầu hệ thống triển khai

[System Requirements]
├── OS: Windows 10/11 (64-bit) hoặc macOS Catalina trở lên
├── CPU: Intel Core i3-6100 / AMD Ryzen 3 1200 tương đương hoặc cao hơn
├── GPU: NVIDIA GeForce GTX 750 Ti / AMD Radeon R7 260X (DirectX 11 compatible)
├── RAM: Tối thiểu 4 GB (Khuyến nghị 8 GB)
└── Storage: 1.5 GB dung lượng trống

Hướng dẫn cài đặt và cấu hình nhanh

  1. Clone mã nguồn từ kho lưu trữ GitHub: git clone https://github.com/uit-project/map-generator-game.git
  2. Mở dự án thông qua Unity Hub (phiên bản Unity 2022.3.x LTS).
  3. Truy cập thư mục Assets/Scenes/ và mở file MainMenu.unity.
  4. Nhấn nút Play trong Unity Editor hoặc chọn File > Build and Run để xuất file thực thi .exe / .app.

Hạn chế và hướng phát triển

Hạn chế kỹ thuật

  • Độ cao địa hình hiện được xử lý trên mặt phẳng logic 2D trước khi ánh xạ sang không gian 3D, chưa tận dụng hết cấu trúc địa hình 3D đa tầng (Voxel/3D Volumetric).
  • Mật độ chướng ngại vật hiện phân bố dựa trên xác suất cố định thay vì tự động điều chỉnh theo kỹ năng thời gian thực của người chơi (Dynamic Difficulty Adjustment).

Hướng phát triển mở rộng

  • Nghiên cứu ứng dụng Wave Function Collapse (WFC) kết hợp với Perlin Noise để sinh bản đồ có tính kiến trúc mô-đun phức tạp.
  • Ứng dụng thuật toán học máy (Reinforcement Learning) cho AI kẻ địch để phối hợp chiến thuật nhóm thay vì tuần tra phân vùng độc lập.

Đối tượng hưởng lợi

  • Sinh viên & Học viên: Nguồn tài liệu tham khảo thực tiễn về toán học ứng dụng trong lập trình game (Nội suy Perlin, cấu trúc dữ liệu đồ thị, thuật toán tìm đường tối ưu).
  • Lập trình viên Game (Game Developers): Kiến trúc mã nguồn mẫu (Source Code Pattern) dạng Component-based trên Unity, dễ dàng tái sử dụng bộ sinh map cho các dự án 2D/3D thương mại.
  • Doanh nghiệp / Indie Game Studios: Giảm thiểu đáng kể chi phí nhân sự và rút ngắn thời gian đưa sản phẩm ra thị trường (Time-to-Market).

Câu hỏi thường gặp

1. Thuật toán Perlin Noise có gây lặp lại cấu trúc bản đồ không?

Không. Bằng cách sử dụng các giá trị độ dời ngẫu nhiên (offset) kết hợp khởi tạo vector gradient độc lập ở mỗi lần chạy, ma trận nhiễu sinh ra hoàn toàn ngẫu nhiên và không trùng lặp cấu trúc hình học giữa các ván chơi.

2. Thuật toán A* có làm giảm hiệu năng khi kích thước bản đồ lớn không?

Hệ thống chỉ chạy A* duy nhất một lần trong pha nạp màn chơi (Generation Phase) trên cấu trúc lưới ma trận rút gọn và sử dụng PriorityQueue tối ưu, do đó không gây nghẽn hiệu năng (stuttering) trong suốt quá trình người chơi điều khiển nhân vật.

3. Làm thế nào để đảm bảo kẻ địch không sinh ra ngay trên vị trí người chơi?

Thuật toán phân vùng loại trừ hoàn toàn phân vùng số $0$ (nơi chứa $10%$ điểm đầu tiên của mảng kiến tạo - khu vực xuất phát của Player). Kẻ địch chỉ được gán xuất hiện từ vùng số 1 đến vùng số 4.

4. Hệ thống có hỗ trợ tùy biến thêm các loại bẫy mới không?

Có. Nhờ thiết kế hướng đối tượng tuân thủ nguyên lý Open/Closed (SOLID), nhà phát triển chỉ cần kế thừa lớp cơ sở ObstacleBase và định nghĩa các thuộc tính sát thương, thời gian hồi (Reset Time), hiệu ứng trạng thái (Stun/Slow) trong Inspector của Unity.

5. Dự án có khả năng chuyển đổi (porting) sang nền tảng di động không?

Kiến trúc mã nguồn sử dụng C# chuẩn và đồ họa tối ưu qua URP hoàn toàn tương thích với Android và iOS. Chỉ cần thay thế hệ thống tiếp nhận sự kiện phím WASD/Chuột bằng Virtual Joystick trên màn hình cảm ứng.

Kết luận

Đồ án tốt nghiệp “Nghiên cứu và phát triển các giải pháp sử dụng Map Generator để tự động tạo ra màn chơi cho game” của nhóm sinh viên Trường Đại học Công nghệ Thông tin - ĐHQG TP.HCM đã giải quyết trọn vẹn bài toán sinh màn chơi tự động trong phát triển game hiện đại. Bằng việc kết hợp chặt chẽ cơ sở toán học (Perlin Noise cải tiến), cấu trúc dữ liệu giải thuật (BFS, A*) cùng giải pháp phân vùng tuần tra AI thực tiễn, đề tài không chỉ đạt chuẩn học thuật mà còn đem lại giá trị ứng dụng cao cho ngành công nghiệp phát triển phần mềm giải trí.