it-swarm-id.com

Bagaimana cara menerapkan algoritma pencarian jalan A *, dengan biaya perpindahan untuk setiap bahasa pemrograman?

Bisakah kita membuat orang memposting kode implementasi algoritma A * pathfinding yang sederhana dan dioptimalkan, dalam setiap bahasa?

Ini sebagian besar untuk bersenang-senang dan untuk bermain dengan apa yang bisa dilakukan oleh stackoverflow ... walaupun saya sebenarnya tertarik untuk mendapatkan versi ActionScript 3 ini.

Tetapi idenya adalah bahwa "Pertanyaan" ini akan terus diperbarui selamanya ke masa depan, bahkan saat bahasa pemrograman yang berbeda dibuat!

Saya tidak tahu ada tempat lain online di mana Anda dapat melihat kode semu "diterjemahkan" ke banyak (apalagi setiap) bahasa yang berbeda. Sepertinya ini adalah sumber daya yang berharga, dan meskipun belum tentu untuk apa situs ini dirancang, tidak ada salahnya untuk mencobanya dan melihat apakah itu ternyata menjadi hal yang bermanfaat yang bisa digunakan oleh stackoverflow!

29
IQpierce

Berikut adalah implementasi JavaScript , bersama dengan kode sumber dan demo online Saya lakukan sebagai proyek hobi/penelitian.

Ini sangat sederhana, tetapi Anda dapat mengubah beberapa params (ukuran kisi, # dinding, info debug aktif/nonaktif). Ini akan menunjukkan Anda nilai f (x), g (x), dan h(x) yang dihitung untuk setiap node yang diperiksa.

Implementasi halaman demo menggunakan jQuery.

11
Brian Grinstead

Inilah implementasi C++. Ini sudah diuji dengan cukup baik sekarang, dan digunakan dalam video game komersial dan berbagai proyek AI.

http://code.google.com/p/a-star-algorithm-implementation/

Dan ada tutorial, yang saya tulis pertama kali:

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

9
justinhj

Inilah implementasi C # dilakukan oleh salah satu orang yang membangun bahasa.

5
Joel Coehoorn

Kode sumber dan demo dalam berbagai bahasa pemrograman:

Daftar demo untuk setiap bahasa:

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 Perintisan Jalan dalam berbagai bahasa

Nikmati :)

3
Sir

Kode sumber Python dan C++ bersama dengan tutorial interaktif . Kode ini ditulis untuk bekerja pada grafik secara umum, dan tidak khusus untuk kisi (seperti yang akan Anda temukan dalam banyak contoh A * di web). Ia menggunakan tumpukan biner untuk antrian prioritas (baik Python dan C++ memiliki tumpukan biner di perpustakaan standar mereka). Saya memiliki Pencarian Pertama Breadth, Algoritma Dijkstra, dan A * di halaman itu. Kode ini cukup pendek (lebih pendek dari kebanyakan kode sampel A * yang saya temukan).

1
amitp
1
Chris

Bukan implementasi, tetapi saya menemukan http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html menjadi penjelasan yang sangat jelas tentang algoritma. Memiliki pseudocode yang membuatnya sangat mudah diimplementasikan, bersama dengan tinjauan luas dari berbagai struktur data yang dapat digunakan untuk mengimplementasikan set terbuka & tertutup, diskusi berbagai heuristik yang berlaku dalam situasi yang berbeda, modifikasi heuristik untuk mendapatkan perilaku spesifik (misalnya mendapatkan perkiraan garis lurus dalam sistem yang hanya mendukung sudut gerakan terbatas), perangkap umum (misalnya menggunakan heuristik dengan skala yang berbeda dengan biaya gerakan aktual), dan beberapa optimisasi (mis. bekerja dengan daerah dengan biaya seragam daripada menggunakan kisi).

1
Jules

A Clojure implementasi, sangat didasarkan pada contoh yang diberikan pada PAIP .

1
Jeff Foster

Implementasi VB6.

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

Ini sangat berguna karena Anda dapat melangkah melalui proses dan mendapatkan pemahaman yang baik tentang bagaimana algoritma bekerja. Ini bisa sangat berharga saat mengonversi algoritme ke bahasa lain.

0
G Mastros

Saya menerapkan A * dalam C sebagai cara untuk belajar C, jadi saya tidak bisa menjanjikan itu indah, tetapi berhasil! Saya menggunakannya untuk menyelesaikan Project Euler # 83 dan bekerja pada dua kasus uji.

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

0
Peter Mitrano

Implementasi Java yang dioptimalkan tersedia di GraphHopper.

0
Karussell