Students Save 30%! Learn & create with unlimited courses & creative assets Students Save 30%! Save Now
Advertisement
  1. Game Development
  2. Artificial Intelligence
Gamedevelopment

Cỗ máy finite-state: Lý thuyết và thực hiện

by
Difficulty:IntermediateLength:LongLanguages:

Vietnamese (Tiếng Việt) translation by Andrea Ho (you can also view the original English article)

Một cỗ máy trạng thái hữu hạn là một mô hình được sử dụng để biểu diễn và kiểm soát luồng thực hiện. Nó là hoàn hảo cho việc thực hiện AI trong trò chơi, tạo ra kết quả tuyệt vời mà không cần một mã phức tạp. Hướng dẫn này mô tả lý thuyết, thực hiện và sử dụng các cỗ máy trạng thái hữu hạn đơn giản và dựa trên stack.

Tất cả các biểu tượng được thực hiện bởi Lorc, và có sẵn trên http://game-icons.net.

Lưu ý: Mặc dù hướng dẫn này được viết bằng cách sử dụng AS3 và Flash, bạn sẽ có thể sử dụng cùng một kỹ thuật và khái niệm trong hầu hết mọi môi trường phát triển trò chơi.


Một cỗ máy hữu hạn nhà nước là gì?

Một cỗ máy trạng thái hữu hạn, hoặc FSM, là một mô hình tính toán dựa trên một cỗ máy giả định được tạo thành từ một hoặc nhiều trạng thái. Chỉ một trạng thái duy nhất có thể hoạt động cùng một lúc, do đó cỗ máy phải chuyển từ trạng thái này sang trạng thái khác để thực hiện các tác vụ khác nhau.

FSM thường được sử dụng để tổ chức và đại diện cho luồng thực thi, rất hữu ích để triển khai AI trong trò chơi. Ví dụ, "bộ não" của kẻ thù có thể được thực hiện bằng cách sử dụng FSM: mỗi trạng thái đại diện cho một hành động, chẳng hạn như tấn công hoặc né tránh:

FSM đại diện cho bộ não của kẻ thù.

FSM có thể được biểu diễn bằng biểu đồ, trong đó các nút là trạng thái và các cạnh là các chuyển tiếp. Mỗi cạnh có một nhãn thông báo khi quá trình chuyển đổi xảy ra, giống như trình phát gần nhãn trong hình trên, điều này cho biết cỗ máy sẽ chuyển từ đi lang thang sang tấn công nếu người chơi ở gần.


Các nước lập kế hoạch và quá trình chuyển đổi của chúng

Việc thực hiện FSM bắt đầu với các tiểu bang và quá trình chuyển đổi sẽ có. Hãy tưởng tượng FSM sau đây, đại diện cho bộ não của một con kiến ​​mang lá về nhà:

FSM đại diện cho bộ não của một con kiến.

Điểm khởi đầu là trạng thái lá tìm kiếm, sẽ vẫn hoạt động cho đến khi con kiến ​​tìm thấy lá. Khi điều đó xảy ra, trạng thái hiện tại sẽ được chuyển về nhà, nó vẫn hoạt động cho đến khi con kiến ​​về nhà. Khi con kiến ​​cuối cùng về nhà, trạng thái hoạt động trở lại tìm thấy lá một lần nữa, vì vậy con kiến ​​lặp lại hành trình của nó.

Nếu trạng thái hoạt động là tìm lá và con trỏ chuột tiếp cận kiến, có sự chuyển đổi sang trạng thái chạy trốn. Trong khi trạng thái đó đang hoạt động, kiến ​​sẽ chạy khỏi con trỏ chuột. Khi con trỏ không còn là mối đe dọa nữa, có một sự chuyển tiếp trở lại trạng thái tìm lá.

Vì có sự chuyển tiếp kết nối tìm lá và chạy đi, con kiến ​​sẽ luôn luôn chạy khỏi con trỏ chuột khi nó tiếp cận miễn là con kiến ​​đang tìm lá. Điều đó sẽ không xảy ra nếu trạng thái hoạt động là về nhà (xem hình bên dưới). Trong trường hợp đó con kiến ​​sẽ đi về nhà một cách lo sợ, chỉ chuyển sang trạng thái lá tìm khi nó về nhà.

FSM đại diện cho bộ não của một con kiến. Chú ý sự thiếu chuyển tiếp giữa chạy trốn và về nhà.

Triển khai FSM

Một FSM có thể được thực hiện và đóng gói trong một lớp duy nhất, có tên FSM chẳng hạn. Ý tưởng là để thực hiện mọi trạng thái như một hàm hoặc phương thức, sử dụng một thuộc tính được gọi là activeState trong lớp để xác định trạng thái nào đang hoạt động:

Vì mỗi trạng thái là một hàm, trong khi một trạng thái cụ thể đang hoạt động, hàm đại diện cho trạng thái đó sẽ được gọi mỗi lần cập nhật trò chơi. Thuộc tính activeState là một con trỏ trỏ đến một hàm, do đó nó sẽ trỏ đến chức năng của trạng thái hoạt động.

Phương thức update () của lớp FSM phải được gọi mỗi khung trò chơi, để nó có thể gọi hàm được chỉ định bởi thuộc tính activeState. Cuộc gọi đó sẽ cập nhật các hành động của trạng thái hiện đang hoạt động.

Phương thức setState () sẽ chuyển FSM sang trạng thái mới bằng cách trỏ thuộc tính activeState đến một hàm trạng thái mới. Chức năng của tiểu bang không phải là thành viên của FSM; nó có thể thuộc về một lớp khác, làm cho lớp FSM chung chung hơn và có thể tái sử dụng được.


Sử dụng FSM

Sử dụng lớp FSM đã được mô tả, đã đến lúc triển khai "bộ não" của một nhân vật. Kiến giải thích trước đó sẽ được sử dụng và kiểm soát bởi FSM. Sau đây là một đại diện của các trạng thái và chuyển tiếp, tập trung vào mã:

FSM của bộ não kiến ​​với tập trung vào mã.

Kiến được đại diện bởi lớp Ant, trong đó có một thuộc tính có tên là não và một phương pháp cho mỗi tiểu bang. Thuộc tính não là một thể hiện của lớp FSM:

Lớp Ant cũng có vận tốc và thuộc tính vị trí, cả hai đều được sử dụng để tính toán chuyển động bằng cách sử dụng tích hợp Euler. Phương thức update () được gọi là mỗi khung trò chơi, vì vậy nó sẽ cập nhật FSM.

Để giữ cho mọi thứ đơn giản, mã được sử dụng để di chuyển con kiến, chẳng hạn như moveBasedOnVelocity (), sẽ bị bỏ qua. Thông tin thêm về điều đó có thể được tìm thấy trong chuỗi Hiểu hành vi chỉ đạo.

Dưới đây là việc thực hiện của mỗi tiểu bang, bắt đầu với findLeaf (), nhà nước chịu trách nhiệm hướng dẫn kiến ​​đến vị trí lá:

Trạng thái goHome (), được sử dụng để hướng dẫn ant home:

Cuối cùng, trạng thái runAway (), được sử dụng để làm cho con kiến ​​chạy trốn con trỏ chuột:

Kết quả là một con kiến ​​được kiểm soát bởi một "bộ não" FSM:

Ant được kiểm soát bởi FSM. Di chuyển con trỏ chuột để đe dọa kiến.

Cải thiện lưu lượng: FSM dựa trên stack

Hãy tưởng tượng rằng con kiến ​​cũng cần phải chạy khỏi con trỏ chuột khi nó đang về nhà. FSM có thể được cập nhật như sau:

Ant FSM được cập nhật với các hiệu ứng chuyển tiếp mới.

Có vẻ như một sửa đổi tầm thường, việc bổ sung một sự chuyển tiếp mới, nhưng nó tạo ra một vấn đề: nếu trạng thái hiện tại bị bỏ đi và con trỏ chuột không ở gần nữa, trạng thái nào cần chuyển đổi sang: về nhà hoặc tìm lá?

Giải pháp cho vấn đề đó là FSM dựa trên stack. Không giống như FSM hiện tại của chúng tôi, FSM dựa trên stack sử dụng ngăn xếp để kiểm soát trạng thái. Đầu ngăn xếp chứa trạng thái hoạt động; chuyển tiếp được xử lý bằng cách đẩy hoặc popping tiểu bang từ ngăn xếp:

FSM dựa trên stack

Trạng thái hiện đang hoạt động có thể quyết định phải làm gì trong quá trình chuyển đổi:

Chuyển tiếp trong FSM dựa trên stack: tự bật + đẩy mới; tự nó; đẩy mới.

Nó có thể tự bật từ ngăn xếp và đẩy một trạng thái khác, có nghĩa là một quá trình chuyển đổi đầy đủ (giống như FSM đơn giản đang làm). Nó có thể tự bật lên từ ngăn xếp, có nghĩa là trạng thái hiện tại đã hoàn thành và trạng thái tiếp theo trong ngăn xếp sẽ trở nên hoạt động. Cuối cùng, nó chỉ có thể đẩy một trạng thái mới, có nghĩa là trạng thái hiện đang hoạt động sẽ thay đổi trong một thời gian, nhưng khi nó tự bật ra khỏi ngăn xếp, trạng thái hoạt động trước đó sẽ tiếp quản lại.


Triển khai FSM dựa trên Stack

Một FSM dựa trên stack có thể được thực hiện bằng cách sử dụng cách tiếp cận tương tự như trước đây, nhưng lần này sử dụng một mảng các con trỏ hàm để kiểm soát ngăn xếp. Thuộc tính activeState không còn cần thiết, vì phần trên cùng của ngăn xếp đã trỏ đến trạng thái hiện đang hoạt động:

Phương thức setState () đã được thay thế bằng hai phương thức mới: pushState () và popState (); pushState () thêm một trạng thái mới vào đầu stack, trong khi popState () loại bỏ trạng thái ở trên cùng của ngăn xếp. Cả hai phương pháp đều tự động chuyển cỗ máy sang trạng thái mới, vì chúng thay đổi phần trên cùng của ngăn xếp.


Sử dụng FSM dựa trên stack

Khi sử dụng FSM dựa trên stack, điều quan trọng cần lưu ý là mỗi trạng thái chịu trách nhiệm tự popping từ ngăn xếp. Thông thường một trạng thái loại bỏ chính nó khỏi ngăn xếp khi nó không còn cần thiết, như nếu tấn công () đang hoạt động nhưng mục tiêu vừa chết.

Sử dụng ví dụ ant, chỉ cần một vài thay đổi để điều chỉnh mã để sử dụng FSM dựa trên stack. Vấn đề không biết trạng thái chuyển đổi sang hiện tại được giải quyết liền mạch nhờ vào bản chất của FSM dựa trên stack:

Kết quả là một con kiến ​​có thể chạy khỏi con trỏ chuột, chuyển về trạng thái hoạt động trước đó trước khi có mối đe dọa:

Ant được điều khiển bởi FSM dựa trên stack. Di chuyển con trỏ chuột để đe dọa kiến.

Tổng kết

Máy hữu hạn trạng thái rất hữu ích để thực hiện logic AI trong trò chơi. Chúng có thể dễ dàng được biểu diễn bằng biểu đồ, cho phép nhà phát triển thấy được bức tranh lớn, tinh chỉnh và tối ưu hóa kết quả cuối cùng.

Việc thực hiện một FSM bằng cách sử dụng các hàm hoặc các phương thức để biểu diễn các trạng thái là đơn giản, nhưng mạnh mẽ. Kết quả phức tạp hơn có thể đạt được bằng cách sử dụng FSM dựa trên stack, đảm bảo luồng thực thi có thể quản lý và súc tích mà không ảnh hưởng tiêu cực đến mã. Đó là thời gian để làm cho tất cả kẻ thù trò chơi của bạn thông minh hơn bằng cách sử dụng FSM!

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.