СОКОБАН
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):

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

Более подробное рассмотрение внутренней модели игры, надеюсь, я изложу в заметке "Алгоритмы".