Cơ bản về thuật toán tìm đường A*

Giới thiệu

Khi phát triển Artificial intelligence (AI), có lẽ thuật toán về tìm đường là một trong những điều cơ bản nhất nhưng đồng thời cũng cần lưu ý nhất, tại thực tế nó không hề đơn giản, đặc biệt là phải làm sao để nâng cao hiệu suất của thuật toán. Bài viết này mình sẽ giới thiệu sơ qua cách làm việc của thuật toán A*, thuật toán tìm đường được sử dụng rộng rãi nhất hiện nay.

Mô tả sơ qua về A*

A* là thuật toán tìm ra con đường ngắn nhất và tốn ít công sức nhất (cost) để đi từ vị trí đầu đến vị trí cuối xác định, và tất nhiên là nó sẽ tránh cả các vật cản trên đường nữa. Để đạt hiệu quả cao nhất cho thuật toán, chúng ra sẽ coi vật và vị trí nằm trên một bàn cờ, mỗi ô vuông là một node. Thuật toán A* đơn giản là tìm những ô mà vật di chuyển có thể đi vào được, đồng thời tính cost để di chuyển đến đó, xong tiếp tục tìm những ô mới xung quanh ô mình đang xét, cứ thế nó sẽ xét tất cả mọi trường hợp (node) theo thứ tự cost nhỏ nhất có thể đến lớn nhất có thể để tìm đường di chuyển.

Chi tiết hơn về các bước trong thuật toán A*

Bước chuẩn bị

1. Chúng ta sẽ có node A (điểm đầu) và node B (điểm cuối), open list (những ô có thể sẽ phải xét trong thuật toán) và closed list (những ô đã xét trong thuật toán).
2. Để di chuyển từ node X bất kì sang node Y cạnh nó, ta sẽ tính cost để di chuyển, tùy thuộc vào địa hình và nó là di chuyển chéo hay ngang (có thể coi chéo tốn 14 cost, ngang tốn 10 cost).
3. Khi xét một node, ta sẽ xét tổng cost của nó: F = G + H, trong đó H là cost dự tính khi di chuyển giữa 2 nodes cạnh nhau và G là tổng cost tính từ điểm khởi đầu cho đến node trước node đang xét. Ví dụ F là cost từ node A đến node Y, G là cost từ node X sang node Y, và H là cost từ node A đến node X theo con đường mình đang xét.

Bắt đầu thuật toán

1. Đưa node A vào open list.
2. Lặp lại toàn bộ các bước sau cho đến khi tìm được đến node B hoặc open list không còn ô nào:
   • Lấy node X từ open list với điểm F = G + H thấp nhất. Tìm tất cả các ô cạnh node X mà vật có thể di chuyển vào.
   • Loại node X khỏi open list và ném nó vào closed list để không phải xét nó thêm một lần nữa.
   • Với mỗi ô node T ở cạnh node X mình vừa tìm được:
   • Nếu node T đã nằm trong closed list, bỏ qua không thương tiếc.
   • Nếu node T chưa nằm trong open list, ném nó vào và ghi nhớ parent node là node X, đồng thời tính F = G + H, G và H cho nó.
   • Nếu node T đã nằm trong open list, so sánh G của node T đối với node X và G của node T mà ta đã ghi nhớ trước đó, nếu G mới lớn hơn thì bỏ qua, còn nếu nhỏ hơn thì ta lưu parent node mới cho node T, đồng thời tính và lưu F = G + H, G và H mới cho nó.
   • Dừng vòng lặp này khi một trong hai trường hợp sau xảy ra:
   • node B đã nằm trong closed list.
   • node B không nằm trong closed list và open list trống, tức là đã xét mọi trường hợp mà không tìm được đường đến node B.
3. Từ node B, ta tìm parent node cho đến khi đến được node A. Tập hợp từ node A đi qua các parent nodes đến node B là đường đi cần tìm.

Một vài lưu ý khi dùng thuật toán A*

1. Chia ô cho bản đồ hợp lý, nếu chúng ta xét từng pixel thì thuật toán này sẽ là thảm họa.
2. Sử dụng thuật toán sắp xếp an toàn nhất cho open list để lấy node X có F = G + H thấp nhất. Thuật toán sắp xếp được dùng phổ biến nhất cho trường hợp này là heapsort.
3. Ghi nhớ những địa điểm không thể với tới được (như các hòn đảo, lính oánh bộ không thể đặt chân vào được) để khỏi phải tính toán mất công.
4. Không sử dụng thuật toán này đối với nhiều vật cùng một lúc, nếu muốn hãy xét lần lượt với chúng, hoặc nhóm chúng thành một hoặc một ít vật tượng trưng và áp dụng thuật toán cho vật tượng trưng đó.
5. Thuật toán này sẽ tìm đường ngắn nhất, tốn ít cost nhất nhưng lại không tìm đường mượt nhất và thực tế nhất. Ví dụ ở bản đồ nhiều vật cản, đường đi tìm được sẽ ngoằn ngoèo chứ không đơn giản và thằng tắp như ta đáng lẽ làm trong thực tế.
6. Các bước cơ bản trên chỉ tìm đường đi từ node A đến node B cố định và đây là trường hợp đẹp nhất vì không có vật nào đang di chuyển trên đường đi của mình. Để xử lý vấn đề này thì cần các bước xử lý nâng cao và phức tạp hơn rất nhiều.
7. Đối với cost H, ta có thể làm nó khác biệt với các node khác nhau tùy vào địa hình (ví dụ đi trong cát mệt hơn đi trên đường nhựa).

Lời cuối

Nhìn chung thuật toán này khá lằng nhằng, đặc biệt là để xử lý thời gian thực, khi mà điểm đến của ta không cố định hoặc có các vật di chuyển khác cản trở. Trên đây chỉ là những bước cơ bản và cái nhìn sơ bộ về thuật toán để bạn hiểu thêm về pathfinding. Và do thuật toán này rất phổ biến nên chỉ mất vài phút Google, bạn có thể tìm được những đoạn implement code cho thuật toán này, nhờ vậy có thể bạn sẽ không phải mất công ngồi code lại toàn bộ các bước trên lại từ đầu.