Pull to refresh

Поиграем в жизнь

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

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

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


Включить мозги
Total votes 154: ↑135 and ↓19 +116
Views 16K
Comments 109

Моделирование развития социальной сети: игра «Социальная жизнь»

Lumber room
Статья навеяна предыдущим постом о игре «Жизнь» Конвея: Поиграем в жизнь
Давайте зададимся целью смоделировать работу социальной сети с помощью аналога игры «Жизнь» — назовем такую игру.
Читать дальше →
Total votes 11: ↑6 and ↓5 +1
Views 719
Comments 23

Игра «Жизнь» Джона Конуэя

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

Игровая поверхность представляет собой бесконечное или ограниченное поле, разделенное на определенное количество клеток. Каждая клетка может быть или живой или мертвой. С каждым ходом население поля меняется в соответствии с простыми правилами:
  • Клетка, у которой менее двух соседей, умирает от одиночества;
  • Клетка, у которой более трех соседей, умирает от перенаселения;
  • Мертвая клетка, у которой ровно три соседа, оживает.
Игровой мир развивает без помощи игрока. От него лишь требуется расставить клетки для первого поколения. Часто развитие мира становится совершенно не предсказуемым. Клетки образуют сложные узоры, и как только вам начинает казаться, что вы все поняли, они вдруг вымирают, или «повисают» в бесконечном цикле.
Читать дальше →
Total votes 26: ↑16 and ↓10 +6
Views 4.9K
Comments 21

Эмулятор игры «жизнь» на языке GLSL

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

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

Но сегодня мы попробуем реализовать такой эмулятор при помощи видеокарты, так как алгоритм самой игры хорошо реализовывается при помощи параллельных вычислений.
Используем OpenGL, соответственно, язык шейдеров — GLSL. Основная программа будет написана на С++
Читать дальше →
Total votes 37: ↑34 and ↓3 +31
Views 7.1K
Comments 21

Javascript и canvas в игре «Жизнь» Джона Конвея

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

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

Недавно проведённый на Хабре опрос [3] показал реальную картину — 20% программистов написали когда-либо её работающую реализацию, а порядка 10% о ней не слышали. Что ж, тем интереснее будет оставшимся 80% узнать, что можно извлечь из реализации игры.
Читать дальше →
Total votes 70: ↑61 and ↓9 +52
Views 19K
Comments 23

Начинаем конкурс параллельного программирования Threading Challenge

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



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

Итак, о конкурсе...
Total votes 49: ↑43 and ↓6 +37
Views 33K
Comments 65

3D Life — в поисках планеров

Games and game consoles


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

.

В 1987 г. Были найдены первые планеры в трехмерных версиях «жизни» ( www.complex-systems.com/pdf/16-4-7.pdf ). К сожалению, из случайных конфигураций они возникают очень редко (в отличие от двумерной версии). Я решил поискать правила игры, в которых планеров было бы побольше.
Много видеороликов
Total votes 71: ↑66 and ↓5 +61
Views 9.2K
Comments 19

HashLife на коленке

Algorithms *
После возни с трехмерной игрой «Жизнь» я вспомнил о том, что для обычной, конвеевской версии этой игры существует алгоритм под названием «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 – он и будет ответом.



Читать дальше →
Total votes 60: ↑59 and ↓1 +58
Views 7.9K
Comments 7

Life3D – в поисках планеров. Часть 2

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

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

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

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


Читать дальше →
Total votes 38: ↑37 and ↓1 +36
Views 645
Comments 11

Перестаньте писать классы

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

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

Перевод доклада Джэка Дидриха, одного из ключевых разработчиков языка Питон. Доклад прозвучал 9 марта 2012 на конференции PyCon US.
Читать дальше →
Total votes 234: ↑206 and ↓28 +178
Views 170K
Comments 147

«Жизнь» Джона Конвея на Qt

Programming *Qt *
Tutorial
Привет, {{username}}!



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

Кому лень — вот тут лежит исходничег проекта. Можно собирать сразу, зависимости на core, gui.
Читать дальше →
Total votes 83: ↑62 and ↓21 +41
Views 13K
Comments 25

Игра «Жизнь» и моделирование естественного отбора

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

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

Самые нетерпеливые сразу могут посмотреть, что получилось, а остальных прошу под кат за рассказом.
Читать дальше →
Total votes 88: ↑77 and ↓11 +66
Views 103K
Comments 44

Игра «Жизнь»: моделируем эволюцию

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

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

Подробности, как водится, под катом.
Читать дальше →
Total votes 73: ↑72 and ↓1 +71
Views 53K
Comments 70

Аналог игры «Жизнь» — Evo

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

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

Читать дальше →
Total votes 54: ↑46 and ↓8 +38
Views 26K
Comments 61

Evo, часть 2 — о скрещивании

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

В продолжение поста «Аналог игры «Жизнь» — Evo» хотелось бы дать более подробное описание команд «языка генов», который используется в Evo, и поделиться своими соображениями по методам скрещивания особей в этой игре.
Читать дальше →
Total votes 14: ↑12 and ↓2 +10
Views 10K
Comments 28

Жизнь на плоскости Лобачевского

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

Осторожно, много математики!
Total votes 255: ↑253 and ↓2 +251
Views 85K
Comments 64

Жизнь во время компиляции

Abnormal programming *Programming *C++ *
Sandbox
Статья не о том, чем заняться, пока собирается проект.

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

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

Существует множество реализаций легендарной игры «Жизнь» Джона Конвея, безумных и не очень. Но все они имеют общий фатальный недостаток: каждая итерация Жизни вычисляется непосредственно во время работы программы. Попробуем это исправить.
Читать дальше →
Total votes 74: ↑71 and ↓3 +68
Views 38K
Comments 35

И снова игра «Жизнь»

Abnormal programming *Algorithms *
Sandbox
image Тема игры «Жизнь», не раз поднималась на хабре. Описывались различные модификации игры, я хочу представить еще одну. Модификация игры довольно тривиальна, но дает больше возможности в наблюдении, чем оригинал.

В классических правилах придуманных Джоном Конвеем, каждая клетка игрового поля, может быть только в двух состояниях: либо клетка пуста, либо заполнена фишкой.
Подобно эволюции в природе, где развитие шло от одноклеточных к многоклеточным, логично представить развитие игры «Жизнь», где в клетке может находиться больше одной фишки.
Читать дальше →
Total votes 29: ↑25 and ↓4 +21
Views 26K
Comments 10