Перемещение игроков в одну и ту же клетку одновременно?

15

Рассмотрим 2 x 2 сетку квадратов. Игрок может перейти на поле, если:

  • ни один другой игрок не хочет выходить на поле в следующий ход
  • ни один другой игрок не ждал и все еще занимает площадь в этот ход

Пример диаграммы

Я включил изображение выше, чтобы описать мою проблему.

Игроки двигаются одновременно.

Если 2 (или более) игрока пытаются перейти на один и тот же квадрат, ни один из них не двигается.

t123
источник
1
может ли игрок переместиться на плитки друг друга за один шаг? например, могут ли желтый и синий поменяться местами в одном и том же шаге (синий идет на одну плитку влево, а желтый - на одну плитку вправо)?
Ali1S232
Гайет да пока. Но в какой-то момент я не хотел бы, чтобы 2 соседних игрока могли поменяться местами напрямую
t123
тогда мой ответ решит эту проблему.
Ali1S232
2
Крайне важно: ознакомьтесь с правилами движения для дипломатии. en.wikipedia.org/wiki/Diplomacy_(game)#Movement_phase
TehShrike

Ответы:

11
  1. Отметьте всех игроков как стационарных или движущихся, в зависимости от того, отправили ли они ход в этот ход.
  2. Просмотрите список ходов. Если два хода указывают на одно и то же место, удалите их из списка и установите игроков неподвижными.
  3. Проходите по списку, удаляя все ходы, указывающие на стационарного игрока или другое препятствие. Делайте это несколько раз, пока список не изменится, когда вы пройдете через него.
  4. Переместить всех игроков.

Я думаю, что это должно работать. Это, безусловно, работает для случая, который вы опубликовали, и для пары других тривиальных случаев, на которых я проверял.

SimonW
источник
Да, это должно работать. Обратите внимание, что на самом деле вы не хотите многократно повторять список игроков; на практике гораздо эффективнее разрешать конфликты путем возврата.
Ильмари Каронен
16

Разрешение столкновений, а не предотвращение столкновений.

Просто переместите объекты, затем проверьте, не было ли столкновений. Если произошло столкновение с другим блоком, вернитесь на предыдущий квадрат или, в зависимости от типа игры, на другой квадрат.

ultifinitus
источник
1
Да, но если нужно вернуться назад, другим тоже придется вернуться ...
t123
2
Вы правы, но опять же, это зависит от фактического типа игры, потребуется больше информации, и ситуация будет меняться в зависимости от типа. Это был самый общий доступный ответ.
ультифинит
5
Вам не нужно разрешать все коллизии за один шаг. переместить весь объект, проверить, нет ли каких-либо столкновений, изменить ходы, связанные с этим столкновением, повторять этот процесс до тех пор, пока не останется никакого столкновения.
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

Это требует, чтобы каждый игрок помнил, откуда он только что переехал, чтобы его можно было вернуть, а также помнит, переместились ли они в этом ходу. Эта вторая проверка означает, что каждый кусок нужно будет возвращать только один раз и должен гарантировать правильное завершение алгоритма. Это также гарантирует, что возвращаются только те игроки, которые переехали - первоначальный игрок остается, поскольку они не рассматриваются для удаления.

Kylotan
источник
3

Другое решение - использовать карту, в 2 раза большую, чем та, которую вы показываете. каждый раз, когда вы хотите переместить игроков, вы перемещаете их дважды, поэтому игроки всегда приземляются на плитки с одинаковым значением для X и Y. снова будут редкие случаи, которые потребуют большего внимания, но большинство возможных случаев разрешены (например, тот, который вы описано) недолго думая.

Ali1S232
источник
Я думаю, что вы имеете здесь в виду что-то, но это не отражено в вашем ответе. Как использование карты 2x решает проблему столкновения?
Zan Lynx
Ладно. Я думаю, что вижу ответ. Две фигуры, движущиеся в противоположных направлениях, приземляются на одном квадрате и сталкиваются. Части, вращающиеся по часовой стрелке, перемещаются на полшага, всегда оставляя свободное пространство для перемещения другой части.
Zan Lynx
@ZanLynx: именно так это решает проблему, единственная проблема будет в том, что две части (скажем, зеленая и синяя) будут сталкиваться, а другая часть (желтая) будет заполнять последнюю позицию зеленого. в случаях, подобных этим (если они возможны), вам необходимо разрешать коллизии в соответствии с предложением ultifinitus.
Ali1S232
Самая простая реализация, которую я знаю для обнаружения столкновений, - это смесь моего и ультифинита. Мой полезен, чтобы проверить, пересекаются ли части друг с другом, и unltifinitus хорош, чтобы решить другие типы столкновения.
Ali1S232
0

Зарегистрируйте все запрошенные ходы, используя массив или карту.

В случае конфликта отмените запрос на перемещение. Если это возвращает объект в квадрат, который пытается занять другой объект, отмените запрос запрашивающего объекта.

Псевдокод:

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

Основываясь на ответе SimonW , вот явный алгоритм:

Позвольте squaresбыть массивом, индексированным местоположениями игрока, и содержащий, для каждого возможного местоположения, или индекс другого местоположения или специальное значение NULL. (Вы можете сохранить это как разреженный массив.) Возможные значения записей в этом массиве могут быть интерпретированы следующим образом:

  • Если squares[S]есть NULL, квадрат Sможет свободно двигаться.
  • Если squares[S] == Sигрок не Sможет или не может двигаться, или два (или более) игрока пытались перейти Sодновременно, и оба были отклонены.
  • В противном случае squares[S]будет содержать индекс квадрата, с которого игрок хочет перейти на квадрат S.

На каждом ходу инициализируйте все записи squaresв NULLи затем запустите следующий алгоритм:

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

После этого снова просмотрите список игроков и переместите тех, кто в состоянии это сделать:

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

Поскольку каждый ход может быть спланирован только один раз и отменен не более одного раза, этот алгоритм будет запущен за O ( n ) времени для n игроков, даже в худшем случае.

(Увы, этот алгоритм не остановит игроков от переключения мест или пересечения путей по диагонали. Возможно, будет возможно адаптировать к нему двухшаговый трюк Гаджета , но совершенно наивный способ сделать это не сработает, и я слишком устал чтобы найти лучший способ только сейчас.)

Илмари Каронен
источник