Menemukan kemungkinan gerakan untuk suatu entitas dalam permainan ubin 2d

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).

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).

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.

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.

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.