Соединяемость-три головоломки - PullRequest
Новая
       7

Соединяемость-три головоломки

2 голосов
/ 01 марта 2012

Я пишу казуальную игру типа connect-three, в которой используется квадратная сетка.Игрок перемещает ряд или столбец (по существу, вращая их в 1D), чтобы собрать как минимум три блока одного типа, чтобы составить совпадение.

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

Помимо использования метода грубой силы (который по крайней мере O (N ^2) время), есть ли более быстрый способ поиска возможных ходов?

1 Ответ

0 голосов
/ 07 июня 2012

Вы можете сделать это в O (N log (M)) , где N - количество позиций на доске, а M - количествоДоступные фигуры:

  1. O (N log (M)) : Для каждой точки ( O (N) ) обновите карту доступных фигурдля его строки и столбца ( O (log (M) ).
  2. O (N log (M)) : Для каждой точки ( O (N) ) проверьте наличие похожих фигур рядом или на расстоянии одного вертикального или горизонтального расстояния.или по диагонали ( O (1) ) и проверьте карту (ы) строк / столбцов ( O (log (M)) ), которые "соединят три", чтобы увидеть,допустимый ход доступен.

Вы также можете улучшить вышеуказанный метод, чтобы он не повторял ненужные проверки (фигуры во 2-м ряду и ниже не проверяются, а фигуры во 2-м столбце)и справа не проверяйте левый), но большая стоимость O будет такой же.

Кроме того, после каждого перемещения вам нужно только обновить карты строк / столбцов, которые изменились, и вам нужно только проверить формы, которые изменились.В худшем случае очищается вся плата, поэтому большая стоимость O будет такой же.

...