Королевство прямых фигур. Создатель «Тетриса» — о секретах легендарной игры | Компьютеры | Техника
Алексей Пажитнов работал в Вычислительном центре Академии наук СССР и занимался электронными системами распознавания речи. И в свободное время создал игру, которая свела с ума весь мир и вот уже более 30 лет не теряет популярности. Мы поговорили с создателем легендарного «Тетриса» — об истории игры, буднях советских программистов и современном игровом рынке.
Людмила Алексеева, АиФ.ru: Алексей Леонидович, чем вы занимаетесь сейчас?
Алексей Пажитнов: Мне почти 60 лет, я уже пенсионер, так что — живу и наслаждаюсь пенсией. Совсем отрасль не оставил, у нас есть маленькая активная группка, мы вместе работаем уже много лет, делаем небольшие головоломные игры для Appstore.
Алексей Пажитнов. Фото: www.globallookpress.com— «Тетрис» — очень простая игра, и в плане правил, и в плане интерфейса. Как вы думаете, если бы её придумали в наше время, была бы она так популярна у современных пользователей?
— История не знает сослагательного наклонения.
Так что то, что я по этому поводу скажу, наверное, будет чистой спекуляцией. Что я могу сказать? Игра хорошая, но сейчас, поскольку мы не прекращаем над ней работать, мы понимаем, что она стала немножечко старомодной. Всё-таки игра была сделана на одного игрока, и многочисленные попытки за эти 30 лет сделать двухигроковую версию пока не увенчались успехом. Было несколько хороших результатов, но такого эффекта, как сам тетрис произвёл, достичь ещё не удалось.
Кроме того, для управления тетрисом нужно 6 клавиш. Современный игрок привык использовать только одну, так что в этом смысле игра тоже немножко старомодна — требует некоторого обучения, как в неё играть. Но независимо от всего этого, за 30 лет технологии сильно изменились, а человеческие мозги, я надеюсь, остались такими же. То, что нравилось нам в молодости, наверняка будет нравиться вам и сейчас.
— Я правильно понимаю, что вы не оставляете попытки сделать «Тетрис» на двоих?
— Да, мы по-прежнему работаем над ним.
И вообще наша задача и глобальная цель — сделать «Тетрис» олимпийским видом спорта. Мы пробуем это сделать, есть медленный прогресс. Но ещё одна проблема — «Тетрис» хорош, чтобы в него играть, но не так хорош, чтобы его смотреть. Не хватает зрелищности. Явно надо сделать какую-то версию, чтобы это было поистине зрелищно для всех.
— Вы бывали на турнирах по игре в «Тетрис», которые периодически проходят?
— Один раз был. Помню, в 90-е годы в Nintendo объявили всемирные соревнования по тетрису. Ну, приехали там человек 15 из Европы, Америки, и пришло в три раза больше японских школьников. Вот такие всемирные соревнования. Всерьёз рассматривать их я бы не стал. Хотя небольшие соревнования часто устраиваются, в разных странах проходят локальные турниры. Ну, приезжает человек 6–10, играют, есть даже комментатор, который громко кричит, всё очень азартно проходит. Но не всемирный размах, конечно.
— Были ли попытки как-то усложнить игру — ведь во многих современных играх много всяких бонусов, монеток, дополнительных раундов?
— С точки зрения дизайнера, обвязка — это некие костыли.
Если у вас в механике что-то не так, то можно создать для пользователей дополнительную мотивацию. Заставить человек получить очки, поставить ему цель добиться чего-то. Но «Тетрису» костыли никогда особо не требовались — сама по себе игра хороша. Нашу другую головоломку, Marbly, мы снабдили этими обвязками, потому что не хотели сильно выделяться среди других игр, чтобы не отпугнуть игроков. Ведь у современных игр обвязка достаточно мощная.
— «Тетрис» был написан в 1984 году на языке программирования «Паскаль». А как объяснить современному человеку, который ещё не родился тогда, на каком компьютере была создана игра? Если сравнить с мощностью обычного современного пользовательского компьютера?
— Это был компьютер, созданный в лаборатории Вычислительного центра Академии наук на базе «Электроники-60». «Электроника-60» — это первый компьютер, претендовавший на то, чтобы быть персональным. Рабочее место, где программист сидел, вбивал программу, прогонял её, получал результаты.
Проблема с «Электроникой-60» была в том, что у неё вводным устройством был консул, такая печатная машинка, вы, наверное, даже не представляете, что это. Когда я говорил слово «консул» 10 лет назад, те, кто помнили, как это выглядело, начинали дико хохотать. Огромная тяжелейшая механическая печатная машинка, которая с диким треском работала, отправляя данные в ЭВМ. Печатала она отвратительно. Худшего наказания для человека, чем поработать на ней, придумать было невозможно. А чтобы данные хранить, была ленточная операционная система. Это были даже не перфокарты, а перфоленты. Если у тебя ошибка в коде, в случае с перфокартами можно было просто заменить одну карту на правильную. Перфоленту приходилось менять полностью! Хоть что-нибудь создать на таких машинах было почти невозможно. Сама машина была отвязана от своих внешних устройств, и к ней можно было присоединять любые другие устройства. И к «Электронике-60» тогда навесили дисплей. Что-то вроде отдельно стоящего телевизора, который умел выдавать на экран текст, 24 строки.
— Получается, на этой махине «Тетрис» и был написан?
— По сути, да. Операционная система тогда была на флоппи-дисках. И вот когда появился дисплей и флоппи-дисковая система, было ощущение какого-то идеального комфорта. Нам казалось, что мы таким образом проработаем ещё многие десятилетия. Мы не чувствовали, что нам нужно что-то ещё. Прекрасно обходились без интернета. Подцепляли графику, чтобы позабавиться. Я вообще занимался системами распознавания речи. Тогда никто всерьёз это не принимал. Да, были какие-то КГБшные и военные приложения этих разработок, например чтобы прослушивать разговоры, автоматически что-то отлавливать в них.
Но это был вопрос такого далёкого будущего, что мы считали это фундаментальным исследованием. Это сейчас я в полном восторге от современных систем распознавания речи, поскольку я знаю немного, как это работает изнутри. Тот факт, что система сходу начинает вас понимать, — для меня это просто чудо.
— С Siri разговариваете?
— Немного. Я ещё в то время, когда профессионально этим занимался, так устал что-то долбить голосом в компьютер, что с тех пор у меня какое-то отторжение.
— Если вернуться к «Тетрису», помните, кто был первым игроком?
— Долгое время только я. В той версии было 10 уровней, и на уровне 5–6 я сидел добрых три-четыре недели. Без графики, цвета, звуков «Тетрис» был совсем не таким. Ещё и экран дрожал. Фигурки были сделаны, по сути, из скобок и пробелов. В общем, было сложновато, поэтому я и был единственным игроком. Но когда она у меня заиграла, я не мог остановиться, ни доделать, ни дооформить. Мои коллеги видели, что я делаю, и тоже захотели попробовать.
— Позже «Тетрис» начала выпускать американская Mirrorsoft, которая продавала игру, ещё не имея прав на неё. Потом был спор за покупку прав на «Тетрис» между двумя компаниями — Atari и Nintendo — настоящие коммерческие войны. А что вы получили за это? Премию, автомобиль отечественный, устную благодарность?
— Ничего. В тот момент, когда какие-то деньги капнули назад в институт, я там уже не работал. Так-то, наверное, они бы и рады были что-то мне предложить. Мне PC-версию помогал сделать 
Все сотрудники Вычислительного центра получили какие-то бонусы: кто холодильник, кто ещё что. Просто я тогда уже там не трудился.
— История, которая меня удивила, — что вы через 10 лет смогли получить назад права на своё изобретение. Как вам это удалось?
— Вопрос о моих правах всегда был серым и непонятным местом и с юридической, и с практической точки зрения. Я особо не педалировал эту тему, не старался настоять на своих правах. Но в определённый момент вокруг «Тетриса» возник юридический спор. Права были неправильно проданы одной компании без согласия советской стороны. Когда стали оформлять эти вещи юридически, понадобилось понять всю историю. И возник вопрос, кто изобретатель. Я написал заявление, что я, такой-то, создал игру тогда-то, первое её публичное появление было там-то. И на 10 лет предоставил права на эту игру Вычислительному центру. В тот момент 10 лет казались совершенно необозримым сроком. В тот момент ни одна игра больше 6 месяцев не жила. Поэтому никто и не думал, что к этому вопросу ещё вернутся.
— Есть ли у тетриса конец? Я слышала, один профессор математически доказал, что выиграть в него невозможно…
— Профессор решал забавную для него задачу — можно ли написать алгоритм, который бы любую последовательность заведомо выигрывал. И на этот вопрос ответ был дан отрицательный. Результат был для меня неожиданным: я-то думал, что такой алгоритм можно составить. Но нельзя сказать, что хороший игрок не может долго продержаться в игре.
В «Тетрисе» не важно, конечный он или бесконечный. Люди получают удовольствием от игры. Если выиграют — это маленький дополнительный леденец. Он может быть, а можно и без него.
— Алексей Пажитнов
— Вы работали в Microsoft, где, наверняка, было огромное количество гиков. А вы персонаж для них по-своему культовый, мне кажется. Не докучали ли вниманием?
— Я работал в игровом департаменте, там всё-таки трудились более-менее профессионалы, они всё видели, их ничем не удивишь.
Ну, первый день они, может, и разинут на меня варежку. А потом — ну я же такой же, как вчера. На улицах меня не узнают. Разве что один раз за 30 лет такое было. «Кинозвездой» я никогда не был и, надеюсь, не буду.
— Я слышала, вы поклонник настольных игр. А какие игры для вас самые любимые?
— Мы в семье часто играем в Settlers of Catan. Классическая настольная игра, по-моему, лучшая из всех. Она существует уже лет 35. Я её обожаю. Ещё очень люблю кубики Рубика! Вот у меня под рукой сейчас 2 на 4, я ещё не умею такой собирать. Головоломки, всякие штучки дурацкие — это всё моё!
— А это пригождается при создании электронных игр?
— Конечно! В основе этих вещей лежат какие-то принципы, которые иногда можно приложить и к компьютерной игре. В общем-то, тетрис я делал, имея в виду настольную игру «Пентамино». У меня до сих пор хранится коробочка с ней, ей лет 50 уже. Это фигурки из пяти квадратов, 12 штук различных форм. Их можно вытряхнуть из коробки, попробовать сложить из них красивую форму.
А предмет головоломки — собрать эти 12 штук в прямоугольник. Я много играл в нее, чувствовал эти формы и решил запрограммировать такую игру. Правда, для игры в реальном времени эти фигурки были сложноваты и по количеству, и по формам. Я сделал 7 фигурок из 4 квадратов.
— Какие игры вам нравятся из электронных?
— Я люблю всякие головоломки. Помимо популярной «2048» (я считаю, хорошая игра, и большая похвала дизайнеру, который её сделал ) я ещё играю в очень похожую на нее игру Catthrees. Она примерно так же устроена, но другой интерфейс. Она не настолько математична, в ней больше случайного. Очень мне понравилась игра Flow: там расставлены точки, и нужно их соединить линиями, чтобы они заполнили всё поле. Мы даже сделали с друзьями игру в таком стиле, она называется Symbol-link.
— Как вы считаете, как должна происходить монетизация игр? Они должны быть платными изначально или зарабатывать рекламой и продажей бонусов и подсказок?
— Я человек старомодный и считаю, что они должны быть изначально платными.
Вам не жалко трёх долларов на чашку кофе? А от чашки кофе вы получаете удовольствие в лучшем случае 15 минут. А почему бы вам не заплатить 5 долларов за несколько часов полного счастья с интересной игрой? Я не понимаю этого: люди почему-то не платят, потому что считают, что кто-то на этих вещах разбогатеет. Поверьте, там доходы такие, что ни о каком богатстве речи быть не может. Это очень тяжёлая работа. Для нашей игры Marbly мы сделали 300 уровней. В день больше 10 уровней сделать нельзя. Это месяц серьёзной работы. Сидишь, пробуешь, исправляешь, решаешь. Перед тобой большой массив данных, которые надо проверить, оттестировать, оформить. Я надеюсь, в конце концов люди начнут ценить результат человеческого труда.
— Это в России такая ситуация с платными играми или везде так?
— Везде. Есть много самонадеянных ребят, которым надо выпендриться или доказать, что они тоже большие. Они пишут и размещают игры бесплатно. Код, как правило, у этих игр ужасный, ошибок много, идеи, как правило, сворованы.
Но они создают у игроков впечатление, что это нормально и все игры должны быть такими. А люди, которые этим профессионально занимаются, должны следовать рынку — раз сложилась такая установка, то надо с ней что-то делать. Пробовали мы выпускать главную игру бесплатно, а всякие удобства и привилегии продавать. Ничего в этом хорошего нет. Мы должны стоять в дурацкой третьей позиции, типа: играйте в плохую версию, а чтобы играть, как человек, заплатите. Ну что это такое? На это сердятся. Ругают нас. Я всё-таки надеюсь, что на рынке наведут порядок. Он сейчас колоссально вырос в связи с распространением смартфонов, планшетов, отсюда и такой хаос. Но это временно.
— «Тетрис» часто воруют?
— Ещё как! Сколько мы судились! Но «Тетрис» — это серьёзный бренд, который защищён. У нас на то, чтобы следить за правом на интеллектуальную собственность, уходят серьёзные средства, но мы готовы их тратить. Мы уже 30 лет следим за качеством игры, улучшаем её. И защищаем, конечно.
— Почему единственная действительно известная компьютерная игра родом из России — «Тетрис»? Ведь у нас достаточно много отличных программистов, математиков…
— Программист и математик — лица с голосом совещательным. Здесь главное игровой дизайн, ведь игра — это скорее психологический продукт, нежели технический. Но у нас есть хорошие дизайнеры, и в России выходили очень неплохие игры. Просто наша часть индустрии немножко в стороне от всего. И пробиться русскому парню тяжелее, чем американскому молодцу.
Вообще, появлялись сильные игры. Вот есть такая игра — шарики, Balls. В неё играют, по-моему, не меньшее количество лет, чем в «Тетрис», хотя Женя Сотников, который сделал эту игру, уже давно ушёл из игровой индустрии.
— Насколько наши программисты сейчас востребованы за рубежом?
Любой хороший программист востребован в мире. Только в Microsoft работают 5-6 сотен русских программистов, что очень немало.
Как и в любом сообществе из 5-6 сотен людей там есть и разгильдяи, и охламоны, и очень талантливые люди.
— Алексей Пажитнов
Как и в любом сообществе из 5-6 сотен людей там есть и разгильдяи, и охламоны, и очень талантливые люди.— В целом, у нас традиционно неплохое техническое образование с хорошим математическим и программистским базисом. В какой-то момент такие сотрудники были не очень востребованы, потому что нужно было выдавать километры кода, причем очень простого. Для этого особого образования не нужно. Но сейчас, поскольку задачи все более интеллектуальные, серьёзные программисты всё более востребованы.
— Вы давно живёте в Сиэтле. Бываете в родной Москве?
— Стараюсь побывать дома каждый год. У меня в Москве квартира, я приезжаю. В этом году был с апреля по июль. Очень люблю весну в Москве, июнь — обожаю.
— С каким чувством вы уезжали из России?
— Да как такового отъезда у меня не было. Я ехал поработать года на три. А в итоге семья приехала, дети в школу пошли, оказалось, есть смысл дом купить. Потом моя страна исчезла.
Там и остался. Оглянуться не успел, как вроде как уехал навсегда. Но что значит навсегда? У меня в Москве квартира, я вроде как вполне себе москвич.
— Последний вопрос по поводу «Тетриса» — от моей коллеги. Вот бывает в игре, что ты так выстроил фигуры, что спасти тебя может только прямая «палочка» и больше ничего. И ты её ждёшь, ждёшь, а она всё не вылетает, как назло. Есть ли в этом умысел программиста, который специально так запрограммировал, что нужная фигурка не появляется? Или это просто совпадение?
— Я понимаю, о чём речь. Это свойство выборочной памяти. Вашей коллеге эта палочка прилетала очень много раз тогда, когда ей не нужно было. Она её ставила и мгновенно об этом забывала. А вот когда нужная деталь не приходит — вот такие случаи запоминаются. И кажется, что какие-то злые силы тебе вредят. Поэтому в первой версии игры я специально (я как знал, что будут меня обвинять в злонамеренности) украсил экран именно статистикой. Я вывел все 7 фигурок, и на экране было показано, сколько раз каждая фигурка появилась.
Чтобы вы знали, что они выпадают равномерно.
На Android вышел новый Тетрис. Подготовили обзор новинки
Игра Тетрис на смартфонах впервые появилась в 2008 году с выходом на iOS и стоимостью в 9,99 долларов. Тогда еще компании не предлагали каких-либо встроенных покупок, игроки получили полную функциональность. Позже, в 2011 году, EA удалила старое приложение и выпустила новое уже со встроенными покупками. С тех пор серия не получала новых игр, и лишь спустя 9 лет мы вновь можем насладиться обновлённым Тетрисом. 23 января в Google Play и App Store вышел новый Тетрис от компании N3twork, и пришло время нам изучить его. При этом интересно то, что Тетрис, выпущенный в 2011 году компанией EA, был удалён из магазинов пару дней назад.
На Android вышел новый Tetris
Чем же так хорош новый Тетрис? Во-первых, я не играл в старый, поэтому не могу сказать наверняка, чем он лучше новой версии, но мы можем оценить её по геймплейным видеороликам.
В новом Тетрисе появилась возможность выбирать уровни.
Всего нам предлагает 6 различных уровней, которые отличаются не только фоновой картинкой, но и эффектами падения фигур. Как и в обычном Тетрисе, на каждом уровне при нескольких удачных заполнениях всего ряда фигур происходит повышение сложности. В зависимости от того, сколько рядов за раз вам удалось уничтожить, игра может перенести вас на один или на несколько уровней выше.
Немного позволю себе отступление рассказом о том, откуда вообще появился Тетрис. Слово “Тетрис” состоит из двух слов “тетрамино” и “теннис”. И если с последним все понятно, то что же такое “тетрамино”? Это геометрическая фигура, состоящая из четырех квадратов, которые соединены сторонами. Всего их 5, и всем известно, как они выглядят.
Тетрис был изобретен советским программистом Алексеем Пажитновым 6 июня 1984 года. До этой игры тетрамино в различном виде использовались в других играх, а вдохновение Алексей черпал из Пентамино, идея которой заключалась в необходимости собрать квадрат или прямоугольник из 12 фигур тетрамино.
Тетрис входит в число десяти важнейших компьютерных игр в истории. К тому же она еще и самая продаваемая. Для одного лишь GameBoy было продано официально 35 миллионов копий, а на мобильных устройствах игру купили 425 миллионов пользователей. В России Тетрис чаще всего встречался в приставке Brick Game:
Brick Game
Итак, вернемся к новой игре. Что же о ней можно еще рассказать? В общем-то ничего. В настройках можно изменить различные параметры звука. Хочется также поговорить и о минусах, потому что, на мой взгляд, они здесь имеются. Главным минусом для меня является управление с помощью жестов. Оно, конечно, актуально в 2020 году, но не совсем удобное. Например, с помощью кнопок можно быстро переместить фигуру в том случае, если она уже вот-вот приземлится. Жестами это сделать сложнее, и если при этом вы попытаетесь провернуть такое при ускоренном режиме, которые активируется свайпом вниз, у вас вряд ли что-то получится. Чтобы повернуть фигуру, необходимо не свайпнуть, а просто тапнуть по экрану.
По графике нельзя сказать, что она здесь какая-то особенная. Приятная картинка, приятные анимации, но удивления всё это точно не вызывает. А вот что игра точно вызовет, так это чувство ностальгии благодаря звуковому сопровождению — на фоне играет стилизованная песня “Калинка Малинка”. К тому же можно выбрать стилизацию приставки Brick Game, в этом случае на фоне в пиксельной стилистике будет изображен символично храм Василия Блаженного.
Читайте также: Квадрис Классика — «Тетрис наоборот»
А какие эмоции у вас вызывает новая игра Тетрис? Делитесь мнением в комментариях. Кроме того, вы всегда можете обсудить эту и другие темы в нашем чате Телеграм.
- Приложение: Tetris
- Разработчик: N3TWORK Inc.
- Категория: Головоломки
- Версия: 1.0.1
- Цена: Бесплатно
- Скачать: Google Play
- Теги
- Google Play
- Игры для Android
- Операционная система Android
Лонгриды для вас
Лучшие новые игры для Android в разных жанрах
Новые игры для Android, к сожалению, не всегда оказываются хорошими.
Но при этом они почти всегда вызывают интерес. Вот и сейчас у нас прошел месяц, и мы получили новые игры, которые просто нельзя пропустить. Про некоторые из них вы, возможно, уже слышали. Мы специально не стали приводить много примеров и откинули то, что нельзя скачать в России, чтобы вы могли попробовать эти игры сами. Давайте посмотрим, что мы для вас приготовили и поговорим о пяти лучших играх октября.
Читать далее
Отличные гонки для Android. Некоторые из них вы хорошо знаете
Гоночные игры говорят сами за себя. Управляйте каким-либо транспортным средством и обгоняйте ИИ или других игроков, пока не добрались до финиша. Достаточно просто, не так ли? В Google Play есть бесчисленное количество таких игр, но только единицы сделаны так, чтобы их было не стыдно посоветовать другим и приятно поиграть самому. В эту подборку включены не самые редкие и не самые новые игры, а те, которые доставят удовольствие, даже если ранее вы в них уже играли.
Если так, то давайте вспомним, как это было. Если для вас они новые — скорее попробуйте их.
Читать далее
Что такое инженерное меню на телефоне Android и как его открыть
Смартфоны имеют массу дополнительных функций, которые по умолчанию скрыты от рядового пользователя. Владельцам мобильных устройств достаточно одного лишь приложения «Настройки», где доступны для изменения все необходимые параметры. Но есть и еще один похожий раздел, изначально спрятанный от посторонних глаз. Это инженерное меню, позволяющее протестировать аппаратные компоненты смартфона, а также отрегулировать скрытые параметры, что поможет вам как для решения проблем, связанных с работой устройства, так и для настройки гаджета под себя.
Читать далее
Новый комментарий
Новости партнеров
Что нового будет в iOS 17? Почти ничего — Apple занята новой ОС для VR-шлема
Ремонт iPhone в 2023 году станет дороже.
Что с ценами в РоссииКлассные обои для iPhone, которые поднимут настроение после праздников
5 функций приложения Контакты в iOS 16, о которых вы не знали
Что с ценами в России. Как я могу гарантировать, что сетка может быть заполнена элементами, подобными тетрису?
спросил
Изменено 6 лет, 7 месяцев назад
Просмотрено 15 тысяч раз
\$\начало группы\$
Я подумываю сделать игру-головоломку, цель которой состоит в том, чтобы заполнить сетку фигурными кусочками головоломки (например, классическими формами тетриса).
Как я могу сгенерировать набор фигур, которые гарантированно будут использоваться для заполнения сетки, не оставляя промежутков? Как я могу адаптировать этот алгоритм для масштабирования сложности получающейся головоломки?
- алгоритм
- головоломка
\$\конечная группа\$
3
\$\начало группы\$
Это известная сложная задача, определяющая, какие прямоугольники можно замостить определенными частями.
Однако, если вы собираете головоломки и можете управлять частями, это обратная, конструктивная задача, и проще…
Конструктивно построить решение. Возьмите несколько кусочков, которые вам нравятся, и соберите головоломку, как хотите. Затем добавьте достаточно одиночных квадратов, чтобы заполнить его, и вы гарантируете, что есть по крайней мере одно решение. Точнее, включите в разрешенный набор кусочков несколько маленьких кусочков.
Что касается решения/размещения частей, типичный подход грубой силы состоит в том, чтобы заполнить его слева направо, а затем сверху вниз. Найдите первую открытую ячейку (пронумерованную L-R, T-B) и попытайтесь поместить разрешенные фигуры в их разрешенных ориентациях (8 ориентаций для асимметричной фигуры, если вы разрешаете переворачивать). Возможно, проверяйте сначала большие разрешенные куски, а при необходимости прибегайте к более мелким. Когда вы достигаете состояния, которое вам не нравится (тупик, слишком много мелких фрагментов или что-то еще), вернитесь назад.
Если данный набор сетки/деталей не соответствует вашим критериям, то есть он полностью откатился без завершения, попробуйте другой набор прямоугольников и элементов.
Одним из способов сделать головоломку «легче» может быть обмен больших частей на более мелкие, такие как мономино и домино, так как это оставит больше способов заполнить последние отверстия. Или, что то же самое, создайте решение, которое благоприятствует этим более мелким элементам.
Некоторые известные полиоминологи включают:
==> http://ee.usc.edu/faculty_staff/faculty_directory/golomb.htm Голомб первоначально ввел термин «Полиомино»
==> http://www.eklhad. net/polyomino/ Дальке решил довольно много прямоугольников, заполненных одинаковыми частями (особенно редкая форма мозаики)
\$\конечная группа\$
\$\начало группы\$
В этой статье (стр. 11-13, отказ от ответственности: я один из авторов) описан алгоритм, который использует динамическое программирование для равномерного создания прямоугольных областей шириной х и высотой х , расположенных линейно во времени.:strip_icc()/pic3948513.png)
за ч после предварительной обработки, которая занимает около 2 ( w . D ) времени/пространства ( D является самым длинным измерением отдельной формы, например, 4 в случае фигур тетриса).
Идея аналогична той, что описана Дэвидом выше, и фокусируется на верхней полосе , размещая части, которые не создают отверстий . Ключевым моментом здесь является то, что нужно начать с предварительного вычисления допустимых альтернатив для каждого состояния верхней полосы, чтобы вам больше не приходилось платить за комбинаторный взрыв при создании регионов.
Алгоритм работает для любого набора (выпуклых) фигур.
Кроме того, интересным аспектом однородной случайной генерации является то, что она обеспечивает максимальное разнообразие между последовательными поколениями (но вы также можете ограничивать генерацию любым удобным для вас способом). Вот некоторые типичные результаты:
Не стесняйтесь спрашивать, если у вас возникли проблемы с реализацией (возможно, у меня даже где-то завалялась быстрая и грязная реализация Python.
..)
\$\конечная группа\$
1
\$\начало группы\$
Вот метод, который мы использовали в прошлом, чтобы немного обмануть более ограниченное оборудование. Это не так чисто, как более сложные решения, но у него есть явное преимущество, заключающееся в том, что его намного проще реализовать, и он работает каждый раз.
Вместо того, чтобы сосредотачиваться на всей головоломке, разбейте ее на более мелкие однородных частей . Каждая из этих единиц состоит из определенного количества частей, которые соединяются вместе, чтобы сформировать квадраты или прямоугольники, которые намного легче заполнить в головоломке. Выберите случайным образом из различных конфигураций, чтобы заполнить ширину головоломки (примеры ниже, но есть много, много конфигураций). Ниже приведены примеры 4×4, 5×4 и даже 10×4.
Идея состоит в том, что вы «разбиваете» головоломку.
.. выбираете ширину случайным образом в зависимости от доступного оставшегося места. Как только «полоса» закончена, начните новую полосу.
Вы выпускаете части по одной полосе за раз, рандомизируя в каждом наборе «полос». Если вы хотите увеличить сложность, произвольно выпускайте две или более полосок за раз.
Используя эту технику, вы не только гарантируете, что головоломка решаема, но и помогаете «обмануть» порядок выпуска, чтобы было легче остаться в живых. Конечно, на практике игроки не могут идеально решить каждую полосу, поэтому возникает хаос.
Продолжайте генерировать полосы, пока игрок не проиграет. Конечно, мой пример — страйп высотой в 4 блока, но вы можете выбрать что-то покрупнее и посложнее:
\$\конечная группа\$
Простое доказательство лампы Tetris
Я получил эту лампу в подарок на день рождения в прошлом году. Это отличная мелочь — вы можете перемещать отдельные части тетриса, чтобы сформировать любую форму, которую вы хотите, и после соединения они все индивидуально загораются благодаря проводящим полосам по краям каждого сегмента.
Оставив на секунду очевидную связь с тетрисом, одна вещь, которая всегда меня раздражала, — это моя неспособность встроить лампу в чистый прямоугольник. Как бы я ни старался, я всегда заканчивал тем, что один блок торчал сбоку, а другой отсутствовал сверху, или какая-то другая раздражающая несовершенная комбинация.
Сама лампа в стандартной раздражающей установке.
Это раздражение распространилось на многих, кто побывал в моей комнате с тех пор, как лампа стала там неотъемлемым атрибутом. В частности, мой друг провел вечер, перетасовывая кусочки в разные места, отказываясь признать, что там был кто-то с таким извращенным умом, что он с радостью спроектировал бы кусочки так, чтобы они не подходили друг к другу. чистый способ. Конечно, , а не .
Он неизбежно потерпел неудачу в своих усилиях, и с тех пор я признал, что лампа, вероятно, не может быть сконструирована таким образом, поскольку частей всего 9.0049 выглядят так, как , как будто они не подходят друг другу.
Однако это не особенно удовлетворительный вывод, и он определенно не подавил мой навязчивый интерес к задаче.
Однако, вчера вечером, когда я выпивал в своей комнате, другой друг (который раньше не подвергался мучительному притяжению лампы) взглянул на конструкцию на моем столе, подумал несколько минут и воскликнул, что у него есть доказательство того, что его нельзя было сформировать в прямоугольник. Услышав подробности, решение оказалось настолько простым и элегантным, что я решил поделиться им здесь.
Сама лампа состоит из 7 отдельных частей, содержащих в общей сложности 28 квадратов. Следовательно, если предположить, что мы действительно можем сформировать из него прямоугольник, он должен иметь размер 7×4 или 14×2 квадрата. Я использую здесь первый случай просто потому, что это более естественная форма, однако это доказательство в равной степени применимо и ко второму. Теперь представьте, что мы помечаем каждый из этих квадратов цветом — черным или белым — так, чтобы они образовывали шахматную доску, как показано выше.
Обратите внимание, что количество черных квадратов должно быть равно количеству белых, свойство, которое мы будем использовать.
Итак, 14 черных квадратов и 14 белых. Глядя на каждую из частей по отдельности, быстро возникает проблема с нашим предположением.
Как показано выше, для фишек 1-6 количество черных квадратов внутри фишки равно количеству белых. Ясно, какие квадраты черные, а какие белые, зависит от фактического размещения фигуры внутри прямоугольника, но сами фигуры определяют количество каждого цвета (поскольку соседние квадраты должны быть разных цветов).
Тем не менее, часть 7 нарушает тенденцию. Независимо от того, как он расположен, он должен состоять из 3 квадратов одного цвета и 1 другого, свойство, которое полностью зависит от его формы.
Итак, принимая это во внимание вместе с другими 6 частями, в сумме они состоят из 13 квадратов одного цвета и 15 другого, без каких-либо предположений о том, как они расположены внутри прямоугольника.