Rogue, Diablo, Bloodborne, Spelunky, giữa chúng có điểm chung gì? Đó là hệ thống hầm ngục chằng chịt được thiết kế ngẫu nhiên bằng thuật toán máy tính với mục đích tránh khiến người chơi cảm thấy nhàm chán và vì vậy, làm tăng giá trị chơi lại cho game. Tưởng chừng đơn giản, thế nhưng đằng sau cơ chế sinh bản đồ tự động đã có từ rất lâu này là một loạt quy trình rắc rối nhưng cũng không kém phần thú vị mà chúng ta sẽ cùng tìm hiểu trong bài viết ngày hôm nay.
Arcane Sanctuary - một trong những màn chơi loằng ngoằng nhất Diablo II.
Không phải ai cũng là lập trình viên nhưng nếu suy nghĩ một cách logic chúng ta có thể nhận ra vấn đề đầu tiên cần xử lý nếu muốn xây dựng một bản đồ ngẫu nhiên, đó là tạo ra nhiều căn phòng với kích thước đa dạng khác nhau. Các hàm random có sẵn trong công cụ lập trình sẽ đảm nhiệm việc này, nhưng còn vị trí của chúng thì sao? Hệ thống phòng không thể tản mát khắp nơi mà phải nằm trong một phạm vi nhất định và các nhà làm game thường chọn vùng giới hạn là hình tròn với bán kính thay đổi được.
Trong hình tròn này, nhiều vị trí ngẫu nhiên bắt đầu được lựa chọn và từ đó sinh ra các căn phòng với chiều dài, bề rộng cũng ngẫu nhiên. Để tiện hình dung các bạn hãy xem tấm hình động phía bên dưới.
Như có thể thấy trong hình, sau khi được tạo ra ngẫu nhiên, các căn phòng đang chồng chéo lên nhau rất lộn xộn. Chúng cần phải được tách riêng rẽ khỏi nhau để hình thành nên một bản đồ hợp lý. Để làm điều này có nhiều cách, nhưng một trong những phương pháp phổ biến nhất là sử dụng engine vật lý để tính toán sự "va chạm", với mỗi căn phòng được coi như một vật thể độc lập. Kết quả như sau:
Thực tế không có bản đồ nào ngẫu nhiên 100%. Vẫn luôn tồn tại những vị trí định sẵn như lối vào, cửa ra, nơi gặp gỡ NPC, đấu trùm hay đơn giản cần diện tích lớn để dành cho giao tranh. Vì vậy, tiếp đến nhà làm game cần phải chọn ra một số căn phòng trong rất nhiều khu vực đã được tạo ra ngẫu nhiên. Thông thường, họ sẽ dựa vào kích thước để quyết định, ví dụ như một căn phòng có bề ngang lớn hơn giá trị x, chiều dài lớn hơn giá trị y nào đó.
Các căn phòng chính được đánh dấu bằng màu đỏ.
Sau khi đã chọn ra được những căn phòng chính, việc tiếp theo là nối chung lại với nhau. Các nhà làm game sử dụng thuật toán có tên gọi Delaunay với công dụng hiểu nôm na là tạo nên những hình tam giác từ một tập hợp điểm có sẵn. Ở đây trung tâm của mỗi căn phòng sẽ đóng vai trò một điểm.
Chỉ dừng lại ở đây thì mỗi căn phòng đều sẽ có nhiều đường đi tới những căn phòng khác, như vậy rất thừa thãi và thiếu tự nhiên. Một thuật toán rút gọn sẽ được áp dụng tiếp theo với mục đích lược bỏ những đoạn thẳng không cần thiết nhưng vẫn đảm bảo tồn tại đường đi thông suốt qua tất cả các khu vực.
Nếu muốn bản đồ rối rắm và bớt tuyến tính đi một chút, các nhà làm game sẽ thêm vào lại vài đoạn thẳng đã bỏ đi trước đó.
Bản đồ ngẫu nhiên của chúng ta đã gần hoàn tất. Công việc cuối cùng là tạo ra những hành lang nối các căn phòng chính lại với nhau. Những khu vực phụ tạm thời bị loại bỏ để dành chỗ trống cho các đường gấp khúc kết nối hệ thống phòng chính dựa trên sơ đồ đã tạo dựng được ở trên.
Sau đó, các căn phòng phụ được thêm vào trở lại, với điều kiện chúng phải tiếp xúc hoặc cắt qua những đường gấp khúc vừa vẽ.
Với những phần đường gấp khúc trông còn quá "cộc", hai dãy ô vuông sẽ được thêm vào hai bên để tạo nên tấm bản đồ hoàn chỉnh cuối cùng.
Một lần nữa, chúng ta hãy nhìn lại quá trình xây dựng một bản đồ ngẫu nhiên từ đầu đến cuối thông qua tấm hình động hoàn chỉnh phía dưới.
Cũng không đến nỗi quá phức tạp đúng không? Nếu trong số các bạn độc giả ngồi đây có ai đó đang nung nấu ý định phát triển game trong tương lai, hy vọng bài viết này đã giúp bạn học hỏi thêm ít kiến thức bổ ích.
Đối với những ai muốn tìm hiểu kĩ càng hơn, các bạn có thể đọc bài viết gốc tại www.gamasutra.com/blogs/AAdonaac/20150903/252889/Procedural_Dungeon_Generation_Algorithm.php.