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 S
może się swobodnie poruszać.
- Jeśli
squares[S] == S
albo gracz S
nie może się ruszyć, albo dwóch (lub więcej) graczy próbowało przenieść się S
w 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 squares
do, NULL
a 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).