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

    Я решил подкинуть Хабрасообществу небольшую задачу по поиску и реализации лучшего алгоритма. Все знают игру «Тетрис». Представьте, что вместо вас в эту игру играет компьютер. Так вот, задачей будет описать алгоритм, который будет правильно размещать фигурки, таким образом, чтобы не было пустых мест. Я сделал на 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 — сообщите мне.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 61

      +2
      В оригинальном тетрисе можно ещё двигать фигурки влево-вправо в процессе падения, что иногда действительно необходимо (по крайней мере, со стандартным тетрисовым набором фигурок).
      Вдобавок вы не разрешаете повороты. Когда тетрис был единственной игрой, в которую я играл, то самые эффективные ходы, которые мне удавалось совершать в трудных ситуациях, производились при помощи комбинаций перемещений и поворотов. Особенно это было круто в «кривых» реализациях тетриса (на некоторых телефонах, например); там иногда удавалось «повернуть» фигурку и одновременно установить её внутрь уже стоящего блока.
        +2
        Вы действительно фанат тетриса! Извините, я не хотел обидеть игру. Всё, что я хотел — это дать возможность читателям решить задачку, подумать немного, возможно, посоревноваться в лучшем алгоритме. Для этого я и упростил входные данные. Думаю, потом можно будет тетрис сделать действительно тетрисом, чтобы функция возвращала не только номер колонки, но еще и состояние поворота.
          +2
          И вы меня простите, пожалуй, я слишком грубо выразился. Думаю, найдутся желающие размять мозги и написать бота для тетриса.
            +2
            В данном случае целевая функция слишком отличается от того, что нужно в настоящем тетрисе. И дело не в форме фигур и возможности поворачивать, а в том, что в тетрисе полностью заполненный ряд — исчезает, поэтому появление внутренних пустот проблемой не является. А в данном случае задача выглядит, как минимизация числа пустот.
        +3
        Мне прислали уже первый алгоритм, к сожалению, у человека read-only аккаунт, поэтому я опубликую за него:
        http://jsfiddle.net/H3kra/
          0
          Еще «speed» не хватает :)
          jsfiddle.net/TZ7HJ/
            0
            Спасибо, добавлю в base-версию
            +1
            Еще одно решение от read-only по имени YemSalat:
            http://jsfiddle.net/YemSalat/76um8/
              0
              Если бы, хотя бы, заполненные ряды бы исчезали бы, это ещё как-то напоминало бы тетрис. А так от него одно название.
              Наверное по этому и интересуются постом в основном те, кто в Read-Only =)
                0
                Вы правы, нужно так сделать, тогда нужно разнообразить фигуры, потому что с двумя это будет бесконечная игра.
                  0
                  тетрис это полный набор тетрамино, семь фигур, если не ошибаюсь… но это будет задача абсолютно другого уровня
                    0
                    Зависит от алгоритма. Как я видел, то предложенные на данный момент алгоритмы оставляют дыры, а значит и не будет игра бесконечной, хотя будет достаточно долгой.
                  +2
                  довольно часто заполняет последний слой:
                  jsfiddle.net/vp_arth/g8S55/
                    +1
                    Интересное у вас решение, у меня всегда слева — 1x4, по центру квадраты, справа колонки:
                    gyazo.com/990fd14e1f1bf6cc83d5b11fb063d42e
                      0
                      да, у фигур есть «свои» места… когда они их заполняют, начинают бороться за чужие :)
                      +1
                        +1
                        Кстати, было пару раз «Squares left: 0»
                      +1
                      Еще одно решение
                      Простой поиск промежутка подходящего по ширине для текущей фигуры, начиная с минимально заполненного столбца. Высота не учитывается.
                        0
                        Мне понравилось ваше решение. Вот только если такой промежуток не найден, то должна тоже быть какая-то логика, куда поставить фигуру. Хотя бы так, чтобы осталось меньше закрытых пробелов.
                          0
                          По логике этого алгоритма, такой промежуток найдется всегда (т.е. последняя строка 'return order[0];' никогда не будет вызвана), другое дело что помещение в него не всегда будет оптимально.
                        +1
                        Моё решение: jsfiddle.net/alex_shnayder/9UsVF/
                        И простенький тест для сравнения всех решений: jsfiddle.net/alex_shnayder/TbYtF/
                          0
                          Упс, вот верная ссылка на решение: jsfiddle.net/alex_shnayder/9UsVF/2/
                            0
                            я когда решение выдумывал, больше не про минимизацию окон думал, а про
                            alert('WOW!. Your algorithm is awesome!');
                              +1
                              Так вот, задачей будет описать алгоритм, который будет правильно размещать фигурки, таким образом, чтобы не было пустых мест.

                              Но у вас все равно получилось лучше, чем у других :) И ещё, судя по результатам, у меня такой же алгоритм.
                              0
                              Классное решение) Почти человеческое.
                              И за тестилку спасибо!
                                0
                                Добавил в тест решение Ogoun: jsfiddle.net/alex_shnayder/TbYtF/1/
                                  0
                                  Добавьте еще одного товарища в таблицу: jsfiddle.net/Night_Death/K4x3M/3/
                                  0
                                  Вот мое решение: jsfiddle Не самое эффективное, но очень простое.
                                    +1
                                    добавил в тестилку, плюс запилил минимакс — jsfiddle.net/vp_arth/TbYtF/4/
                                      0
                                      Ух ты, у меня 6 место, я попал в десятку лучших:)
                                    +1
                                      +3
                                      Ловите очень тупое, очень быстрое решение, которое за призы может и побороться :)
                                      jsfiddle.net/by8c6/1/
                                        +2
                                        Хм, добавил свое решение в тестилку: jsfiddle.net/TbYtF/6/
                                        Стабильно показывает лучший результат и по очкам и по времени. Не думал, что столь тупой алгоритм может быть настолько эффективен.
                                        0
                                        С первого же раза все заполнил :)
                                        jsfiddle.net/QPC7v/
                                        –4
                                        Никого здесь не смущает, что задача о заполнении рюкзака (частными случаем которой является и предложенный вариант тетриса) является NP-полной? И что оптимальное решение NP-полной задачи может быть получено только методом полного перебора?
                                          0
                                          Нет не смущает. В задаче с рюкзаком, нам известен набор вещей заранее, а тут другая задача.
                                            –3
                                            И что? NP-полной задачей является не только задача в канонической форме, но и любая задача, сводимая за полиномиальное время к любой из канонических.

                                            Доказано, что классический тетрис является именно NP-полной задачей.
                                              0
                                              Доказано, что классический тетрис является именно NP-полной задачей.
                                              А ссылочкой не поделитесь?
                                              Ну или хотя бы формулировкой «классической задачи тетриса», так чтобы ее можно было к NP-задачам отнести?
                                                0
                                                  0
                                                  При условии что имеют известный порядок фигур. В случае рандома, задача не будет полная же.
                                                    0
                                                    Ага, я так и думал, что вы детерменированный тетрис подгоните. Не уверен, что такую задачу можно назвать «классическим тетрисом».
                                                  0
                                                  Наоборот, NP-полная задача — та, к которой сводится другая NP-полная задача (плюс наша задача еще сама должна лежать в NP).
                                                0
                                                Дык частный случай же. Да и NP-полные задачи необязательно решаются «полным перебором».
                                                  +2
                                                  Даже если эта задача NP-полная, то что в этом плохого? Наоборот, это даже хорошо, в чём интерес соревноваться в том, для чего есть известный идеальный алгоритм? Вот по решению проблемы SAT даже соревнования проводят на лучшие алгоритмы, хотя она NP-полная.
                                                  +1
                                                  А можно еще один мой алгоритм разместить? Он тоже довольно простой, но намного эффективнее: jsfiddle
                                                    0
                                                    Действительно хороший алгоритм, но финишную часть надо бы доработать, чтобы при сильном заполнении стакана оставлял место для вертикальной «палки»
                                                      0
                                                      Спасибо. Попробую, но он и так очень медленный, боюсь, что тогда придется 5 секунд ждать на выполенние:)
                                                        0
                                                        Добавил оставление места для палки, но так он наоборот теряет в эффективности, где-то 2-5(в зависимости от порога сильного заполнения) очек на 100 запусков. Ну по крайней мере в моей реализации.
                                                        +1
                                                        Алгоритм ваш мне понравился, компактно написан.
                                                          0
                                                          Пасиб!
                                                          0
                                                          jsfiddle.net/TbYtF/7/
                                                          оставил лучший из трёх
                                                            0
                                                            Да, спасибо!
                                                              0
                                                              Что-то меня так никто и не добавил :) jsfiddle.net/QPC7v/7/
                                                                0
                                                                  0
                                                                  Спасибо вам огромное за ваш тест! С ним намного удобней. Давайте тогда добавим всех участников. На моём блоге оставили такое решение:
                                                                  jsfiddle.net/H3kra/
                                                                    0
                                                                    Это не мой тест, а товарища tigerforce
                                                                    Вам ничто не мешает добавлять самому — это же fiddle
                                                                    0
                                                                    Вот товарищ один еще усовершенствовал своё решение, тоже может принять участие. jsfiddle.net/Night_Death/K4x3M/5/
                                                              –2
                                                                +2
                                                                во первых, невалидный код — не закрыт блок switch.
                                                                во вторых, некорректный алгоритм:
                                                                — возвращает значения от 0 до 9, вместо «от 1 до 10»
                                                                — не проверяет влезет ли фигура в эту колонку
                                                                  0
                                                                  Извините, я не сохранил последнюю версию в jsFiddle, поэтому и глупейшие ошибки присутствуют. Вот: jsfiddle.net/kaY62/2/

                                                              Only users with full accounts can post comments. Log in, please.