A* Tìm kiếm trên đường đi dựa trên lưới với khả năng tránh chướng ngại vật

Giới thiệu về thuật toán A*

Thuật toán A* là một thuật toán tìm kiếm đường đi thông minh, được sử dụng rộng rãi trong nhiều lĩnh vực như trò chơi điện tử, điều khiển robot và lập kế hoạch đường đi. A* hoạt động bằng cách sử dụng một hàm heuristic để ước tính khoảng cách từ điểm hiện tại đến điểm đích, kết hợp với chi phí di chuyển từ điểm bắt đầu đến điểm hiện tại.

Cách thức hoạt động của A*

A* sử dụng một lưới để đại diện cho không gian tìm kiếm, với mỗi ô lưới đại diện cho một vị trí có thể di chuyển đến. Mỗi ô lưới có một giá trị chi phí di chuyển, đại diện cho chi phí cần thiết để di chuyển từ ô lưới đó đến ô lưới khác. A* cũng sử dụng một hàm heuristic để ước tính khoảng cách từ điểm hiện tại đến điểm đích.

Áp dụng A* vào thực tế

Để áp dụng A* vào thực tế, chúng ta cần phải định nghĩa hàm heuristic và chi phí di chuyển cho mỗi ô lưới. Hàm heuristic có thể được định nghĩa dựa trên khoảng cách Euclid giữa điểm hiện tại và điểm đích, hoặc dựa trên khoảng cách Manhattan nếu chúng ta chỉ cho phép di chuyển theo hướng ngang và dọc.

Ví dụ, giả sử chúng ta có một lưới 10x10, với điểm bắt đầu tại ô lưới (0,0) và điểm đích tại ô lưới (9,9). Chúng ta có thể định nghĩa hàm heuristic như sau:

python
def heuristic(x, y):
    return abs(x - 9) + abs(y - 9)

Chi phí di chuyển có thể được định nghĩa dựa trên loại địa hình của mỗi ô lưới. Ví dụ, nếu ô lưới là đất liền, chi phí di chuyển có thể là 1, trong khi nếu ô lưới là nước, chi phí di chuyển có thể là 5.

Tránh chướng ngại vật

A* cũng có thể được sử dụng để tránh chướng ngại vật trên lưới. Để làm điều này, chúng ta cần phải thêm một bước kiểm tra chướng ngại vật vào thuật toán A*. Nếu ô lưới hiện tại là chướng ngại vật, chúng ta sẽ không cho phép di chuyển đến ô lưới đó.

Ví dụ, giả sử chúng ta có một lưới 10x10, với điểm bắt đầu tại ô lưới (0,0) và điểm đích tại ô lưới (9,9). Chúng ta có thể định nghĩa một danh sách chướng ngại vật như sau:

python
obstacles = [(3,3), (3,4), (3,5)]

Sau đó, chúng ta có thể thêm một bước kiểm tra chướng ngại vật vào thuật toán A* như sau:

python
def a_star(start, goal, obstacles):
    # ...
    for neighbor in neighbors:
        if neighbor in obstacles:
            continue
        # ...

Kết luận

A* là một thuật toán tìm kiếm đường đi hiệu quả trên lưới, giúp tránh chướng ngại vật và tìm ra đường đi ngắn nhất. Để áp dụng A* vào thực tế, chúng ta cần phải định nghĩa hàm heuristic và chi phí di chuyển cho mỗi ô lưới, và thêm một bước kiểm tra chướng ngại vật vào thuật toán A*. Với việc áp dụng A*, chúng ta có thể xây dựng các hệ thống tìm kiếm đường đi thông minh và hiệu quả.

Nguồn: https://dev.to/saksham780/a-search-on-grid-based-pathfinding-with-obstacle-avoidance-1knm