Представьте себе листок бумаги в клетку. Подозреваю, что уже на этом этапе некоторые хабралюди догадались, о чем пойдет речь. Что ж, моё почтение им. Остальные же продолжают представлять себе листок бумаги в клетку. Во всех подробностях. В мельчайших деталях.

А теперь представьте, что на этом простом листочке мы создадим простой, но оттого не менее впечатляющий симулятор жизни. Ни больше, ни меньше. Конечно, он будет очень упрощенный, но ведь чтобы понять что-то сложное надо начать с простого, не так ли? Этот симулятор можно применить ко множеству наук и с каждой из них он будет иметь множество достаточно интересных точек соприкосновения. От социологии до астрономии, от биологии до электротехники.

Ладно, хватит завлекалок. Пора удариться в математику.

Статья навеяна предыдущим постом о игре «Жизнь» Конвея: Поиграем в жизнь

Давайте зададимся целью смоделировать работу социальной сети с помощью аналога игры «Жизнь» — назовем такую игру.

Игра «Жизнь» (Conway's Game of Life) — забавнейшая штука, которую серьезные люди сурово называют «клеточный автомат». Ее придумал английский математик Джон Конуэй (John Horton Conway) в далеком 1970 году.

Игровая поверхность представляет собой бесконечное или ограниченное поле, разделенное на определенное количество клеток. Каждая клетка может быть или живой или мертвой. С каждым ходом население поля меняется в соответствии с простыми правилами:

• Клетка, у которой менее двух соседей, умирает от одиночества;
  
• Клетка, у которой более трех соседей, умирает от перенаселения;
  
• Мертвая клетка, у которой ровно три соседа, оживает.
  

Игровой мир развивает без помощи игрока. От него лишь требуется расставить клетки для первого поколения. Часто развитие мира становится совершенно не предсказуемым. Клетки образуют сложные узоры, и как только вам начинает казаться, что вы все поняли, они вдруг вымирают, или «повисают» в бесконечном цикле.

Для начала небольшой ликбез: раз, два, три.

Наверное, многие хоть раз в жизни писали эмулятор игры «жизнь».
Может быть для обучения программированию, может быть для интереса, экспериментов…
В любом случае, реализация на многих популярных языках программирования — несложное упражнение для обучения этому языку.

Но сегодня мы попробуем реализовать такой эмулятор при помощи видеокарты, так как алгоритм самой игры хорошо реализовывается при помощи параллельных вычислений.
Используем OpenGL, соответственно, язык шейдеров — GLSL. Основная программа будет написана на С++

 

Напишем эту алгоритмическую игру [1] так, чтобы извлечь из неё максимальную образовательную пользу в области алгоритмов, языка Javascript, хорошего стиля программ, умения оптимизировать код. Центральным местом обсуждения будет не игра, а код, способы реализации, оптимизация.

Неоднократно встречалось в литературе и статьях мнение, что эту игру знает каждый программист и что почти каждый пробовал её программировать. Например, разные авторы писали, что через неё изучают новые для них языки программирования.

Недавно проведённый на Хабре опрос [3] показал реальную картину — 20% программистов написали когда-либо её работающую реализацию, а порядка 10% о ней не слышали. Что ж, тем интереснее будет оставшимся 80% узнать, что можно извлечь из реализации игры.

Коллега Boomburum уже показывал скриншот диспетчера задач похожего монстра. Четыре сокета, в каждом их них по процессору Intel® Xeon® E7-4860 с 24MB кэша, а сверху – 64 гигабайта оперативки. Что со всем этим богатством делать? У меня есть пара идей!



Мы начинаем конкурс параллельного программирования Threading Challenge 2011. Участники получат доступ к этой машине, а победители отправятся на IDF в Сан-Франциско, где нам, надеюсь, еще и не такие картинки покажут. Задача конкурса сводится к тому, чтобы загрузить все доступные ядра на 100%, снять скриншот и поместить на Хабре! Шутка. Не все так просто.

Многим известна игра «Жизнь», изобретенная Дж.Конвеем еще в 1970 г. Еще шире известен один из объектов этой игры – планер (или глайдер) – движуееся образование из 5 клеток:

.

В 1987 г. Были найдены первые планеры в трехмерных версиях «жизни» ( www.complex-systems.com/pdf/16-4-7.pdf ). К сожалению, из случайных конфигураций они возникают очень редко (в отличие от двумерной версии). Я решил поискать правила игры, в которых планеров было бы побольше.

После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «Hashlife». Он несколькими фразами описан в Википедии, и приведенной там картинки с комментарием («конфигурация через 6 октиллионов поколений») для меня было достаточно, чтобы держаться от этой идеи подальше: сколько же ресурсов нужно этому алгоритму? Стоит ли за него браться вообще?

Общая идея алгоритма такая.

Допустим, что у нас есть квадрат поля размером N*N (N>=4 – степень двойки). Тогда мы можем однозначно определить состояние его центральной области размером (N/2)*(N/2) через T=N/4 шага. Если мы запомним состояние исходного квадрата и результат его эволюции в словаре, то сможем в следующий раз, встретив такой квадрат, сразу определить, что с ним станет.

Предположим, что для квадратов N*N эволюцию на N/4 шага мы считать умеем. Пусть у нас есть квадрат 2N*2N. Чтобы просчитать его развитие на N/2 шагов, можно сделать следующее.

Разобьем квадрат на 16 квадратиков со стороной N/2. Составим из них 9 квадратов со стороной N, для каждого из них найдем результат эволюции на N/4 шага. Получится 9 квадратов со стороной N/2. В свою очередь, из них составим уже 4 квадрата со стороной N, и для каждого из них найдем результат эволюции на N/4 шага. Полученные 4 квадрата со стороной N/2 объединим в квадрат со стороной N – он и будет ответом.

В первой части публикации я рассказывал про поиски планеров в 3-мерной игре «Жизнь» (с 26 соседями у клетки). Там было несколько примеров того, что удалось найти. Но оказалось, что правил с планерами несколько больше, чем я ожидал вначале. Хотя и ненамного…

Программа, которая искала планеры, выдала довольно много «подозрительных» стартовых конфигураций. Но планеры были далеко не во всех. Во многих случаях возмутителями спокойствия оказывались пульсары – периодические конструкции с периодами, не являющимися делителями 60.

Чаще всего, период таких пульсаров равнялся 8:

Правило B5/S2,3:

Признак того, что объект не должен быть классом — если в нём всего 2 метода, и один из них — инициализация, __init__. Каждый раз видя это, подумайте: «наверное, мне нужна просто одна функция».

Каждый раз когда из написанного класса вы создаёте всего один экземпляр, используете только раз и тут же выбрасываете, следует думать: «ой, надо бы это отрефакторить! Можно сделать проще, намного проще!»

Перевод доклада Джэка Дидриха, одного из ключевых разработчиков языка Питон. Доклад прозвучал 9 марта 2012 на конференции PyCon US.

Привет, {{username}}!



Сегодня я хочу показать, как реализовать всеми любимую игру Game Of Life Джона Конвея на Qt. Писать будем на виджетах. На примере этого проекта я покажу как работать с QPainter, несколькими классами из core, лэйаутами и вообще с графикой в Qt Widgets. Всем кому интересна эта игра или работа с графикой на Qt, прошу читать дальше. Вообще, статья ориентирована на новичков, но и продвинутым ребятам тоже будет что прочитать:).

Кому лень — вот тут лежит исходничег проекта. Можно собирать сразу, зависимости на core, gui.

Валялся я на прошлой неделе в больнице. И так как обсуждать с дедушками в холле рецепт яблок, мочёных в капусте, и как хорошо на Покров гулять по заливным лугам — особого желания не было, пришлось придумывать себе развлечение.

Я задумался об игре «Жизнь», которую на Хабре не так давно вспоминали. Мне стало обидно за несчастные клетки, которые живут и умирают в зависимости от одних только начальных условий, и ничего сами для своего выживания сделать не могут. В результате я придумал расширение для правил игры, с которым можно моделировать не только изменение численности популяции, но и естественный отбор внутри неё.

Самые нетерпеливые сразу могут посмотреть, что получилось, а остальных прошу под кат за рассказом.

В комментариях к моему предыдущему посту «Игра «Жизнь» и моделирование естественного отбора» первое же, что предложили, — добавить скрещивание, чтобы новая клетка получала не копию генома одного родителя, а смесь от нескольких. Я подозревал, что итог это не изменит. Но, покрутив в голове идею, заинтересовался: ведь так можно получить модель не просто естественного отбора, а уже полноценной эволюции. Благо, реализовать это было не сложно. Так что встречайте: «Жизнь», теперь со скрещиванием и мутациями.

Ну да, ещё и с мутациями. Моделировать, так моделировать.

Подробности, как водится, под катом.

Немецкий учёный Штефан Рафлер создал интересную модификацию «Жизни» — клеточного автомата, придуманного в 1970 году Джоном Конвеем, в которой вместо дискретной прямоугольной сетки жизнь развивается в непрерывной среде. «Клетки» в ней имеют форму дисков, планеры могут летать в любых направлениях и водить хороводы — получается совершенно завораживающая картина.



Вот слайд-шоу с кратким описанием алгоритма, документ с более глубоким погружением в детали и исходники.

Приветствую вас, хабражители!

Недавно прочитал статью про игру Жизнь, и вспомнилось мне, что я в мае этого года начинал писать свой проект подобной направленности. Только вот интерес к нему за рутиной работы быстро угас, хотя написано было немало. И сейчас, вдохновлённый этой статьёй, я взял этот проект с пыльной полки и добавил несколько фич, о которых расскажу далее.
Вкратце, мой вариант имеет следующие условия:

• жизнь развивается на поле 256*256 клеток;
• на поле могут размещаться объекты трёх типов: живность, пища(назовем её травой) и камень (препятствие);
• живность представляет собой фактически модифицированную машину Тьюринга, если точнее, то это больше похоже на Автомат с магазинной памятью, т.е. живность является «процессором», выполняющим свой «генетический» код;
• живность имеет возможность совершать определенные действия (двигаться, есть, размножаться (пока только клонированием, мутации будут со дня на день, скрещивание в перспективе)), отдавая соответствующие команды;
• наступив на траву, живность её вытаптывает;
• для поглощения еды надо дать команду «Ешь в этом направлении!», находясь в соседней клетке;
• живность имеет память, что позволяет строить циклы, условия и т.п., т.е. полная по Тьюрингу (поправьте меня, если не прав!), объем памяти неограничен;
• живность может складывать и вычитать значения в уме, разрядность ограничена одним байтом;
• существует возможность реализации генетических алгоритмов (пока не реализовано).

Кому интересны подробности, прошу под кат!

Приветствую вас, хабражители!

В продолжение поста «Аналог игры «Жизнь» — Evo» хотелось бы дать более подробное описание команд «языка генов», который используется в Evo, и поделиться своими соображениями по методам скрещивания особей в этой игре.

Различные реализации игры «Жизнь» описывались на Хабре уже неоднократно. В этой статье, в качестве продолжения этой темы, рассматривается ещё один её вариант: в качестве игрового поля используется регулярная решётка на плоскости Лобаческого. Описываются общие методы использования плоскости Лобачевского в программах и необходимые для этого математические приёмы.
Как возникла плоскость Лобачевского, достаточно известно. В позапрошлом веке господа Гаусс, Лобачевский и Бойяи, проживавшие примерно в одно время в разных странах тогдашней Европы, задумались, что будет, если отменить пятый постулат Евклида и заменить его на противоположную аксиому. Оказалось, что не случится ничего плохого, и никаких противоречий не возникнет. Заметная часть последующего изучения неевклидовой геометрии была посвящена выяснению того, кто из них у кого украл идею этой самой геометрии.
Менее известно, что несмотря на «отрицательный» способ определения неевклидовой геометрии (вместо того, чтобы сказать, что через точку проходит ровно одна прямая, не пересекающая данную, мы говорим, что таких прямых может быть сколько угодно), мы, тем не менее, получаем систему теорем и формул, не менее стройную, чем та, что есть в евклидовой геометрии. И одновременно, у нас есть гораздо большее разнообразие геометрических фигур, в том числе, разбиений плоскости на правильные многоугольники.

В продолжение 30-ти строчного мема, выкладываю реализацию известной игры Жизнь на LiveScript (язык, транслируемый в Javascript).

Статья не о том, чем заняться, пока собирается проект.

Фраза «Шаблоны — полноценный, тьюринг-полный, язык» часто воспринимается с недоверием. Это же просто обобщающая возможность современных языков программирования, откуда там вычислительные возможности? Так думал и я. Теперь хочу переубедить остальных, попутно объясняя принципы работы шаблонов для начинающих, вроде меня.

Мое понимание шаблонов впервые пошатнулось после прочтения главы «Метапрограммирование» из книги о С++ от создателя С++ — показалось, что они действительно могут быть полноценным языком программирования внутри языка программирования. Во всяком случае, там точно есть рекурсия. Но лучший способ доказать себе что-то — попытаться сделать, что мы и сделаем.

Существует множество реализаций легендарной игры «Жизнь» Джона Конвея, безумных и не очень. Но все они имеют общий фатальный недостаток: каждая итерация Жизни вычисляется непосредственно во время работы программы. Попробуем это исправить.