it-swarm-vi.tech

Làm cách nào để triển khai thuật toán tìm đường A *, với chi phí chuyển động cho mọi ngôn ngữ lập trình?

Chúng ta có thể khiến mọi người đăng mã các triển khai đơn giản, được tối ưu hóa của thuật toán tìm đường dẫn A *, bằng mọi ngôn ngữ không?

Điều này chủ yếu là để giải trí và để chơi với những gì stackoverflow có khả năng ... mặc dù tôi thực sự quan tâm đến việc có được phiên bản ActionScript 3 này.

Nhưng ý tưởng là "Câu hỏi" này sẽ tiếp tục được cập nhật vĩnh viễn trong tương lai, ngay cả khi các ngôn ngữ lập trình khác nhau được tạo ra!

Tôi không biết bất kỳ nơi nào khác trực tuyến nơi bạn có thể thấy mã giả "được dịch" sang nhiều ngôn ngữ khác nhau (ít hơn nhiều). Có vẻ như đó là một tài nguyên đáng giá, và mặc dù không nhất thiết là trang web này được thiết kế để làm gì, không có hại gì khi dùng thử và xem liệu nó có phải là một thứ đáng giá mà stackoverflow có thể được sử dụng cho!

29
IQpierce

Đây là một triển khai JavaScript , cùng với mã nguồn và một bản demo trực tuyến Tôi đã làm như một dự án sở thích/nghiên cứu. 

Nó rất đơn giản, nhưng bạn có thể thay đổi một số thông số (kích thước lưới, # tường, gỡ/tắt thông tin). Nó sẽ hiển thị cho bạn các giá trị f (x), g (x) và h(x) được tính cho mỗi nút được kiểm tra.

Việc thực hiện trang demo sử dụng jQuery.

11
Brian Grinstead

Đây là một triển khai C++. Hiện tại nó đã được thử nghiệm khá tốt và được sử dụng trong các trò chơi video thương mại và các dự án AI khác nhau.

http://code.google.com.vn/p/a-star-alerskym-imcellenceation/

Và có một hướng dẫn, mà tôi thực sự đã viết đầu tiên:

http://www.heyes-jones.com/astar.html

9
justinhj

Đây là triển khai C # được thực hiện bởi một trong những người xây dựng ngôn ngữ.

5
Joel Coehoorn

Mã nguồn và bản demo trong các ngôn ngữ lập trình khác nhau:

Danh sách các bản demo cho từng ngôn ngữ:

C++: 1
Java: 3
Processing: 1
Actionscript 3 (Flash): 4
Flex (Flash): 1
Javascript: 6
C#: 1
Ruby: 1
Prolog: 1
Unity: 1
Lua: 1

Demo tìm đường trong các ngôn ngữ khác nhau

Thưởng thức :)

3
Sir

Mã nguồn Python và C++ cùng với hướng dẫn tương tác . Mã được viết để làm việc trên các biểu đồ nói chung và không cụ thể cho các lưới (như bạn sẽ tìm thấy trong nhiều ví dụ về A * trên web). Nó sử dụng các đống nhị phân cho hàng đợi ưu tiên (cả Python và C++ đều có các đống nhị phân trong các thư viện chuẩn của chúng). Tôi có Tìm kiếm đầu tiên của Breadth, Thuật toán của Dijkstra và A * trên trang đó. Mã này khá ngắn (ngắn hơn hầu hết mã mẫu A * tôi tìm thấy).

1
amitp

Một ví dụ AS 3 ... http://www.dauntless.be/astar/

1
Chris

Không phải là một triển khai, nhưng tôi đã tìm thấy http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html là một giải thích đặc biệt rõ ràng về thuật toán. Có mã giả giúp thực hiện rất dễ dàng, cùng với việc xem xét mở rộng các cấu trúc dữ liệu khác nhau có thể được sử dụng để triển khai các tập mở và đóng, thảo luận về các phương pháp phỏng đoán khác nhau có thể áp dụng trong các tình huống khác nhau, sửa đổi các heuristic để có các hành vi cụ thể (ví dụ: lấy xấp xỉ các đường thẳng trong các hệ thống chỉ hỗ trợ các góc di chuyển hạn chế), các cạm bẫy phổ biến (ví dụ: sử dụng phương pháp heuristic với quy mô khác với chi phí di chuyển thực tế) và một số tối ưu hóa (ví dụ: làm việc với các vùng có chi phí thống nhất thay vì lưới điện).

1
Jules

Việc triển khai Clojure , chủ yếu dựa trên một ví dụ được đưa ra trong PAIP .

1
Jeff Foster

Một triển khai VB6.

http://www.gandraxa.com/pathfinding_with_a_star.xml

Điều này đặc biệt hữu ích vì bạn có thể thực hiện từng bước và hiểu rõ về cách thức hoạt động của thuật toán. Điều này có thể khá có giá trị khi chuyển đổi thuật toán sang ngôn ngữ khác.

0
G Mastros

Tôi đã triển khai A * trong C như một cách để học C, vì vậy tôi không thể hứa nó đẹp, nhưng nó hoạt động! [.___.

https://github.com/PeterMitrano/A-star-Pathfinding/blob/master/probols_83.c

0
Peter Mitrano

Một triển khai Java được tối ưu hóa có sẵn trong GraphHopper.

0
Karussell