Bagaimana menentukan rentang gerakan yang mungkin dalam permainan strategi berbasis giliran, berbasis jarak?

11

Saya membuat game strategi 2 dimensi, berbasis giliran menggunakan c ++ dan SFML-2.0. Gerakan berbasis jarak daripada berbasis grid, dengan beberapa potongan berbentuk segitiga berbeda yang, pada gilirannya, masing-masing dapat berputar di tempat atau bergerak maju.

Gerakan akan bekerja sedemikian rupa sehingga pemain memilih lokasi untuk potongan untuk bergerak, yang menghasilkan jalur potensial untuk potongan untuk mengambil. Setelah pemain mengonfirmasi keputusannya, karya tersebut akan bergerak di sepanjang jalan itu ke lokasi yang diinginkan. Jalur dibatasi oleh dua faktor: jarak, seberapa jauh sebuah karya dapat berjalan, memperhitungkan setiap belokan (jadi jika ada kurva, itu akan menjadi panjang di sepanjang kurva, dan tidak langsung dari titik ke titik); dan sudut kemudi, seberapa jauh potongan dapat berputar di titik (dan hingga setiap) saat bergerak (misalnya, dari -30 hingga 30 derajat).

Pertanyaan saya adalah, bagaimana saya harus menentukan kisaran lokasi potensial yang bisa dipilih pemain untuk dipindahkan?

Saya tidak sepenuhnya yakin persamaan dan / atau algoritma apa yang digunakan di sini. Rencana awal saya sangat rumit, sampai pada titik di mana hampir tidak mungkin untuk dilaksanakan, apalagi menjelaskan, dan saya pada titik ini benar-benar kehilangan dengan proyek terhenti.

Bagaimana saya bisa menentukan rentang unit yang bisa bergerak, dengan mempertimbangkan radius beloknya?

Misalnya, pada gambar di bawah ini. Garis merah, biru dan hijau semuanya akan memiliki panjang yang sama. Lingkaran ungu menunjukkan rentang gerakan yang dapat dipindahkan unit. (Bentuknya mungkin tidak akurat dan garis-garisnya mungkin sebenarnya tidak sama, tetapi Anda tahu)

masukkan deskripsi gambar di sini

sfphilli
sumber
Itu masih hanya akan bisa bergerak dengan jarak (total) yang sama. Jadi pertanyaannya sebenarnya tentang mencari tahu "seberapa jauh itu berubah?" / "Berapa banyak yang perlu berubah?" / "Di mana ia harus berubah?". Anda mungkin perlu mulai dari menentukan jalur reguler, lalu melangkah mundur untuk sudut di atas jumlah tertentu; perhatikan bahwa jarak akhir akan lebih panjang di jalur garis lurus (berbelok terbaru) daripada dengan kurva.
Clockwork-Muse
Ya, jarak yang ditempuh adalah faktor pembatas utama. Rintangan terbesar saya di sini adalah saya perlu memperhitungkan bahwa kepingan itu bisa berputar, dan terus berbelok, pada titik mana pun yang bisa dijangkau, selama masih ada jarak yang tersisa.
sfphilli
Apa maksud Anda, rentang yang bisa dipindahkan unit? Maksud Anda poin yang bisa dipindahkan? Seberapa familiar Anda dengan aljabar linier (vektor)?
BlueRaja - Danny Pflughoeft
1
Skenario kehidupan nyata apa yang Anda coba modelkan? Masalah Anda terlalu samar pada persyaratan, sehingga terlalu banyak pendekatan solusi yang diusulkan. Ada beberapa pendekatan terkenal untuk (secara virtual) setiap masalah khusus di bidang ini, tetapi semua orang menebak dari banyak masalah yang sebenarnya Anda atasi.
Pieter Geerkens
1
@PieterGeerkens Saya kira karena OP tidak meminta kode, mereka meminta algoritma. Dan telah memberikan detail yang cukup tentang skenario bahwa suatu algoritma dapat dipahami. Ini umum dan dapat diterima.
MichaelHouse

Jawaban:

4

Hasilkan bidang aliran atau jarak, menggunakan Dijsktra.

Pada dasarnya, isi kotak menggunakan algoritma Dijkstra tanpa tujuan (mungkin nama yang berbeda untuk itu; tidak tahu itu). Ambil saja setiap simpul terbuka, hitung tetangga yang dapat dijangkau, dorong mereka pada daftar terbuka, atur pada daftar tertutup, perbarui jalur "berikutnya" simpul induk sesuai keperluan, dll. Saat menentukan biaya untuk mencapai simpul baru, pertimbangkan batasan belok.

Hasilnya sekarang adalah bahwa Anda memiliki jaringan semua node Anda tentang cara untuk kembali ke awal. Node yang tidak dapat dijangkau tidak akan tersentuh oleh langkah pertama. Node yang dapat dijangkau akan dikomputasi dengan elemen "node berikutnya di sepanjang jalur terbaik ke induk" sehingga Anda dapat menyorot semua node dan kemudian juga menggunakan informasi ini untuk menampilkan atau mengeksekusi jalur pergerakan saat pengguna melayang atau mengklik area yang disorot.

Sean Middleditch
sumber
Tidak cukup bagaimana saya akan menjelaskan konsep, atau bagaimana saya akan mengimplementasikannya, tetapi tentu saja pendekatan yang tepat.
Pieter Geerkens
Pemahaman saya tentang algoritma, sebagaimana adanya, adalah bahwa node-traversal harus independen jalur. Jadi, untuk mencapai ini, Anda perlu menambahkan tingkat kebebasan lain (sumbu lain untuk membuat simpul Anda) yang didedikasikan untuk menghadap. Dengan kata lain, Anda akan memiliki simpul untuk setiap kombinasi yang berbeda X, Y, berpotensi Z, dan Menghadapi. Jika tidak, menemukan jalur terpendek untuk memasuki sebuah simpul tidak membedakan antara berbagai sisi ketika meninggalkannya. Apakah itu benar? Jika demikian, apakah metode ini mungkin terlalu intensif?
TASagent
@TASagent: Poin bagus, saya tidak memikirkan itu sepenuhnya. Algoritme mungkin sedikit tidak aktif tetapi pendekatannya harus bekerja.
Sean Middleditch
@PieterGeerkens: Saya setuju itu penjelasan yang buruk. Anda harus membuat jawaban sendiri yang menjelaskan semuanya dengan lebih baik.
Sean Middleditch
Ini sepertinya cukup dekat dengan apa yang saya butuhkan, tetapi saya harus mengakui bahwa saya belum pernah mendengar tentang algoritma itu, jadi saya tidak tahu bagaimana menggeneralisasikannya dengan apa yang saya butuhkan. Apakah Anda memiliki tautan ke info atau tutorial yang bagus di sana?
sfphilli
4

Solusi brute force adalah:

  1. Buat lingkaran simpul di sekitar unit, dengan unit di tengah. Jari-jari lingkaran adalah jarak gerakan maksimum. Kepadatan simpul bisa berubah tergantung seberapa detail hasil akhir yang Anda inginkan.
  2. Untuk setiap posisi simpul, simulasikan gerakan setir unit ke posisi itu. Ini dilakukan dalam loop ketat tanpa rendering.
  3. Ketika jarak maksimum dicapai dalam simulasi kemudi, pindahkan titik ke titik unit simulasi. Titik ini adalah yang paling dekat dengan unit yang bisa mencapai titik itu sebelum giliran saat ini berakhir. Ini memiliki efek menyusutkan lingkaran ke ukuran gerakan aktual.
  4. Gunakan simpul-simpul itu, bersama dengan simpul yang berpusat pada unit untuk membuat lingkaran yang diberikan untuk menggambar jarak gerakan yang mungkin.

masukkan deskripsi gambar di sini

Jadi, dimulai dengan lingkaran biru, Anda akan memproses jalur Anda, berakhir dengan lingkaran ungu. Kemudian Anda dapat menggunakan titik-titik tersebut dengan titik tengah pada unit untuk membuat segitiga merah yang diperlukan untuk menampilkan bentuk. (Hanya membuat gambar itu membuat saya menyadari bahwa bentuk itu tidak benar, tetapi akan menarik untuk melihat apa yang sebenarnya benar)

MichaelHouse
sumber
3

Saya akan memperluas solusi Sean dalam jawaban yang terpisah, karena itu mewakili pendekatan yang berbeda dari apa yang saya usulkan pada awalnya.

Solusi ini mungkin merupakan metode yang paling mudah diakses. Ini membutuhkan partisi lingkungan Anda menjadi node. Ya, ini memperkenalkan kembali pendekatan berbasis grid, tetapi dapat dibuat relatif baik, atau digunakan untuk pencarian jalur luas dengan posisi yang lebih halus ditangani dalam node. Semakin kasar struktur node, semakin cepat pathfinding.

Masalah besar di sini adalah bahwa Anda benar-benar berurusan dengan menghadap ke kapal, begitu banyak solusi merintis jalan tradisional tidak dapat digunakan tanpa modifikasi. Ini biasanya path-agnostik, karena mereka tidak peduli bagaimana Anda sampai ke simpul Anda berada. Itu berfungsi dengan baik ketika akselerasi, deselerasi, dan belok instan dan gratis. Sayangnya bagi Anda berbelok tidak gratis. Namun, karena benar-benar ada satu informasi tambahan yang hilang dalam penyederhanaan ini, kita dapat menyandikannya sebagai variabel lain. Dalam fisika, ini akan dikenal sebagai ruang-fase.

Dengan asumsi 2 dimensi untuk saat ini, Anda dapat memperkirakan 3:

Biasanya, Anda akan memerlukan satu simpul untuk setiap posisi koordinat yang diijinkan dan terpisah. Sebagai contoh:

(0,0) - (1,0) - (2,0)
  | \  /  |  \  / |
(0,1) - (1,1) - (2,1)

Dll. Anda akan membangun sebuah nodegraf dari titik-titik yang berdekatan dan menghubungkannya dengan jarak spasial. Kemudian Anda akan menggunakan algoritma Dijkstra, membunuh node yang melebihi nilai pergerakan yang diizinkan untuk belokan, sampai tidak ada node hidup yang belum dijelajahi yang masih terhubung ke node yang dieksplorasi. Setiap node melacak jarak terkecil yang diperlukan untuk mencapainya.

Untuk memperluas metode ini agar dapat digunakan dengan Rotasi, bayangkan nodegraf yang sama ini dalam 3 dimensi. Arah Z sesuai dengan rotasi / menghadap, dan bersifat siklis, artinya jika Anda terus bepergian ke arah + Z Anda kembali ke tempat Anda memulai. Sekarang, node yang sesuai dengan posisi yang berdekatan hanya terhubung melintasi menghadap yang sesuai dengan arah itu. Anda mengulangi node yang terhubung ke node yang sudah dieksplorasi seperti biasa. Saya akan merekomendasikan membatasi ke N, NE, E, SE, S, SW, W, NW dalam skema ini.

Solusi ini dapat memberi tahu Anda semua wilayah ruang yang dapat diakses, serta jalur terbaik untuk sampai ke sana, berapa rotasi yang Anda miliki saat tiba di sana, dan semua orientasi yang bisa Anda miliki ketika tiba di sana.

Kemudian, ketika benar-benar mengeksekusi pathing, Anda bebas untuk menginterpolasi / kubik spline jalan Anda agar terlihat lebih otentik.

Agen TAS
sumber
1
Ini luar biasa. Saya perlu melakukan sedikit riset pada algoritma dan bereksperimen dengan itu di permainan saya, tetapi ini benar-benar menurut saya sangat cocok, terutama karena saya bisa menggeneralisasikannya ke beberapa bagian penting lain dari permainan.
sfphilli
1

Kedengarannya seperti Anda mungkin perlu terlebih dahulu memutuskan bagaimana tepatnya Anda ingin mengaktifkan on-the-go untuk bekerja. Opsi seperti:

  • Jika mereka bergerak di dalam kerucut, pertama-tama memutar, kemudian mulai bergerak. Ini adalah solusi yang lebih mudah untuk diterapkan dan dilalui. Ini juga kurang menarik sehingga saya tidak ingin menggunakannya.

  • Terus berputar sambil bergerak, hingga total 45 derajat. Yang ini jauh lebih rumit, dan mudah-mudahan yang Anda kejar. Berintegrasi secara numerik pada jalur menggunakan stempel waktu tetap mungkin merupakan cara termudah untuk mendekati yang ini. Kerucut Anda akan dibatasi oleh putaran maksimum (+ X derajat setiap langkah) dan minimum (-X derajat setiap langkah).

Cara terbaik untuk melewati ruang angkasa dengan persyaratan kedua ini sangat tergantung pada lingkungan tempat mereka akan bergerak. Jika ada banyak kendala yang harus Anda lalui, maka segala sesuatunya menjadi sangat rumit dan sangat mahal. Namun, jika tidak ada, maka Anda dapat memuat-depan rotasi (dan bahkan meruncing) untuk berakhir di lokasi yang diinginkan.

Saya merasa bahwa saya mungkin hanya membahas sebagian topik yang Anda tanyakan, jadi silakan menambahkan lebih banyak di komentar dan saya dapat memperluas diskusi.

Agen TAS
sumber
Saya pasti ingin menggunakan opsi kedua, yaitu memutar hingga (misalnya) 45 derajat pada titik apa pun, dan berpotensi setiap, di sepanjang jalur. Juga akan ada hambatan, masing-masing lebih besar dari potongan-potongan (pikirkan batu raksasa). Cara saya awalnya berpikir tentang ini adalah untuk menghasilkan kerucut titik akhir yang mungkin, dan kemudian untuk masing-masing titik akhir menghasilkan kerucut baru, dan seterusnya untuk setiap lokasi yang mungkin sampai menyentuh jarak maksimum yang ditempuh. Yang mengatakan, saya tidak sepenuhnya yakin bagaimana cara mengimplementasikan ini tanpa kerumitan gila.
sfphilli
Hmmm, sepertinya saya sedikit tidak jelas tentang beberapa detail. Melihat kembali pertanyaan yang saya lihat Anda tentukan 'turn-based' dan bahwa unit dapat 'memutar atau memindahkan' pada gilirannya. Apakah itu berarti, kemudian, bahwa pemain merencanakan tindakan mereka banyak belokan di muka, dan Anda ingin melakukan pathfinding saat mereka bergerak? Beberapa klarifikasi lebih lanjut tentang bagaimana gerakan seharusnya bekerja akan sangat membantu.
TASagent
Tidak, yang saya maksudkan adalah bahwa pada giliran tertentu pemain dapat memutar bagian mereka di tempat, betapapun jauh, atau mereka dapat bergerak ke arah yang sudah mereka cari. Jika mereka bergerak, mereka dapat menempuh jarak tertentu di sepanjang jalan, dan mereka dapat memutar atau mengarahkan ke sudut tertentu (jadi di mana saja dari -45 hingga 45 derajat misalnya) saat bergerak. Jadi bayangkan jalur yang dipilih akan melibatkan kurva untuk bergerak ke kiri atau ke kanan. Jalur akan ditentukan oleh pemain memilih titik yang ingin mereka pindahkan, dalam rentang poin yang mungkin saya kesulitan menentukan.
sfphilli
Ok, jadi ini kedengarannya seperti, sayangnya, karakteristik yang Anda inginkan mungkin terlalu ketat untuk algoritma Dijkstra yang kita bicarakan di atas: - \. Mungkin. Saya akan membuat sketsa beberapa hal untuk ini nanti ketika saya pulang.
TASagent
Anda mungkin ingin mengedit beberapa informasi yang Anda kumpulkan untuk mengklarifikasi masalah menjadi pertanyaan awal, sehingga orang yang datang kemudian dapat mulai dengan informasi lebih lanjut.
TASagent