Przenosisz graczy na ten sam kwadrat jednocześnie?

Rozważ siatkę kwadratów 2 x 2. Gracz może przejść na pole, jeżeli:

• żaden inny gracz nie chce przejść na pole w następnej turze
• żaden inny gracz nie czekał i nadal zajmuje pole w tej turze

Dołączyłem obraz powyżej, aby opisać mój problem.

Gracze poruszają się jednocześnie.

Jeśli 2 (lub więcej) graczy próbuje przenieść się na to samo pole, żaden z nich nie porusza się.

1. Oznacz wszystkich graczy jako stacjonarnych lub w ruchu, w zależności od tego, czy zgłosili ruch w tej turze.
2. Przejrzyj listę ruchów. Jeśli dwa ruchy wskazują na to samo miejsce, usuń je z listy i ustaw graczy nieruchomo.
3. Zapętlaj listę, usuwając wszystkie ruchy wskazujące na stacjonarnego gracza lub inną przeszkodę. Rób to wielokrotnie, dopóki lista nie zmieni się, gdy przejdziesz przez nią.
4. Przenieś wszystkich graczy.

Myślę, że to powinno działać. Z pewnością działa w przypadku opublikowanej przez Ciebie skrzynki i kilku innych trywialnych przypadkach, w których ją przetestowałem.

Rozwiązywanie kolizji zamiast zapobiegania kolizjom.

Po prostu przesuń obiekty, a następnie sprawdź, czy nie doszło do kolizji. Jeśli doszło do kolizji z innym blokiem, wróć na poprzedni kwadrat lub, w zależności od rodzaju gry, inny kwadrat.

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

Wymaga to, aby każdy gracz pamiętał, skąd się przeprowadził, aby mógł zostać zwrócony, a także pamiętał, czy przeprowadził się w tej turze. To drugie sprawdzenie oznacza, że ​​każdy element będzie wymagał zwrotu tylko raz i powinien gwarantować prawidłowe zakończenie działania algorytmu. Zapewnia również, że tylko gracze, którzy się przenieśli, są zwracani - pierwotny użytkownik może pozostać, ponieważ nie są brani pod uwagę do usunięcia.

Innym rozwiązaniem jest użycie mapy 2x większej niż to, co pokazujesz. za każdym razem, gdy chcesz przenieść graczy, przenosisz ich dwukrotnie, więc gracze zawsze lądują na kafelkach o równej wartości zarówno dla X, jak i Y. Znowu pojawią się rzadkie przypadki, które będą wymagały więcej uwagi, ale większość możliwych przypadków zostanie rozwiązana (np. opisane) bez zastanowienia.

Zarejestruj wszystkie wymagane ruchy za pomocą tablicy lub mapy.

W przypadku konfliktu wycofaj dane żądanie przeniesienia. Jeśli to zwróci obiekt na kwadrat, który inny obiekt próbuje zająć, cofnij żądanie obiektu żądającego.

Pseudo kod:

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);
    }
}

Opierając się na odpowiedzi SimonW , oto wyraźny algorytm:

Pozwolić squares będzie tablicą indeksowaną przez lokalizacje gracza i zawierającą dla każdej możliwej lokalizacji indeks innej lokalizacji lub wartość specjalną NULL. (Możesz zapisać to jako rzadką tablicę.) Możliwe wartości wpisów w tej tablicy można interpretować w następujący sposób:

• Jeśli squares[S]jestNULL , kwadrat Smoże się swobodnie poruszać.
• Jeśli squares[S] == Salbo gracz Snie może się ruszyć, albo dwóch (lub więcej) graczy próbowało przenieść się Sw tym samym czasie i obaj zostali odrzuceni.
• W przeciwnym razie squares[S]będzie zawierać indeks kwadratu, z którego gracz chce przejść do kwadratu S.

W każdej turze zainicjuj wszystkie wpisy squaresdo, NULLa następnie uruchom następujący algorytm:

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

Następnie ponownie przejrzyj listę graczy i przesuń tych, którzy są w stanie to zrobić:

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

Ponieważ każdy ruch można zaplanować tylko raz i anulować maksymalnie raz, ten algorytm będzie działał za O ( n ) czasu n graczy, nawet w najgorszym przypadku.

(Niestety, ten algorytm nie powstrzyma graczy przed zamianą miejsc lub krzyżowaniem ścieżek po przekątnej. Może być możliwe dostosowanie do niej dwuetapowej sztuczki Gajeta , ale całkowicie naiwny sposób nie działa i jestem zbyt zmęczony wymyślić teraz lepszy sposób).