Pull to refresh

История сумасшествия или свой морской бой на BrainFuck`e

Abnormal programming *

Доброго времени суток, хабралюди. Перед Вами самадиогностика безнадёжного BrainFuck больного.
Те, кто всё понял из названия и не хотят читать весь пост целиком могут скачать игру и BFDev и сразу перейти под кат в конец поста к разделу «Как играть». В посте рассказано как я заболел BrainFuck`ом, а также описан процесс создания игры «Морской бой» на этом замечательном языке.


История болезни


Заражение

Язык BrainFuck был создан исключительно ради того, чтобы сломать (если переводить культурно, а не дословно) себе мозг. Если коротко, то в языке всего 8 операторов, позволяющих работать с лентой памяти из 8-ми битных ячеек. Подробнее написано на википедии (eng). Когда я впервые прочёл эту статью, я подумал, что язык действительно эзотерический и кодить на этом невозможно вообще. Разве что на чём-нибудь нормальном написать программу, которая будет писать программы, которые будут писать программы… Однако это было ложное впечатление. Так как делать было нечего, я решил разобраться. Как можно узнать на той же википедии, существует множество производных языков: и параллельный BrainFork и процедурный pBF. Перечитав очередной раз статью на википедии, я обнаружил линк на среду разработки на языке BrainFuck — BFDev. К счастью BFDev поддерживает процедурный BrainFuck, что значительно сокращает код, не изменяя при этом атмосферы извращённого языка. По сути, это лишь способ уйти от копипаста. Реализовано всё через 3 новых оператора: ( и ) для описания процедуры, и: для вызова. Именем процедуры является число, лежащее в ячейке на момент вызова оператора (. На то, чтобы выучить все операторы ушло секунд 30. BFDev оказался очень удобен, что подлило масла в огонь.

Первые симптомы

Я сразу же приступил к программированию: быстро написал программу-сумматор, складывающую введённые числа, а точнее цифры. Далее я научился умножать и… И всё. Больше я ничего изобрести не смог. Придумать алгоритм деления мне оказалось не под силу. Практически появившееся ощущение того, что я смогу написать на «этом» всё что угодно моментально исчезло, и я вернулся на землю. То моё мнение о языке я считаю верным до сих пор: кодить на этом можно, но очень быстро начинается BrainFuck в своём истинном значении. После этого BFDev был надолго заброшен до тех пор, пока снова не захотелось размять мозги.

Вторая волна

Вновь меня накрыло после постов на хабре о сапёре и судоку на батниках. Я решил, что тоже знаю толк в извращениях, и начал писать крестики-нолики на BrainFack`е. Для этого был придуман алгоритм работы с массивами. Все алгоритмы, о которых будет идти речь, описаны в конце поста. Нарисовать псевдографикой поле по данным из массива оказалось довольно просто. Записать элемент в массив по двум координатам тоже не было проблемой. В то, что я написал, уже можно было играть двум игрокам, но компьютер не принимал никакого участия. Программа лишь покорно рисовала на экране крестики и нолики, ни о чем при этом не думая. Всё это конечно здорово, но не интересно. Дальше я попробовал судоку. Была усовершенствована система работы с таблицами, реализованная в крестиках-ноликах, но из-за полной неграмотности в вопросе составления и решения судоку проект развития тоже не получил, остановившись на том же этапе, что и крестики-нолики.

Начало конца

И вот, наконец, я перешёл к программе, которой посвящён этот пост – Морской бой. Сразу оговорюсь, что я понимаю по этим названием. Это не классический морской бой, а его модификация с полем 5x5 и 4-мя однопалубными кораблями, на расположение которых не накладывается никаких ограничений. И так, к этому моменту я уже умел взаимодействовать с пользователем и работать с таблицами. Собственно дело осталось за малым: реализовать всевозможные игровые ситуации и научить играть компьютер. Проблемы появились сразу. На bf нет даже простейшего if, поэтому пришлось изобретать. Когда эта проблема была решена, я перешел к проблеме с интеллектом.

Заражение компьютера

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

Что же плохого в этом алгоритме?

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

Вскрытие показало (Описания алгоритмов)


Простейшие алгоритмы

[-] – обнуление текущей ячейки.
[>] – идём вправо пока не найдём 0. Удобно хранить массив в стиле строк си.
[>+<-] – перенос элемента на ячейку вправо
[++++++++++>,––––––––––] – запрос строки у пользователя. Единственный алгоритм, который был подсмотрен в примерах к BFDev.

Для неизлечимых

Сравнение значения ячейки с заданным числом
Сравнивать в Brainfuck`е можно только с нулём, поэтому сначала вычтем из того, что сравниваем, то, с чем сравниваем. Таким образом, можно через оператор [] выполнить действие, предусмотренное на случай else и обнулить заранее выставленный флаг. Соответственно в [] по флагу пишем действие на случай равенства. Тонкостью является то, что код в квадратных скобках должен завершаться на той же ячейке, на которой и начался. Потом не забываем восстановить значение. Допустим нужно сравнить с 1, и мы стоим на ячейке с элементом, с которым сравниваем.
[>+>+<<-]>>[<<+>>-] резервное копирование
+ установка флага
>[код на случай несовпадения >-<[-]]
>[код на случай совпадения[-]]

Плюс по модулю 25
Идея заключается в обычном плюсе, только с проверкой не получилось ли 25, если да, то обнуляем. Сохранение старого значения не интересует, поэтому резервного копирования нет.
([-]>+------------------------->[-]-<[>+<[<->+]]
>[<<------------------------->>[-]]<<+++++++++++++++++++++++++[>+<-])

Работа с двумерным массивом
Допустим у нас есть двумерный массив размерами 6x22. Именно такой массив используется в программе. Такие размеры массива связаны с тем, что оба отображаемых поля, а также символы изображения таблицы хранятся в одном массиве.
Для начала нам нужно из двух координат получить номер в массиве. Для этого к номеру столбца прибавляем номер строки, умноженный на 22. Далее самое интересное. Нам надо как-то добраться до этого элемента. Допустим мы стоим в ячейке с подсчитанным номером, у нас есть символ, который мы хотим записать, или в который хотим записать значение слева, и ещё одна пустая ячейка. Всё это дело расположено прямо перед первым элементом массива. Копируем первый элемент в пустую ячейку. Сдвигаем две ячейки с номером и значением на единицу вправо и декрементируем номер. Повторяем до тех пор пока номер не станет нолём. По сути сдвигаем первые n-1 элементов массива на две клетки влево, чтобы добраться до n-го. Далее производим копирование и сдвигаем первые элементы на место. Для остановки нам нужен ноль перед массивом.

Деление с остатком
Алгоритм деления не любого числа на любое, а некоторого, не превосходящего заранее заданной константы, на константу. В нашем случае делимое ограничено 25, а делитель равен 5. Всё просто – декрементируем число, пока оно не обнулиться, при этом каждые 5 итераций инкрементируем результат. Остаток увеличивается на каждой итерации и обнуляется на каждой пятой.
[->+<[->+<[->+<[->+<[->>+<[-]<
[->+<[->+<[->+<[->+<[->>+<[-]<
[->+<[->+<[->+<[->+<[->>+<[-]<
[->+<[->+<[->+<[->+<[->>+<[-]<
[->+<[->+<[->+<[->+<[->>+<[-]<
]]]]]]]]]]]]]]]]]]]]]]]]]

Линейный конгруэнтный метод генерирования псевдо-случайной величины
Необходимо сгенерировать число от 0 до 25. Алгоритм основан на следующем рекурентном соотношении:


По формуле необходимо умножить на a и прибавить с, при этом всё по модулю 25. Посчитав по нехитрой формуле, получаем a=6. с может быть любым, и вообще говоря, лучше бы его считать от Сида, вот только в этой программе с=2. Воспользовавшись алгоритмом плюса по модулю 25, получаем код:
[>[-]::::::<-]>[-]::, где: вызов процедуры плюса по модулю 25. Вот такой оказывается несложный генератор случайных чисел.

Как играть


Для запуска программы необходима среда BFDev. Через неё открываете файл игры. Далее необходимо выбрать процедурный BrainFuck на панели инструментов (самая правая кнопка, около кнопки с цифрой 16). Всё готово, нажмите F9 для запуска и наслаждайтесь игрой. Игра запустится в окне Output, что снизу. Сначала нужно расставить 4 своих корабля. Внимательно читайте, что пишет игра. Координаты вводятся в виде двух цифр в порядке строка-столбец (без пробелов и разделителей). Не вводите координаты больше 5, а также больше 2 цифр. Не ставьте корабли в одну ячейку! Проверок никаких нет, поэтому программа просто начнёт делать что попало. В случае неправильного ввода возможно зацикливание. Для экстренного завершения нажмите Ctrl+F2. После расстановки кораблей игра запросит у Вас сида. Сидом может быть любая цифра от 0 до 9. Это необходимо, чтобы при одной и той же расстановке кораблей игрока было возможное разное поведение компьютера. Первым ходите Вы. В случае попадания ход остаётся за тем, кто ходил. Игра завершится, как только, кто-либо разобьёт все корабли противника. Здесь есть один глюк. Игра может завершиться только промахом. Если выигрываете Вы, то игра сразу не закончится. Для завершения необходимо выстрелить в любую ячейку или нажать Ctrl+F2.
Вот и всё! Приятной игры!
P.S. Ссылка приведена на dropbox, так как оригинальный сайт Bfdev не отличается устойчивым хостингом.
Tags:
Hubs:
Total votes 196: ↑179 and ↓17 +162
Views 12K
Comments Comments 66