A* Pathfinding

Hẳn là bạn đã từng chơi game hoặc đang phải làm một game nào đó mà có phải điều khiển nhân vật hoặc viết AI cho bot đi từ một điểm A tới một điểm B, đi qua các trở ngại như sông, nhà, tường, … muốn làm được điều đó hãy đọc bài viết này của tui.

Thật ra những bài hướng dẫn về A-star Pathfinding có trên mạng có rất rất nhiều rồi, nhưng mình thấy toàn bài viết dành cho người đã biết cơ bản về A-star rồi. Thiết nghĩ nhiều người chưa biết khả năng đọc chúng sẽ khó hiểu và rất mất công.

Bài viết này sẽ giới thiệu các nguyên tắc cơ bản từ đầu, chúng ta sẽ từng bước thảo luận thuật toán A-star pathfinding làm việc như thế nào, và mình sẽ kèm luôn hình ảnh minh họa.

Với bản thân thì áp dùng Unity 3D vào ví dụ minh họa này sẽ rất rất dễ dàng với mình chỉ nháy mắt là xong bởi vì mình thành thục Unity 3D hơn. Nhưng ví dụ này mình sẽ viết trên Java trên android project để thấy rằng dù có sử dụng bất kỳ ngôn ngữ lập trình hoặc bất cứ nền tảng nào đi chăng nữa bạn đều có thể áp dụng được sau khi đọc bài viết này.

Chém thế thôi, chúng ta bắt đầu thôi nào.

Bài toán Pathfinding của sếp

**Cùng tưởng tượng, trong khu văn phòng bàn ghế được sắp xếp như trong hình dưới. Giả sử ổng sếp ABCS gì đó của tôi(ở đây tôi đưa hình ảnh con cá sấu vào vì không dám đưa ảnh của ổng lên sợ bị kết tội bôi xấu ) muốn tìm tôi để tính sổ vì tội danh đi muộn không báo cáo và đặc biệt chuyên gia nói xấu sếp sau lưng. Nhưng mà từ chỗ ổng tới chỗ tôi xa quá, mà không thể đi thẳng tắp tới chỗ tôi được, trên đường thẳng có rất nhiều bàn ghế. Ổng cũng lười nên ổng giao cho ông GL nào đó nhiệm vụ tìm cho ổng 1 con đường tới chỗ ngồi cụa tôi là ngắn nhất. **

Đơn giản hóa vùng tìm kiếm

Bước đầu tiên của thuật toán tìm đường là đơn giản hóa khu vực tìm kiếm cho việc quản lý dễ dàng hơn.

Để làm được điều này lại còn phụ thuộc vào bài toán của chúng ta. Ví dụ: Chúng ta có thể chia vùng tìm kiếm trong ảnh thành từng pixel, nhưng mà thực sự là nó không cần thiết lắm bởi chia như vậy thì số pixel có vẻ hơi lớn. Trong khi đó bài toán của chúng ta có thể tính toán theo từng dãy bàn, từng ô vuông

Vậy chúng ta sẽ chia cái vùng tìm kiếm thành các ô vuông. Mỗi ô vuông là một phần tử của thuật toán tìm đường. Dĩ nhiên ngoài cái hình vuông ra bạn cũng có thể chọn hình tam giác hay lục giác… gì đó. Nhưng tôi nghĩ hình vuông là phù hợp và dễ nhất để vừa khít được vùng tìm kiếm.

Chia như trên thì vùng tìm kiếm của chúng ta sẽ được biểu diễn bởi một mảng hai chiều có kích thước giống như cái bản đồ. Vậy nếu map có 15×12 ô thì vùng search của chúng ta sẽ có một mảng 180 ô vuông. Nếu chúng ta chia map của chúng ta thành pixel thì (lol). Biết rồi đấy nhé.

Ở ví dụ này tôi sẽ để kích thước như trong ảnh là 12×15 ô vuông.

Danh sách Open và Close

Giờ chúng ta sẽ tạo một vùng search đơn giản và thảo luận cách hoạt động của thuật toán A* nhé.

Trước tiên chúng ta cần có 2 danh sách:

• Một ghi lại tất cả các ô vuông mà chúng ta cần xem xét để tìm ra con đường ngắn nhất(Tạm gọi Open list).
• Một list ghi lại các ô vuông mà chúng ta không cần xem xét nó lại lần nữa.(Tạm gọi Close list)

Giờ chúng ta sẽ add vị trí của ông sếp vào Close list đầu tiên(là điểm bắt đầu). Sau đó add tất cả các ô vuông lân cận của vị trí hiện tại vào Open list. Nhớ là nếu ô vuông đó có thể đi được tức là không phải cái bàn hoặc obstacle nào đó nhé.

Xem hình ảnh để thấy rõ hơn nhé Các điểm lân cận sẽ được thêm vào Open, là 2 cái ô vuông màu da cam kia kìa:

Giờ thì làm sao để xác định được đường đi ngắn nhất. Vì nền văn phòng là phẳng nên nhìn từ trên xuống nó sẽ là 2D. Vậy sẽ đặt cho mỗi ô vuông 1 giá trị vị trí theo hệ tọa độ mặt phẳng OXY, trục trẹo thế nào tùy bạn quy định nhé.

Tính toán giá trị đường đi

Đặt mỗi ô vuông một giá gị là G+H, trong đó:

• G là khoảng cách di chuyển từ điểm bắt đâì A tới ô vuông hiện tại. Vậy các ô vuông lân cận từ điểm bắt đầu sẽ có khoảng cách là chiều dài từ ô vuông bắt đầu tới chúng. Vì chúng ta đã quy nó về hệ tọa độ nên việc tính khoảng cách dựa vào tọa độ 2 điểm bạn tự search nhé. Ngày xưa học toán nhiều rồi.
• H là khoảng cách từ ô vuông hiện tại đang xét mà tới điểm đích gọi là điểm B. Nó chỉ là phỏng đoán tại vì chúng ta không thể biết được giá trị của nó. Chỉ là ước lượng.

Ở đây tôi chỉ xét tới việc ổng sếp chỉ có thể đi thẳng giữa các ô vuông chứ không di chuyển chéo theo các ô vuông được. Tuy nhiên cũng có thể làm theo những cách khác nhau cho trò chơi của chúng ta. Ví dụ:

• Nếu bạn cho phép một chuyển động chéo, cần xét thêm ô vuông liền kề
• Nếu bạn có các loại địa hình khác nhau, hoặc đường đi phải lên núi xuống biển, cho nó vào hệ tọa độ OXYZ là xong.

Đó là những ý tưởng chung, giờ chúng ta cùng đi chi tiết vào các giá trị G và H.

Về G

Luôn nhớ rằng G là khoảng cách từ điểm bắt đầu tới điểm hiện tại.

Để tính toán được G, chúng ta cần lấy thông tin G của điểm trước điểm hiện tại cộng với khoảng cách từ điểm trước đó tới điểm hiện tại là ok. Bởi vậy mà mỗi hình vuông sẽ có được giá trị G từ điểm xuất phát tới điểm đó riêng.

Hình minh họa bên dưới biểu diễn giá trị G của từng ô vuông một từ điểm xuất phát tới đích. Lười vẽ pts nên mình cho luôn vào exel. Giả xử khoảng cách giữa các ô vuông của chúng ta là a. Vậy ta sẽ có:

Về H

H chúng ta gọi nó là tổng khoảng cách ước lượng từ điểm hiện tại tới đích. Khi H càng gần với giá trị ước lượng thực tế con đường ngắn chúng ta tìm sẽ càng gần. Đơn giản nhất ta sẽ tính H bằng cách tính khoảng cách từ điểm hiện tại tới điểm đích bằng đường chym bay.

Ví dụ: hình vẽ phía dưới sử dụng cách tính trên để ước lượng H từ các điểm bắt đầu khác nhau tới điểm đích B.

Thuật toán A*

Giờ chúng ta đã biết cách tính toán giá trị mỗi hình vuông(gọi F = G + H). Cùng xem cách làm việc của A* như thế nào nhé.

Việc tìm ra con đường ngắn nhất của anh GL sẽ lặp lại các bước như sau:

• Lấy ô vuông trong Open có giá trị nhỏ nhất. Gọi nó là ô vuông S.
• Xóa bỏ S từ Open và add S vào Close.
• Nếu T là tập hợp dách sách các ô vuông liền kề của S thì gọi I là duyệt mỗi ô vuông trong tập T:

• Nếu I đã có trong Close thì bỏ qua.
• Nếu I không trong Open thì add nó vào tính toán các giá trị khoảng cách.
• Nếu I đã ở trong Open: Kiểm tra nếu giá trị F là nhỏ hơn giá trị F của điểm hiện tại thì update mới điểm hiện tại.

Xét cụ thể đường đi ngắn nhất

Trong hình bên dưới, ta có danh sách các giá trị cho F = G + H:

• F(giá trị của ô vuông): góc trái trên
• G (giá trị từ A tới ô vuông hiện tại): Góc dưới bên trái
• H (ước tính giá trị từ ô vuông hiện tại tới B): Góc dưới bên phải

Ô vuông màu đỏ sẽ được đưa vào Close.

_ Bước 1_

Trong bước đầu tiên, anh GL này sẽ xác định các ô vuông liền kề có thể đi được với điểm bắt đầu A, tính toán F của chúng và thêm chúng vào Open:

Bạn có thể thấy, giá trị H được liệt kê cho mỗi ô vuông.

Bước 2

Trong bước tiếp theo, anh này sẽ chọn ra F ngắn nhất và thêm ô hiện tại vào Close. Trường hợp F bằng nhau thì tùy bạn code rồi chọn nhé.

_ Bước 3_

Tiếp tục chọn F nhỏ nhất:

Bước 4

Cứ lặp đi lặp lại các bước:

Cho tới khi tới khi xét tới điểm đích B.

Trên lý thuyết là như trên, giờ còn áp dụng vào code

Dưới đây là code push nên githup. Mời bạn tham khảo. Hiện code mình đang sửa, rảnh rảnh mình sửa lại code rồi push lên. Nhưng thuật toán trên đó mình chạy đã ok rồi. Bạn có thể tham khảo thuật toán trước. https://github.com/daminhtung/AStar