Есть прекрасная игра/алгоритм «Conway's Game of Life» [wiki] — это набор правил для клеточного автомата который определяет жизнь колонии. Алгоритм был придуман английским математиком в далеком 1970 году.
Игровое поле — квадратная сетка неограниченного размера.
Каждая клетка может иметь два значения Живая или Мертвая
Игрок задает начальное положение клеток на поле и потом наблюдает как они эволюционируют.
- Живая клетка у которой меньше двух соседей умерает от одиночества.
- Живая клетка у которой 2 или 3 соседа живет до следующего хода.
- Живая клетка у которой больше 3 соседей умирает от перенаселения.
- Мертвая клетка у которой ровно 3 живых соседа становаится живой (рождается).
Соседними считаются клетки по вертикали, горизонтали и диагонали. Т.е. у одной клетки может быть восемь соседей.
Эти простые правила позволяют реализовать машину Тьюринга и даже простые колонии (наборы живых клеток) могут обладать очень интересными свойствами.
Я решил реализовать алгоритм на джаваскрипте с ипользованием TTD и рассказать об этом.
Вдохновила меня на пост книжка из этого топика: habrahabr.ru/post/150238/
Задача
Я хотел научиться пользоваться каким-нибудь тестировочным фреймворком для JS.
Обкатать IDE (тестирование, дебаг и гитхаб прямо из интерфейса IDE)
Написать что-нибудь красивое и интересное.
Глобально задача стояла так: Мне не хочется фиксить баги в спагетти коде написанном для вордпресса, а хочется писать что-то для современного интересного проекта. Я решил найти удаленную работу JS программистом. Мне интереснее Node.js, но и JS проект в портфолио не помешает.
Инструменты
В качестве IDE использовал PHPStorm.
Для тестов Buster.
Про этот фрейморк на хабре ничего не нашлось. Да и в гугле его было найти нелегко, проект относительно новый.
Мне он очень понравилсся.
- Гибкий, легкий в настройке и подключении.
- Может тестировать как Node.js так и код в браузере.
- Поддерживает все разумные браузеры для тестов
- Может запускать тесты как локально в хтмл файлике (мини тест) так и удаленно на тестовом сервере где установлен весь зоопарк браузеров.
Ниже опишу то как им пользовался я, хотя можно пользоваться по разному.
Ставится с помощью npm install -g buster
Нужно создать в директории с проектом простейший файл конфиг (указывает какие модули загружать перед тестом)
var config = module.exports;
config["My tests"] = {
rootPath: "../",
environment: "browser", // or "node"
sources: [
"lib/jquery-1.8.0.min.js",
"lib/life.js"
],
tests: [
"test/life-test.js"
]
}
и дальше запускается из консоли командой buster static.
Эта команда поднимает локальный сервер который исполняет тесты и висит на 1111-ом порту.
Перезапуск тестов делается клавишей F5. В браузере это выглядит так.
Сами тесты выглядят стандартно
buster.testCase("A module", {
"states the obvious": function () {
assert(true);
}
});Тесты
Итак, переходим к коду и тестам.
Я обещал себе четко следовать TTD и прям, вот не писать ни строчки кода без тестов.
Было очень непривычно. Постоянно хотелось накидать функционал. Но для того чтобы писать код приходилось заставлять себя писать для этого тесты. Такое вот TTD наоборот.
В итоге в тестах получилось 320 строк кода, а в, собственно, библиотеке 180. Это было для меня некоторой неожиданностью.
Хочу пройтись по некоторым тестам которые мне написать хоть и удалось, но осталось легкое чувство недоделанности и криворукости.
Я, кстати, искал литературу о том как правильно организовывать тестирование, потому как ясно что это дело требует методики. Но так ни на чем путном и не остановился. Если есть что посоветовать, пишите в коментариях.
Пример №1: Пустой тест
buster.testCase("A module life", {
"exists":function () {
assert(Life);
},
"has matrix":function () {
assert(Life.matrix);
},
"has speed":function () {
assert(Life.speed);
}
});
Этот тест просто проверяет наличие переменных. Зачем он нужен?
Т.е. я бы начал писать программу с того что накидал каркас из основных функций, модулей и констант с которыми буду работать дальше. Но TTD мне не позволяет просто взять и написать какой-нибудь класс. А начать писать с чего-то надо. Я сделал вот такой тест который просто проверяет наличие функций.
Осталось сильное чувство что TTD придумали не для таких тестов.
Пример №2: Неполный тест.
buster.testCase("A function count neighbors", {
setUp:function () {
Life.matrix = [
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1]
];
},
"exist":function () {
assert(Life.countNeighbors);
},
"counts all 8 neighbors":function () {
assert.equals(Life.countNeighbors(1, 1), 8)
},
"counts all 8 neighbors in corner":function () {
assert.equals(Life.countNeighbors(0, 0), 8)
},
"counts all 8 neighbors near wall":function () {
assert.equals(Life.countNeighbors(0, 1), 8)
},
"do not counts zeroes":function () {
Life.matrix = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
];
assert.equals(Life.countNeighbors(2, 2), 0)
}
});
Функция Life.countNeighbors(row,column) берет в себя координаты точки на матрице. И возвращает количество её живых соседей. Матрица инициализируется в начале теста в переменную Life.matrix.
Проблема с этим тестом в том что я не могу в качестве теста подставить все возможные варианты исходных матриц. Я могу дать пару граничных вариантов, вроде матрицы состоящей только из живых клеток или только из мертвых. Писать отдельные тесты на правильность подсчета каждого из 8 потенциальных соседей я считаю глупым. А другого способа красиво решить эту проблему я не знаю. Т.е. знаю. Но этот способ нарушает одно из правил TTD — независимость тестов.
Пример №3: Зависимый тест
buster.testCase("A function matrixTick", {
setUp:function () {
this.matrix1a = [
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0]
];
this.matrix1b = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
];
this.matrix2a = [
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0],
[0, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0]
];
this.matrix2b = [
[0, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0]
];
},
"alternates test matrixes 1a => 1b and 2a => 2b":function () {
Life.matrix = this.matrix1a;
Life.matrixTick();
assert.equals(Life.matrix, this.matrix1b);
Life.matrix = this.matrix2a;
Life.matrixTick();
assert.equals(Life.matrix, this.matrix2b);
},
"alternates test matrixes to themselves after 2-nd itereation":function () {
Life.matrix = this.matrix1a;
Life.matrixTick();
Life.matrixTick();
assert.equals(Life.matrix, this.matrix1a);
Life.matrix = this.matrix2a;
Life.matrixTick();
Life.matrixTick();
assert.equals(Life.matrix, this.matrix2a);
}
});
Что тут происходит. Дело в том что есть матрицы «осцилляторы» т.е. такие наборы клеток которые согласно правилам игры будут циклично сменять друг друга. Вот они на гифках.
Я выбрал два таких осциллятора чтобы скормить их фунции Life.matrixTick(); Эта функция должна рассчитать вид матрицы Life.matrix к следующему ходу. Если осциллятор действительно меняется и возвращается в исходное стостояние значит фунция скорее всего работает нормально.
Проблема в том что функция Life.matrixTick() использует внутри себя Life.countNeighbors. И если Life.countNeighbors работает неверно, то тут полезут ошибки которые явно сюда не относятся. Зато это хороший способ протестировать сразу обе функции.
Как быть в этом случае?
Пример №4: Тест UI изнутри.
Как протестировать что видит пользователь?
Есть функция которая создает таблицу и размещает её на странице. Есть функция которая раскрашивает ячейки этой таблицы. Я могу проверить в DOM'e наличие таблицы и наличие нужных классов у ячеек. Но что если где-то затесался style=«display:none»? Функция работает, а пользователь ничего не видит.
Или у двух классов похожие цвета, так что разницу глазом на экране не видно.
Еще один пример за который хочется краснеть:
if cell.getAttribute("onClick") === "Life.changeCell(this.id);"Мне надо убедиться что при нажатии на ячейку вызывается функция и я тупо проверяю что эта функция там указана. Тут надо было бы использовать какой-нибудь фреймворк который умеет кликать куда скажут. Но мне было лень его искать и я просто проскочил этот момент. Подскажите что можно было тут сделать. Я не знаю как автоматизировать такие тесты.
Пример №5: Тест = код.
Есть функция Life.addPattern(pattern) которая добавляет паттерн (маленькую матрицу например размером 2х2) на большое поле (30х15). И должна разместить паттерн в центре поля.
Общий тест проверки что паттерн размещен в центре поля и будет тем самым кодом для размещения. А писать тест частного варианта с захардкожеными исходными данными черевато Примером №2.
Мне было очень неприятно от того что я связался с TTD. Пока где-то ближе к концу мне не захотелось вернуться назад и переписать одну из функций. Я решил что будет прикольней «завернуть» игровое поле чтобы оно было «бесконечным». Самая правая клетка граничит с самой левой. Все четыре угла являются соседями и т.п.
Тут тесты очень помогли. Не надо вспоминать где в коде были расставлены console.log и что я там выводил. Не надо ничего вспоминать о подводных камнях. Просто пиши-код-блядь и всё будет работать. А если где-то что-то поломаешь, то тесты сами подскажут где именно.
Очень приятное чувство.
Код
Весь код есть на гитхабе.
В коде я скатился к использованию God object'a. У меня все функции и методы работают с одним объектом Life. Они в него пишут, из него читают и в нем находятся.
Скатился я к этому т.к. меня утомило таскать за собой аргументы для вложенных функций. А как сделать лучше я не знаю.
Life.clearMatrix = function () {
Life.pause();
Life.matrix = Life.matrix.map(function (row) {
return row.map(function () {
return 0;
});
});
Life.updateGrid();
};Например есть функция очищения матрицы Life.clearMatrix(); она:
- Вызвает функцию остановки анимации Life.pause();
- Обнуляет ячейки матрицы.
- Вызвает функцию перерисовки таблицы Life.updateGrid();
Чтобы остановить анимацию таблицы, для функции Life.pause(); нужно передать указатель на активный setTimeout, но я не передаю указатель. Функция Life.pause(); сама берет этот указатель из объекта Life по адресу Life.timeout.
Не то чтобы мне этот God object сильно мешал, но хочется сделать красивее.
Игра
Симулятор работает тут.
Попробуйте нарисовать вот такую «рыбку» и запустить анимацию. 
Она не будет двигаться т.к это устойчивая(статичная) колония. Пока анимация включена попробуйте кликать на клетки 1 и 2.
Есть cкучная колония квадрат:
Она обладает интересным свойством устойчивости к «эпидемиям». Сколько вы ни кликайте на ее живые клетки, они будут самовосстанавливаться.
Можно одним кликом поблизости сделать из неё рыбку. Или другим уничтожить. А третим превратить в 2 другие устойчивые фигуры. Поиграйтесь.
Если кликнуть в самый центр «таракана»:
то он умрет красиво и симметрично или оставит 4 куколки, в зависимости от фазы в которй он находился. А если выстрелить ему в ногу (коленку), будет долго мучаться.
На wiki есть ещё много интересных примеров:
Двигающиеся колонии.
Колонии создающие другие двигающиеся колонии
и т.п.
Каждый раз когда я начинаю играться с этим алгоритмом. Меня захватывает фантазия. Это же Tьринг машина! Можно же запрограммировать что угодно!
Хочется стать каким-нибудь ученым и посвятить всю жизнь исследованию свойств различных колоний. Придумывать самому какими свойствами они должны обладать, а потом делать алгоритмы для поиска таких колоний. Только потом опять что-то отвлекает и программа отправляется на полку.
По крайней мере если я окажусь на необитаемом острове с ноутбуком, но без интернета я знаю чем заняться.
Встретил я эту игру лет 15 назад и с тех пор долго хранил программу симуляции под виндоус среди своих бэкапов.
Пусть тепрь на гитхабе полежит.
Ссылки:
Симулятор в интернете: ian.ru/life
Симулятор на гитхабе: github.com/yangit/Life
Вики по игре: Game of Life
Тестовый фреймворк BusterJS busterjs.org
Автор: ian_238
