Hướng dẫn a star algorithm shortest path python - một thuật toán sao con đường ngắn nhất python

Hôm nay, chúng tôi sẽ đi qua thuật toán A* Pathfinding, cách thức hoạt động và việc triển khai của nó trong mã giả và mã thực với Python.

Tìm kiếm chỉ mã giả hoặc mã nguồn? Cuộn xuống!

Nếu bạn là một nhà phát triển trò chơi, bạn có thể luôn muốn thực hiện một lối đi* nhân vật (hoặc kẻ thù). Tôi biết một vài năm trước đây tôi đã làm, nhưng với trình độ lập trình của tôi tại thời điểm tôi gặp vấn đề với các bài viết hiện tại ngoài kia. Tôi muốn viết điều này như một phần giới thiệu dễ dàng với một ví dụ về mã nguồn rõ ràng cho một pathfinding* để bất cứ ai cũng có thể dễ dàng chọn nó và sử dụng nó trong trò chơi của họ.

F = g + h

Một khía cạnh quan trọng của A* là f = g + h. Các biến F, G và H nằm trong lớp nút của chúng tôi và được tính toán mỗi khi chúng tôi tạo một nút mới. Nhanh chóng tôi sẽ đi qua những gì các biến này có nghĩa là gì.

• F là tổng chi phí của nút.
• G là khoảng cách giữa nút hiện tại và nút bắt đầu.
• H là heuristic - khoảng cách ước tính từ nút hiện tại đến nút cuối.

Hãy cùng xem một đồ họa nhanh chóng để giúp minh họa điều này.

Đáng kinh ngạc! Hãy nói rằng node(0) là vị trí khởi đầu của chúng tôi và node(19) là vị trí cuối cùng của chúng tôi. Hãy nói rằng, nút hiện tại của chúng tôi là ở Quảng trường Đỏ node(4).

G

G là khoảng cách giữa nút hiện tại và nút bắt đầu.

H là heuristic - khoảng cách ước tính từ nút hiện tại đến nút cuối.

Hãy cùng xem một đồ họa nhanh chóng để giúp minh họa điều này.

wow những con số như vậy, rất màu

H là heuristic - khoảng cách ước tính từ nút hiện tại đến nút cuối.

Hãy cùng xem một đồ họa nhanh chóng để giúp minh họa điều này.

wow những con số như vậy, rất màu

Đáng kinh ngạc! Hãy nói rằng node(0) là vị trí khởi đầu của chúng tôi và node(19) là vị trí cuối cùng của chúng tôi. Hãy nói rằng, nút hiện tại của chúng tôi là ở Quảng trường Đỏ node(4).

G

Nếu chúng ta đếm ngược, chúng ta có thể thấy rằng node(4) cách nút bắt đầu 4 khoảng trống của chúng ta.

F là tổng chi phí của nút.

G là khoảng cách giữa nút hiện tại và nút bắt đầu.

H là heuristic - khoảng cách ước tính từ nút hiện tại đến nút cuối.

Hãy cùng xem một đồ họa nhanh chóng để giúp minh họa điều này.

wow những con số như vậy, rất màu

Ở đây, một đồ họa để minh họa. Trên đầu, chúng tôi có thuật toán Dijkstra, trong đó tìm kiếm mà không có giá trị f = g + h3 này và bên dưới chúng tôi có một* sử dụng giá trị f = g + h3 này.

Thuật toán Dijkstra

Vì vậy, hãy nhìn vào thuật toán Dijkstra, chúng tôi thấy rằng nó chỉ tiếp tục tìm kiếm. Nó không biết nút nào là ’tốt nhất, vì vậy nó tính toán các đường dẫn cho tất cả chúng.

Một* thuật toán

Với A*, chúng ta thấy rằng một khi chúng ta vượt qua chướng ngại vật, thuật toán ưu tiên nút có f = g + h3 thấp nhất và cơ hội tốt nhất để đạt được kết thúc.

Các bước phương pháp - từ Patrick Lester

Tôi đã dán các bước cho A* từ bài viết của Patrick Lester, mà bạn có thể xem ở đây. Các trang web tương tự cũng được liệt kê dưới đây trong tài nguyên. Đây là một lời giải thích cực kỳ tốt, và là lý do tại sao tôi quyết định đi với nó hơn là viết lại.

1. Thêm hình vuông bắt đầu (hoặc nút) vào danh sách mở.

2. Lặp lại như sau:

A) Tìm kiếm hình vuông chi phí F thấp nhất trong danh sách mở. Chúng tôi gọi đây là hình vuông hiện tại.

B). Chuyển nó sang danh sách đóng.

C) Đối với mỗi trong số 8 hình vuông liền kề với hình vuông hiện tại này

• Nếu nó không thể đi bộ hoặc nếu nó nằm trong danh sách đóng, hãy bỏ qua nó. Nếu không làm như sau.
• Nếu nó không có trong danh sách mở, hãy thêm nó vào danh sách mở. Làm cho hình vuông hiện tại là cha mẹ của hình vuông này. Ghi lại chi phí F, G và H của hình vuông.
• Nếu nó nằm trong danh sách mở, hãy kiểm tra xem đường dẫn đến hình vuông đó có tốt hơn không, sử dụng chi phí g làm thước đo. Chi phí G thấp hơn có nghĩa là đây là một con đường tốt hơn. Nếu vậy, hãy thay đổi cha mẹ của hình vuông thành hình vuông hiện tại và tính toán lại các điểm G và F của hình vuông. Nếu bạn đang giữ danh sách mở của mình được sắp xếp theo điểm F, bạn có thể cần phải sử dụng danh sách để giải thích cho sự thay đổi.

D) Dừng khi bạn:

• Thêm hình vuông mục tiêu vào danh sách đóng, trong trường hợp đó đường dẫn đã được tìm thấy hoặc
• Không tìm thấy hình vuông mục tiêu và danh sách mở trống. Trong trường hợp này, không có đường dẫn.

3. Lưu đường dẫn. Làm việc ngược từ hình vuông mục tiêu, đi từ mỗi hình vuông đến hình vuông cha mẹ của nó cho đến khi bạn đến quảng trường bắt đầu. Đó là con đường của bạn.

Mã giả

Theo ví dụ dưới đây, bạn sẽ có thể thực hiện A* bằng bất kỳ ngôn ngữ nào.

// A* (star) Pathfinding// Initialize both open and closed list
let the openList equal empty list of nodes
let the closedList equal empty list of nodes// Add the start node
put the startNode on the openList (leave it's f at zero)// Loop until you find the end
while the openList is not empty    // Get the current node
    let the currentNode equal the node with the least f value
    remove the currentNode from the openList
    add the currentNode to the closedList    // Found the goal
    if currentNode is the goal
        Congratz! You've found the end! Backtrack to get path    // Generate children
    let the children of the currentNode equal the adjacent nodes
        for each child in the children        // Child is on the closedList
        if child is in the closedList
            continue to beginning of for loop        // Create the f, g, and h values
        child.g = currentNode.g + distance between child and current
        child.h = distance from child to end
        child.f = child.g + child.h        // Child is already in openList
        if child.position is in the openList's nodes positions
            if the child.g is higher than the openList node's g
                continue to beginning of for loop        // Add the child to the openList
        add the child to the openList

Mã nguồn (trong Python)

Hãy sử dụng mã này trong các dự án của riêng bạn.

CẬP NHẬT: Vui lòng xem các nhận xét về ý chính của tôi ở đây và một ngã ba ý chính của tôi ở đây - nó bao gồm các bản sửa lỗi có mặt trong mã bên dưới.: Please see the comments on my gist here, and a fork of my gist here — It includes bug fixes that are present in the code below.

Resouces

Có một số trang web tuyệt vời dưới đây bạn nên kiểm tra. Tôi đặc biệt đề xuất một* pathfinding cho người mới bắt đầu.

Một python * thuật toán * là gì?

Có phải A * tìm thấy con đường ngắn nhất?

Thuật toán A * là gì?

Làm thế nào để tôi tìm thấy con đường ngắn nhất trong Python?