Algoritma untuk menghitung jalur peluru ke target dengan maks. 2 ricochets

Maaf untuk judul yang jelek tapi saya tidak punya cara yang lebih baik untuk mengatakannya ...

Jadi ada game luar biasa dari Nintendo (ya!) Di Wii yang disebut WiiPlay . Ada 9 minigame di dalamnya, dan favorit saya disebut Tank! . Ini tentang menghancurkan tank musuh COM tanpa membuat dirimu hancur. Berikut screenshot dari level:

Salah satu cara untuk menghancurkan tank adalah dengan menembakkan peluru. Ada tangki musuh hijau limau yang menembakkan peluru berkecepatan tinggi yang memantul (ke dinding dan blok) dua kali. Anda dapat melihat bagaimana tank pemain dapat langsung hancur jika tetap di tempat sekarang, karena tangki kapur di tengah dapat menembakkan peluru yang mengikuti jalur hijau yang saya gambar.

Sebagai seorang programmer amatir, saya sendiri bertanya-tanya bagaimana tangki kapur menentukan arah mana yang harus ditembakkan untuk memukul tangki pemain.

Saya memikirkannya sendiri tetapi tidak menemukan algoritma yang memungkinkan. Saya akan menjelaskan kesimpulan saya jika mereka menginspirasi seseorang. Hanya untuk kesederhanaan selama penjelasan saya, saya menganggap dinding sebagai permukaan yang dapat dipantulkan peluru . Dengan demikian, balok persegi yang terisolasi membentuk empat dinding.

Saya menyimpulkan bahwa 2 poin di mana peluru ricochets selalu terletak di satu sisi jajar genjang atau menjadi titik berlawanan dari jajaran genjang. Tank musuh yang ditembakkan dan tank pemain yang dibidiknya tidak harus dengan 2 simpul lainnya, tetapi jelas terletak pada garis-garis yang bertautan ke salah satu dari keempat sisi jajaran genjang. Berikut adalah ilustrasi dari 4 kemungkinan cara jajar genjang dapat dibentuk:

HOR-VER berarti peluru pertama mengenai dinding horizontal, kemudian mengenai dinding vertikal.

Dan kemudian saya mandek. Saya berpikir untuk bergerak di sekitar garis yang menghubungkan tangki musuh dan tangki pemain di sekitar peta untuk melihat apakah itu membentuk jajaran genjang dengan dua hit dengan dinding apa pun, tetapi ini tidak selalu berhasil karena tangki musuh dan tangki pemain tidak tentu saja kebetulan dengan simpul dari jajaran genjang.

Juga, saya tidak yakin dengan alur umum dari algoritma. Apakah algoritma mengambil salah satu dari 2 struktur berikut, atau mungkin saya salah dengan keduanya?

• Terus mencari tahu jalur yang mungkin dan selalu tandai satu sebagai yang terbaik (bisa menjadi yang terpendek, paling tidak jelas, paling tak terhindarkan, atau penilaian gabungan dan tertimbang berdasarkan beberapa kriteria) dan lupakan sisanya. Yang tersisa setelah semua perhitungan adalah yang terbaik untuk diambil.
• Pertama-tama tentukan semua dinding yang pertama-tama dapat dijangkau dengan peluru (peluru tidak perlu memantul ke dinding lain untuk mencapai masing-masing dinding ini), kemudian tentukan semua rentang yang dapat dicapai pada setiap dinding ini (kadang-kadang mustahil untuk mencapai titik jauh pada dinding tanpa memantul jika dinding lain berdiri di dekat Anda), kemudian tentukan kembali semua dinding yang dapat dijangkau dengan memantul, dan semua rentang dapat dicapai pada dinding ini. Keempat proses ini dapat dilakukan dengan cara yang mirip dengan penelusuran sinar. Selama setiap proses, jika tangki pemain terkena sinar apa pun, cari tahu jalur peluru sesuai dengan sinar itu.

Menurut pendapat saya, algoritma ini sulit diketahui karena:

• sebuah peluru bisa ditembakkan ke segala arah; dan
• ada banyak titik di dinding mana pun, seperti dalam matematika, di mana ada banyak titik di garis.

Tapi orang-orang Nintendo tetap melakukannya, jadi ... ada yang punya ide?

Diberikan garis pandang langsung, masalahnya jelas sepele. Namun, kita berhadapan dengan refleksi. Menemukan dengan benar bagian pemandangan mana yang terlihat menantang ketika menerapkan refleksi sebagai bagian dari pelacak sinar, karena ini mungkin kehilangan beberapa celah. “Pencarian biner” antara dua sudut yang menjanjikan juga tidak dapat dilakukan: karena pantulan, ruang yang terlihat sebenarnya tidak kontinu, jadi heuristik “jika di sebelah kanan A dan di sebelah kiri B, harus ada target solusi antara A dan B " tidak diizinkan , dan akan kehilangan solusi" kreatif ". Sebagai gantinya saya akan merekomendasikan menerapkan refleksi dengan menjalankan kembali pelacak dari posisi virtual - posisi di mana tangki penembakan kita tampaknya berada di cermin:

target |obstacle
   X   |
    \  |  X real position
     \   /
      \ /
   ----------- mirror surface
        \
         \
          X virtual position

Keuntungannya adalah bahwa sinar cermin sekarang adalah garis lurus yang berasal dari posisi virtual. Saya mencoba menggambarkan teknik dalam sketsa berikut:

X menandai posisi menembak, (X) target. Area berwarna terlihat.

1. Pandangan langsung: target tidak terlihat. Namun, kita bisa mengenai permukaan (1) dan (2).

2. Satu refleksi. Ada dua posisi tembak virtual dalam rintangan. Posisi bawah memiliki LOS langsung ke target, jadi kami memiliki solusi penembakan pertama kami: jalur peluru adalah bagian dari sinar antara target dan permukaan cermin yang lebih rendah, dan antara titik tabrakan ray-cermin dan posisi menembak nyata.

3. Dua pantulan: Posisi virtual atas dari pantulan pertama dapat melihat bagian dari penghalang bawah melalui permukaan cerminnya. Karena dua pantulan diperbolehkan, kita dapat mencerminkan posisi ini ke hambatan yang lebih rendah. Posisi ditandai sebagai (I) posisi nyata, (II) posisi virtual dari refleksi pertama, dan (III) posisi virtual dari refleksi kedua.

   Dari (III), kami memiliki LOS langsung ke target (X), jadi kami telah menemukan solusi penembakan lainnya. Jalur peluru berada di sepanjang garis X-III hingga titik tumbukan cermin kedua, kemudian di sepanjang garis III-II antara titik-titik tumbukan cermin, dan akhirnya sepanjang garis II-I dari titik tumbukan cermin pertama ke posisi sebenarnya I.

   Sebenarnya, posisi virtual yang lebih rendah dari refleksi pertama juga dapat tercermin ke hambatan atas, tetapi ini tidak akan mengarah pada solusi langsung.

Setelah Anda bisa mengetahui bagian mana dari penghalang yang terlihat (dan karenanya dapat digunakan untuk memantulkan peluru), menerapkan pencerminan melalui pencarian mendalam-pertama akan terasa mudah. Untuk menemukan permukaan cermin yang cocok, teknik yang diuraikan dalam Sight & Light Nicky Case mungkin digunakan: daripada mencoba 360 vektor - yang mungkin kehilangan bukaan, dan juga boros - kami meluncurkan sinar hanya ke tepi hambatan.

Hanya memperluas ide Karl Bielefeldt untuk refleksi 2 dinding:

A dan B diberikan (tank-tank). Pertama-tama Anda harus membuat daftar semua dinding yang dapat dilihat A dan daftar semua dinding yang dapat dilihat B. Kemudian Anda membuat pasangan di mana dinding pertama berada di daftar tinju dan dinding kedua berbeda dari dinding pertama dan di daftar kedua. Anda perlu melakukan tes ini untuk semua pasangan dinding yang memungkinkan (kecuali jika Anda menemukan cara untuk menghilangkan kandidat). Setelah Anda menemukan R dan S untuk sepasang dinding yang Anda periksa

1) jika A memiliki visi langsung R

2) jika R milik wall1 (dinding hanya segmen, tidak seluruh garis)

3) jika R memiliki akses langsung ke S

4) jika S milik wall2 (dinding hanya segmen, tidak seluruh garis)

5) jika S memiliki akses langsung ke B.

Untuk menemukan R dan S : Karena Anda tahu wall1 Anda dapat menentukan persamaan garis tangen ke wall1, karena R milik garis tangen ke dinding 1, Anda memiliki hubungan antara 2 koordinat R (berakhir dengan satu derajat kebebasan untuk R) Demikian pula dengan S (Anda memiliki hubungan antara koordinat S karena titik ini milik garis tanget ke wall2). Jadi sekarang Anda memiliki 2 derajat kebebasan dan Anda harus memiliki 2 persamaan independen tambahan untuk menentukan solusi. Salah satu persamaan adalah:

(AA')/(RA')=(SS')/(RS')

persamaan lainnya adalah:

(BB')/(SB')=(RR')/(SR')

perhatikan bahwa dalam persamaan di atas A, A ', B, B' diketahui atau dapat dihitung secara langsung. R 'dan S' adalah fungsi dari koordinat R dan S dan persamaan dinding. Saya tidak menyelesaikan matematika, jadi saya tidak tahu bagaimana persamaannya.

Anda dapat mengambil keuntungan dari kenyataan bahwa sudut yang meninggalkan ricochet harus sama dengan sudut yang memasukkannya. Untuk dinding horizontal tertentu dengan koordinat y cdan dua tangki tetap dengan koordinat (a,b)dan (d,e), hanya ada satu sudut yang memenuhi persamaan di bawah ini.

Pecahkan saja untuk xmendapatkan jarak di sepanjang dinding tempat Anda harus membidik. Dua dinding bekerja sama. Anda hanya memiliki dua persamaan dan dua tidak diketahui.

Anda memiliki diagram rapi yang menunjukkan cara mengarahkan sinar, jadi saya akan meninggalkan detail tentang cara menentukan sepasang permukaan pantulan.

Mari kita sebut permukaan yang harus memukul permukaan pertama A , dan yang kedua, B .

Cobalah untuk memukul (terlihat) tepi B dengan menembaki A . Dengan kata lain, menentukan titik-titik di mana orang akan melihat refleksi dari ujung B jika melihat cermin-selesai A . Ini harus mudah dilakukan, Anda hanya memiliki satu titik refleksi untuk ditangani.

Sekarang Anda tahu dua sinar yang mengenai tepi B (terlihat) . Sebut saja sinar tepi Hitung pantulannya dari B; mereka harus pergi ke suatu tempat melewati target Anda. Anda dapat menentukan apakah target terletak di antara mereka, yaitu di sebelah kiri satu sinar tetapi di sebelah kanan yang lain, atau sebaliknya. Ini sepele untuk dilakukan dengan menggunakan persamaan umum dari garis lurus .

Jika target tidak berada di antara sinar tepi, Anda jelas tidak dapat memukulnya dengan sinar perantara; pilih sepasang permukaan lain.

Jika target berada di antara sinar, cari sinar pemukul menengah menggunakan pencarian biner. Anda memiliki dua sudut tembak yang berhubungan dengan sinar tepi, sudut memukul Anda berada di antara mereka. Asalkan diameter sudut target Anda, seperti yang terlihat dari titik tembak, tidak terlalu kecil, Anda akan memerlukan beberapa iterasi sampai Anda menemukan arah sinar yang mengenai.

Ini gambarnya:

Di sini kedua ujung sinar ditampilkan dalam warna merah dan biru. Tampaknya Anda dapat menemukan sinar yang dipancarkan pada sudut yang lebih kecil dari yang merah tetapi lebih besar dari yang merah sehingga sinar itu akan mengenai target hijau.

Pertama, ingat di kelas fisika ketika Anda berbicara tentang pembiasan cahaya? Nah masalah Anda dapat diselesaikan dengan menggunakan prinsip-prinsip itu. Sudut kejadian sama dengan sudut pantulan. jadi tank musuh perlu berlari melalui setiap sudut yang memungkinkan untuk pantulan pertama sehingga pantulan kedua dapat mengenai pemain. Teruskan dengan gagasan penelusuran sinar juga. Sekarang, ini menjadi rumit ketika pemain bergerak tetapi itu harus menjadi ide yang cukup baik bagi Anda untuk memulai suatu algoritma