Рассмотрим 2 x 2 сетку квадратов. Игрок может перейти на поле, если:
- ни один другой игрок не хочет выходить на поле в следующий ход
- ни один другой игрок не ждал и все еще занимает площадь в этот ход
Я включил изображение выше, чтобы описать мою проблему.
Игроки двигаются одновременно.
Если 2 (или более) игрока пытаются перейти на один и тот же квадрат, ни один из них не двигается.
turn-based
t123
источник
источник
Ответы:
Я думаю, что это должно работать. Это, безусловно, работает для случая, который вы опубликовали, и для пары других тривиальных случаев, на которых я проверял.
источник
Разрешение столкновений, а не предотвращение столкновений.
Просто переместите объекты, затем проверьте, не было ли столкновений. Если произошло столкновение с другим блоком, вернитесь на предыдущий квадрат или, в зависимости от типа игры, на другой квадрат.
источник
Это требует, чтобы каждый игрок помнил, откуда он только что переехал, чтобы его можно было вернуть, а также помнит, переместились ли они в этом ходу. Эта вторая проверка означает, что каждый кусок нужно будет возвращать только один раз и должен гарантировать правильное завершение алгоритма. Это также гарантирует, что возвращаются только те игроки, которые переехали - первоначальный игрок остается, поскольку они не рассматриваются для удаления.
источник
Другое решение - использовать карту, в 2 раза большую, чем та, которую вы показываете. каждый раз, когда вы хотите переместить игроков, вы перемещаете их дважды, поэтому игроки всегда приземляются на плитки с одинаковым значением для X и Y. снова будут редкие случаи, которые потребуют большего внимания, но большинство возможных случаев разрешены (например, тот, который вы описано) недолго думая.
источник
Зарегистрируйте все запрошенные ходы, используя массив или карту.
В случае конфликта отмените запрос на перемещение. Если это возвращает объект в квадрат, который пытается занять другой объект, отмените запрос запрашивающего объекта.
Псевдокод:
источник
Основываясь на ответе SimonW , вот явный алгоритм:
Позвольте
squares
быть массивом, индексированным местоположениями игрока, и содержащий, для каждого возможного местоположения, или индекс другого местоположения или специальное значениеNULL
. (Вы можете сохранить это как разреженный массив.) Возможные значения записей в этом массиве могут быть интерпретированы следующим образом:squares[S]
естьNULL
, квадратS
может свободно двигаться.squares[S] == S
игрок неS
может или не может двигаться, или два (или более) игрока пытались перейтиS
одновременно, и оба были отклонены.squares[S]
будет содержать индекс квадрата, с которого игрок хочет перейти на квадратS
.На каждом ходу инициализируйте все записи
squares
вNULL
и затем запустите следующий алгоритм:После этого снова просмотрите список игроков и переместите тех, кто в состоянии это сделать:
Поскольку каждый ход может быть спланирован только один раз и отменен не более одного раза, этот алгоритм будет запущен за O ( n ) времени для n игроков, даже в худшем случае.
(Увы, этот алгоритм не остановит игроков от переключения мест или пересечения путей по диагонали. Возможно, будет возможно адаптировать к нему двухшаговый трюк Гаджета , но совершенно наивный способ сделать это не сработает, и я слишком устал чтобы найти лучший способ только сейчас.)
источник