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

в 13:15, , рубрики: javascript, Алгоритмы

Я решил подкинуть Хабрасообществу небольшую задачу по поиску и реализации лучшего алгоритма. Все знают игру «Тетрис». Представьте, что вместо вас в эту игру играет компьютер. Так вот, задачей будет описать алгоритм, который будет правильно размещать фигурки, таким образом, чтобы не было пустых мест. Я сделал на 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 — сообщите мне.

Автор: plutov

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js