Tweaking AStar untuk menemukan lokasi terdekat ke tujuan yang tidak terjangkau

11

Saya telah mengimplementasikan AStar di Jawa dan berfungsi baik untuk area dengan rintangan di mana tujuan yang dipilih dapat dijangkau.

Namun, ketika tujuan tidak dapat dijangkau, "lintasan" yang dihitung sama sekali tidak menuju ke lokasi terdekat (ke lokasi yang tidak terjangkau) tetapi sebaliknya merupakan beberapa jalur acak.

Apakah ada cara yang layak untuk mengubah AStar agar menemukan jalur ke lokasi terdekat ke tujuan yang tidak terjangkau?

path-finding Shivan Dragon
sumber

Jawaban:

20

Melacak node dengan yang terendah EstimatedDistanceToEnd(mis. Yang terendah h(x)), dan jika tidak ada end-node yang dapat dicapai untuk mundur, mundur dari sebaliknya.

BlueRaja - Danny Pflughoeft
sumber
Sederhana. Aku menyukainya!
John McDonald
Saya baru saja menampar kepala saya dan berkata "doh" ketika saya membaca jawaban Anda. Terima kasih!
Shivan Dragon
1

Ini sebenarnya bukan pertanyaan A *. A * adalah semua tentang menemukan jalur dari titik A ke titik B. Meskipun dapat diperpanjang, hasilnya bisa dengan mudah berantakan dan tidak dapat diprediksi. Yang Anda butuhkan adalah sebuah algoritma yang memilih tujuan terdekat yang dapat dijangkau.

Inilah salah satu cara untuk melakukan ini: Jika A * mengembalikan jalur yang valid (mulai / akhir node dalam masukan jalur yang cocok), kembalikan jalur. Jika tidak...

  • Mulai mencari dari simpul awal
  • Lintasi semua simpul yang ditautkan (ingat untuk menandai yang dikunjungi untuk menghindari rekursi tak terbatas)
  • Bandingkan jarak ke tujuan untuk menemukan simpul terdekat
snake5
sumber
Sesuatu seperti Flood Fill tampaknya sesuai dengan en.wikipedia.org/wiki/Flood_fill perhatikan bahwa Anda masih perlu A * dari mulai node ke node dengan jarak terendah. Perhatikan juga bahwa ini selalu melibatkan memeriksa semua node yang terhubung dan karenanya bisa sangat lambat.
Roy T.
Ya, bisa lambat. Tetapi lambatnya kemungkinan besar datang dari memiliki node yang tersebar di seluruh memori; yang bisa dengan mudah diperbaiki. Juga, mungkin untuk mempercepatnya dengan mengorbankan akurasi - lewati saja tautan yang terlalu jauh atau arahkan ke arah yang salah.
snake5
1
@Roy: A *, BFS, dan semua algoritma pathfinding serupa akan persis seperti yang lambat seperti banjir-fill, karena mereka semua perlu memeriksa setiap simpul terhubung untuk memastikan ada adalah tidak ada jalan sampai akhir. Namun ada cara untuk mengatasi masalah ini; lihat di sini .
BlueRaja - Danny Pflughoeft