Как стать автором
Обновить

Задача по расположению фигур в игре «Тетрис»

Время на прочтение2 мин
Количество просмотров23K
Я решил подкинуть Хабрасообществу небольшую задачу по поиску и реализации лучшего алгоритма. Все знают игру «Тетрис». Представьте, что вместо вас в эту игру играет компьютер. Так вот, задачей будет описать алгоритм, который будет правильно размещать фигурки, таким образом, чтобы не было пустых мест. Я сделал на JSFiddle простой UI для тестирования алгоритма. Всё, что вам нужно — это реализовать одну функцию. Но стойте, для начала я объясню правила.

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

  • Всего 2 фигурки: 1x4 и 2x2
  • Размер поля: 10x20
  • 2 положения — вертикальное и горизонтальное
  • Нельзя поворачивать фигурки
  • Фигурки появляются случайным образом, случайно повернутые. Вам нужно найти оптимальное для нее место


В коде есть одна пустая функция (точнее, сейчас она возвращает какое-то случайное число) — getColumnNumberForLeftFigureSquare(w, h). Вам нужно будет ее реализовать. w — это ширина новой фигурки, h — это высота. Всего вы можете пользоваться 3-мя переменными: w, h и cols. cols — это массив, состоящий из 10 элементов. Каждый элемент — это колонка, значение — занятая высота колонки. Функция должна возвращать целое число от 1 до 10 включительно. Это будет номер колонки, в которую упадет самая левая клеточка фигуры.

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

Делайте форки фиддла и отправляйте в комментарии. Любая попытка будет оценена. Идеально, решение должно быть максимально эффективным и максимально производительным. Потом мы можем усовершенствовать тетрис до оригинального.

Еще раз ссылка на JSFiddle

P.S. Если увидите ошибки в самом UI — сообщите мне.
Теги:
Хабы:
Всего голосов 38: ↑28 и ↓10+18
Комментарии61

Публикации

Истории

Работа

Ближайшие события

11 – 13 февраля
Epic Telegram Conference
Онлайн
27 марта
Deckhouse Conf 2025
Москва
25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань