Memindahkan pemain ke kotak yang sama secara bersamaan?

15

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

Diagram Contoh

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.

t123
sumber
1
dapatkah pemain pindah ke ubin satu sama lain dalam satu langkah? misalnya dapatkah kuning dan biru berpindah tempat dalam langkah yang persis sama (biru pergi satu ubin ke kiri, dan kuning pergi satu ubin ke kanan)?
Ali1S232
Gajet ya untuk saat ini. Tetapi pada titik tertentu saya tidak ingin 2 pemain tetangga dapat bertukar tempat secara langsung
t123
maka jawaban saya memecahkan masalah itu.
Ali1S232
2
Sangat relevan: lihat aturan pergerakan untuk Diplomasi. en.wikipedia.org/wiki/Diplomacy_(game)#Movement_phase
TehShrike

Jawaban:

11
  1. Tandai semua pemain sebagai stasioner atau bergerak, tergantung jika mereka mengirimkan gerakan ini.
  2. Pergi melalui daftar bergerak. Jika dua gerakan mengarah ke lokasi yang sama, hapus dari daftar dan atur stasioner pemain.
  3. Loop melalui daftar menghapus semua gerakan yang mengarah ke pemain stasioner atau hambatan lainnya. Lakukan ini berulang kali hingga daftar tidak berubah ketika Anda melewatinya.
  4. Pindahkan semua pemain.

Saya pikir itu harus berhasil. Ini pasti berfungsi untuk case yang Anda pasang, dan beberapa kasus sepele lainnya yang saya uji.

SimonW
sumber
Ya, ini seharusnya berhasil. Perhatikan bahwa Anda sebenarnya tidak ingin mengulang-ulang daftar pemain; dalam praktiknya, akan jauh lebih efisien untuk menyelesaikan tabrakan dengan mundur.
Ilmari Karonen
16

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.

ultifinitus
sumber
1
Ya tetapi jika seseorang harus mundur maka yang lain juga harus mundur ...
t123
2
Anda benar, tetapi sekali lagi itu tergantung pada jenis permainan yang sebenarnya, lebih banyak informasi akan diperlukan dan situasinya akan berubah berdasarkan jenis permainan. Ini tentang jawaban paling umum yang tersedia.
ultifinitus
5
Anda tidak harus menyelesaikan semua tabrakan dalam satu langkah. pindahkan semua objek, periksa apakah ada tumbukan yang bergerak terbalik terkait dalam tumbukan itu, ulangi proses ini sampai tidak ada tumbukan yang tersisa.
Ali1S232
4
Move all players according to their request.
while there are still some squares multiply occupied:
    For each square that is now multiply occupied:
        For each player in that square that moved there this turn:
            Return them to their previous square
            Mark them as having not moved this turn

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.

Kylotan
sumber
3

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.

Ali1S232
sumber
Saya pikir Anda memiliki sesuatu dalam pikiran di sini, tetapi itu tidak muncul dalam jawaban Anda. Bagaimana cara menggunakan peta 2x menyelesaikan masalah tabrakan?
Zan Lynx
Baik. Saya rasa saya melihat jawabannya. Dua potong bergerak berlawanan arah mendarat di alun-alun yang sama dan bertabrakan. Potongan bergerak searah jarum jam bergerak setengah langkah, selalu menyisakan ruang terbuka untuk bagian lain untuk bergerak.
Zan Lynx
@ ZanLynx: itulah cara memecahkan masalah, satu-satunya masalah adalah ketika dua potong (katakanlah hijau dan biru) akan bertabrakan dan sepotong lainnya (kuning) akan mengisi posisi terakhir hijau. dalam kasus yang serupa dengan ini (jika memungkinkan) Anda perlu menyelesaikan tabrakan seperti yang disarankan ultifinitus.
Ali1S232
implementasi termudah yang saya tahu untuk deteksi tabrakan adalah campuran tambang dan ultifinitus. Tambang saya baik untuk memeriksa apakah potongan saling bersilangan dan unltifinitus baik untuk menyelesaikan jenis tabrakan lainnya.
Ali1S232
0

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:

int[][] game; // game board

var doMoves() {
    int[][] dest = [][]; // destinations; cleared each run

    for (obj in gameObjects)
        if (obj.moveRequest) {
            var o = dest[obj.moveX][obj.moveY];
            if (o) {
                // collision!
                o.doNotMove = true;
                obj.doNotMove = true;
            } else {
                dest[obj.moveX][obj.moveY] = obj;
            }
        }
    }

    // check move validity
    for (obj in gameObjects) {
        if (obj.doNotMove) continue;

        var o = game[obj.moveX][obj.moveY];
        if (o and o.doNotMove)
            revertRequest(obj, dest);
    }

    // process moves
    //etc
}

// recursive function to back up chained moves
var revertRequest(obj, dest) {
    if (!obj.doNotMove) {
        obj.doNotMove = true;
        var next = dest[obj.x][obj.y];
        if (next)
            revertRequest(next, dest);
    }
}
Charles Goodwin
sumber
0

Membangun jawaban SimonW , berikut ini adalah algoritma eksplisit:

Membiarkan squaresmenjadi array yang diindeks oleh lokasi pemain, dan berisi, untuk setiap lokasi yang mungkin, baik indeks lokasi lain atau nilai khusus NULL. (Anda mungkin ingin menyimpan ini sebagai array yang jarang.) Nilai yang mungkin dari entri dalam array ini dapat ditafsirkan sebagai berikut:

  • Jika squares[S]adalah NULL, alun-alun Sbebas untuk pindah ke.
  • Jika squares[S] == S, salah satu pemain di Stidak dapat atau tidak akan bergerak, atau dua (atau lebih) pemain mencoba untuk pindah Spada saat yang sama dan keduanya ditolak.
  • Jika tidak, squares[S]akan berisi indeks kuadrat dari mana pemain ingin pindah ke kuadrat S.

Di setiap belokan, inisialisasi semua entri squareske NULLdan kemudian jalankan algoritma berikut:

for each player:
   current := the player's current location;
   target := the location the player wants to move to (may equal current);
   if squares[target] is NULL:
      squares[target] := current;  // target is free, mark planned move
   else
      // mark the target square as contested, and if necessary, follow
      // the pointers to cancel any moves affected by this:
      while not (target is NULL or squares[target] == target):
         temp := squares[target];
         squares[target] := target;
         target := temp;
      end while
      // mark this player as stationary, and also cancel any moves that
      // would require some else to move to this square
      while not (current is NULL or squares[current] == current):
         temp := squares[current];
         squares[current] := current;
         current := temp;
      end while
   end if
end for

Setelah itu, ulangi daftar pemain sekali lagi, dan pindahkan yang bisa melakukannya:

for each player:
   current := the player's current location;
   if not squares[current] == current:
       move player;
   end if
end for

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

Ilmari Karonen
sumber