| 29.07.2009 |
Краткий обзор 1 Краткий обзор 2 Краткий обзор 3 Краткий обзор 4 Краткий обзор 5 Краткий обзор 6 Солверы и генераторы 1 Солверы и генераторы 2 Алгоритмы КОНКУРС |
SVBGEN Author: С.Беляев Эта программа, в общем то, давно лежит на этом сайте, но к ней не было никаких комментариев. Отчасти это связано с тем, что мне она казалась неким промежуточным этапом работы над солвером, во-первых. И, во-вторых, меня сдерживало нежелание делиться "секретами ремесла", которые позволили мне "создать" набор уровней, не очень плохих по мнению многих. Работа над солвером прервалась на неопределенный срок, а "собственнический" инстинкт легко преодолевается. Правда, еще остается серьезный сдерживающий фактор - нехватка времени. SVBGEN - генератор уровней. Коротко о работе с этой программой. Шаг 1. Создаем текстовый файл с конечной позицией, например, файл A1.XSB: ###### # # #****# # # # # ###### Шаг 2. Запускаем программу: SVBGEN.EXE A1.XSB После отработки программа создает файлы A1.LOG, S_A1.XSB и S_A1.XHT. Файл S_A1.XSB представляет собой созданный уровень: S_A1 ###### #@ # #***.# # $# # # ###### Файл S_A1.XHT - соответствующее решение этого уровня: rDurrdLddlluRdrrUdlU Файл A1.LOG содержит информацию о ходе работы программы: 0: 1(0) 1: 4(1) 2: 10(6) 3: 14(8) ... Например, строка 3: 14(8) обозначает, что имеется 14 позиций, из которых за 3 перемещения ящика достигается конечная позиция. Среди этих позиций имеется такая, что потребуется минимум 8 ходов для достижения цели и это число ходов максимальное среди 14 позиций. В программе проводится полный перебор позиций, поэтому она неплохо работает на "тесных" позициях и перестает работать при превышении допустимого размера внутренней модели - в этом случает она перестает добавлять в модель новые уровни, индикатором служит появление точки "." при выводе информации на экран. Если информацию из файла *.LOG представить в виде графика, то можно наблюдать интересные эффекты, пример (svb367.xsb):  Подобные колебания косвенно характеризуют целевую позицию. Небольшое изменение целевой позиции может приводить к довольно значительным изменениям, допустим, приводить к резкому увеличению длины решения. Не скрою, эксперименты с различными позициями достаточно увлекательны сами по себе. Более подробное рассмотрение внутренней модели игры, надеюсь, я изложу в заметке "Алгоритмы". |