Menemukan kemungkinan gerakan untuk suatu entitas dalam permainan ubin 2d

10

Saya mengalami masalah dengan istilah pencarian khusus untuk ini, tetapi bagaimana cara menemukan langkah yang mungkin dalam game strategi berbasis giliran 2D (mis. FF: Taktik, Fire Emblem, Advance Wars).

masukkan deskripsi gambar di sini

Saya tidak terlalu memikirkan medan (atau bahkan tabrakan) pada saat ini. Saya hanya ingin tahu algoritma apa yang dapat saya gunakan untuk mengetahui bahwa entitas X dapat memindahkan 5 ubin dan menyerang 2 ubin lebih jauh dari itu.

Saya tahu saya bisa menggunakan sesuatu seperti Dijkstra untuk menemukan jarak antara dua titik. Salah satu implementasi yang mungkin adalah mulai di lokasi pemain dan kemudian bercabang dari sana sampai jarak yang dikembalikan oleh Dijkstra lebih besar dari jumlah langkah.

Hanya ingin tahu apakah seseorang bisa mengarahkan saya ke arah yang benar (yaitu nama algoritma, teknik, artikel, dll).

NRaf
sumber
Saya pikir ini disebut pencarian jalur, untuk istilah pencarian? Jika Anda menggunakan pencarian jalan maka Anda dapat memiliki penghitung untuk menangani apa yang Anda butuhkan
Contoh
Ini pada dasarnya adalah bagian dari pencarian jalur (menghitung data meta untuk biaya perpindahan). Anda hanya menentukan lokasi yang berada dalam jangkauan, tetapi Anda tidak perlu menentukan rute yang akan Anda ambil juga.
Mario
1
Ini bukan real-time (RTS) jika berbasiskan à la FFTactics. : p
Alayric
Dalam 2d, Anda dapat menggunakan penghitungan Taxicab / Manhattan en.wikipedia.org/wiki/Taxicab_geometry
Gerben Jacobs

Jawaban:

5

Saya pikir Dijkstra yang dibatasi persis seperti yang ingin Anda gunakan. Cara Dijkstra menemukan jarak antara dua titik adalah memetakan jarak ke setiap simpul dari simpul asal, dan kemudian 'memilih' jalur terpendek dari peta jarak ini. Anda ingin melakukan hal yang hampir sama, kecuali Anda ingin grafik simpul jarak yang dibuatnya sebagai keluaran, bukan jalur ke titik tertentu.

Satu modifikasi yang ingin Anda lakukan adalah melewati penghitungan jarak dari node yang telah melebihi rentang pergerakan maksimum Anda. Kemudian Anda akan memiliki grafik simpul dari semua node yang dapat dituju oleh unit, ditambah perbatasan, jadi cukup potong node yang memiliki jarak lebih besar dari batas pergerakan.

Biola.

Dengan kata lain, cukup banyak apa yang Anda gambarkan dalam pertanyaan Anda adalah apa yang perlu Anda lakukan. Ini juga memiliki keuntungan karena dapat menggunakan output untuk melakukan pathfinding, tanpa perlu melakukan perhitungan lebih lanjut.

Agen TAS
sumber
Saya pikir Dijkstra terlalu banyak dalam kasus ini. OP tidak perlu jalur ke semua tujuan pergerakan yang mungkin, hanya jawaban ya / tidak pada apakah agen bisa sampai di sana. Dia bisa menghitung jalur nanti setelah pengguna memilih satu.
Michael Kristofik
Biaya menggunakan algoritma Dijkstra untuk menghitung lintasan setelah suatu tujuan telah diputuskan hampir sama persis dengan menggunakannya di muka (kecuali jika Anda menggunakan pendekatan heuristik seperti A * untuk lintasan). Tidak melakukannya di depan hanya menciptakan pekerjaan yang berlebihan, karena Dijkstra akan menjawab kedua pertanyaan 'ke mana saya bisa pergi' dan 'bagaimana saya bisa sampai di sana?'. Ini juga memungkinkan untuk penambahan komplikasi pada lingkungan yang mengubah biaya perpindahan, meskipun itu mungkin tidak perlu untuk aplikasi. Selanjutnya, pendekatan ini didokumentasikan dengan baik, yang bermanfaat bagi pelaksana.
TASagent
1
Saat melihat jawaban Mario, ia sebenarnya menggambarkan algoritma Dijkstra, kecuali ia membalikkan jarak, dan tidak menyebutkan itu adalah Dijkstra.
TASagent
1
Tidak akan mengatakan itu Dijkstra, karena Anda tidak benar-benar mencari rute terpendek juga tidak mencoba untuk mencapai titik tertentu. Ini pada dasarnya adalah bagian pertama dari Algoritma Dijkstra, itu benar. Masalah dengan kata-kata Anda, menggunakan Dijkstra, bisa menyesatkan dan saya pikir ini juga yang membingungkan Michael. Dia mungkin berpikir Anda menyarankan menggunakan Dijkstra sekali untuk setiap bidang / sel.
Mario
1
Berakhir menggunakan pendekatan ini karena bekerja dengan baik dan sangat mudah diperluas untuk menangani hambatan.
NRaf
12

Pendekatan paling sederhana (dan mungkin paling naif) yang bisa saya pikirkan saat ini:

  • Mulai karakter Anda dan tandai semua bidang sekitarnya sebagai steps - 1.
  • Iterasi semua bidang yang baru ditandai dan sekali lagi tandai bidang di sekitarnya sebagai steps - 1tempat stepsnomor langkah bidang saat ini, kecuali jika bidang baru memiliki angka yang sudah lebih tinggi.
  • Ulangi langkah terakhir sampai Anda kehabisan langkah.
Mario
sumber
1
Algoritma ini memiliki nama: Flood Fill .
Michael Kristofik
6
@MichaelKristofik: Saya akan menyebutnya pencarian pertama yang luas . Isi banjir tidak melacak jarak.
BlueRaja - Danny Pflughoeft
2

Saya pikir apa yang Anda cari mungkin Jarak Manhattan . Dengan asumsi tidak ada kendala, Anda dapat mengatakan bahwa kotak dapat dijangkau hanya jika:

| toX-fromX | + | toY-fromY | <maxMoveDistance

Algoritme ini mungkin bukan arah yang tepat untuk digunakan jika Anda akan mengalami hambatan di kemudian hari; salah satu cara yang mungkin untuk mengadaptasinya mungkin melibatkan rintangan yang membuat 'bayangan' dan mengevaluasi kembali dari titik terdekat.

EDIT (Karena saya punya sedikit waktu luang sekarang):

Dengan 'bayangan' maksud saya sesuatu seperti ini, jika 0 adalah kotak yang dapat dijangkau, C adalah karakter, dan X adalah hambatan:

 012345678
0    0
1   00
2  000X
3 000C000
4  00000
5   000
6    0
 012345678

Karena (5, 2) merupakan hambatan, Anda mulai dengan mengasumsikan bahwa Anda tidak dapat mencapai apa pun dengan x> = 5 DAN y <= 2. Anda kemudian dapat menghitung ulang dari kotak lain; jika Anda ingin pergi ke (5, 1) Anda bisa menghitung jarak manhattan dari (4, 1) dan melihat apakah + jarak dari karakter ke (4, 1) kurang dari jarak pergerakan pemain.

Ini adalah contoh yang cukup sepele, tetapi jika Anda memiliki banyak hambatan dan / atau rentang gerakan yang sedikit lebih lama, itu harus dapat menangani kompleksitas.

Apakah itu sebenarnya lebih baik dari sekadar mengisi banjir, baik dalam kompleksitas pemrograman atau efisiensi eksekusi, saya tidak tahu. Sepertinya cara yang lebih menarik untuk menyelesaikan masalah.

Manusia Timah
sumber
Apa yang Anda maksudkan dengan casting bayangan?
NRaf
1
Diedit untuk klarifikasi.
Tin Man