Пишем задачки на FBD. Пятнашки и Симпсон01.07.2016 15:03

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

Для начала напомню правила игры: игра в »15», «Пятнашки», «Такен» — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов, соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке, добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.

Как мы видим, правила предельно простые. И реализация будет простой и займет минут 15 без графической части и полчаса со всеми картинками. При этом хочу обратить ваше внимание на то, что вопросы оптимизации алгоритмов и логики остаются за рамками этой статьи т.к. эти вопросы уже не такие простые и потребуют куда больше времени.

Вот что получилось в итоге:

Описание программы, комментарии и картинки под катом.

Основа программы

— Наша «клетка пятнашек» должна принимать внешние команды, когда игрок говорит, что хочет передвинуть ее на соседнее пустое место.
 — Клетка должна знать о соседях по вертикали и горизонтали, чтобы понять, есть ли рядом пустая клетка, с которой можно поменяться местами.
 — Клетка должна на старте игры установить начальное значение.
 — На выход Клетка должна передать значение, установленное в ней на данный момент.
 — Если игрок подал команду Клетке переместиться на соседнее пустое поле, то Клетка должна передать команду соседней пустой Клетке о том, что они сейчас будут меняться местами.

Исходя из этих требований получаем набор входных и выходных сигналов.

Входы:

• УпрКоманда — команда управления от игрока, соседних клеток или начальной установки значения
• Сверху — значение соседней сверху клетки
• Снизу — значение соседней снизу клетки
• Слева — значение соседней слева клетки
• справа — значение соседней справа клетки
• УстЗначение — значение, которое должно быть установлено в клетку при старте игры

• Значение — значение клетки
• Поехали — команда соседу, что мы хотим «поменяться с ним местами»

В итоге получается вот такой макрос:

Поставим таких макросов в нашу задачу 16 штук и свяжем их между собой. В итоге получаем:

Все очень просто. Поставили в задачу шестнадцать макросов «Клетка пятнашки» и связали каждую клетку с соседями по вертикали и горизонтали. Если каких-то соседей у клетки нет (например в клетке_1_1 нет соседа сверху и слева), ставим на соответствующем входе »-1».

Набивка основы

Это готовая реализация нашего макроса. Кратко принцип работы:

1. Получаем на вход управляющую команду и распаковываем ее. Выделяем отдельно сигнал длительностью один цикл — признак, что поступила команда, и параметр команды. В нашем случае параметр команды это набор целых чисел от 1 до 6, где числа 1 — 4 это команда поменяться значениями с одним из соседей, число 5 означает команду установить начальное значение в ячейку, а число 6 — что игрок кликнул мышкой по данной клетке и хочет «передвинуть» ее на возможно находящееся по соседству пустое поле.

2. Проверяем всех соседей на нулевое значение (числом 0 у нас обозначается пустое поле).

3. Дальше смотрим на текущее значение данной клетки и команду. Если значение клетки равно нулю (клетка пустая) и одновременно пришла команда поменяться значениями с соседом (команды 1–4), то перезаписываем в клетку значение соседней клетки.

4. Если нам пришла команда 5 (установить начальное значение), то просто записываем в память значение со входа «УстЗначение».

5. Если нам пришла команда 6 (игрок кликнул мышкой по данной клетке) и значение одной из соседних клеток равно нулю, то записываем в данную клетку нулевое значение и отправляем команду «Поехали» на соседние клетки с указанием, с каким именно соседом мы хотим поменяться.

Вот собственно и все. Единственный тонкий момент в нашей реализации, это алгоритмы «Задержка». Но догадаться, зачем они нужны, легко просто представив как проходит выполнение программы:

— мы получили команду от игрока «передвинуть» эту клетку на пустое место.
 — проверили, действительно рядом есть пустое место.
 — записали в клетку »0» и передали соседу, что хотим поменяться с ним значениями.
 — сосед (при этом нужно понимать, что отрабатывает все тот же макрос «Клетка пятнашки», просто другой его экземпляр) видит, что ему пришла команда поменяться местами с другой клеткой.
 — сосед проверяет что в нем самом записан »0» т.е. он сейчас пустая клетка и записывает себе значение первой клетки, от которой пришла команда поменяться местами.

Но секундочку! Ведь одновременно с тем, как отправить команду соседу мы в нашу первую клетку записали »0», следовательно сосед тоже запишет себе ноль и у нас получатся две пустые клетки, а одно значение (из ряда 1–15) пропадет. И так пока все игровое поле не станет пустым. Чтобы этого не произошло, задерживаем в первой клетке перезапись нулем. Таким образом пустая соседняя клетка успеет себе записать правильное значение.

Победа или поражение

Начнем с автоматической проверки победы или проигрыша игрока.

В игре «пятнашки» есть забавный момент заключающийся в том, что из всех возможных начальных раскладов плиток половина раскладов нельзя собрать если плитки с номерами »14» и »15» стоят не в том порядке.

Исходя из этого сформируем два условия:
 — условие 1: значение, записанное в каждую клетку соответствует ее порядковому номеру. Т.е. игрок победил.
 — условие 2: значения, записанные в клетки соответствуют их порядковому номеру за исключением клеток »14» и »15», которые поменяны местами. Т.е. немного не повезло с раскладом.

Ставим 18 алгоритмов сравнения, и собираем по И два набора по шестнадцать равенств. По ИЛИ формируем признак, что мы пришли к одному из концов расклада.

18 алгоритмов потому, что мы проверяем соответствие 16 ячеек для первого случая и дополнительно перестановку ячеек »14» и »15» для второго случая. Кстати т.к. у нас массив данных заранее определенный, то достаточно пятнадцати проверок для всего поля, т.к. последняя ячейка проверяется автоматом.

Начальная расстановка

Сначала делаем генератор случайных целых чисел 0 — 15. Пойдем старым проверенном способом. Это вполне допустимый вариант т.к. получившаяся последовательность случайных чисел зависит от момента времени, когда была нажата кнопка «Новая игра». А т.к. этот момент времени случает и никогда не повторяется, то в итоге мы получаем довольно простой и хороший генератор случайных чисел.

На выходе алгоритма Действительное-в-Целое (ДвЦ) получаем случайное целое значение 0 — 15.

Теперь стоит задача сформировать ряд неповторяющихся значений, и записать каждое значение в свою ячейку.

Как я уже сказал, конкретно для языка FBD более или менее хорошее решение этой задачи сделать сложно. Или может просто я не вижу очевидное для остальных красивое и простое решение. Конечно всегда есть вариант сделать вставку на ST, но цель сделать задачу именно целиком на языке FBD.

Решение задачи «в лоб» заключается в следующем:

— ставим управляющие элемент.
 — при подаче команды забиваем начальный массив »-1» (можно было и любыми числами вне диапазона [0…15]).
 — обнуляем счетчик.
 — далее генерируем случайное число от 0 до 15 и проверяем, есть ли такое в нашем массиве. Если есть — продолжаем генерацию случайных чисел.
 — если такого числа нет — увеличиваем счетчик на единицу и записываем в соответствующую ячейку памяти наше значение.
 — повторяем эти действия еще 15 раз.
 — проверяем, если мы дошли до шестнадцатого шага, то формируем импульс, по которому отправляем команду на запись этих значений во все ячейки.

Главным недостатком данного алгоритма является многократный перебор выкинутых ранее значений. В теории время генерации такой случайной последовательности может быть бесконечным. В реальности при десятках прогонов программы оно не было больше чем полсекунды. В любом случае на время генерации (раз оно не мгновенное) ставим блокировку на действия игрока.

Вот что в итоге получилось:

Приделываем графику

Для этого выбираем в интернете любые понравившиеся картинки с пятнашками. Одновременно выбираем картинки для удачного сбора расклада и неудачного. Я решил поместить туда Гомера Симпсона.

Ставим 16 картинок и приделываем к ним анимацию чтобы они показывали число, соответствующее числу в ячейке. А в ячейке с нулем плитка должна быть невидимой. Ставим на каждую плитку формирование команды »6». Снизу располагаем кнопку «Новая игра» по которой будем запускать алгоритм генерации случайной начальной расстановки. Одновременно не забываем поставить блокировку на все плитки во время генерации. Поверх всего этого дела помещаем Гомера. Все. Графика готова, можно играть.

Нарисованный вариант. Можно заметить что изначально все плитки у нас с единицей.

Начальная позиция.

Неудачный расклад.

И победа!

Что осталось нереализованным

— можно приделать счетчик ходов. Делается это элементарно. В макросе «Клетка пятнашки» есть команда »6» — команда игрока. Достаточно взять от нее логический сигнал длительностью в один цикл. Вывести этот сигнал наружу. Собрать все шестнадцать сигналов по ИЛИ и завести на алгоритм сложения, охваченный обратной связью. Т.е. всего три дополнительный алгоритма и пара минут работы.

— статистика. Можно сделать счетчик выигранных и неудачных игр. Добавляется два алгоритма сложения и пару алгоритмов обвязки. Тоже пара минут работы.

— отбор раскладов. Как уже говорилось, половина раскладов не сходится изначально из-за невозможности поменять местами плитки »14» и »15». Можно при старте проверять «неудачный расклад» и сразу менять эти две плитки местами.

Сделать все это не сложно, поэтому оставлю такую возможность всем желающим.

Выводы

Для проверки накидал примерно то же самое на С. Вот что получилось:

#include 
#include "cstdlib"
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;


int main(void)
{
	int MyPyatn[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
	int i = 0, x = 0, y = 0, MyRand = 0, MyBuffer = 0, MyButton = 0;
	bool MyGameover = false, MyChange = false;

	setlocale(LC_ALL, "ru-RU");
	srand(time(NULL));

	cout << "Нажми 'n' для новой игры или любую другую кнопку для выхода:  ";

	kbhit();
	if(getch() != 110)
		return 0;
	
	std::system("cls");

	cout << "Играем в пятнашки:  ";

	for(i=0;i<16;i++)
	{
		MyRand = rand() %(16-i);
		MyBuffer = MyPyatn[15-i];
		MyPyatn[15-i] = MyPyatn[MyRand];
		MyPyatn[MyRand] = MyBuffer;
	}
	
	for (i=0;i<16;i++)
	{
		
		if ((i %4) == 0)
		{
			cout << "\n";
			cout << "\n";
		}

		if ((MyPyatn[i]<10) || (MyPyatn[i] == 16))   cout << "   ";
		else cout << "  ";

		if (MyPyatn[i] == 16) 
		{
				cout << "_";
				x = i %4 + 1;
				y = int (i/4) + 1;
		}

		else cout << MyPyatn[i];
	
		cout << "   ";

			
	}
	
	cout << "\n";
	cout << "\n";
	cout << "Управление стрелками вверх-вниз-влево-вправо. Выход - '0' \n";
	cout << "Знак _ это пустая клетка";

	do
	{
		MyChange = false;
		MyGameover = true;
		for(i=0;i<16;i++)
		{
			if (MyPyatn[i] != (i+1))  MyGameover = false; 
		}
		
		while(!kbhit ());

		MyButton = getch();
		
		if ((MyButton == 48) || (MyButton == 72) || (MyButton == 75) || (MyButton == 77) || (MyButton == 80))
		{
		
			if (MyButton == 48) return 0;

			if ((MyButton == 72) && (y > 1))
			{
				MyBuffer = MyPyatn[(y-1)*4 + x - 1];
				MyPyatn[(y-1)*4 + x - 1] = MyPyatn[(y-2)*4 + x - 1];
				MyPyatn[(y-2)*4 + x - 1] = MyBuffer;
				y = y - 1;
				MyChange = true;
			}

			if ((MyButton == 80) && (y < 4))
			{
				MyBuffer = MyPyatn[(y-1)*4 + x - 1];
				MyPyatn[(y-1)*4 + x - 1] = MyPyatn[y*4 + x - 1];
				MyPyatn[y*4 + x - 1] = MyBuffer;
				y = y + 1;
				MyChange = true;
			}

			if ((MyButton == 75) && (x > 1))
			{
				MyBuffer = MyPyatn[(y-1)*4 + x - 1];
				MyPyatn[(y-1)*4 + x - 1] = MyPyatn[(y-1)*4 + x - 2];
				MyPyatn[(y-1)*4 + x - 2] = MyBuffer;
				x = x - 1;
				MyChange = true;
			}

			if ((MyButton == 77) && (x < 4))
			{
				MyBuffer = MyPyatn[(y-1)*4 + x - 1];
				MyPyatn[(y-1)*4 + x - 1] = MyPyatn[(y-1)*4 + x];
				MyPyatn[(y-1)*4 + x] = MyBuffer;
				x = x + 1;
				MyChange = true;
			}
		}

		if (MyChange)
		{
			std::system("cls");

			cout << "Играем в пятнашки:  ";

			for (i=0;i<16;i++)
			{
		
				if ((i %4) == 0)
				{
					cout << "\n";
					cout << "\n";
				}

				if ((MyPyatn[i]<10) || (MyPyatn[i] == 16))   cout << "   ";
				else cout << "  ";

				if (MyPyatn[i] == 16)  cout << "_";
				else cout << MyPyatn[i];
	
				cout << "   ";
		
			}
		
			cout << "\n";
			cout << "\n";
			cout << "Управление стрелками вверх-вниз-влево-вправо. Выход - '0' \n";
			cout << "Знак _ это пустая клетка";
		}
				
	} while(!MyGameover);
	
	std::system("cls");

	cout << "ПОБЕДА!!!";
	
	getch();
	
	return 0; 

}

На этом все. Надеюсь было интересно.

Комментарии (0)