КИРИЛЛ ТКАЧЕНКО, инженер 1-й кат. ФГАОУ ВО «Севастопольский государственный университет», tkachenkokirillstanislavovich@gmail.com

Игровой генератор псевдослучайных чисел
на основе линейного конгруэнтного метода в 1С

Современные компьютерные игры для построения внутри игровых пространств требуют воспроизводимой генерации псевдослучайных чисел. Одним из наиболее простых способов достичь этой воспроизводимости является применение линейного конгруэнтного метода [1]

Этот метод достаточно прост в вычислительном плане, нетребователен к используемым арифметическим компьютерным возможностям. Задание для констант его рекуррентного соотношения других наборов параметров может привести к другим последовательностям.

Для многих пользователей персональных компьютеров и некоторых других устройств хорошо известны головоломки-пасьянсы типа FreeCell, в которых для заданного номера игры воспроизводится конкретное игровое поле или начальный расклад [2]. Это обеспечивается за счет линейного конгруэнтного метода с определенными константами, характерными для ряда известных трансляторов высокоуровневых языков C/C++.

Отсюда можно перейти к задаче получения воспроизводимого расклада пасьянса для заданного номера игры. Данная задача является хорошим образцом для построения предсказуемого и одинакового игрового поля. Помимо прочего, на языке 1С программное решение по генерации поля является предельно компактным и использует минимум языковых средств.

Поэтому целью работы является разработка на языке 1С подпрограмм для обеспечения генерации начального расклада головоломки типа FreeCell.

В основе построения начального расклада лежит использование генератора псевдослучайных последовательностей на основе линейного конгруэнтного метода. По этому методу вначале происходит начальная инициализация генератора:

семя←НачальноеЗначение (1)

В формуле (1) семя – это состояние генератора, НачальноеЗначение – его начальное значение. На каждой итерации использования генератора, при каждом его вызове происходит, во-первых, установка нового значения состояния генератора:

семя←(214013*семя+2531011) ОстатокОтЦелочисленногоДеления 2147483648 (2)

А во-вторых, непосредственно возврат результата вызова:

результатВызова←семя ЦелочисленноеДеление 65536 (3)

На основе формул (1)-(3) и реализуется генератор для головоломки.

Программа начинается с объявления используемой в подпрограммах переменной:

Перем семя;

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

Затем описывается функция для изменения состояния генератора и получения с него нового значения:

Функция ЛКГ()
	семя = (214013 * семя + 2531011) % 2147483648;
	Возврат Цел(семя / 65536);
КонецФункции

Расчет в функции ЛКГ() ведется по формулам (2)-(3). Соответствующая функции схема алгоритма находится на рис. 1.

Рисунок 1. Схема алгоритма генерации псевдослучайного числа

Основное тело программы сосредотачивается в процедуре Игра(номерИгры):

Процедура Игра(номерИгры)
	Перем буквыКарт;
	Перем буквыМасти;
	Перем карты;
	Перем картыРез;
	Перем карта, масть;
	Перем i;
	Перем инд;
	Перем Рез;

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

Одномерные массивы карты и картыРез с индексами от 0 до 51 служат для хранения карт расклада в неупорядоченном виде и в виде, пригодном для использования как начальной игровой позиции.

В свою очередь, карта и масть используются на итерациях при формировании неупорядоченной последовательности карт. Индексная переменная i задействована в циклах с параметром.

Для выборки по генератору номер карты в неупорядоченной последовательности сохраняется в инд. Наконец, строковый результат для вывода накапливается в Рез.

Простым присваиванием инициализируются буквыКарт и буквыМасти:

	буквыКарт = "A23456789TJQK";
	буквыМасти = "♣♦♥♠";

Затем создаются одномерные массивы карты и картыРез:

	карты = Новый Массив(52);
	картыРез = Новый Массив(52);

В цикле с параметром от 0 по 51 происходит инициализация начальной последовательности карты:

	Для i = 0 По 51 Цикл
		карта = Сред(буквыКарт, Цел(i / 4) + 1, 1);
		масть = Сред(буквыМасти, (i % 4) + 1, 1);
		карты[i] = карта + масть;
	КонецЦикла;

Вначале из буквыКарт и буквыМасти выделяются соответствующие буквы карты и масти, которые присваиваются в карта и масть. Затем результат конкатенации карта и масть помещается в место i-й карты карты[i].

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

	семя = номерИгры;

В цикле с параметром по всем картам происходит следующее:

	Для i = 0 По 51 Цикл
		инд = ЛКГ() % (52 - i);
		картыРез[i] = карты[инд];
		карты[инд] = карты[51 - i];
	КонецЦикла;

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

Подготовка к выводу полученного расклада пользователю осуществляется также в цикле со счетчиком:

	Рез = "";
	Для i = 0 По 51 Цикл
		Рез = Рез + " " + картыРез[i];
		Если (i + 1) % 8 = 0 Тогда
			Рез = Рез + ""
				"";
		КонецЕсли;
	КонецЦикла;

Собственно, помимо конкатенации с накопленной в Рез строкой, на каждой итерации выполняется проверка условия завершения строки. Если строка должна завершиться, то добавляется в ее конец терминатор.

После этого строка сообщается пользователю, и процедура завершается:

	Сообщить(Рез);
КонецПроцедуры

Соответствующая процедуре схема алгоритма находится на рис. 2.

Рисунок 2. Схема алгоритма нахождения начального расклада головоломки

Головная программа содержит тестовый вызов с номерами игр 1 и 617 [2]:

Игра(1);
Игра(617);

Результаты работы программы:

 J♦ 2♦ 9♥ J♣ 5♦ 7♥ 7♣ 5♥
 K♦ K♣ 9♠ 5♠ A♦ Q♣ K♥ 3♥
 2♠ K♠ 9♦ Q♦ J♠ A♠ A♥ 3♣
 4♣ 5♣ T♠ Q♥ 4♥ A♣ 4♦ 7♠
 3♠ T♦ 4♠ T♥ 8♥ 2♣ J♥ 7♦
 6♦ 8♠ 8♦ Q♠ 6♣ 3♦ 8♣ T♣
 6♠ 9♣ 2♥ 6♥
 7♦ A♦ 5♣ 3♠ 5♠ 8♣ 2♦ A♥
 T♦ 7♠ Q♦ A♣ 6♦ 8♥ A♠ K♥
 T♥ Q♣ 3♥ 9♦ 6♠ 8♦ 3♦ T♣
 K♦ 5♥ 9♠ 3♣ 8♠ 7♥ 4♦ J♠
 4♣ Q♠ 9♣ 9♥ 7♣ 6♥ 2♣ 2♠
 4♠ T♠ 2♥ 5♦ J♣ 6♣ J♥ Q♥
 J♦ K♠ K♣ 4♥

Полный исходный текст программы доступен на сайте журнала http://samag.ru.

Полученный результат позволяет производить имитацию игровых подсистем в 1С. Кроме того, с другими параметрами разработанный генератор может применяться для задач упорядочивания после нумерования им последовательностей.

1. Линейный конгруэнтный метод [Электронные текстовые данные] / Режим доступа: URL: https://ru.wikipedia.org/wiki/Линейный_конгруэнтный_метод 10.04.2018 19:00.
2. Deal cards for FreeCell [Электронные текстовые данные] / Режим доступа: URL: http://rosettacode.org/wiki/Deal_cards_for_FreeCell 10.04.2018 19:00.

Ключевые слова: 1С, генератор псевдослучайных чисел, линейный конгруэнтный метод.

Комментарии могут оставлять только зарегистрированные пользователи