Chủ nhật, ngày 4 tháng 12 năm 2016

GameDev – Áp dụng AI trong game Rắn Săn mồi – Part 1

Ngày đăng: 31/5/2012, 8:26:54PM | Lượt xem: 1,732
Hot!

AI hay trí tuệ nhân tạo được sử dụng trong rất nhiều game, từ đơn giản đến phức tạp. Tùy theo từng trường hợp mà AI có thể tính toán vị trí để di chuyển, tìm đường đi, phân tích trạng thái để đưa ra quyết định,…

snake-iconAI hay trí tuệ nhân tạo được sử dụng trong rất nhiều game, từ đơn giản đến phức tạp. Tùy theo từng trường hợp mà AI có thể tính toán vị trí để di chuyển, tìm đường đi, phân tích trạng thái để đưa ra quyết định,…

Một trong những game thuộc loại AI đơn giản nhất là trò chơi Pong được phát hành năm 1970. Dạng game bóng bàn này cho phép người chơi đấu với máy bằng cách điều khiển một thanh paddle dọc để đón và đánh trả bóng. Và bạn cũng có thể hình dung được AI của máy hoạt động như thế nào: chỉ cần thay đổi vị trí của paddle lên xuống theo trái bóng.

Pong-game
Sau này, những thể loại game mới ra đời đòi hỏi trình độ AI phải nâng lên một tầm mới. Thường thấy nhất là các thể loại game với thuật toán tìm kiếm trên cấu trúc dữ liệu dạng cây để tìm đường đi hay đưa ra quyết định (decision tree).
Trong các thuật toán duyệt cây, tùy theo trường hợp và độ lớn của dữ liệu, lập trình viên có thể thay đổi và chọn lựa thuật toán như Hill climbing, Breadth First Search, Depth First Search, Best First Search, Iterative Depth First Search hay thậm chí có thể kết hợp một, hai loại thuật toán với nhau.

Quay lại với game Rắn Săn Mồi mà tôi vừa giới thiệu cách đây không lâu. Một ý tưởng của tôi là áp dụng AI trong game này để người chơi có thể đấu với máy. Như vậy bài toán đặt ra là phải làm sao để con rắn mà máy điều khiển có thể tìm được đường ngắn nhất đến thức ăn mà không lao đầu vào tường hoặc cắn nhầm thân của nó.

Phân tích để lựa chọn thuật toán

1. Không gian dữ liệu nhỏ. Ở đây chính là kích thước của bản đồ, với loại game này thì chỉ giới hạn trong khoảng 50×50 ô là đủ.
2. Cần tìm ra đường đi ngắn nhất.

Với hai yếu tố này, bạn dễ dàng nhận ra lựa chọn giải thuật tìm kiếm theo chiều sâu (Breadth First Search) là hợp lý nhất. Ta cũng có thể loại trừ để chọn ra được thuật giải đúng:
- Hill climbing hay Best First Search: không khả thi do cần một hàm lượng giá hay heuristic. Với loại game mà vị trí hay trạng thái nhân vật không bị ảnh hưởng nhiều bởi các yếu tố môi trường thì điều này không cần thiết, thậm chí có thể đưa ra kết quả sai.
- Depth First Search hay Iterative Depth First Search: tìm kiếm theo chiều sâu theo kiểu may rủi có thể khiến nhân vật “đi lạc” quá đà và làm chậm thời gian tìm thấy con đường chính xác. Hơn nữa, kết quả tìm được có thể không phải là đường đi ngắn nhất.

Thuật toán Breadth First Search

(Nếu bạn đã quen thuộc với thuật toán Breadth First Search, có thể bỏ qua phần này.)
Cơ chế làm việc của thuật toán tương tự như vết dầu loang, tìm kiếm những điểm gần nhất trước. Bạn có thể thấy một vài game sử dụng bản đồ hay liên quan đến AI cũng có thể sử dụng thuật toán này. Một ví dụ bạn có thể áp dụng thuật toán này là n-puzzle mà tôi đã cài đặt bằng thuật toán A* để giải quyết.

Trong giải thuật này ta cần định nghĩa các thành phần sau:

Open  Danh sách chứa các vị trí chờ được xét
Close  Danh sách chứa các vị trí đã xét.
start  Vị trí bắt đầu
goal  Vị trí kết thúc
n  vị trí đang xét.
G(n)  Tập các vị trí có thể đến từ vị trí n.

Hình minh họa bằng hiệu ứng động (nguồn wikipedia):

Animated_BreadthFirstSearch
Giải thuật được mô tả bằng mã giả như sau:

Begin
	Open := {start};
	Close := ø;
	While (Open <> ø) do
		begin
			n:= Dequeue(Open);
			if (n=goal) then Return True;
			Open := Open + G(n);
			Close := Close + {n};
		end;
	Return False;
End;

Ta thấy rằng G(n) dựa vào tập Close để kiểm tra các vị trí có cần được kiểm tra hay không. Nếu bạn cài đặt hai tập này bằng một collection thì tốc độ thực thi sẽ tương đối chậm vì phải thực hiện tìm kiếm phần tử trong danh sách.

Do ví dụ của ta có dạng bản đồ nên thay vì dùng collection, ta sẽ sử dụng mảng hai chiều để có thể truy xuất trực tiếp đến một phần tử dựa vào vị trí. Khi đó ta có thể kiểm tra thuộc tính của phần tử xem nó đã được duyệt chưa.

Các quy tắc trong game

Do có cách chơi khác với các game cùng loại nên ta cần đặt thêm một vài quy tắc để xây dựng game:
- Tốc độ di chuyển của (con rắn) người chơi và máy phải bằng nhau.
- Khi cả hai đến đồ ăn cùng lúc, ưu tiên cho người chơi lấy được nó.
- Hai con rắn có thể di chuyển xuyên qua nhau (nếu không chúng có thể cắn nhau và con bị cắn sẽ chết).
- Khi độ dài con rắn của máy đạt đến một mốc nào đó, người chơi sẽ thua cuộc.
- Để giảm mức độ khó, độ dài con rắn mà máy cần đạt được sẽ cao hơn người chơi.

Tạm ổn, trong phần tới ta sẽ thực hiện việc cài đặt game này trên Html5-Canvas.

YinYangIt’s Blog

http://yinyangit.wordpress.com
 Chia sẻ qua: 
Hot!
Ý kiến bạn đọc

These items will be permanently deleted and cannot be recovered. Are you sure?

Gallery

image

Maecenas viverra rutrum pulvinar

Maecenas viverra rutrum pulvinar! Aenean vehicula nulla sit amet metus aliquam et malesuada risus aliquet. Vestibulum rhoncus, dolor sit amet venenatis porta, metus purus sagittis nisl, sodales volutpat elit lorem…

Read more

Text Links

Thiết kế logo chuyên nghiệp Insky
DAFABET
W88 w88b.com/dang-ky-tai-khoan-w88
W88
Copyright © 2011 - 2012 vietshare.vn by phamkhuong102@gmail.com doanhkisi2315@gmail.com. All rights reserved.