Áp dụng mô phỏng state space vào thiết kế game giải đố

Đầu năm 2014, tôi từng rất thích thú với việc thiết kế game giải đố PC quanh các nhân tố đển hình như công tắc, cổng; hộp hay đá tảng;… có thể kích hoạt hoặc đẩy,… Những yếu tố này được đưa vào rất nhiều game. Đặc biệt là game Lara Croft and the Guardian of Light mà tôi đã học hỏi rất nhiều.

Để hiểu sâu hơn về các câu đố và nhân tố tạo nên nó, tôi đã tạo ra một công cụ phân tích và mô phỏng lại trạng thái không gian (state space) của câu đố. Trong phần Procedural Content Generation (kỹ thuật tạo nội dung theo thủ tục) mailing list. Đến nay, tôi có nghiên cứu vấn đề này nhiều lần, và nhận thấy bản thân công cụ này cực kỳ hữu ích dù chưa có thuật toán tạo game đố theo thủ tục. Công cụ mang tên PuzzleGraph và hiện đang được phát hành miễn phí.

Tải PuzzleGraph tại itch.io

Với công cụ, bạn có thể thiết lập và kết nối các thành phần của câu đố như cổng, công tắc, sàn ấn và đá tảng. Đồng thời, bạn cũng có thể thấy được không gian trạng thái mô phỏng của câu đố, bao gồm hướng giải quyết, ngõ cụt và tình trạng thất bại.

Bạn nhất định sẽ bị mê mẩn trước những câu đố tự tạo trong Puzzle Graph!

Ở đây, tôi có một video minh họa cho các bạn. Ở cuối bài, tôi có thêm một chút thông tin và thông báo cho các bạn đã xem video cũ.

Lúc tôi công bố PuzzleGraph trên Twitter, có rất nhiều người hào hứng. Tôi thấy mọi người (đặc biệt là giới học thuật) re-tweets, và còn forward, cc cho nhau nữa.

Không chỉ là một công cụ thực tiễn hằng ngày giúp bạn làm việc với quy tắc đố (khá chung và thường thấy) dễ dàng hơn, đây cũng còn là một dự án nghiên cứu và hệ khái niệm hoàn chỉnh với cách nhìn thiết kế mới mẻ có thể khơi gợi được khả năng sáng tạo nơi người dùng.

Phân tích và mô phỏng không gian trạng thái game cũng là một lĩnh vực được quan tâm nghiên cứu chuyên sâu từ những góc nhìn khác nhau. PuzzleGraph tuy chưa có những bước đột phá lớn về lĩnh vực này, nhưng chí ít với hình thức đơn giản và dễ tiếp cận, công cụ đã gây sự hứng thú với không gian trạng thái với đông đảo người dùng hơn.

PuzzleGraph hiện là phần mềm mã nguồn mở

Để tối đa hóa độ hữu dụng và phổ biến của công cụ, tôi đã quyết định biến PuzzleGraph thành mã nguồn mở để mọi người thêm bớt, tích hợp tùy thích. Hay các bạn cũng có thể nghiên cứu cấu trúc code và thuật toán của công cụ nếu muốn.

Các bạn cũng có thể liên lạc với tôi nếu các bạn có góp ý cải thiện phiên bản gốc.

Code của công cụ được lưu trữ tại https://bitbucket.org/runevision/puzzlegraph do Mozilla Public License version 2.0 sỡ hữu bản quyền.

Nhân tố giải đố trong PuzzleGraph

PuzzleGraph 1.1 có các nhân tố giải đố (theo vị trí – nodes, và theo liên kết – edges) như sau:

Như đã đề cập trong video trên, so với phiên bản đầu, tôi có thêm vào một số tính năng mới. Giờ đây, nếu chưa quen thuộc, bạn có thể đọc trợ giúp, tổng quan, hay chú giải giải thích các chức năng. Ngoài ra, công cụ còn có thêm ba nhân tố giải đố mới: one way edge, blockable hazard edge và ball track edge.

Phát triển cao hơn

Tôi cũng không biết PuzzleGraph sẽ được phát triển đến khi nào. Hiện nay, tôi không có nhiều thời gian dùng đến nó. Nên nếu các bạn đang dùng PuzzleGraph (làm hay chơi cũng được), vui lòng thông tin thêm cho tôi biết về trải nghiệm, cũng như sản phẩm câu đố của các bạn.

Bên cạnh đó, tôi cũng sẽ theo dõi các thêm các thành phẩm từ mã nguồn mở.

Trong phần kế tiếp, tôi sẽ đi sâu hơn vào kỹ thuật mô phỏng không gian trạng thái, trong trường hợp bạn muốn tích hợp các kỹ thuật này vào bộ công cụ của mình.

Công nghệ đằng sau mô phỏng không gian trạng thái

Có rất nhiều cách thực hiện phân tích và mô phỏng không gian trạng thái. Tuy nhiên, tôi có thể giải thích chi tiết hơn về phương pháp mà tôi áp dụng cho PuzzleGraph. Bạn có thể kiểm tra mã nguồn để biết rõ hơn. Tiếp đây, tôi sẽ dùng một số thuật ngữ thông dụng trong phần graph theory.

Khi nào ta nên phân tích trạng thái không gian

Bạn chỉ mô phỏng trạng thái không gian khi trạng thái không gian đủ đơn giản và hữu dụng. Nói cách khác, mỗi thay đổi trong trạng thái phải có mục đích cụ thể và tương ứng với lựa chọn của người chơi. Hơn nữa, các tình huống lựa chọn trong mỗi trường hợp nên được giới hạn bằng con số cụ thể. Với lượng tình huống cấp số mũ, việc mô phỏng trạng thái không gian sẽ không phát huy được tác dụng.

Bạn có thể thấy rõ format này trong PuzzleGraph. Bằng việc xây dựng câu đố quanh các địa điểm rời rạc, tôi không cần phải mô phỏng không gian liên tục và chi tiết. Các format đơn giản khác của trạng thái không gian cũng xoay quanh quan niệm này, công cụ chỉ hỗ trợ rất ít cho các tính năng gameplay gắn liền với không-thời gian như: cơ chế giải đố tính giờ hay tương tác vật lý đa vật thể.

Trong một số trường hợp, bạn cũng có thể hình dung trạng thái không gian đa dạng hơn, nhưng sẽ loại bỏ các yếu tố không liên quan khi đưa vào công cụ. Ví dụ như, trong game Sokoban, nếu trạng thái trực tiếp ghi lại ô lưới vị trí của người chơi, số lượng trạng thái sẽ rất cao. Tuy nhiên, ta có thể đơn giản hóa bằng việc xem xét ô lưới hiện tại mà người chơi duy chuyển được (mà không động đến hộp), và ghi lại thành trạng thái thay cho vị trí chính xác của người chơi.

Có thể thấy rằng, ta cũng có thể áp dụng một số phương pháp thu gọn trạng thái tương tự cho thế giới 3D. Ví dụ như, từ hình học 3D tùy hướng, ta có phương pháp tự động chia lưới vị trí (nav-meshes); chia các khu vục duy chuyển được thành đa giác lồi cũng là một phương pháp hay nếu bạn muốn đơn giản hóa vị trí người chơi cho mục đích phân tích không gian trạng thái.

Phân biệt giữa trạng thái và vật tĩnh

Một khi bạn đã xác địch được mỗi biểu hiện trạng thái ứng với mỗi lựa chọn người chơi tương ứng, bạn có thể bắt tay thực hiện ngay. Việc đầu tiên, hãy tách trạng thái thay đổi khỏi trạng thái bất biến.

Nói cách khác, bênh cạnh các vật thể thông thường dùng cho thiết kế, ta còn có các vật thể công tắc với trạng thái là một biến số. Nhưng vậy, bạn sẽ có hai nhóm vật thể khác nhau:

• Một là thiết kế đố tĩnh chứa thông tin node (loại và địa điểm), edge (loại và các node sẽ liên kết) và trạng thái khởi điểm của mỗi vật thể động.
• Hai là trạng thái đố chứa mọi dữ liệu sẽ thay đổi trong quá trình chơi.

Với cách phân biệt này, để xác định trạng thái hiện tại của nhân tố kích hoạt,  vật thể trạng thái đố sẽ được gán với vật thể công tắc, và công tắc sẽ tự tìm được trạng thái của nó. nếu công tắc nằm trong nhân tố thứ tư trong câu đố, công tắc sẽ tìm trạng thái gán với nó trong mảng của những biến bools của nhân tố thứ tư.

Vì vật thể trạng thái động hoàn toàn dựa theo thiết kế đố bất biến. Nên khi trạng thái hiện nay được tách khỏi thiết kế đố, trạng thái ban đầu sẽ được mã hóa trực tiếp vào thiết kế. Nếu thiết kế đố bị thay đổi, các phần tử sẽ không khớp với nhau nữa. Vì vậy mỗi khi thiết kế thay đổi, vật thể trạng thái đố phải bị bỏ đi và ta phải xây dựng vật thể mới từ con số không dựa theo tính chất trạng thái ban đầu của các nhân tố trong vật thể thiết kế đố.

Trước khi thực hiện bất cứ phân tích hay mô phỏng trạng thái không gian nào, bạn có thể kiểm tra và xác thực phân biệt trạng thái đố và thiết kế đố. Bước đầu tiên là bạn nên thêm vào chức năng “chơi” thử câu đố dựa theo các trạng thái đã phân biệt.

Tìm kiếm không gian trạng thái

Khi bạn đã có vật thể trạng thái riêng biệt, bạn cần tìm cách đánh giá và theo dõi trạng thái mới nào có thể đạt được từ một trạng thái nhất định, và tạo biểu đồ thể hiện mối liên kết của các trạng thái khác nhau. Nếu bạn tích hợp sẵn tính năng “chơi”, bạn đã đi được nửa đường rồi đấy.

Trước khi xây dựng biểu đồ, bạn cần vật thể ứng với node và edge trong biểu đồ. Vật thể trạng thái đố không phải là node. Các trạng thái phải độc lập hoàn toàn, vậy nên ta cần node trạng thái bọc (wrapper state node) chứa cả hai trạng thái của node, và thông tin về mỗi trạng thái mà node đó liên kết. Node trạng thái không chứa đường dẫn (reference) trực tếp tới các node trạng thái khác, mà tới các vật thể edge trạng thái. Edge trạng thái, ngoài việc liên kết đến các node trạng thái khác, còn phải chứa loại hành động tương ứng với edge đó. Ta cần lưu trữ rõ ràng thông tin này vì không phải lúc nào cũng có thể suy được từ trạng-thái-trước-đó và trạng-thái-sau-đó.

Để khám phá không gian trạng thái bạn cần cấu trúc dữ liệu sau:

• Dictionary: trạng thái là key và node trạng thái là value. Cấu trúc này để kiểm tra một trạng thái mới có giống với trạng thái hiện có hay không. Nếu giống, cấu trúc sẽ khôi phục node trạng thái của trạng thái hiện có
• Danh sách chờ xử lý node trạng thái theo thứ tự.

Tiếp đến, bạn có thể tìm hiểu không gian trạng thái sâu hơn theo thuật toán sau:

• Tách trạng thái ban đầu khỏi puzzle và tạo node trạng thái tương ứng. Thêm node trạng thái vào dictionary và lịch chờ.
• Xử lý các node trạng thái theo lịch chờ (nếu lịch không trống). Đặt node trạng thái chọn từ lịch chờ là A.

Node trạng thái trong PuzzleGraph có cả hai danh sách adge trạng thái nhập và xuất. Edge xuất là hành động có thể thực hiện từ trạng thái hiện tại với các trạng thái khác. Edge nhập là các hành động có thể thực hiện để đi từ các trạng thái khác đến trạng thái này. Có hai danh sách này, code và thực thi code dùng cho mô phỏng trạng thái không gian sẽ trở nên dễ dàng hơn (ví dụ như quay trở lại lúc chưa thực hiện chức năng chơi).

Hình ảnh hóa biểu đồ

Giờ đây, bạn đã có cấu trúc dữ liệu cho biểu đồ thể hiện không gian trạng thái câu đố, nhưng việc kiểm soát không dễ dàng. Việc ta cần xác định tiếp theo là vị trí của mỗi node không gian trạng thái trên biếu đồ. Từ đây, việc vẽ node và liên kết giữa các node lên vị trí tương ứng trở nên vô cùng dễ dàng.

Xác định vị trí là một khâu phức tạp. Tuy có một số thuật toán và khung chương trình cho khâu này, nhưng tôi không hề động đến mấy thứ này mà tự tạo thực thi riêng.

Phương pháp chung là kích thích (đa phần là kích thích vật lý) tại kết nối giữa các node, với mỗi kết nối cách một khoảng phù hợp để kéo hoặc đẩy. Có hai thách thức:

• tìm khoảng cách lý tưởng giữa các cặp node.
• Xác định phải kéo hay đẩy khoảng cách giữa hai node cụ thể.

Thách thức đầu tiên chỉ được giải quyết sau khi cài đặt bố cục biểu đồ node trạng thái. Trạng thái lý tưởng được tính toán theo số thay đổi trạng thái cần có giữa hai node, theo cách này hay cách khác. Với PuzzleGraph, mỗi loại thay đổi trạng thái sẽ tăng một khoảng cách như nhau. Nhưng nếu một số thay đổi trạng thái được xem là quan trọng hơn, khoảng cách này có thế chênh lệch.

Thách thức thứ hai phải được thực hiện nhiều lần, và ngưng hẳn nếu node không di chuyển được. Bạn cần thử nghiệm nhiều lần trước khi tìm được phương pháp áp dụng được chho nhiều loại biểu đồ. Bản thân tôi tính toán độ dài này qua chênh lệch giữa khoảng cách hiện tại và khoảng cách lý tưởng (có được khi chia cho bình phương của khoảng cách lý tưởng). Rồi nhân kết quả với hằng số 0,1. Đây là con số đồng quy nhanh nhất mà không gây dao động, tăng đột biết hoặc các trường hợp bất ổn khác.

Ta cần chia theo khoảng cách lý tưởng vì việc duy trì khoảng cách lý tưởng giữa các node ở xa không quan trọng bằng giữa các node ở gần. Hơn nữa, node ở xa thì nhiều hơn node ở gần, vì vậy node ở gần sẽ có lực hút mạnh hơn. Và dựa theo kết quả thử nghiệm, ta cần chia cho bình phương của khoảng cách lý tưởng. Biểu đồ sẽ trong khác đi đôi chút dựa theo năng lượng sử dụng.

Vấn đề khác

Đây chỉ mới là cơ bản! Ta còn nhiều nhiệm vụ khác như: tạo node trạng thái như là một phần của cách giải đố tối ưu, hay trạng thái thất bại mà ta không thể đến trạng thái đích được nữa (còn gọi là điều kiện “game over”). Các bạn có thể tìm hiểu mã nguồn để hiểu thêm!

Nếu thấy bài viết này hữu ích, các bạn cũng có thể theo dõi các bài viết trên runevision blog hay twitter liên quan đến procedural project và kỹ thuật lập trình game tổng quát.

Techtalk via gamasutra