Pertimbangkan kotak 2 x 2 kotak. Seorang pemain dapat pindah ke kotak jika:
- tidak ada pemain lain yang ingin pindah ke kotak giliran berikutnya
- tidak ada pemain lain yang menunggu dan masih menempati alun-alun giliran ini
Saya telah memasukkan gambar di atas untuk menggambarkan masalah saya.
Pemain bergerak secara bersamaan.
Jika 2 (atau lebih) pemain mencoba untuk pindah ke kotak yang sama, tidak ada yang bergerak.
turn-based
t123
sumber
sumber
Jawaban:
Saya pikir itu harus berhasil. Ini pasti berfungsi untuk case yang Anda pasang, dan beberapa kasus sepele lainnya yang saya uji.
sumber
Resolusi tabrakan, bukannya pencegahan tabrakan.
Cukup pindahkan objek, lalu periksa apakah ada tabrakan. Jika ada tabrakan dengan blok lain, kembali ke kotak sebelumnya, atau tergantung pada jenis permainan, kotak yang berbeda.
sumber
Ini mengharuskan setiap pemain mengingat di mana mereka baru saja pindah, sehingga mereka dapat dikembalikan, dan juga mereka ingat apakah mereka pindah giliran ini. Pemeriksaan kedua ini berarti masing-masing bagian hanya perlu kembali satu kali dan harus menjamin algoritma berakhir dengan benar. Ini juga memastikan bahwa hanya pemain yang pindah yang dikembalikan - penghuni asli dapat tetap karena mereka tidak dipertimbangkan untuk dihapus.
sumber
Solusi lain adalah menggunakan peta 2x lebih besar dari apa yang Anda tunjukkan. setiap kali Anda ingin memindahkan pemain, Anda memindahkannya dua kali sehingga pemain selalu mendarat di ubin dengan nilai genap untuk X dan Y. sekali lagi akan ada beberapa kasus langka yang membutuhkan perhatian lebih tetapi sebagian besar kasus yang mungkin diselesaikan (seperti yang Anda dijelaskan) tanpa berpikir dua kali.
sumber
Daftarkan semua gerakan yang diminta menggunakan array atau peta.
Jika ada konflik, kembalikan permintaan perpindahan yang dimaksud. Jika itu mengembalikan objek ke kotak objek lain yang mencoba untuk menempati, mengembalikan permintaan objek yang meminta.
Kode palsu:
sumber
Membangun jawaban SimonW , berikut ini adalah algoritma eksplisit:
Membiarkan
squares
menjadi array yang diindeks oleh lokasi pemain, dan berisi, untuk setiap lokasi yang mungkin, baik indeks lokasi lain atau nilai khususNULL
. (Anda mungkin ingin menyimpan ini sebagai array yang jarang.) Nilai yang mungkin dari entri dalam array ini dapat ditafsirkan sebagai berikut:squares[S]
adalahNULL
, alun-alunS
bebas untuk pindah ke.squares[S] == S
, salah satu pemain diS
tidak dapat atau tidak akan bergerak, atau dua (atau lebih) pemain mencoba untuk pindahS
pada saat yang sama dan keduanya ditolak.squares[S]
akan berisi indeks kuadrat dari mana pemain ingin pindah ke kuadratS
.Di setiap belokan, inisialisasi semua entri
squares
keNULL
dan kemudian jalankan algoritma berikut:Setelah itu, ulangi daftar pemain sekali lagi, dan pindahkan yang bisa melakukannya:
Karena setiap gerakan hanya dapat direncanakan satu kali dan dibatalkan paling banyak sekali, algoritma ini akan berjalan dalam waktu O ( n ) untuk n pemain bahkan dalam kasus terburuk.
(Sayangnya, algoritme ini tidak akan menghentikan pemain untuk berpindah tempat atau melintasi jalur secara diagonal. Mungkin dimungkinkan untuk menyesuaikan trik dua langkah Gajet dengannya, tetapi cara yang sepenuhnya naif untuk melakukannya tidak akan bekerja dan saya terlalu lelah untuk mencari cara yang lebih baik sekarang.)
sumber