AI 1.3 - BẦY, ĐÀN VÀ LŨ (PHẦN II)

1.3 - Bầy, đàn và lũ ( Phần II )

Tìm đường A*

Có nhiều game, trong đó bạn có thể tìm các con quỷ hoặc địch mà theo sau người chơi, hoặc đi đến một điểm riêng khi tránh các chướng ngại. Chẳng hạn, chúng ta nhìn về một trò game RTS một cách hình thức. Các bạn có thể chọn một nhóm các đơn vị và nhấp vào một vị trí nơi bạn muốn chúng di chuyển hoặc nhấp vào các đơn vị địch để tấn công chúng. Đơn vị của bạn khi đó cần tìm ra đường để đến đích mà không đụng vào các chướng ngại. Đơn vị địch cũng cần có thể làm cùng như thế. Các chướng ngại có thể khác nhau từ các đơn vị khác nhau. Chẳng hạn, một đơn vị hạm đội trên không có thể băng qua đồi, trong khi đất hoặc các đơn vị pháo binh cần tìm ra đường quanh nó.


A* (phát âm là « A sao ») là thuật toán tìm đường được sử dụng rộng rãi trong game, vì sự biểu diễn và độ chính xác của nó. Hãy nhìn vào một ví dụ để thấy làm sao nó làm việc. Hãy nói chúng ta muốn đơn vị của mình di chuyển từ điểm A đến điểm B, nhưng có một bức tường trên đường, và nó không thể di chuyển thẳng đến mục tiêu. Vì thế, cần tìm ra một con đường đến điểm B khi đang tránh bức tường.

Hình : Top-down view of our map

Chúng ta đang tìm một ví dụ 2D đơn giản. Nhưng cùng ý tưởng có thể được áp dụng vào môi trường 3D. Để tìm ra đường từ điểm A đến điểm B, chúng ta cần biết nhiều về bản đồ chẳng hạn như vị trí của vật thể. Vì điều đó chúng ta có thể chia toàn bộ bản đồ thành những lát nhỏ, tiêu biểu là gắn lưới cho bản đồ, như việc biểu diễn trong hình sau :

Map represented in a 2D grid

Các ô cũng có thể là một trong những hình khác như lục giác hoặc tam giác. Nhưng chúng ta sẽ chỉ dùng ô vuông ở đây, nó đơn giản và đầy đủ cho mục đích của chúng ta. Đại diện cho toàn bộ bản đồ lưới, tìm kiếm khu vực đơn giản hơn, và đây là một bước quan trọng trong việc tìm đường. Chúng ta giờ đây có thể liên quan đến bản đồ của chúng ta trong một mảng 2D nhỏ. Bản đồ của chúng ta bây giờ biểu diễn bằng 5 x 5 ô vuông, có tổng cộng 25 ô. Chúng ta có thể tìm kiếm con đường tối ưu để đến đích. Làm sao chúng ta làm được điều này ? Bằng việc tính toán điểm số di chuyển của mỗi ô kề sát với ô bắt đầu, là một ô trên bản đồ không có một chướng ngại, và rồi chọn ô có giá trị thấp nhất.

Có bốn ô kề nhau với người chơi, nếu chúng ta không xét những bước di chuyển chéo. Bây giờ, chúng ta cần biết hai số để tính điểm di chuyển cho mỗi ô đó. Hãy gọi chúng là G và H, với G là giá trị di chuyển từ ô đầu đến ô hiện tại, và H là giá trị để đến ô đích từ ô hiện tại.

Bằng cách thêm G và H, chúng ta có thể có điểm cuối cùng của ô đó; hãy gọi nó là F. Vì thế chúng ta sẽ dùng công thức này: F = G + H.

Valid adjacent tiles

Trong ví dụ này, chúng ta sẽ dùng một cách đơn giản gọi là chiều dài Manhattan (cũng được biết như là hình học Taxicab), trong đó chúng ta chỉ tính tổng số ô giữa ô đầu và ô đích để biết khoảng cách giữa chúng.

Calculating G

Hình trên chỉ ra những tính toán của G theo 2 cách khác nhau. Chúng ta chỉ thêm một đối tượng (giá trị để di chuyển một ô) đến điểm G của ô trước khi đến điểm G hiện tại của ô hiện tại. Chúng ta có thể cho những giá trị khác nhau đối với các ô khác nhau. Chẳng hạn, chúng ta có thể muốn cho giá trị di chuyển cao hơn đối với các di chuyển chéo (nếu chúng ta đang xét đến chúng), hoặc để chỉ những ô đang bị chiếm, hãy nói một cây cầu hoặc một đường bùn. Giờ chúng ta biết làm sao để có G. Chúng ta nhìn vào phép tính H. Hình sau biểu thị giá trị H khác nhau từ những ô đầu khác nhau đến ô đích. Bạn có thể cố tính các ô vuông giữa chúng để hiểu làm sao chúng ta có những giá trị đó.

 

Calculating H

Vì thế, bây giờ chúng ta biết làm sao để có G và H. Hãy đi trở lại ví dụ đầu để tìm ra đường ngắn nhất từ A đến B. Đầu tiên chúng ta chọn ô bắt đầu, và xét những ô liền kề hợp lý, chỉ ra trong hình sau. Rồi chúng ta tính điểm G và H của mỗi ô, chỉ ra trong những góc trái bên dưới và bên phải của ô theo thứ tự. Và rồi điểm F cuối cùng, mà G + H chỉ ra góc trái bên trên. Hiển nhiên, ô đến bên phải trực tiếp của ô đầu có điểm F thấp nhất.

Vì thế, chúng ta chọn ô này như bước di chuyển tiếp theo của chúng ta, và lưu giữ ô trước đó như ô cha của nó.

Ô cha này sẽ có ích về sau, khi chúng ta theo để vết phía đường cuối cùng của chúng ta.

Starting position

Từ ô hiện tại, chúng ta làm bước phát triển tương tự lần nữa, xác định các ô liền kề đúng. Lần này chỉ có hai ô liền kề hợp lý ở trên và dưới. Ô bên trái là ô mà chúng ta đã xác định, và có chướng ngại ở ô bên phải. Chúng ta tính G, H, và rồi điểm F của những ô liền kề mới đó. Lần này chúng ta có bốn ô ở bản đồ của chúng ta với tất cả các ô có cùng điểm, sáu. Vì thế, cái nào là ô chúng ta chọn? Chúng ta có thể chọn bất kỳ trong chúng. Điều đó thật sự chẳng là vấn đề trong ví dụ này, nếu chúng có cùng điểm số. Thông thường, chúng ta chỉ chọn ô được thêm vào gần đây để liệt kê ô liền kề của chúng ta. Điều này vì sau đó, chúng ta sẽ dùng vài cấu trúc dữ liệu, như một danh sách để lưu trữ các ô đó, mà đang được xem xét cho bước tiếp theo. Vì thế, việc kết nối đến ô gần nhất được thêm vào danh sách có thể nhanh hơn việc tìm kiếm thông qua danh sách để đến một ô riêng mà được thêm vào trước đó.

Trong phần demo này, chúng ta sẽ chỉ chọn ngẫu nhiên ô cho phần test tiếp theo của chúng ta, để chứng minh rằng nó có thể tìm ra đường đi ngắn nhất.

Second Step

Vì vậy, chúng ta chọn ô được tô đỏ này. Chúng ta kiểm tra lần nữa ở những ô liền kề. Trong bước này, chỉ có một ô liền kề mới với một điểm F được tính của 8. Vì thế, điểm thấp nhất ngay bây giờ vẫn là 6. Chúng ta có thể chọn bất kỳ ô nào với điểm 6.

 

Third Step

Vì thế, chúng ta chọn một ô ngẫu nhiên từ tất cả những ô với điểm 6. Nếu chúng ta lặp lại bước tiến này cho tới khi chúng ta đến ô đích, chúng ta sẽ kết thúc với một bảng hoàn toàn với tất cả các điểm cho mỗi ô hợp lý.

 

Reach target

Bây giờ chúng ta phải làm để lưu vết điểm đầu từ ô đích bằng cách dùng ô cha (parent). Nó sẽ cho ta một con đường như hướng dẫn dưới đây:

 

Lưu vết - Path traced back

Đây là khái niệm của tìm đường A* bằng nút thắt, không hiển thị bất kỳ mã. A* là một khái niệm quan trọng trong khu vực tìm đường AI, nhưng từ Unity 3.5, có một cặp của những đặc điểm mới như việc mạng lưới điều hướng tự động và chi tiết trong chương 8, Navigation Mesh. Những đặc điểm này làm cho việc tìm đường trong game của chúng ta dễ dàng hơn. Quả thật, thậm chí bạn có thể cần biết về A* để thực thi việc tìm đường cho nhân vật AI của bạn. Tuy nhiên, việc biết cách hệ thống hiển nhiên hoạt động phía sau scene sẽ giúp bạn trở thành một nhà lập trình AI chắc chắn. Không may, những đặc điểm điều hướng tiến triển đó trong Unity chỉ có thể trong phiên bản Pro vào thời điểm này.