Задача по автоматическому расположению фигур в игре "Тетрис"
17 июля 2014 JavaScript 13642 просмотра
Я решил подкинуть читателям моего блога небольшую задачу по поиску и реализации лучшего алгоритма. Все знают игру "Тетрис". Представьте, что вместо вас в эту игру играет компьютер. Так вот, задачей будет описать алгоритм, который будет правильно размещать фигурки, таким образом, чтобы не было пустых мест. Я сделал на JSFiddle простой UI для тестирования алгоритма. Всё, что вам нужно - это реализовать одну функцию. Но стойте, для начала я объясню правила.

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

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

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

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

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

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

P.S. Если увидите ошибки в самом UI - сообщите мне.