Przenosisz graczy na ten sam kwadrat jednocześnie?


15

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

Przykładowy diagram

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
czy gracz może przesuwać do siebie kafelki w jednym kroku? na przykład, czy żółty i niebieski mogą zamieniać miejsca dokładnie w tym samym kroku (niebieski przesuwa się o jeden kafelek w lewo, a żółty przechodzi o jeden kafelek w prawo)?
Ali1S232,

Gajet tak na razie. Ale w pewnym momencie nie chciałbym, aby 2 sąsiednich graczy mogło bezpośrednio zamieniać się miejscami
t123 29.09.11

wtedy moja odpowiedź rozwiązuje ten problem.
Ali1S232,

2
WYJĄTKOWO istotne: sprawdź zasady ruchu dla dyplomacji. pl.wikipedia.org/wiki/Diplomacy_(game)#Movement_phase
TehShrike 30.09.11

Odpowiedzi:


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


Tak, to powinno działać. Zauważ, że tak naprawdę nie chcesz wielokrotnie przewijać listy graczy; w praktyce rozwiązywanie kolizji będzie znacznie bardziej wydajne przez cofanie się.
Ilmari Karonen

16

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.


1
Tak, ale jeśli ktoś musi się wycofać, inni też będą musieli się cofnąć ...
t123 29.09.11

2
Masz rację, ale znowu zależy to od faktycznego typu gry, wymagane będą dodatkowe informacje, a sytuacja zmieni się w zależności od rodzaju. Chodziło o najbardziej ogólną dostępną odpowiedź.
ultifinitus

5
nie musisz rozwiązywać wszystkich kolizji w jednym kroku. przesuń cały obiekt, sprawdź, czy w kolizji są jakieś odwrotne ruchy, powtarzaj ten proces, dopóki nie pozostanie kolizja.
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

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.


3

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.


Myślę, że masz tu coś na myśli, ale nie ma to miejsca w twojej odpowiedzi. W jaki sposób użycie mapy 2x rozwiązuje problem kolizji?
Zan Lynx,

W porządku. Myślę, że widzę odpowiedź. Dwa elementy poruszające się w przeciwnych kierunkach lądują na tym samym placu i zderzają się. Kawałki poruszające się zgodnie z ruchem wskazówek zegara poruszają się o pół kroku, zawsze pozostawiając wolną przestrzeń, na którą można się przenieść.
Zan Lynx

@ZanLynx: dokładnie tak rozwiązuje problem, jedynym problemem będzie zderzenie dwóch elementów (powiedzmy zielonego i niebieskiego), a kolejny element (żółty) zajmie ostatnią pozycję zieleni. w podobnych przypadkach (jeśli są one możliwe) musisz rozwiązać kolizje, jak sugeruje ultifinitus.
Ali1S232,

najłatwiejszą implementacją, jaką znam do wykrywania kolizji, jest mieszanka mojej i ultifinitus. mój jest dobry, aby sprawdzić, czy kawałki się krzyżują, a unltifinitus dobrze jest rozwiązać inne rodzaje kolizji.
Ali1S232,

0

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

0

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.