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

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

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

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

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

Краткое описание

Программу я обозвал Evo (git), поскольку изначально планировалось, чтобы организмы там эволюционировали. Но ничто не мешает самому описать алгоритм поведения живности и подгрузить его в программу. На текущий момент только правкой кода (в MainWindow::MainWindow()), но загрузка живностей будет реализована в скором времени.
Evo написана на С++/Qt. Работоспособность проверена только под Linux, хотя программа должна работать на любой платформе, которая поддерживается библиотекой Qt.
Для получения бинарника достаточно выполнить:

    git clone git@github.com:icoz/evo.git     cd evo     qmake     make 

Для пользователей Windows я собрал бинарник, только скорее всего он уже устарел. Поэтому рекомендую поставить QtSDK и собрать проект из исходников.

Итак, при старте появляется окно с несколькими кнопками.Стартуем и наблюдаем как поле заполнилось цветами.

Поясню, что какой цвет имеет:

• пустота — белая;
• камень — красный;
• трава, конечно же, зелёная;
• а синим я выделил живность.

При старте генетический код живности генерируется с помощью ДСЧ. Так что никакого волшебства нет. Правда, позже волшебство появляется! Что-то произвольно сгенерированное начинает ползать, жрать друг друга, да и подножный корм тоже.
Есть несколько простых правил:

• Каждые 150 (по умолчанию) раундов на поле подкидывается от 100 до 1100 клеток травы для компенсации поедания и вытаптывания, причем для каждой травинки подыскивается исключительно незанятая клетка.
• Каждые 500 (по умолчанию) раундов добавляется по 150 произвольно сгенерированных живностей, которые тоже начинают пытаться выживать.
• При превышении численности населения свыше 1500 особей проводится чистка: убиваются все живности, у которых fitness == 0.

Логическое разбиение следующее.
Поле (класс Map) реализует функции хранения и перемещения объектов, а также фукнцию разбрасывания заданного количества пищи.
Мир (класс World) описывает взаимодействие живностей с окружающим миром.
Живности (экземпляры класса Animal) являются автоматами, программой которого является «генетический» код (и напомню, что каждая особь имеет память и возможность складывать и вычитать в уме). В процессе исполнения этого кода организм принимаетте или иные решения. Мир обрабатывает эти запросы (всё это реализовано посредством системы сигналов/слотов).

В случае приемлимого поведения живность премируется повышением параметра fitness. За поглощение травы fitness увеличивается на 1, за поедание другой живности — +10, за размножение — +50. Чем выше значение fitness, тем более успешен организм. Фактически, этот параметр описывает живучесть организма. Кстати, жду Ваших предложений по введению новых правил, чтобы усложнить этим милым существам жизнь и заставить их придумывать что-то новое.

Реализовано всё это безобразие так:

• поле: в файлах map.h и map.cpp;
• мир: world.h, world.cpp;
• живность: animal.h, animal.cpp, common.h;
• основное окно для визуализации происходящего: mainwindow.h, mainwindow.cpp

Хочется отметить, что была проведена работа по оптимизации работы программы, чтобы она не поглощала тонны ресурсов. Но ввиду специфики её работы — проц она загружает сильно. Самое медленное — это отрисовка кадра, поэтому по умолчанию отрисовка производится только каждый 100-й раунд.
При сохранении живности сохраняется не только бинарный код, но и создается текстовый файл с расширением *.code, в котором приведена расшифровка этого кода.

Что ещё хочется сделать

Список пожеланий таков:

• Не хвататет ещё реализации генетических алгоритмов, чтобы можно было бы отбирать наиболее живучих особей и скрещивать их. Наиболее сложным в этом мне кажется реализация именно скрещивания, ведь фактически нам надо скрестить 2 набора байт-кода. (Если есть идеи алгоритмов — прошу в комменты).
• Возможно, имеет смысл пересмотреть набор доступных команд.
• Хотелось бы реализовать животным «зрение», т.е. возможность определять тип соседних ячеек
• Можно доработать генератор, чтобы не совсем наобум шло генерирование живностей, а с учетом весов команд.
• Рассмотреть варианты, как можно распараллелить вычисления для повышения быстродействия.
• Написать редактор для «генетического» кода, чтобы удобно было самому разрабатывать живность.

Что будет сделано в ближайшее время

Список предстоящих изменений таков:

• При размножении в «генетический» код будут вноситься мутации.
• При нажатии «Save Current Picture» будет выдаваться запрос имени файла для сохранения текущей карты.
• Можно будет подгружать сохраненных живтоных.
• Возможность подгрузки из папки сразу нескольких живностей при старте (рабочее название — Autorun-папка).

Напоследок

Пока начинал писать эту заметку у меня в фоне крутилась эта программка (на пеньке четвертом и не было проведено оптимизаций по скорости работы). На тот момент я достиг для живности значения fitness = 3441. Для этого у меня пожило и умерло более 210000 особей, и прошло более 6500 раундов.
Для получения действительно интересных живностей, которые чего-нибудь интересное умели, надо (по моим оценкам) не менее 10^6 раундов. Может у кого комп помощнее, покрутит? Но интереснее, конечно, станет когда будут реализованы генетические алгоритмы и более интеллектуальный генератор первоначальных наборов. Ну и при дополнении генерируемых живностей особями, написанными живыми людьми. Это даст неплохой старт для следующих поколений.
Погоняв же программу на core i5 я довольно быстро получил гуляющие стада. Живучесть уже достигала 10390 единиц!
Интересно наблюдать за этими милыми тварюшками. Даже сопереживать начинаешь им.
Напоследок вот несколько интересных «жизненных» картинок. Видны пути миграции популяций, образование стад.

Самый серьёзный результат — 36480 (это после 10 часов работы и 2*10^6 раундов):

Качайте, запускайте, наблюдайте!
Кому интересно, можете сами попробовать написать ботов и посмотреть, кто сильней!

На этом всё. Спасибо за внимание!

Баг-репорты и предложения новых фич приветствуются.

UPD: мутация уже реализована на базовом уровне.